Bresenham's Line Algorithm

From RogueBasin
Jump to navigation Jump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

Bresenham's Line Algorithm is a way of drawing a line segment onto a square grid. It is especially useful for roguelikes due to their cellular nature. A detailed explanation of the algorithm can be found here or on Wikipedia

Below are several hand-coded implementations in various languages.

C#

Here is a simple way of using the algorithm in C# with delegates.

// Author: Jason Morley (Source: http://www.morleydev.co.uk/blog/2010/11/18/generic-bresenhams-line-algorithm-in-visual-basic-net/)
using System;

namespace Bresenhams
{
    /// <summary>
    /// The Bresenham algorithm collection
    /// </summary>
    public static class Algorithms
    {
        private static void Swap<T>(ref T lhs, ref T rhs) { T temp; temp = lhs; lhs = rhs; rhs = temp; }

        /// <summary>
        /// The plot function delegate
        /// </summary>
        /// <param name="x">The x co-ord being plotted</param>
        /// <param name="y">The y co-ord being plotted</param>
        /// <returns>True to continue, false to stop the algorithm</returns>
        public delegate bool PlotFunction(int x, int y);

        /// <summary>
        /// Plot the line from (x0, y0) to (x1, y10
        /// </summary>
        /// <param name="x0">The start x</param>
        /// <param name="y0">The start y</param>
        /// <param name="x1">The end x</param>
        /// <param name="y1">The end y</param>
        /// <param name="plot">The plotting function (if this returns false, the algorithm stops early)</param>
        public static void Line(int x0, int y0, int x1, int y1, PlotFunction plot)
        {
            bool steep = Math.Abs(y1 - y0) > Math.Abs(x1 - x0);
            if (steep) { Swap<int>(ref x0, ref y0); Swap<int>(ref x1, ref y1); }
            if (x0 > x1) { Swap<int>(ref x0, ref x1); Swap<int>(ref y0, ref y1); }
            int dX = (x1 - x0), dY = Math.Abs(y1 - y0), err = (dX / 2), ystep = (y0 < y1 ? 1 : -1), y = y0;

            for (int x = x0; x <= x1; ++x)
            {
                if (!(steep ? plot(y, x) : plot(x, y))) return;
                err = err - dY;
                if (err < 0) { y += ystep;  err += dX; }
            }
        }
    }
}

C++

Here's a C++ version; plot() draws a "dot" at (x, y):

#include <cstdlib>

////////////////////////////////////////////////////////////////////////////////
void Bresenham(int x1,
    int y1,
    int const x2,
    int const y2)
{
    int delta_x(x2 - x1);
    // if x1 == x2, then it does not matter what we set here
    signed char const ix((delta_x > 0) - (delta_x < 0));
    delta_x = std::abs(delta_x) << 1;

    int delta_y(y2 - y1);
    // if y1 == y2, then it does not matter what we set here
    signed char const iy((delta_y > 0) - (delta_y < 0));
    delta_y = std::abs(delta_y) << 1;

    plot(x1, y1);

    if (delta_x >= delta_y)
    {
        // error may go below zero
        int error(delta_y - (delta_x >> 1));
 
        while (x1 != x2)
        {
            // reduce error, while taking into account the corner case of error == 0
            if ((error > 0) || (!error && (ix > 0)))
            {
                error -= delta_x;
                y1 += iy;
            }
            // else do nothing

            error += delta_y;
            x1 += ix;

            plot(x1, y1);
        }
    }
    else
    {
        // error may go below zero
        int error(delta_x - (delta_y >> 1));

        while (y1 != y2)
        {
            // reduce error, while taking into account the corner case of error == 0
            if ((error > 0) || (!error && (iy > 0)))
            {
                error -= delta_y;
                x1 += ix;
            }
            // else do nothing

            error += delta_x;
            y1 += iy;
 
            plot(x1, y1);
        }
    }
}

A template metaprogram implementation (requires the Boost.MPL library):

#include "boost/mpl/bool.hpp"
#include "boost/mpl/char.hpp"

#include "boost/mpl/for_each.hpp"

#include "boost/mpl/bitwise.hpp"
#include "boost/mpl/shift_left.hpp"

#include "boost/mpl/list.hpp"
#include "boost/mpl/push_front.hpp"

