M
MishMash
Guest
Hey, I wanted to create this discussion to try and get a primer on ideas for how to best approach pathfinding in an open-world, 2D sandbox platformer. I've hit a bit of a wall with it so far, and am looking for reasonable ideas for how to improve the pathfinding system in general.
To get straight to the point, these are the aims of the system:
- For an NPC to be able to accurately path-find from one location to another. This can include both the following/chasing of another instance, or just moving to a known coordinate location.
- For a pathfinding object to be able to determine if pathing is not possible, or if an existing path has been compromised (as a result of dynamic sandbox interaction, such as placing blocks/destroying blocks). This can be simplified to giving up if a node in the expected path is now obstructed.
- Ability to deal with multiple scenarios within the terrain: Jumping over gaps (given specified size parameters), climbing up ladders, jumping up onto higher ledges, grabbing ledges (This last one is less important, but a stretch goal).
- Ability to path globally across a large world. The player might not see the NPC Travelling, however it would be nice if the player were to move, they might see that NPC in their travels.
- Ability to handle the fact that certain locations might not have been generated at the time and thus disregard paths, unless they are global paths.
- Fast enough that it can be done in real-time for a number of instances simultaneously.
- Paths do not have to be shortest paths, just a reasonable valid path.
I've had a few ideas how to tackle these, however I wanted to get a bit of external opinion from people who may have had experience with similar systems.
Ideas i've had (and tried) so far:
- Split system into "Local" and "Global" paths. Local paths would be the actual node-to-node path that you would see an NPC performing, global paths would be a general mapping from one location to a more distant one in the world. To simplify the overall pathing problem, the NPC would create a local path (which actually follows the terrain) between global path nodes (which could be more arbitrary, such as one node per chunk, or for a point of interest).
- Conventional A* and constructing a grid where each cell is a node and a block seems too slow to do for a world that is constantly changing, so perhaps a scanning algorithm would work better, where each time a path constructed, a grid is generated around that NPC continously testing which regions are validly accessible. (Similar to generating a more localised nodemap, rather than maintaining a world-wide one).
- Global paths would be determined from chunk data rather than pure terrain. (This data-set is far more coarse, and smaller, but not 100% representative of how the world is).
I've attempted a few implementations, the current of which is a crude system where the player generates a path as they walk, the NPC then follows that path. It's okay, but not very robust. I'd love to have the functionality to be able to get an NPC to go anywhere that is feasible for it to go. Having a system like that would make programming certain interactions a dream. (i.e. telling an NPC to walk into a mine, go break some known block and walk back could be a breeze with an advanced pathfinding system).
I appreciate anyone who takes the time to provide suggestions or ideas
P.S. If you need any information about the sort of setup i'm working with feel free to ask! Currently the world data is just a grid of block IDs (This is being upgraded to use a custom dll datastructure, however functionally, it'll be the same as a ds_grid, just less memory and faster).
To get straight to the point, these are the aims of the system:
- For an NPC to be able to accurately path-find from one location to another. This can include both the following/chasing of another instance, or just moving to a known coordinate location.
- For a pathfinding object to be able to determine if pathing is not possible, or if an existing path has been compromised (as a result of dynamic sandbox interaction, such as placing blocks/destroying blocks). This can be simplified to giving up if a node in the expected path is now obstructed.
- Ability to deal with multiple scenarios within the terrain: Jumping over gaps (given specified size parameters), climbing up ladders, jumping up onto higher ledges, grabbing ledges (This last one is less important, but a stretch goal).
- Ability to path globally across a large world. The player might not see the NPC Travelling, however it would be nice if the player were to move, they might see that NPC in their travels.
- Ability to handle the fact that certain locations might not have been generated at the time and thus disregard paths, unless they are global paths.
- Fast enough that it can be done in real-time for a number of instances simultaneously.
- Paths do not have to be shortest paths, just a reasonable valid path.
I've had a few ideas how to tackle these, however I wanted to get a bit of external opinion from people who may have had experience with similar systems.
Ideas i've had (and tried) so far:
- Split system into "Local" and "Global" paths. Local paths would be the actual node-to-node path that you would see an NPC performing, global paths would be a general mapping from one location to a more distant one in the world. To simplify the overall pathing problem, the NPC would create a local path (which actually follows the terrain) between global path nodes (which could be more arbitrary, such as one node per chunk, or for a point of interest).
- Conventional A* and constructing a grid where each cell is a node and a block seems too slow to do for a world that is constantly changing, so perhaps a scanning algorithm would work better, where each time a path constructed, a grid is generated around that NPC continously testing which regions are validly accessible. (Similar to generating a more localised nodemap, rather than maintaining a world-wide one).
- Global paths would be determined from chunk data rather than pure terrain. (This data-set is far more coarse, and smaller, but not 100% representative of how the world is).
I've attempted a few implementations, the current of which is a crude system where the player generates a path as they walk, the NPC then follows that path. It's okay, but not very robust. I'd love to have the functionality to be able to get an NPC to go anywhere that is feasible for it to go. Having a system like that would make programming certain interactions a dream. (i.e. telling an NPC to walk into a mine, go break some known block and walk back could be a breeze with an advanced pathfinding system).
I appreciate anyone who takes the time to provide suggestions or ideas
P.S. If you need any information about the sort of setup i'm working with feel free to ask! Currently the world data is just a grid of block IDs (This is being upgraded to use a custom dll datastructure, however functionally, it'll be the same as a ds_grid, just less memory and faster).