Find the closest tile along a path

Question

I have a tile based game and I need to find the closest tile within a 32px radius. So say a user is at 400, 200 and the user clicks at 500, 400. I need to create a path or line from the player to the mouse position on click and the closest tile that is underneath the path within 32px (or 2 tiles) must be chosen. The map is tiled at 16px.

A function call to see if a tile is at a given tile position is available Map.at(x,y).

I just don't know the maths to use to work this out.

The block blocks are within 16px, the red are within 32px. The grey block is the tile to be destroyed and the blue line is the invisible path between the player and mouse.

Answer 1

If you work in terms of tile coordinates, the problem becomes a line-drawing problem from the title the user is at to the tile the mouse was clicked in. A line drawing algorithm would generate, in sequence, all the tiles along a straight-line path between those two tiles. Just pick the first one where Map.at(x,y) satisfies your requirements and exit the line-drawer.

A number of line drawing algorithms exist. Two simple ones are DDA and Bresenham's. Both generate the discrete "pixels" (tiles, in your question) in the correct order. The DDA is the simple choice if floating point arithmetic can be used in your application. Bresenham's uses only integer math.

Answer 2

With a lot of games, it's not necessary a straight line, but a search for the shortest path. If that's where you are heading then you might want to look at the A* algorithm.