glob2-devel
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [glob2-devel] gradient improvement


From: Kai Antweiler
Subject: Re: [glob2-devel] gradient improvement
Date: Wed, 22 Mar 2006 20:01:16 +0100
User-agent: Gnus/5.1002 (Gnus v5.10.2) XEmacs/21.4 (Jumbo Shrimp, linux)

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


-- 
Kai Antweiler





reply via email to

[Prev in Thread] Current Thread [Next in Thread]