# How to get all tiles along a straight vector path?

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.

• Are you perhaps looking for this algorithm? (Don't fret that the paper describes it in 3D — shaving off a dimension to work in 2D is straightforward) – DMGregory Mar 2 at 1:07

## 1 Answer

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.

• Actually, I think I just realized this was harder than I thought. Not sure whether I should edit this question or make an entire new one. For one, I don't think I can get the tile coordinates this simply (by doing Math.floor(pos / 16)), because depending on the unit's absolute position, the line segment connecting it to the other unit will differ in which tiles it intersects. Currently I'm just assuming it's in the middle of the tile, but that won't always work. Hmm.. – Ryan Peschel Mar 1 at 23:56