I am new to game development and just want to ask for advice. I need to know which path-finding algoritm will be suitable for my scenario:
- Units - any shape. But in most cases rectangles of different sizes.
- I have random generated maze and destination point or area.
- Because of different maze borders not all unit can fit and move to the end.
How to find path from unit to destination area and check that shape can move to this area?
Answer
A* is the logical choice. Your main concern is going to be with generating good navigation nodes. The nodes will tell you everything you need to know about how traversable each node is with respect to each unit.
Having size information associated with your nodes will be very helpful to you. In the above, we see a size 1 unit can use any of the nodes.
Where the same map for a size two unit looks pretty different, since all the size 1 areas are also non-traversable:
The above images are from the article "Clearance-based Pathfinding and Hierarchical Annotated A* Search". There are additional implementation details to be found there.
You don't have to implement a fixed grid to keep size information, you can also create nodes that have a 'best fit' approach and fit the largest area possible:
No comments:
Post a Comment