MegaGlest Forum
Archives (read only) => Glest Advanced Engine => General discussion => Topic started by: silnarm on 19 September 2009, 04:12:35
-
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 ;)
(http://i687.photobucket.com/albums/vv231/silnarm/glest/SearchEngine1.png)
(http://i687.photobucket.com/albums/vv231/silnarm/glest/SearchEngine2.png)
(http://i687.photobucket.com/albums/vv231/silnarm/glest/SearchEngine3.png)
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!
-
Perfect! Although I admit, I'd rather see some certain new functions ;) implimented before the pathfinding.
Still, this does look good (I think I understand half of it. I surprised myself by how much easier it was to understand big flowcharts!)
-
templates are fun ;D
I have a good half-dozen uses in mind now, and I'm in no doubt more will materialise.
It's up and running, I wouldn't mind templating on the search domain and node storage as well, but I'll try to resist that urge, for the time being at least.
I was trying to think of a good way to do pathing for harvesting units, my code in 0.2.12 for 'goal based' pathing is rather the kludge, and with a shiny new templated search engine... something better was called for. I still haven't got resource based pathing implemented, but the mechanism by which it will be done is working... an influence map, built by sticking known resource locations in the open set and running a Dijkstra search (A* with zero heuristic) with a custom goal function, which fills in the influence map for us.
Got Gold ?
(http://i687.photobucket.com/albums/vv231/silnarm/glest/first_influence_map.jpg)
-
Ah yes, I like that. BTW: if you're going to post screenshots that are zoomed out, it's best to either temporarily disable fog in the tileset.xml, or to make a separate tileset (ie: render) for picture taking (I prefer the latter, with the evergreen tileset).
Still, I can see the picture clear enough I guess, though any more zoomed out and I might end up just seeing a sea of blue!
I'm curious, if we had good pathfinding implimented, could a unit get though this:
xxxxxxxxxxxxxxxx
D
xxxxxxxxx xxx
x O xxxxxx xxx
x xxxxx xxx
x xxxxx xxx
x xxxxx xxx
Where O is the unit and D is the destination, assuming that it cannot pass through the X's.
-
I'm curious, if we had good pathfinding implimented, could a unit get though this:
xxxxxxxxxxxxxxxx
D
xxxxxxxxx xxx
x O xxxxxx xxx
x xxxxx xxx
x xxxxx xxx
x xxxxx xxx
Where O is the unit and D is the destination, assuming that it cannot pass through the X's.
Where are the 'borders' of your little map? It doesn't look like any path is possible, if there is more 'room' at the bottom such that a path is possible, said path will be found easily.
-
Uh... sorry. Bad drawing. Basically, what I mean to say is, can it loop around this part like this:
xxxxxxxxxxxxxxxx
DOOOOOOOOO
xxxxxxxxx O xxx
x O xxxxxx O xxx
x O xxxxx O xxx
x O xxxxx O xxx
x O xxxxx O xxx
OOOOOOOOOO
That's a bit better. The O's are the path this time.
-
Progress! Yay!
(http://i687.photobucket.com/albums/vv231/silnarm/glest/haa_star.jpg)
-
now what are we seeing here?
-
Hierarchical decomposition of the map :) (oooerr, big words!)
My take on HAA*. Not finsihed, but not far off now. Will also need some tweaking probably... we'll see, and soon :)
-
Ok....
So here's the problem, this is A*
(http://i687.photobucket.com/albums/vv231/silnarm/glest/non_abstract_search.jpg)
All that red is expanded nodes, red is bad. To stop such searches stalling the game, Glest and GAE have used a node limit on the search, if the limit is hit, you pick the node 'closest' the goal and start heading there. This leads to poor paths, and the AI repeatedly getting units stuck on some maps.
So by breaking the map up into 16 by 16 cell 'clusters', recording in the 'borders' (red bits) a 'transition'(green bits) for each field specifying the the maximum clearance and its location, and then computing the path length from a cluster's border's 'transitions' to its other border 'transitions' (the blue bits), we get a smaller graph to search on...
(http://i687.photobucket.com/albums/vv231/silnarm/glest/abstract_map.jpg)
If we get a long search, we can search this much smaller graph first, and use the solution to guide the low level A* unerring to the target via the shortest path (or very close to anyway).
(http://i687.photobucket.com/albums/vv231/silnarm/glest/abstract_search.jpg)
One more picture to come, showing the closed/open nodes after a search guided by the abstract path, but I need to write the code to do that first :P and I need a break now, so I might just kick back on the couch and turn the xbox on 8)
Edit:
The low level search assisted by the abstract path (in need of tweaking)...
(http://i687.photobucket.com/albums/vv231/silnarm/glest/abstract_assisted_search.jpg)
In reality we wont refine the whole path at once, with the abstract path at hand we can calculate as few or as many 'steps' as we please, being able to refine it incrementally is very nice of course, as many long paths will not be used in their entirety anyway.
Will commit a bunch of really ugly code tonight some time, it's going to need a bit of work before I can even get to the polish, but it works :)
-
looks realy nice ;)
-
Maybe try a harder path, I'd like to see how well the GAE pathfinder can do under a harder situation.
-
Well, the point was the reduction in search effort (less red).
But, here you go...
A* 'In the Forest' [With-out a node-limit, Glest/GAE would never calculate a path this long to completion]
(http://i687.photobucket.com/albums/vv231/silnarm/glest/astar_in_the_forest.jpg)
HAA* 'In the Forst'
(http://i687.photobucket.com/albums/vv231/silnarm/glest/haastar_in_the_forest.jpg)
-
I'm glad you provide a lot of visual examples to keep us non-programmers from getting lost in the technobabble. It looks like a huge difference on the map, but are we talking about a noticeable performance difference or just a little tweak?
-
It's a little deceptive, I must admit, as there is no visualisation of the search on the 'abstract map', but it's so much smaller than the low level map that it is searched very quickly (and I haven't actually optimised that part yet, it has some quick and dirty, just work style code in it).
But the performance 'gain' will be hard to measure, Glest uses a node-limited search normally, which stops it from calculating paths like the one above, which can lead to poor paths, and serious problems for the AI on some maps, but keeps performance acceptable, by simply not calculating long paths.
This will be faster, and significantly, yes... and the abstract graph will be (brace yourselves) representationally complete, what that means is, if a path is possible on the low level map, it is possible on the abstraction, A* needs to search every accessible cell to determine if a path is not possible (this is the 'worst case' scenario for A*), we can now do that search on a much smaller abstract graph, if no path is possible on it, no path is possible on the low level map. This is a massive win.
-
awesome! Yea, this is no small win here. For a long time, I've had to compile the path finding code with full optimizations in debug builds just to get it to run at a speed that I can reasonably work with to do tests & debugging. I ran quite a lot of performance analysis last year and found most of my CPU time being spent on path finding ordering a large number of units to move or attack to another location. This also happens when the AI executes a "mass attack" AIRule.
This is cool because you're using some of the ideas that I had previously when talking about enhancing the pathfinder (which means I was actually moving in the right direction, w00t!). The other option, instead of simply breaking the map int 16x16 grids is to use a quadtree (http://en.wikipedia.org/wiki/Quadtree) and keep splitting it until you get nodes that are under some desirable maximum size -- this will keep it working smoothly on maps of varying sizes, but I'm just happy you got this working! :)
-
I learned in my AI unit that if you are going to have a separate process for smoothing the path then it's more efficient to exclude adjacent diagonal tiles. I'm not sure if that's applicable here.
-
I learned in my AI unit that if you are going to have a separate process for smoothing the path then it's more efficient to exclude adjacent diagonal tiles. I'm not sure if that's applicable here.
yes, it's very true and is applicable here. I should do that sometime, paths calculated for units (that invoke hierarchical search) are smoothed after, but this is mainly because the waypoint path the hierarchical search produces can 'pull' paths towards the centre of the clusters.
But the 'octile' (8-way movement) version will need to stay anyway, lots of small paths are calculated (and recalculated) to connect up the transitions between clusters, calculating these on a four-way grid map then smoothing would not be faster than just doing it octile to start with, at least I think... (famous last words? worth a test perhaps...)
But for units refining paths, this would be trivial to change, and would be worth doing (that said, its fast enough for now, as best I'm aware, so I'm not going to do it just yet, maybe a ticket is in order).
-
Hmm not sure if this is the correct place to post this but...
The cartographer in the new release of GAE is mighty slow.
On a medium (128 x 128) map the cartographer takes longer to load than the techtree/factions/game world basically doubling the load time for GAE.
This is worse if it is repeated game (factions already in RAM) in which case it takes about three times longer than the 'standard' loading.
Can maps not be read beforehand and the cartographer info stored in a binary/text file next to the map then simply read rather than calculated?
-
Can maps not be read beforehand and the cartographer info stored in a binary/text file next to the map then simply read rather than calculated?
Good idea, it will still need to happen once for each map, but the results could indeed be written to a file somewhere to avoid having to do it again.
Will do.
-
The map editor might be good to generate it too. That way it can be packaged with the map. If it doesn't exist (or needs updating, don't forget to add version in header) then it can be created on first run.
-
I'm in a state of awe , that was incredible silnarm it leaves me speechless :silence:
-
I did some profiling, and tweaked some things to speed up ClusterMap init, but it turns out the main culprit was actually rendering the loading screen... I was re-rendering after each cluster init, it was actually spending most of the time rendering and/or waiting to swap buffers...
Init map mountains with progress bar : (approx) 4.24 seconds
Init map mountains without progress bar : (approx) 0.52 seconds (after other tweaks, 0.7 before).
So I think just ditching the progress bar will do :)
-
I completely agree , the progress bar is just , in my opinion a luxury , so woot agian silnarm :thumbup:
-
I came across some videos of pathfinding that someone else has done with Glest. http://www.youtube.com/user/ciingames
-
I came across some videos of pathfinding that someone else has done with Glest. http://www.youtube.com/user/ciingames
That's pretty cool. I especially liked the automatic group assignment. I think it would have to be integrated with some kind of indicator on the minimap for it to be really useful, but I don't know of any other games that do this, so it would maybe be a way to make Glest stand out.
-
I had actually seen that some time ago, I did some digging around and discovered it was a university project, unfortunately it was never publicly published (to my knowledge).
Everything is in place now to do these things, generic A*, influence maps, and function objects to build influence maps using the generic A*, it'll largely be a process of 'assembling the pieces'.