# Line drawing on a grid

from Red Blob Games

Graphics libraries provide line-drawing routines, sometimes with antialiasing and variable width. On a grid map, line drawing is useful for for visibility, the path of an arrow/bullet, and enemy AI. I sometimes see people adapting the Bresenham line drawing algorithm to draw lines on a grid (especially for roguelike games), but I prefer simpler algorithms. I’ll show the algorithms I use. I’m not a line-drawing expert so please let me know if there are better algorithms that are similarly simple.

## 1  Linear interpolation#

This demo shows what grid locations should be marked if you’re drawing a line between two points. Try moving the endpoints around.

I find the easiest way to find these points is to use linear interpolation. Let’s see how that works.

### 1.1 Interpolating numbers#

Here’s a simple (Javascript) helper function I’ll use:

```function lerp(start, end, t) {
return start + t * (end-start);
}
```

Linear interpolation (“lerp”) gives you a number between two other numbers. When `t` = 0.0 you get the start point; when `t` = 1.0 you get the end point. Try setting t, the third parameter to lerp():

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

In shaders, this function is called `lerp` in DirectX and `mix` in OpenGL. It’s called `lerp` in Unity and Unreal.

### 1.2 Interpolating points#

We can extend the idea of interpolation to work on points, by interpolating both the x and y coordinates. Try varying t = :

Here’s the code to find point x,y between point p0 = (x0,y0) and point p1 = (x1,y1):

```function lerp_point(p0, p1, t) {
return new Point(lerp(p0.x, p1.x, t),
lerp(p0.y, p1.y, t));
}
```

Let’s divide the line into equal line segments:

Here’s the code to find those points:

```var points = [];
for (var step = 0; step <= N; step++) {
var t = step / N;
points.push(lerp_point(p0, p1, t));
}
```

Variant: we can replace step <= N with another condition, such as stopping at a wall or at the edge of the map.

### 1.3 Snap to grid#

Next we need to figure out which grid squares those points are in. We can round x and y to the nearest integer to find the grid tile:

We also need to decide how many points to include. Too few and the line has holes. Too many and the line has overdraw. How many do we need? The right number is the diagonal distance between the endpoints, which in this case is .

Adjust N = to to see how the line fills in.

That’s it!

1. Set N to the diagonal distance between the start and end point.
2. Pick N+1 interpolation points, evenly spaced.
3. Round those points to the nearest grid tile.

Here’s the final code:

```function line(p0, p1) {
var points = [];
var N = diagonal_distance(p0, p1);
for (var step = 0; step <= N; step++) {
var t = N == 0? 0.0 : step / N;
points.push(round_point(lerp_point(p0, p1, t)));
}
return points;
}
```

This is the simplest line drawing algorithm I know of. Here are the helper functions, which you may have already implemented:

```function diagonal_distance(p0, p1) {
var dx = p1.x - p0.x, dy = p1.y - p0.y;
return Math.max(Math.abs(dx), Math.abs(dy));
}

function round_point(p) {
return new Point(Math.round(p.x), Math.round(p.y));
}

function lerp_point(p0, p1, t) {
return new Point(lerp(p0.x, p1.x, t),
lerp(p0.y, p1.y, t));
}

function lerp(start, end, t) {
return start + t * (end-start);
}
```

### 1.4 Interpolating other types#

I defined the `lerp` function to interpolate between two numbers, and then I defined `lerp_point` to work on two points. How about other types T? We need these operations to define interpolation:

b = a + d where a: T, b: T, and d: ΔT. For points, b.x = a.x + d.x; b.y = a.y + d.y
subtraction
d = a - b where a: T, b: T, and d: ΔT. For points, d.x = a.x - b.x; d.y = a.y - b.y
multiplication by scalar
e = k * d where d: ΔT, e: ΔT, and k: number. For points, e.x = k * d.x; e.y = k * d.y

We can do interpolation on any vector space. T can be a number, a 2d point, a 3d point, an angle, a time, a color, or other things too. My guide to hexagonal grids uses interpolation to draw lines on a hex grid. Note that T and ΔT may be the same type, but sometimes they are different. For example, T may be a timestamp and ΔT may be a time difference, or T may be an orientation and ΔT may be a rotation. When T and ΔT are the same type, d = a - b can be implemented as d = a + (-1 * b).

### 1.5 TODO Aesthetics#

Linear interpolation is calculating a position and then rounding it. What happens when the value is exactly 0.5? Rounding rules vary. That, and floating point precision, make linear interpolation not always choose points in a way that preserves consistency with rotation, reversing, and other symmetry.

I think the thing to do would be to “nudge” the initial points by epsilon. However I haven’t explored this.

### 1.6 Code optimization#

You can optimize the regular line drawing algorithm with these steps; it will turn into the DDA algorithm:

