Re: [glob2-devel] gradient improvement

[Nuage]

Kai Antweiler wrote:
>>Thanks for the ideas. I did applied the patch, can you check if they are
>>correct, plz. Compile one of them by uncommenting the #define you want: (I 
>>know
>>the name are only the names of the guy who added the new idea, give me a new
>>name if you want something politically correct).
> 
> 
> It looks correct, except for the "else if" part Simon referred to in this
> thread.

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


>   The names shouldn't be an issue since they won't stay long.
> Simon works on an improvement which will outperform all others soon. :-)
> 
> 
> 
>>In this test, the new algos (Simon+Kai) are actually slower. If I remember 
>>well,
>>it was about 1% faster in 128x128 maps. My conclusion is that the complexity
>>added by the simon/kai algo is too high compair to the speed gain.
> 
> 
> I guess that this performance loss does not come from the increased
> complexity of large maps.

I was just talking about the algorithm complexity.

> The algorithm depends on the order in which
> fields that need to be processed are listed.  When this sequence
> becomes unfavorable, due to obstacles the effect on large maps will be
> bigger.  (Since the ratio of the distances "resource to obstacle" and
> "obstacle to the last field that suffers from the unfavorable order"
> will be worse.)  That is at least my working hypothesis.
> 
> But Simon has an idea to partition the map like a chess board into
> let's say white and black fields.  Depending on their "color" the
> fields would be processed by different loops (I think?) using two
> different lists (each half the size?).
> This way a diagonal spreading of gradients can be resumed after an
> obstacle causes an unfavorable step.  I expect this to become the uber
> gradient calculation algorithm.

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
3- forbidden gradients
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.

Thanks again for the work and ideas!

Nuage