Bresenham's Line Algorithm
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.
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 x2,
int y2)
{
// if x1 == x2 or y1 == y2, then it does not matter what we set here
int delta_x(x2 - x1);
signed char ix((delta_x > 0) - (delta_x < 0));
delta_x = std::abs(delta_x) << 1;
int delta_y(y2 - y1);
signed char 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)
{
if (error || (ix > 0))
{
y1 += iy;
error -= delta_x;
}
// else do nothing
}
// else do nothing
x1 += ix;
error += delta_y;
plot(x1, y1);
}
}
else
{
// error may go below zero
int error(delta_x - (delta_y >> 1));
while (y1 != y2)
{
if (error >= 0)
{
if (error || (iy > 0))
{
x1 += ix;
error -= delta_y;
}
// else do nothing
}
// else do nothing
y1 += iy;
error += delta_x;
plot(x1, y1);
}
}
}
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.
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