Inlining function calls
Your compiler will likely do this but you may spot additional optimization opportunities by doing this yourself first.
Unrolling lerp
Instead of calculating t each time through the loop, and then x = (b.x-a.x)*t (a subtract and multiply), you can calculate Δx = (b.x-a.x)*Δt outside the loop, and then use x += Δx. Same for y. This will replace the multiplies with adds.
Unrolling loop
You can unroll the loop by keeping four x and y pairs, and then using t += 4*Δt. Would this allow the use of SSE instructions? I don’t know.
Separate cases
Either Δx or Δy will be ±1. You might want to have a separate versions for each case. For diagonal lines, both will be ±1. For orthogonal lines, one or the other will be 0. If these cases are common, write a separate routine for them.
Floating point vs fixed point
If you profile and find Math.round() is expensive, you can switch to fixed point arithmetic, and replace rounding with bit shifting. On x86, consider using the `fist=/=fistp` instruction or maybe SSE for `cvtsd2si` (I haven’t gone this far in optimization).

Before optimizing, profile and make sure linear interpolation is your bottleneck. In my projects, it rarely is, so I haven’t bothered implementing these optimizations. Here’s an example (in approximate C# syntax, to show the types) of inlining + unrolling lerp, but without applying the other optimizations:

```List<Point> line(Point p0, Point p1) {
List<Point> = new List<Point>();
int dx = p1.x - p0.x;
int dy int = p1.y - p0.y;
int N = Math.Max(Math.Abs(dx), Math.Abs(dy));
float divN = (N == 0)? 0.0 : 1.0 / N;
float xstep = dx * divN;
float ystep = dy * divN;
float x = p0.x, y = p0.y;
for (int step = 0; step <= N; step++, x += xstep, y += ystep) {
}
return points;
}
```

## 2  Grid walking#

Interpolation is simple and general but doesn’t take into account properties of the grid. Another approach to line drawing is to take one step at a time. This type of movement also allows putting walls on edges so that a wall could block line of sight or movement.

### 2.1 Orthogonal steps#

In the above lines, we took both orthogonal steps (north, east, south, west) and diagonal steps. Step-by-step algorithms give us more flexibility. What if we only want to take orthogonal steps?

The strategy here is to think about the grid edges being crossed, both vertical and horizontal. At every step we either cross a vertical edge (horizontal step) or cross a horizontal edge (vertical step).

```function walk_grid(p0, p1) {
var dx = p1.x-p0.x, dy = p1.y-p0.y;
var nx = Math.abs(dx), ny = Math.abs(dy);
var sign_x = dx > 0? 1 : -1, sign_y = dy > 0? 1 : -1;

var p = new Point(p0.x, p0.y);
var points = [new Point(p.x, p.y)];
for (var ix = 0, iy = 0; ix < nx || iy < ny;) {
if ((0.5+ix) / nx < (0.5+iy) / ny) {
// next step is horizontal
p.x += sign_x;
ix++;
} else {
// next step is vertical
p.y += sign_y;
iy++;
}
points.push(new Point(p.x, p.y));
}
return points;
}
```

It’s more work to make it symmetric. Also, sometimes you’ll want more control over whether you pick a horizontal step or a vertical step, especially if the choice is close, and there’s a wall in one direction but not the other.

### 2.2 Supercover lines#

“Supercover” lines catch all the grid squares that a line passes through. I believe (but am not sure) that it is somewhere in between regular line drawing and grid movement line drawing. Unlike grid movement line drawing, we can take a diagonal step only if the line passes exactly through the corner.

This looks just like the grid movement line drawing, except when the line goes through a grid corner.

Let’s modify the grid movement line drawing code for this:

```function supercover_line(p0, p1) {
var dx = p1.x-p0.x, dy = p1.y-p0.y;
var nx = Math.abs(dx), ny = Math.abs(dy);
var sign_x = dx > 0? 1 : -1, sign_y = dy > 0? 1 : -1;

var p = new Point(p0.x, p0.y);
var points = [new Point(p.x, p.y)];
for (var ix = 0, iy = 0; ix < nx || iy < ny;) {
if ((0.5+ix) / nx == (0.5+iy) / ny) {
// next step is diagonal
p.x += sign_x;
p.y += sign_y;
ix++;
iy++;
} else if ((0.5+ix) / nx < (0.5+iy) / ny) {
// next step is horizontal
p.x += sign_x;
ix++;
} else {
// next step is vertical
p.y += sign_y;
iy++;
}
points.push(new Point(p.x, p.y));
}
return points;
}
```

Implementation note: it’s usually a bad idea to compare two floating point numbers for equality, as I do here. However, since `ix`, `nx`, `iy`, `ny` are all integers, we can ensure this works properly by cross-multiplying and rewriting the test with integer arithmetic.

```        if ((1+2*ix) * ny == (1+2*iy) * nx) { ... }
```

It still feels somewhat fragile to me, and I’m guessing there are better algorithms out there.

### 2.3 Line of sight

If you allow diagonal steps, some algorithms will step through walls:

In this case, you can either take the diagonal step if either the horizontal or vertical step is clear, or you can disallow the diagonal step unless both the horizontal and vertical steps are clear.