Skip to main content
replaced broken link with WebArchive version
Source Link

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 meshnavigation mesh pathfinding algorithmspathfinding algorithms, which are inherently width-aware.

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.

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.

Source Link
Keeblebrox
  • 800
  • 4
  • 18

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.