#include "boost/mpl/max.hpp"

#include "boost/mpl/minus.hpp"
#include "boost/mpl/arithmetic.hpp"

#include "boost/mpl/pair.hpp"

namespace mpl = boost::mpl;

template <std::size_t N,
  typename x1, typename y1,
  typename delta_x, typename delta_y,
  typename ix, typename iy,
  typename error, typename swap>
struct bresenham_line_pair :
  mpl::push_front<typename bresenham_line_pair<N - 1,
    typename mpl::plus<x1, ix>::type,
    typename mpl::if_c<(error::value > 0)
      || (!error::value && (ix::value > 0)),
      mpl::plus<y1, iy>, y1>::type,
    delta_x, delta_y,
    ix, iy,
    typename mpl::if_c<(error::value > 0)
      || (!error::value && (ix::value > 0)),
      mpl::minus<mpl::plus<error, delta_y>, delta_x>,
      mpl::plus<error, delta_y> >::type,
    swap>::type,
    typename mpl::if_<swap, mpl::pair<y1, x1>, mpl::pair<x1, y1> >::type
  >
{
};

template <typename x1, typename y1,
  typename delta_x, typename delta_y,
  typename ix, typename iy,
  typename error, typename swap>
struct bresenham_line_pair<0, x1, y1, delta_x, delta_y, ix, iy, error, swap> :
  mpl::list<typename mpl::if_<swap, mpl::pair<y1, x1>,
    mpl::pair<x1, y1> >::type>
{
};

template <int x1, int y1, int x2, int y2>
struct bresenham_line
{
  typedef typename mpl::minus<mpl::int_<x2>, mpl::int_<x1> >::type dx;
  typedef typename mpl::minus<mpl::int_<y2>, mpl::int_<y1> >::type dy;

  typedef typename mpl::if_<mpl::less<dx, mpl::int_<0> >,
    mpl::char_<-1>, mpl::char_<1> >::type ix;
  typedef typename mpl::if_<mpl::less<dy, mpl::int_<0> >,
    mpl::char_<-1>, mpl::char_<1> >::type iy;

  typedef typename mpl::max<dx, mpl::negate<dx> >::type abs_dx;
  typedef typename mpl::max<dy, mpl::negate<dy> >::type abs_dy;

  typedef typename mpl::shift_left<abs_dx, mpl::char_<1> >::type delta_x;
  typedef typename mpl::shift_left<abs_dy, mpl::char_<1> >::type delta_y;

  typedef typename mpl::if_<mpl::less<delta_x, delta_y>, mpl::bool_<true>,
    mpl::bool_<false> >::type swap;

  typedef typename mpl::if_<swap, mpl::minus<delta_x, abs_dy>,
    mpl::minus<delta_y, abs_dx> >::type error;

  typedef typename mpl::max<abs_dx, abs_dy>::type N;

  typedef typename mpl::if_<swap,
    bresenham_line_pair<N::value, mpl::int_<y1>, mpl::int_<x1>,
      delta_y, delta_x, iy, ix, error, swap>,
    bresenham_line_pair<N::value, mpl::int_<x1>, mpl::int_<y1>,
      delta_x, delta_y, ix, iy, error, swap> >::type::type sequence_type;
};

struct plotter
{
  template<typename T>
  inline void operator()(T)
  {
    plot(T::first::type::value, T::second::type::value);
  }
};

int main(int, char*[])
{
  mpl::for_each<bresenham_line<0, 0, 20, 10>::sequence_type>(plotter());

  return 0;
}

Lua

Here's a Lua port:

function bresenham(x1, y1, x2, y2)
  delta_x = x2 - x1
  ix = delta_x > 0 and 1 or -1
  delta_x = 2 * math.abs(delta_x)

  delta_y = y2 - y1
  iy = delta_y > 0 and 1 or -1
  delta_y = 2 * math.abs(delta_y)

  plot(x1, y1)

  if delta_x >= delta_y then
    error = delta_y - delta_x / 2

    while x1 ~= x2 do
      if (error > 0) or ((error == 0) and (ix > 0)) then
        error = error - delta_x
        y1 = y1 + iy
      end

      error = error + delta_y
      x1 = x1 + ix

      plot(x1, y1)
    end
  else
    error = delta_x - delta_y / 2

    while y1 ~= y2 do
      if (error > 0) or ((error == 0) and (iy > 0)) then
        error = error - delta_y
        x1 = x1 + ix
      end

      error = error + delta_x
      y1 = y1 + iy

      plot(x1, y1)
    end
  end
