[glob2-devel] my experiments on pathfinding and gradients (huge)

[Nuage]

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