Hello Everybody. Sorry for being away. I would like to describle some of my experiences with the pathfinding with gradients.
*gradients* The way you describe gradients is correct, so I think you got the idea. Trying to optimise gradients has been a concern to me for a very long time and I already spent allot of time into it. I think there are some ways to fo better, but it will be quite complex. *localy-update based gradients* Actualy I did tried to make space-scale localy-update based system to save computation time. The problem is that it leads to non-obvious problems and tricks. If you don't update all the map, one problem is that you sometimes will have to solve the "meeting places problem". Those are the place were from there two differents way to another place. The only way to decently solve them is to update all the gradient. If you ignore these, the units will have an behaviours which can be quite bad. How much sad will be a player if an unit walk all around an obstacle if there is a new shortcut right into it ? Anyway, if you want to go trough this idea, here are the other experiments I made. With some work on the way the gradient is processed, you can improve the behaviour of an unit. The furthest you will read the gradient, the better it will be, but the slower it will be. But this willnever completely solve the problem, and it will always end up by locked units, walking-in-circle, or they will use the wrong way. Next idea is to detect when there is a "meeting place problem", and update all the gradient. If we do so, then the speed improvement is not great at all. The reason is that if there is no "meeting place" problem, then, by all chances, the update, even local, is not needed. To explain why, I have to add some more explaination. We can split any map alteration, into two types. Either one obstacle is added, or an obstacle is removed. If the obstacle is added, and the shape is convex, then the gradient need no update. The shape is the shape of the added obstacle, plus all things it does touch. If the shape is concave, a gradient update is needed, only if the target is inside the concave part. If the obstacle is removed, then a gradient update is needed if this creates a shortcut to the target. The size of the update is at least as big as the size of the obstacle. Currently, when any obstacle is removed, all big gradients have to be recomputed. Now I think about it, there may by a way to improve speed here. But I don't know if the computation time to update only the area worth it. Overall, the localy-update based gradients system where not good enugh and not that fast. One reason is that you don't really know when to make full updates to prevent bad cases to happen. *optimising the constrution of building* Don't forget that the units use the gradient information to find out which is most efficient building to build. Those calls take more computation time than the pathfinding. For each unit, multipiled by each bulding it tries, multipiled by all required ressource, does generate a path-finding-like request. *current choice* The current way to save time is to save computation time by on a time-space based scale. So I try to use gradient re-use, and avoid gradient recomputation as much as possible. This is possible, precisely because the gradient computation itself is known to be perfect. I spent allot of time to find the fastest way to compute perfect gradient. *current ressources gradients* The number of ressources gradients is low, compair to the number of building gradients. Detecting the changes of the obstacles from the building can be done on each event. But it is impossible to do it for the ressources, it happen much to often, and everywhere in the map. And from the gameplay point of view, the importance of all the ressources gradients is as imporant as all the building gradients. Computation time spikes can alter gameplay too. For this reason, the ressources gradients are simply recomputed time to time. Actualy, each tick, one ressource gradient is recomputed. *current building gradients* I can't remember the exact way all this is computed, but here is the idea. Each building have four gradients. Two local, the size is fixed of 32x32 cases, and two global of the size of the map. One local and one global are used for non-swimming units. One local and one global are used for swimming units. The global gradients do not always exist, it can be memory freed if not used. By default, the global gradients do not exists. The idea is to compute gradient only at request, and save compuation time this way. As much as possible, the local gradient is used, and if needed, recomputed. This local gradient compuation is really fast, so there are good chances for it to be recomputed if there is a chance as it can be usefull. If the unit is too far, then it will use the global gradient, without recomputing it. If the unit detects it is blocked, then it requests a global gradient update. In other words: Expect the gradient to be exact, but if you meet any inconsistency, recompute it. This allows almost cost-less detection of the gradient update need. There are a few stats about the gradients reuse at the end of Map.log (Take a look at yours). If I read my last one, I can see that the pathfinding for building is split this way: _55.66% of the calls a local gradient is used. _89.66% of the calls it use a global gradient, it can re-use it. __1.44% of the calls end up in a global gradient computation (of which 12.97% for the first time) Local gradient computation is very fast. That mean that excluding useless full-computation is about 70 times faster than recomputing it all the time. This is possible because the full gradient computation is know to find out the exact result. Other system I did explore would never reach such a speed-up. *summary* Fact is that I started with the same ideas of making local-updates, and playing with funny things like feromons. I tried some ways and it would not work, like explained. This does *not* mean that I tried all ways to make local-updates, but I fairly think it will be less efficient. Summary for time-based optimisation is: - expensive cost of full update. - cost-less detection when recomputation is needed. - very efficient exclusion of recomputation needs. Summary for space-based optimisation is: - low cost of update. - significant computation costs to detect when recomputation is needed. - average efficency of the exclusion of recomputation needs. *conclusion* What I think can be done for improvement: - When a building is erased, and the full-shape is concave, just make a local update. Still this is quite hard and I don't know if it really worth. - Try to optimise the global gradient update. But I did work so much on this one that I don't know if it is really possible. I did use the "-nox" flag to diable the graphics and wait for the end of the game. This allows deterministic behaviour of the engine for benchmarking. Then take a look into the cpu usage stats of Engine.log. - Report the end of your Map.log if you think you are experiencing slow game because of the gradients. Maybe the way you play makes a diffrences. Still, this is a funny and interresting field. So don't refrain from suggesting new idea! I didn't drew ultra-scientific experiments, so it still could be wrong. And you'll have the fun to blame me if you find a better way :) Luc-Olivier _______________________________________________ glob2-devel mailing list [email protected] http://lists.nongnu.org/mailman/listinfo/glob2-devel
