A* finds an optimal path, but it has a high space complexity because it looks at a large amount of the potential space. To keep things performant, different strategies can be used to reduce the potential space. Reducing the explore-able space is rather crucial for having a large number of agents running around.
For a large world, going to needs zones. Paths will need to navigate from one zone to another. When a new zone is entered, a new path will need to be calculated.
Todo
[ ] Create a simulation that flushes out unreachable geometry.
[ ] Determine the size of a zone (e.g. 40 x 40 cells). Look at Game Programming Gems again.
[ ] Create a sim that calculates a path across multiple zones.
Possible Strategies
Mark cells as unreachable. Different algorithms can do this or they can be flagged by a designer.
Algorithms: Flood Fill, Procedurally generated geometry could flag things (trees, rocks, etc.). Others?
Potentially use this to introduce the concept of a navigation mesh. There could be a terrain the has a rich set of data for various aspects of the simulation, but then an algorithm (flood fill, scan line) could be used to select the traversable cells and create a lighter data structure for just navigation.
A* finds an optimal path, but it has a high space complexity because it looks at a large amount of the potential space. To keep things performant, different strategies can be used to reduce the potential space. Reducing the explore-able space is rather crucial for having a large number of agents running around.
For a large world, going to needs zones. Paths will need to navigate from one zone to another. When a new zone is entered, a new path will need to be calculated.
Todo
Possible Strategies
Potentially use this to introduce the concept of a navigation mesh. There could be a terrain the has a rich set of data for various aspects of the simulation, but then an algorithm (flood fill, scan line) could be used to select the traversable cells and create a lighter data structure for just navigation.