I'm at it again... A* can be very addictive.
I've been reading some books on game AI, and picked up a few ideas for interesting use of the A* algorithm, for things other than finding paths. So we need a more generic A*, not something I was all that keen on, because I'm not willing to use polymorphism in the path finder. So I've resorted to templates, everything can be inlined, there'll still be code bloat in the generated code, but not in the source
So the ultimate idea is that there will be
"One A*, to rule them all". We get our desired search by calling the appropriately templated 'aStar'.
So, the PathFinder class is on the way out, there will be a PathManager in it's place, which will serve as a 'smart interface' to the SearchEngine. The PathManager will take requests for paths from individual units, and groups of units with the same destination. The 'groups of units with the same destination' is they key here, the path finder is only a problem when it gets swamped with requests, when deos this happen? When lots of units need paths at the same time. When does this happen? When the player commands a large group of units (which is to a single destination) or when an AI launches a 'massive attack' (which again, is to a single destination).
Single search requests will be processed with a node limited A* using the shared NodePool and team's annotated map. If the search completes, all good and well. If the node limit is reached, the best heuristic node is plucked from the closed set, and a 'partial' path is provided (this is essentially what happens currently), the PathManager then queues the search to be performed 'in full' using one of the NodeMaps. As a partial path was returned, this search is not high priority, when the PathManager deems it can spare one of the NodeMaps and has some cycles to kill, it runs the search in full (possibly over multiple frames) and
provides the complete path to the unit.
In David Silver's paper on Cooperative A*, he describes a 'Reverse Resumable A*', he uses it for searches in the abstract space, but I think we can use the same idea at the 'low level', slightly modified.
So when we get a group of units all going to the same place, we grab a NodeMap, and run the first search, in reverse! One unit, one path. Next. We now have a NodeMap full of data, we DO NOT 'clear' it for the next search, the data is still good! Normally, when we close a node in A*, we have found the shortest path from the start location to that node. This is of no use to us if we run the search in the forward direction, but by swapping the start/destination, we now have a NodePool with closed nodes that all point their way back to the actual destination.
For the next search, we do this: check if the start location is in the closed set, if so we already have the path, we just need to pull it out of the closed set. If not, we run over the open set, recalculating the heuristics to the new 'goal' location (the 'actual' start
) and re-sort it, and then resume running the A* algoirthm. This will 'branch' off at the most appropriate location from the open set (the previous search's frontier) until it gets the best path to the new unit, adding more nodes to the closed set (full of good data). Next!
The open set will grow too unfortunately, depending on how spread out the units are, but the heuristic function is small and fast, and inlined thanks to the templating, so recalculating them shouldn't prove too time consuming, fingers crossed
We'll keep one annotated map per team, these are small and cheap to update anyway, so we can update them based on what that team knows, giving us a proper fog-of-war effect, (ie, you wont see new buildings in fogged area, until you 're-sight' the area). This also prevents us from inadvertently exploiting information not know by that team, which would be a concern if these searches were performed on the 'master' annotated map.
The NodePool is a limited array of nodes, used for the 'bread and butter' searches, a NodeMap is an array of nodes the same size as the map, and its nodes therefore 'map' directly to cells on the map. These take a bit of memory, but we will need more than one, probably not one per player like I suggest in those pictures though... These arrays are for the hard case searches that couldn't be resolved with the node limited version, and for the group searches. There is no node limit, the search will find a path or fail, indicating there is no path. Thus it must be 'interruptable' and run over multiple frames if needs be, and hence the need to have a few lying about.
Ok, that's a lot of explanation, and I'm not sure how good it is! Any questions, fire away!
