Introduction

When a line crosses a tiled grid, many applications need every cell the line touches, not just a few sampled points. This comes up in tile games, ray casting, occupancy grids, and line-of-sight systems. A robust answer uses deterministic grid traversal rather than ad hoc interpolation.

Define the Coverage Rule First

Before writing code, decide what counts as a touched square. Two common policies are:

• raster-style coverage, similar to plotting one representative pixel path,
• supercover coverage, which includes every grid cell intersected by the segment.

For collision and visibility work, supercover is usually the safer choice because it avoids missing cells near diagonal boundaries or corner crossings.

Traverse the Grid Boundary by Boundary

A reliable method is to step from one grid boundary to the next. This is often described as Amanatides-and-Woo style grid traversal.

1import math
2
3
4def cells_on_line(x0, y0, x1, y1):
5    cells = []
6
7    cx = math.floor(x0)
8    cy = math.floor(y0)
9    tx = math.floor(x1)
10    ty = math.floor(y1)
11
12    cells.append((cx, cy))
13
14    dx = x1 - x0
15    dy = y1 - y0
16
17    step_x = 0 if dx == 0 else (1 if dx > 0 else -1)
18    step_y = 0 if dy == 0 else (1 if dy > 0 else -1)
19
20    if dx != 0:
21        next_x = cx + 1 if step_x > 0 else cx
22        t_max_x = (next_x - x0) / dx
23        t_delta_x = step_x / dx
24    else:
25        t_max_x = float("inf")
26        t_delta_x = float("inf")
27
28    if dy != 0:
29        next_y = cy + 1 if step_y > 0 else cy
30        t_max_y = (next_y - y0) / dy
31        t_delta_y = step_y / dy
32    else:
33        t_max_y = float("inf")
34        t_delta_y = float("inf")
35
36    while cx != tx or cy != ty:
37        if t_max_x < t_max_y:
38            cx += step_x
39            t_max_x += t_delta_x
40            cells.append((cx, cy))
41        elif t_max_y < t_max_x:
42            cy += step_y
43            t_max_y += t_delta_y
44            cells.append((cx, cy))
45        else:
46            cx += step_x
47            cy += step_y
48            t_max_x += t_delta_x
49            t_max_y += t_delta_y
50            cells.append((cx, cy))
51
52    return cells
53
54print(cells_on_line(0.2, 0.2, 6.8, 4.3))
55print(cells_on_line(2.5, 1.2, 2.5, 6.9))

This returns the cells in traversal order, which is useful if the caller wants to stop at the first obstacle.

Why Corner Crossings Matter

When the line reaches the next vertical and horizontal boundary at the same moment, you have a corner crossing. If that case is handled carelessly, diagonal lines can miss cells.

For some uses, advancing diagonally is enough. For conservative collision systems, you may also choose to include side-adjacent cells at corner crossings depending on the exact supercover rule you want.

That is why the coverage definition from the first section matters so much.

Coordinate Conventions Must Stay Consistent

The same algorithm works across coordinate systems, but you must decide and document:

• whether the origin is top-left or bottom-left,
• whether the vertical axis increases upward or downward,
• whether cell coordinates refer to corners or to cell indices.

A surprising number of "algorithm bugs" are really coordinate-mapping mistakes.

Testing Strategy

A good implementation should be tested on:

• horizontal lines,
• vertical lines,
• diagonals with corner crossings,
• reverse-direction traversal,
• short segments that stay inside one cell.

Even a small set of tests catches most grid-traversal regressions.

1def test_same_cell():
2    cells = cells_on_line(1.1, 1.1, 1.8, 1.7)
3    assert cells == [(1, 1)]
4
5
6def test_vertical():
7    cells = cells_on_line(2.5, 1.2, 2.5, 3.9)
8    assert cells[0] == (2, 1)
9    assert cells[-1] == (2, 3)

Common Pitfalls

A common mistake is not deciding whether supercover or raster-style coverage is required before coding.

Another issue is ignoring equal-boundary cases at corners, which can cause missed diagonal intersections.

Developers also often forget to handle divide-by-zero cases for perfectly vertical or horizontal lines.

Summary

• Decide the coverage rule before implementing the traversal.
• Use boundary-distance stepping for deterministic cell enumeration.
• Treat corner crossings explicitly so diagonal lines do not miss cells.
• Keep coordinate conventions consistent across the whole pipeline.
• Preserve traversal order so the result is useful for collision and visibility checks.