Bresenham's Line Algorithm
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
Below are several hand-coded implementations in various languages.
Here is a simple way of using the algorithm in C# with delegates.
Here's a C++ version; plot() draws a "dot" at (x, y):
A template metaprogram implementation (requires the Boost.MPL library):
Here's a Lua port:
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.
Here's a Ruby version, it returns an array of points, each being a hash with 2 elements (x and y).
Here is a generic way of using the algorithm in VB.NET using delegates.
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.
Here's an ActionScript implementation that creates a Line object with an array of points.
This is a translation for golang from the Python example above, it returns a slice to a struct that contains two ints.
Adapted from the C# example above, but improved so line is drawn in original direction. Demo here: .
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)
Adapted from python example above, it returns an Array of Vector2i.