Bresenham's Line Algorithm
Revision as of 02:35, 7 August 2023 by HexDecimal (talk | contribs) (Added Wikipedia link, the other link is linked from the Wikipedia page so it might be redundant)
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
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)
{
// 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.0
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