Line drawing on a grid

Bresenham is slower on modern hardware. Well, still better on microcontrollers and less gates to implement it on silicon / FPGA resources.

Ever since 486 days, it's been faster just to do a division and loop in direction of the longer delta axis. Fixed point addition and shift to truncate for shorter axis coordinate.

In some old CPUs, add to eax (or even ax) and ah (higher half of 16-bit ax) for the coordinate. Requires a small (or split/tiled) frame buffer. I remember it was still worth it 20 years ago.

Nowadays you don't have to perform that ax/ah/al trickery, because CPUs have been capable of register renaming, pipelining, multiple issue, etc. for at least 20 years, and extra mov, shr etc. to replace it could be sank between other instructions and memory waits. Accessing ax ah/al halves is the slower, unoptimized path in anything that resembles a modern CPU.

Bresenham lines are not "quality." For one, they're obviously jaggy. As well, most implementations of the algorithm will give you different results if you invert the start and end points. This matters a great deal for the common use-case in games of casting rays to determine sight lines. It is quite annoying to have a tactical combat game where a foe can shoot from behind a wall and you can't shoot back from the exact same position. Amit notes lack of symmetry in the "2.1 Orthogonal steps" implementation, which leads him to the "Supercover" implementation.

You are right. Thanks for bringing this to my attention. http://www.redblobgames.com/pathfinding/a-star/introduction....

Every now and then I visit Amit's pages and find something interesting that he explains in an awesome way.

Another great one by the same author for those who haven't see it is the terrain generation document:

http://www-cs-students.stanford.edu/~amitp/game-programming/...

I used to draw the lines that way, but I've switched to drawing the squares instead. It tends to look cleaner, the code is simpler, and it also lets me color the squares individually. If I really need to draw the lines, I can set a background color. It's a cheap trick :-)

One nice thing about linear interpolation is that the same algorithm works for 2D grids, 3D grids, and hex grids. For 3D, the diagonal_distance, point_lerp, and point_round functions can look at at z in addition to x and y. For hex grids, you need hex grid distances and hex grid rounding (http://www.redblobgames.com/grids/hexagons/#line-drawing).