end

Python

This Python version returns a list of (x, y) tuples. It was converted from the Ruby version below, but also reverses the list to begin with the first coordinates.

def bresenham_line(start: tuple[int, int], end: tuple[int, int]) -> list[tuple[int, int]]:
    """Return a list of coordinates from `start` to `end` including both endpoints.

    This implementation is symmetrical. It uses the same set of coordinates in either direction.

    >>> bresenham_line((0, 0), (3, 4))
    [(0, 0), (1, 1), (1, 2), (2, 3), (3, 4)]
    >>> bresenham_line((3, 4), (0, 0))
    [(3, 4), (2, 3), (1, 2), (1, 1), (0, 0)]
    """
    # Setup initial conditions
    x1, y1 = start
    x2, y2 = end
    dx = x2 - x1
    dy = y2 - y1

    # Determine how steep the line is
    is_steep = abs(dy) > abs(dx)

    # Rotate line
    if is_steep:
        x1, y1 = y1, x1
        x2, y2 = y2, x2

    # Swap start and end points if necessary and store swap state
    swapped = False
    if x1 > x2:
        x1, x2 = x2, x1
        y1, y2 = y2, y1
        swapped = True

    # Recalculate differentials
    dx = x2 - x1
    dy = y2 - y1

    # Calculate error
    error = dx // 2
    ystep = 1 if y1 < y2 else -1

    # Iterate over bounding box generating points between start and end
    y = y1
    points = []
    for x in range(x1, x2 + 1):
        coord = (y, x) if is_steep else (x, y)
        points.append(coord)
        error -= abs(dy)
        if error < 0:
            y += ystep
            error += dx

    # Reverse the list if the coordinates were swapped
    if swapped:
        points.reverse()
    return points

Ruby

Here's a Ruby version, it returns an array of points, each being a hash with 2 elements (x and y).

def get_line(x0,x1,y0,y1)
  points = []
  steep = ((y1-y0).abs) > ((x1-x0).abs)
  if steep
    x0,y0 = y0,x0
    x1,y1 = y1,x1
  end
  if x0 > x1
    x0,x1 = x1,x0
    y0,y1 = y1,y0
  end
  deltax = x1-x0
  deltay = (y1-y0).abs
  error = (deltax / 2).to_i
  y = y0
  ystep = nil
  if y0 < y1
    ystep = 1
  else
    ystep = -1
  end
  for x in x0..x1
    if steep
      points << {:x => y, :y => x}
    else
      points << {:x => x, :y => y}
    end
    error -= deltay
    if error < 0
      y += ystep
      error += deltax
    end
  end
  return points
end

VB.NET

Here is a generic way of using the algorithm in VB.NET using delegates.

' Author: Jason Morley (Source: http://www.morleydev.co.uk/blog/2010/11/18/generic-bresenhams-line-algorithm-in-visual-basic-net/)

Module BresenhamsLineAlgorithm
    Sub Swap(ByRef X As Long, ByRef Y As Long)
        Dim t As Long = X
        X = Y
        Y = t
    End Sub
    ' If the plot function returns true, the bresenham's line algorithm continues.
    ' if the plot function returns false, the algorithm stops
    Delegate Function PlotFunction(ByVal x As Long, ByVal y As Long) As Boolean
    Sub Bresenham(ByVal x1 As Long, ByVal y1 As Long, ByVal x2 As Long, ByVal y2 As Long, ByVal plot As PlotFunction)
        Dim steep As Boolean = (Math.Abs(y2 - y1) > Math.Abs(x2 - x1))
        If (steep) Then
            Swap(x1, y1)
            Swap(x2, y2)
        End If
        If (x1 > x2) Then
            Swap(x1, x2)
            Swap(y1, y2)
        End If
        Dim deltaX As Long = x2 - x1
        Dim deltaY As Long = Math.Abs(y2 - y1)
        Dim err As Long = deltaX / 2
        Dim ystep As Long
        Dim y As Long = y1
        If (y1 < y2) Then
            ystep = 1
        Else
            ystep = -1
       End If
       For x As Long = x1 To x2
            Dim result As Boolean
            If (steep) Then result = plot(y, x) Else result = plot(x, y)
            If (Not result) Then Exit Sub
            err = err - deltaY
            If (err < 0) Then
                y = y + ystep
                err = err + deltaX
            End If
       Next
    End Sub
    Function plot(ByVal x As Long, ByVal y As Long) As Boolean
        Console.WriteLine(x.ToString() + " " + y.ToString())
        Return True 'This just prints each co-ord
    End Function
    Sub Main()
        ' example
        Bresenham(1, 1, 10, 15, New PlotFunction(AddressOf plot))
        Console.ReadLine()
    End Sub
