Re: [glob2-devel] gradient improvement

[Simon Schuler]

> >> I forgot that Simon's algorithm already "repairs" the local order
> >> in which the fields will be listed by inserting the diagonal
> >> neighbours before the others.
> >
> > Yes, that's why I only separated even and odd fields at the
> > beginning. But once a line is in a bad order it won't be repaired.
> > (only the start of it) The bad part remains at the end of the line.
> 
> Are you sure?  I don't see this.  
> If I draw a horizontal line, no matter how distorted the order is,
> if I have enough steps of undisturbed propagation the line will be
> in a beneficial order.

If the line grows, the end remains in bad order.
Let me show you what I mean with some ascii art wich shows the order in
which a line is processed
      1 2 3 4           1. generation line
    1 3 2 4 5 6         2. generation
  1 3 2 5 4 6 7 8       3. 
1 3 2 5 4 7 6 8 9 10    4.
The last 3 elements remain in bad order.
As long as it's only 3 elements it doesn't hurt, but if you have a 20
fields long line of ressources the last 19 fields remain in bad order.
But perhaps such long lines don't appear often and don't hurt that much.
 
> >> But I have two ideas which might use the cache better:
> >> 
> >> 1. When initializing the array listedAddr, omit the fields
> >> which have a right and left neighbour of same or higher gradient
> >> value, if these will be put in the list.  This uses only
> >> information which just was processed or will be in the next step.
> >> Since resources tend to cluster, also checking for upper and lower
> >> values wouldn't gain much.
> >> (The idea is that every neighbour of the omited field, is also
> >> neighbouring one of the other two fields.)
> > I don't expect this to make a very big difference because it just
> > removes some fields at the start.
> 
> At least for the forbidden gradient this should make a difference,
> since there most fields are resources.
> 
Oh, sorry, I forgot about the forbidden gradient. I think there it would
really make a big difference. Perhaps for maps with lots of ressources
it would also make a remarkable difference.
In the forbidden gradient you could even just list the fields at the 
edge of the forbidden zone...
something like this:
if (field is forbidden)
{
        if (there is a free field next to the current one)
        {
                set gradient to 254
                add the field to the list
        }
        else
                set gradient to 1
}
else if (field is free)
        set gradient to 255

because you usually have more free fields than forbidden ones that
could be a speedup. It would prevent more fields from being listed than
your suggestion, but it would be slightly more complex.

> 
> >> 2. In updateGlobalGradient:  check if the next field in listedAddr
> >> is my right neighbour.  If it is, check if the next one is its
> >> right reighbour. And so on ...
> >> And then process that whole part of the line.
> >> You also would have to check, if the right neighbour has the same
> >> gradient value as you.
> >
> > This is close to another idea I had. It was based on the observation
> > that you only have horizontal and vertical wave fronts. So my other
> > algorithm stores the wave fronts instead of fields. It has the
> > advantage that you don't have to check the fields around the one you
> > are currently updating. The next generation wave fronts are derived
> > from the obstacles in the current wave front: (obstacles more than 2
> > fields wide cause the wave to split and there is breaking at the
> > ends of the wavefront)
> > I've tried to implement this algorithm. It resulted in very ugly
> > code, but it produced correct gradients. The speedup of this
> > algorithm compared to the simple one was between 0% and 40%,
> > depending on the map. (compiled with -O3, measured with gprof)
> > But it is far too complicated to be useful.
> 
> I guess the way I proposed will be nice and easy to implement.
It's much easier than my algorithm... so if it works it seems nice.
> Of course vertical wave fronts are not regarded at all.
> Would your implementation have been ugly, if you would have omitted
> vertical wave fronts?
The whole concept of the algorithm was to have only wave fronts and no
single fields... The code for vertical waves was the same as for
horizontal waves. Just some changed variables. It would have been
uglier to have another system for vertical waves.
I didn't find a simple way to initialize the wave fronts, so I just
started a wave front in each direction from each ressource field... The
wave fronts grow themselves. It didn't actively search lines like your
suggested optimization. Like this vertical wave fronts are really not
different from horizontal ones.
> 
> 
> >> Why is it possible to have so different gradient values in field
> >> which are in listedAddr?
> >> I would expect only two values:
> >> the present one and the present one minus one
> > erm, I'd expect that too.
> 
> I once changed the:
> 
> if (g <= 2)
>    continue;
> 
> to:
> 
> if (g <= 2)
>    return;
> 
> and got different gradients.
> Maybe I had changed some other thing too.
> (but I don't think so.)
I don't know about all the places which initialize a gradient, but if
gradients are really initiallized with different values, I think this
is a bug. (listedAddr would no more be guaranteed to be big enough
because fields could be listed more than once)