Bresenham's Line Algorithm

From RogueBasin
Revision as of 23:16, 20 August 2012 by Johndoe (talk | contribs)
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.

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);
        }
    }
}

Check out the template metaprogram implementation (requires Boost.MPL library)

#include "boost/mpl/for_each.hpp"

#include "boost/mpl/bool.hpp"
#include "boost/mpl/size_t.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)),
      typename mpl::plus<iy, y1>::type,
      y1>::type,
    delta_x, delta_y,
    ix, iy,
    typename mpl::if_c<(error::value >= 0)
      && (error::value || (ix::value > 0)),
      typename mpl::minus<typename mpl::plus<error,
        delta_y>::type, delta_x>::type,
      typename mpl::plus<error, delta_y>::type>::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>
class bresenham_line
{
public:
  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::int_<-1>, mpl::int_<1> >::type ix;
  typedef typename mpl::if_<mpl::less<dy, mpl::int_<0> >,
    mpl::int_<-1>, mpl::int_<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::times<mpl::int_<2>, abs_dx>::type delta_x;
  typedef typename mpl::times<mpl::int_<2>, abs_dy>::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,
    typename mpl::minus<delta_x, abs_dy>::type,
    typename mpl::minus<delta_y, abs_dx>::type>::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>
  void operator()(T)
  {
    plot(T::first::type::value, T::second::type::value);
  }
};

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

  return 0;
}

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)