> I a while back wrote a thread which discussed ways a gradient could be > updated, rather than fully recomputed. This could save magnitudes of time > alone. I also suggested several other gradient speed ups.
Ok, I've read it. http://lists.gnu.org/archive/html/glob2-devel/2008-03/msg00026.html I agree for improving the speed of obstacle lookup using a stack (idea #1). Just keep in mind that it should be per team and per swim/non-swim ability. Maybe the increase in memory overhead is too big; but maybe your solution still improves the performance. For idea #2 I fail to see the real improvement wrt the actual gradient, that also only recomputes cases that need to by bookkeeping the propagation front. Maybe the subtleties you propose to add will help, but I'm not sure. For idea #3 yes in theory, but the cost of the heuristic to estimate which unit is the farthest would probably be bigger than the gain of computing less gradient, knowing that the gradient is in cache and that the units are everywhere in the memory. In fact, if you optimize obstacles lookup using idea #1 in a preprocessing phase for all gradients, this idea would probably improve event less the performances because of cache trash. Idea #4 (2x2 gradient case instead of 1x1) is really interesting and could fix the 1 case large passage problem. The question there is wether the players would be frustrated by the resulting sub-optimality of the gradients. There would also be choices on how to consider a partially-filled 2x2 element that would be non-trivial to make. I like idea #5, but I'm afraid that with 4x4 gradient the suboptimality in behaviour is a problem for the player. In general, I think that we should not make the pathfinding sub-efficient from a player pov, even if it makes it faster. We had sub-efficient gradient a long time ago and it was very frustrating from a player point of view. For the others optimizations, why not; but I'm not sure it would boost the performances as much as you hope, yet there is no way to know for sure before testing. Have a nice day, Steph -- http://stephane.magnenat.net _______________________________________________ glob2-devel mailing list [email protected] http://lists.nongnu.org/mailman/listinfo/glob2-devel
