Path finding in grid for objects that occupy more than one tile

Question

In a grid-based game I am working on, I want to add objects that occupy more than one tile of the grid. Are there any algorithms or techniques to find paths for this kind of objects?

Answer 1

In general you'll be adapting existing pathfinding algorithms to be width-sensitive. Primarily that means adapting A*, though since your game is grid-based you may find the algorithm for solving fat mazes helpful.

For A*, the most basic solution is to simply add an assertion for width to your calculations, according to your movement rules. However, this will make a mess of your pathfinding code and slows down pathfinding for any regular-sized entities.

Alternatively, you can consider your grid to be a node-based pathfinding network, and for your larger entities you could create a secondary network which accounts for their size, and use that for movement and pathfinding. This has the benefit of allowing you to tailor your pathfinding for larger entities so that it behaves as expected, but means creating multiple maps for each scene and holding them in memory, which may impact games on mobile platforms.

If neither of those methods suits your purposes, you could look for inspiration in navigation mesh pathfinding algorithms, which are inherently width-aware.

Answer 2

One option would be to calculate a second grid that takes the object's size into account by "painting" it onto the grid, like so. Here's the original grid:

#########
#..b....#
#.#.....#
#.####..#
#.......#
#.......#
#..#.#..#
#a.#.#..#
#########

We want to see if a 2x2 object can get from a to b. We calculate a second grid where every time we have a wall (#), we add walls above and to the left of it (x), turning each single wall segment into a 2x2 one. Now it looks like:

xxxxxxxxxx
x#########
x#xxb...x#
x#x#xxx.x#
x#x####.x#
x#......x#
x#.xxxx.x#
x#.x#x#.x#
x#ax#x#xx#
x#########

We can then pathfind on this grid by treating the object as 1x1 since the grid itself takes their size into account.

Answer 3

You can extend munificent's answer to store a single supporting grid, which rather than storing passability for each different object size, it stores a distance field recording the number of half-tile widths between this location and the closest barrier. (Or alternatively, the width of the largest object that can be centered on this tile without hitting anything)

• A wall tile has a distance of -1 (the center of this tile is inside the bulk of the wall).
• A tile adjacent to a wall on at least one side has a distance of 1 (one half a tile separates the center of this tile from the edge of the closest wall)
• A tile with no adjacent walls, that's adjacent to a tile that's adjacent to a wall, has a distance of 3 (one full tile width to reach its neighbour's center, and one half tile from there to the wall)

You can populate this grid by initializing the map to an integer larger than your map size in empty spaces, and -1 at wall sites. Then iteratively set each tile > 0 to the minimum of its neighbours plus two.

Now inside your pathfinding algorithm, you replace

if (!IsPassable(PassabilityMap[x, y])) continue;

with

if (DistanceToObstacleMap[x, y] < pathfindingAgent.size) continue;

Now you can handle pathfinding for any size of unit with a single map, and storing / checking passability remains comparable in cost to the one-bool-per-tile case.