End Module

Haskell

A slightly verbose version in Haskell. See the discussion page for a variant one line shorter, but IMHO less readable. I bet other version, more readable and more succinct, can be written.

-- | See <http://roguebasin.roguelikedevelopment.org/index.php/Digital_lines>.
balancedWord :: Int -> Int -> Int -> [Int]
balancedWord p q eps | eps + p < q = 0 : balancedWord p q (eps + p)
balancedWord p q eps               = 1 : balancedWord p q (eps + p - q)

-- | Bresenham's line algorithm.
-- Includes the first point and goes through the second to infinity.
bla :: (Int, Int) -> (Int, Int) -> [(Int, Int)]
bla (x0, y0) (x1, y1) =
  let (dx, dy) = (x1 - x0, y1 - y0)
      xyStep b (x, y) = (x + signum dx,     y + signum dy * b)
      yxStep b (x, y) = (x + signum dx * b, y + signum dy)
      (p, q, step) | abs dx > abs dy = (abs dy, abs dx, xyStep)
                   | otherwise       = (abs dx, abs dy, yxStep)
      walk w xy = xy : walk (tail w) (step (head w) xy)
  in  walk (balancedWord p q 0) (x0, y0)

ActionScript

Here's an ActionScript implementation that creates a Line object with an array of points.

package  
{
        import flash.geom.Point;
	
	public class Line 
	{
		public var points:Array = [];
 
		public function Line(x0:int, y0:int, x1:int, y1:int) {
			calculate(x0, y0, x1, y1);
		}

		private function calculate(x0:int, y0:int, x1:int, y1:int):void {
			var dx:int = Math.abs(x1 - x0);
			var dy:int = Math.abs(y1 - y0);
			var sx:int = x0 < x1 ? 1 : -1;
			var sy:int = y0 < y1 ? 1 : -1;
			var err:int = dx - dy;
			
			while (true){
				points.push(new Point(x0, y0));
			 
				if (x0==x1 && y0==y1)
					break;
			 
				var e2:int = err * 2;
				if (e2 > -dx) {
					err -= dy;
					x0 += sx;
				}
				if (e2 < dx){
					err += dx;
					y0 += sy;
				}
			}
		}
	}
}

Go

This is a translation for golang from the Python example above, it returns a slice to a struct that contains two ints.

type Vector2i struct {
	X, Y int
}

func getLine(pos1, pos2 Vector2i) (points []Vector2i) {
	x1, y1 := pos1.X, pos1.Y
	x2, y2 := pos2.X, pos2.Y

	isSteep := abs(y2-y1) > abs(x2-x1)
	if isSteep {
		x1, y1 = y1, x1
		x2, y2 = y2, x2
	}

	reversed := false
	if x1 > x2 {
		x1, x2 = x2, x1
		y1, y2 = y2, y1
		reversed = true
	}

	deltaX := x2 - x1
	deltaY := abs(y2 - y1)
	err := deltaX / 2
	y := y1
	var ystep int

	if y1 < y2 {
		ystep = 1
	} else {
		ystep = -1
	}

	for x := x1; x < x2+1; x++ {
		if isSteep {
			points = append(points, Vector2i{y, x})
		} else {
			points = append(points, Vector2i{x, y})
		}
		err -= deltaY
		if err < 0 {
			y += ystep
			err += deltaX
		}
	}

	if reversed {
		//Reverse the slice
		for i, j := 0, len(points)-1; i < j; i, j = i+1, j-1 {
			points[i], points[j] = points[j], points[i]
		}
	}

	return
}

func abs(x int) int {
	switch {
	case x < 0:
		return -x
	case x == 0:
		return 0
	}
	return x
}

