Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers

up vote 3 down vote accepted

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.

share|improve this answer
add comment

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 everytime 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.

share|improve this answer
    
I don't like this option much because I would need to create a different grid for every object size... –  miguelSantirso Jun 22 '11 at 18:51
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.