Re: [glob2-devel] Todo List For Beta 4

[Stéphane Magnenat]

> 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