[glob2-devel] hoping for removal of hidden forbidden areas (was: Optimization suggestions (Map::updateLocalGradient()))

[Joe Wells]

"Kai Antweiler" <address@hidden> writes:

>> > 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.
>
> I guess this itself would be the most significant advance.  When no changes
> happen, we don't need to update the gradient at all.  This would even work
> with current gradient algorithms.
> By the way: hidden forbidden areas might hit performance really bad, because
> they mix the fast changing glob movement with the slow changing landscape.

I think hidden forbidden areas should be replaced by congestion
penalties.  Basically, I think the estimated movement cost of a cell
should not always be 1 but should depend on a recent sampling of
usage.  Cells that tend to always have a worker/warrior in them should
have a cost of 2 (or maybe even 3) and only cells that are usually
empty should have a cost of 1.

(It might even be better to also adjust the cost depending on the
cell's terrain type (grass/sand vs. water).  Doing that in a sensible
way however would require more than 255 distinct values, so I think
that is a low priority thing that maybe someone can try someday.  But
we will need more distinct values anyway if we ever want large 512x512
maps to work well.)

In the meantime, until hidden forbidden areas are removed, I think the
hidden forbidden areas should not be hidden, because they are a source
of hard-to-diagnose bugs and cause player confusion.

-- 
Joe

> Right now as we use highly suboptimal gradient computation this doesn't matter
> much.  But it might ruin our improvement.  Especially since the
> proposed algorithm
> has a two times as high worst case runtime as the current algorithm.
> Hidden forbidden areas mix two things that don't belong together.
>
> I wanted to do statistics on the ratio of turns in which changes occur to the
> total number of turns, but I shied away from glob2 code.
> With this we could estimate the effect of the optimization, which in my 
> opinion
> will be large.
> -- 
> Kai Antweiler