Re: [glob2-devel] Optimization suggestions (Map::updateLocalGradient())

[Kai Antweiler]

> 2) Alternatively, we can do a continuous update system, rather than a
> complete refresh. Basically, we keep track of changes on the map, where a
> change is from a path obstacle to a non obstacle, or vice versa.
>
>  a) for each obstacle->non obstacle, at that position, take the value of the
> smallest neighbor, then propagate that value like the normal algorithm does,
> except this algorithm only propagates into cells that will change with this
> prorogation. This means that, most of the time, the algorithm will quit
> quickly.
>
> b) for each non obstacle->obstacle, mark each neighbor that has a higher
> value than the cell had before it changed as 0. Propagate into these cells,
> doing the same thing, propagating into each neighbor that has a higher
> value, and leaving behind the new values of 0. This is basically marking the
> region that is affected by the new obstacle. Each neighbor that had an equal
> or lower value was marked as a source and added to a list (or set, so
> duplicates don't occur). After this portion of the algorithm exits, the next
> portion fills in the damaged portion of the map by propagating from the
> sources like a normal gradient algorithm would.
>
> These two updates don't have to be done in parallel, one can do a, then b or
> vice versa it won't affect the result. The danger here is that the same
> value may be touched many times, but in reality, the glob2 world doesn't
> change much between updates, so may improve performance.


That is similar to what I planned last year.  Some of this is in our
bug tracker.
You forgot the resource->noresource and noresource->resource cases.
And you mixed up our gradients, high gradient is near, low gradient is far away.
You don't need to mark the areas in your b case which need to be updated in an
extra data structure.  Simply set them to 1 in the gradient map and
start the update
algorithm with their borders when they all have been found.

But you will have to modify that update algorithm further.  You have
to take care
that you do the first step (your marking) beginning with the lowest
values and considering
all changed fields with the same value at the same time.

Also be careful with the init.
And be careful anywhere else too.  Messing around with the gradient
makes globs tipsy.

Good luck!
-- 
Kai Antweiler