Line drawing

On a grid map, line drawing is useful for for visibility, the path of an arrow/bullet, and enemy AI. There are several fast algorithms for this but I prefer using a very simple algorithm. Here's the algorithm in action:

Linear interpolation: numbers

Let's look at linear interpolation, or lerp, for numbers:

lerp(  0,   1, ) = 
lerp(  0, 100, ) = 
lerp(  3,   5, ) = 
lerp(  5,   3, ) =

Linear interpolation: points

Let's look at linear interpolation for points. We can separately linearly interpolate the x and y values, and it behaves as we might expect:

Try varying t = .

Number of points

Instead of picking 1 interpolation point, let's pick N of them:

Try varying N = .

Snap to grid

Now let's round each of those N points to the closest grid square:

Try varying N = until it reaches the optimal value of = max(Δx,Δy).