How to get all tiles along a straight vector path?

Question

Let's say I have a 100x100 map of tiles where each tile is 16x16 pixels.

How would I get all tiles along a path? For example, let's say I wanted to get a list of all tiles along the shortest direct path between x: 50, y: 100 and x: 225, y: 200

To convert a coordinate to tile space, you simply divide the coordinate by the tile size and then floor it.

So with this example, the world coordinates would be converted to the following tile coordinates:

let tileStartX = Math.floor(50 / 16); // 3
let tileStartY = Math.floor(100 / 16); // 6

let tileEndX = Math.floor(225 / 16); // 14
let tileEndY = Math.floor(200 / 16); // 12

So, we'd be looking for all tiles between x: 3, y: 6 and x: 14, y: 12 like in this example image (0, 0 is top left here):

It's easy enough to convert world coordinates to tile coordinates, but what I'm having trouble with how to get all the intermediate tiles along the diagonal.

Also, I think I may have messed up the drawing slightly because I didn't fill in some white squares where the units have to briefly walk through.

Answer 1

This is known as a line-drawing algorithm. That link has multiple algorithms to solve this problem - for your case you'll want to ignore the algorithms which anti-alias. The simplest solution is the naive algorithm:

dx = x2 − x1
dy = y2 − y1

for x from x1 to x2 do
    y = y1 + dy × (x − x1) / dx
    plot(x, y)

(pseudocode copied from wikipedia)

A more complex but slightly faster version is Bresenham's algorithm.