JavaScript

Adapted from the C# example above, but improved so line is drawn in original direction. Demo here: [1].

function drawline(x0,y0,x1,y1){
  var tmp;
  var steep = Math.abs(y1-y0) > Math.abs(x1-x0);
  if(steep){
    //swap x0,y0
    tmp=x0; x0=y0; y0=tmp;

    //swap x1,y1
    tmp=x1; x1=y1; y1=tmp;
  }
  
  var sign = 1;
  if(x0>x1){
    sign = -1;
    x0 *= -1;
    x1 *= -1;
  }
  var dx = x1-x0;
  var dy = Math.abs(y1-y0);
  var err = ((dx/2));
  var ystep = y0 < y1 ? 1:-1;
  var y = y0;
  
  for(var x=x0;x<=x1;x++){
    if(!(steep ? plot(y,sign*x) : plot(sign*x,y))) return;
    err = (err - dy);
    if(err < 0){
      y+=ystep;
      err+=dx;
    }
  }
}

Rust

This is a translation for Rust from the Go example above, it returns a Vec of structs that contains two ints. (tested rustc ver 1.14.0)

#[derive(Copy, Clone, Debug)]
struct Point2d{
    pub x: u32,
    pub y: u32
}
fn get_line(a: Point2d, b: Point2d) -> Vec<Point2d> {
    let mut points = Vec::<Point2d>::new();
    let mut x1 = a.x as i32;
    let mut y1 = a.y as i32;
    let mut x2 = b.x as i32;
    let mut y2 = b.y as i32;
    let is_steep = (y2-y1).abs() > (x2-x1).abs();
    if is_steep {
        std::mem::swap(&mut x1, &mut y1);
        std::mem::swap(&mut x2, &mut y2);
    }
    let mut reversed = false;
    if x1 > x2 {
        std::mem::swap(&mut x1, &mut x2);
        std::mem::swap(&mut y1, &mut y2);   
        reversed = true;
    }
    let dx = x2 - x1;
    let dy = (y2 - y1).abs();
    let mut err = dx / 2;
    let mut y = y1;
    let ystep: i32;
    if y1 < y2 {
        ystep = 1;
    } else {
        ystep = -1;
    }
    for x in x1..(x2+1) {
        if is_steep {
            points.push(Point2d{x:y as u32, y:x as u32});
        } else {
            points.push(Point2d{x:x as u32, y:y as u32});
        }
        err -= dy;
        if err < 0 {
            y += ystep;
            err += dx;
        }
    }

    if reversed {
        for i in 0..(points.len()/2) {
            let end = points.len()-1;
            points.swap(i, end-i);
        }
    }
    points
}

GDScript

Adapted from python example above, it returns an Array of Vector2i.

# Bresenham's Line Algorithm
func get_line(start:Vector2i, end:Vector2i)->Array[Vector2i]:

	# Setup initial conditions
	var x1: float = start.x
	var y1: float = start.y
	var x2: float = end.x
	var y2: float = end.y
	var dx: float = x2 - x1
	var dy: float = y2 - y1

	# Determine how steep the line is
	var is_steep = abs(dy) > abs(dx)
	var swap_var = 0.0
	
	# Rotate line
	if is_steep:
		swap_var = x1
		x1 = y1
		y1 = swap_var
		
		swap_var = x2
		x2 = y2
		y2 = swap_var

	# Swap start and end points if necessary and store swap state
	var swapped := false
	if x1 > x2:
		swap_var = x1
		x1 = x2
		x2 = swap_var
		swap_var = y1
		y1 = y2
		y2 = swap_var
		swapped = true

	# Recalculate differentials
	dx = x2 - x1
	dy = y2 - y1

	# Calculate error
	var error: float = floor(dx / 2.0)  # Try int
	var ystep = 1 if y1 < y2 else -1

	# Iterate over bounding box generating points between start and end
	var y = y1
	var points: Array[Vector2i] = []
	for x in range(x1, x2 + 1):
		var coord = Vector2i(y, x) if is_steep else Vector2i(x, y)
		points.append(coord)
		error -= abs(dy)
		if error < 0:
			y += ystep
			error += dx

	# Reverse the list if the coordinates were swapped
	if swapped:
		points.reverse()
	return points