Re: [glob2-devel] gradient improvement

[Kai Antweiler]

> Sorry, I did miss it, can you tell me exactly how to fix it ? Or fix it 
> directly.

I attach the patch.
I never used CVS for uploading.  Won't I need developer rights or something
like that?


>> The algorithm depends on the order in which
>> fields that need to be processed are listed.  

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.
In fact that was one of the smart things that I liked about his
algorithm.  


>> But Simon has an idea to partition the map like a chess board into
>> let's say white and black fields.  

After what you explained to me about the cache, I am no longer sure
that this will be beneficial.  I'll try it anyway.
(my mail took about one week till it appeared in the mailing list)

I always thought Simon's algorithm outperformed my own, because it
was designed smarter.
In my own implementations I included the direction in which the
gradient spreads.  For this I needed additional arrays, and this
resulted in worse cache usage.  I tried to limit the number of
operations, but of course this didn't gain anything.


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.)

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.

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

> What about processing the various gradient differently depending on its type ?
> For instance, we have at least 3 types:
> 1- resources gradients
> 2- buildings gradients
Has each building its own gradient?

> 3- forbidden gradients
What do we need forbidden gradients for?
Is this a gradient which will be initialized from every free
non-forbidden field?
So that a glob on a forbidden field can find a way out.


> Theirs statical behaviors are different, and there is probably some speed to 
> be gained out of it.
> If you think it's useful, I can add structure in the code, so you can access 
> this information. Then I'll let you try to take this into account.

Might be useful.
But I must know more of their differences to exploit them.

Map.cpp.patch
Description: Patch against Map.cpp correcting simons idea

-- 
Kai Antweiler