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
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.
No comments:
Post a Comment