Bresenham Lines
The Bresenham Line algorithm is an approach to drawing integerbased lines. It comes from a time when realtime rendering on PCs was nearly nonexistant, and the drawing of a simple image was measured not in milli or nanoseconds, but in seconds and minutes. It offered primitive lines at high speed, especially in it’s assembly form, at the cost of fidelity.
Developed in 1962, it was later supplanted by Xiaolin Wu’s Line algorithm in 1992 which boasted fast antialiased lines (though slower then Bresenham). Wu’s arrival was nearly three decades ago, so of what use is Bresenham’s in 2019, 57 years after it’s initial development?
Well, sometimes you just need a simple, integerbased line algorithm. Which is exactly what Bresenham’s is.
The Algorithm
To start, Bresenham uses only the slope of the line, in the form of x and y delta values. That, used in combination with the current position, is sufficient for plotting the line points.
The algorithm takes in a starting point (x0, y0)
and an ending point (x1, y1)
. It calculates the deltas and then begins to step along the line going from the start to the end. For each step, we always move once along the major line axis. If it is a horizontal line we always move along the xaxis, if it is a vertical line we always move along the yaxis.
All points in the plane can be split into two categories: those that lie exactly on the line, and those that are on one side of the line. During each step of the algorithm, we keep a running error
value which tracks how far off from the line the last point was.
When the error
value is too large (greater or equal to 0
), then we move once along our minor axis. The pseudocode for calculating the error
is as follows:


Intuitively this can be thought of as we move once along the minor axis each time the line moves halfway between cells along the minor axis. Or, the error
value is large enough that we know the next point on the minor axis is closer to the true line.
The graphic below shows the stepbystep progress of plotting a Bresenham line. Notice that only the first and last points are exactly on the line, and that we plot with an origin in the upperleft corner. Some adaptations have an origin in the center of the cell which misses the point that Bresenham is first and foremost an integerbased line.
As we step along the major x
axis we can see the error
increasing. Once it is greater or equal to zero, the error
is readjusted and we move once along the minor y
axis. The number of steps taken is always equal to the major delta plus one, so for a horizontal line we take (x1  x0) + 1
steps.
Hopefully at this point you have an understanding of the Bresenham algorithm. Below is an implementation in C++, which can be easily adapted to any other language.


Uses and Adaptations
Cool, now what?
I assume that you came into this post with ideas in mind for what you were going to use Bresenham’s for. That you googled 2d line drawing
or something similar, and if that is the case I will leave it to you to go forth and implement the algorithm for your own use.
However, if you stumbled upon this post by accident, or you knew what Bresenham’s was but didn’t have a good use for it, I will share my particular case.
In mid2018 I began development on a modern Roguelike, Realms. Though it makes use of many newish technologies (Unity 5, C#, ECS programming, etc.) it, as a byproduct of being a Roguelike, still has some oldschool problems which require oldschool solutions.
One such problem is calculating diagonal movement along a tile grid. In short, when traveling in the cardinal directions we can simply move one unit. The distance from (0, 0)
to (1, 0)
is 1. However moving diagonally from (0, 0)
to (1, 1)
the distance is √2 which isn’t quite as neat.
In fact, it can quickly start getting messy and you may begin contemplating using hex tiles instead. Plus there are addtional challenges when we want to move further than one space at a time, or we want to shoot a fireball at a faraway target. And that is where Bresenham’s comes in, and it can be seen in use by a multitude of games, including other Roguelikes such as Dungeon Crawl Stone Soup.
There is a followup ramble in which an implementation of Variable Length Bresenham Lines is discussed.
References
 Abrash, Michael. Graphics Programming Black Book. Coriolis, 1997, pp. 654–678. http://downloads.gamedev.net/pdf/gpbb/gpbb35.pdf.