Path Finding Design Documentation
The purpose of this article is to discuss the Pathfinding mechanisms. This article contains details of both an implementation and some proposals for an improved system.
The reasoning behind a pathfinder system is as follows:
- Multi-purpose, agents can use it to navigate their environment for example.
- Provides a generic graph-searching mechanism which is expandable, many different types of graph search available.
- To prevent the system from hanging during long searches.
- To encapsulate as much of the pathfinding code as possible within a small area.
To begin with a little background on how Pathfinding is intended to work within FIFE. I think it is a little over the top to talk about this solution in terms layers, but I find it a useful way to separate areas of responsibility and code. So I'm going to talk about this solution in terms three layers: the Route Service Layer, Map Adapter Layer and Generic Solver Layer.
Roughly speaking each layer will correspond to a directory (package) of closely coupled classes (files) that loosely depend on the layer below, the following diagram outlines the responsibility for each layer.
Here I will focus primarily on the Solver layer. The PathFinding system itself is split between several different areas, as seen below.
The above diagram is a simplified overview of the system, although the system in reality isn't that much more complex. I will now give a brief explanation of each of the different parts involved.
Instances are created and maintained by the engine. The path-finder has no knowledge or influence of/on the instances but nonetheless requires instances to provide it with information and cause it to update. The Instances use the paths generated by the pather to move themselves, this means that the pather can have a limited knowledge of the map's structure and still do it's job. Every instance contains a pointer to the same pather.
The Pather in the diagram acts as an interface to more specialized pathers (see: Linear Pather and Real Time Pather). The Pather performs some basic functionality off the bat. This includes formulating search spaces (see Search Spaces) and maintaining Searches (see Searches) in a map.
Real Time Pather & Linear Pather
As mentioned above, real time pather and linear pather are specializations of the pather interface.
In the path-finding session a "Search" represents a session. The pather keeps track of all different searches using the session_id. When an instance requests a search to be either created or updated that search is either given or referenced by a search id that will remain the same through the searches life span. Search represents a hierarchy. The idea is to have different search types derive from the same base class.
Around 80% done. The pather is in a state at which it should be able to locate paths in a static-environment (see proposals for more information) however it requires bug testing. There are still some questions over how the implementation of the real-time pather will work with the current Instance code, since the real-time pather can return empty paths while it's still ticking over.
Q: Will the pather be geared towards RPG's (i.e. Fallout) meaning purely tile based movement or an RTS which has weak tile based movement, the tiles present a rough way of moving a unit from A to B but the unit can deviate from it's route, it isn't "on rails" in other words? This could potentially mean that units would have to carry collision information, such as a sphere or box that identifies the boundries on the instance. This could be helpful for cross layer movement to since the collision information is detached from the layer.
Q: User-Feedback ( new )
The agents must behave logic at any time. Apart from any background algorithms, the user needs always to be confirmed with the agents moving. If you have a river with only one bridge and this bridge gets blocked, what will happen? Will the agent stop? Or proceed until the blocked object is in sight / direct-contact ? Or just "silently" choose an alternative path ? Which pathfinding output-values need to be transported to the GUI ? -> Showing the path at the map/minimap ?
Currently the pathfinding system contains no checking for blocked cells and only operates on a static environment (ironic for something called a real-time pather I know :)). To change this is a fairly big task which will be tackled after the next release. The system needs some way of marking cells as being blocked. At the moment this is difficult due to how cells are being represented (not individually). The solution could be something as simple as a boolean lookup table held by a layer, or something else a bit more complex. The system needs to take into accout obstacles on one layer that may be placed according to a different cellgrid structure interfering with cells on the movement layer. This will probably require some sort of masking of objects accross several different layers to determine which cells in other layers they interfere with.
Dynamic (moving) blockers are also something that needs to be accounted for. My suggestion here is to take the dynamic aspect out of the pathfinders hands all-to-gether and leave that in the instance's hands (since it is the instance responsible for the actual movement). These are three ways I suggest of approaching the problem:
What I'm calling the move-block-replan method involves asking the pather to create a route to the solution (target cell, avoiding blocking cells obviously). Then when the instance is actually moving according to that route it looks at the cell it's about to move into and determines if it's blocked or not. If it isn't blocked the movement is valid, if it is that means the state of the map has changed since the path was discovered. The instance will then throw out the current solution and ask the path-planner to re plan to the target again. The downside to this method is that it isn't particularly efficient. The upside is that the system will always attempt to follow the best path to the destination.
The move-block-patch method is similar to the move block replan method except when the instance attempts to move into a blocked cell the whole path isn't thrown out, instead it is "patched". This is the same as the above method up until the point at which a newly blocked cell is found. Instead of throwing away the entire path this method would require the instance to search through the remaining cells in the path until it found the next cell that isn't blocked. The instance would then ask the path-planner to generate a path from the instance's current location to the next unblocked cell on it's path, throwing away all blocked cells in between. Once the patch path is returned the remnants of the old path is added onto the end of the patch path and the instance can continue along its route. The upside is that it's much more efficient than throwing away the entire solution like in the latter method, since the next free node will almost always be a maximum of 3 or 4 steps away. The downside is the additional logic that we would have to imbue the instances with and also that the entire path may not always be the best one.
This solution will leave it up to the pather to avoid dynamic obstacles. This is the most difficult solution to implement because it will require a true real-time algorithm. While this is possible real-time algorithms are often much more memory intensive than their offline counter-parts, especially if the algorithm has any learning capabilities. Incorrectly designed real-time algorithms can also cause agents to get stuck in infinite loops. One alternative is to have an algorithm which plans several steps into the future but not the whole solution and then returns part of the path, while the agent is following this part of the path the algorithm could be working on the next part of the solution, which could simply be "added" onto the end of the old solution. This could be combined with one of the above methods to create possibly the most efficient solution to the dynamic environment problem, but also the most difficult to implement and understand.
- While investigating improvements to pathfinding, here are things I came across as useful. -Cryptomancer