Bresenham's Line Algorithm
Jump to navigation
Jump to search
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)),
typename mpl::plus<y1, iy>::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>
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::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::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,
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>
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;
}
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)