Bresenham's Line Algorithm

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.

In libtcod it is accessible using line(x1, y1, x2, y2, callback). 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)
        {
            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)
        {
            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) and ((error ~= 0) or (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) and ((error ~= 0) or (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 get_line(x1, y1, x2, y2):
    points = []
    issteep = abs(y2-y1) > abs(x2-x1)
    if issteep:
        x1, y1 = y1, x1
        x2, y2 = y2, x2
    rev = False
    if x1 > x2:
        x1, x2 = x2, x1
        y1, y2 = y2, y1
        rev = True
    deltax = x2 - x1
    deltay = abs(y2-y1)
    error = int(deltax / 2)
    y = y1
    ystep = None
    if y1 < y2:
        ystep = 1
    else:
        ystep = -1
    for x in range(x1, x2 + 1):
        if issteep:
            points.append((y, x))
        else:
            points.append((x, y))
        error -= deltay
        if error < 0:
            y += ystep
            error += deltax
    # Reverse the list if the coordinates were reversed
    if rev:
        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 = 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
}