Re: [glob2-devel] gradient improvement

[Bradley Arsenault]

On 3/9/06, Kai Antweiler <address@hidden> wrote:
> Hi,
>
> I have thought about how we could improve the gradient algorithm.
> Since our geometry is based on the sup-norm I guessed that the
> propagation of the gradient tends to occur in squares or rectangles.
> If we take for example a single isolated resources like a fruit tree
> on an open area, we soon get 2 horizontle and 2 vertical lines of
> "active" areas running in different directions.
>
> 253 253 253 253 253
> 253 254 254 254 253
> 253 254 255 254 253        The resource is in the middle (255)
> 253 254 254 254 253
> 253 253 253 253 253
>
> Maybe that is exploitable.
>
> Considering the general case:
> We could that split the general case into two cases:
> If an area is active and is not a resource, then there has to be
> a neighbour with a higher gradient. If we consider the symmetry
> there are only two cases:
>
> _|_|_       _| |_
> _|0|_  and  _|0|_      0 is active, * has higher gradient
>  |*|        *| |
>
>
> But then we must have:
>
> _|_|_     _|_|_
> .|0|.     .|0|_        . already has current gradient value or higher
> .|*|.     *|.|         or is an obstacle
>
> If we would pass the direction (that is its position relative its "father")
> every time a new area is marked to become active (when the next gradient
> level will be processed), then we would just have to check for
> 3 (resp. 5) neighbours instead of 8.
>
> I don't know if the special treatment for these two cases would cause a
> noticable speedup since checking the 8 neighbours looks pretty fast to me.
> But I will consider the "line-front" case further - some day.
>
>
>
> While thinking about the first part of this mail I recognized an easy way
> to improve Simons implementation.
>
> http://lists.gnu.org/archive/html/glob2-devel/2005-12/msg00178.html
>
> Simon wrote:
> > This leads me to an interesting idea about the gradient
> > computations. In updateGradientSmall you don't always have to add
> > every neighbour of a square into the listedAddr list. If you process
> > a square and for example the squares on the upper left and the lower
> > left aren't obstacles you can just update the square on the left,
> > without having to add it into the list. Every square which could be
> > reached from there can also be reached from one of the other two
> > squares.
>
>
>
> Map.cpp line 2267:  if (side > 0 && side < g)
>
> This tests for obstacles and already processed areas.
> But these two cases should be considered separately.
> Because most of the time we can see the gradient propagation
> locally as a horizontal or vertical line.
>
> .|.|_|_|_|_|_      Here the gradient is spreading up from below.
> :|:|0|.|.|.|.      The lowest line is already processed as are
> *|*|*|*|*|*|*      the first two fields on the left of 0
>
> The field above the 0 is empty because diagonal neighbours are
> marked to be processed be before the others.
>
> _|_|_|_|_|_|_
> .|_|0|_|_|_|_      * marks 0 before 0's immediate left neighbour.
>  |*| | | | |
>
> As you can see Simons version can't optimize in this frequently
> occuring situation, because there are no two edges with gradient < g.
> But Simons idea works never the less.
>
> I changed just that and ran 30 games on the map WaterInTheDesert using the
> standard version (old) Simons version (simon) and the modified one (new).
>
>
> The jointed gprof results:
>
>   %   cumulative   self              self     total
>  time   seconds   seconds    calls  ms/call  ms/call  name
>
>  ------------------------------------- old 
> ------------------------------------
>  62.98      3.42     3.42     1011     3.38     3.38  void 
> Map::updateGlobalGradient
>  61.38      3.29     3.29     1011     3.25     3.25  void 
> Map::updateGlobalGradient
>  60.71      3.23     3.23     1011     3.19     3.19  void 
> Map::updateGlobalGradient
>  66.73      3.59     3.59     1011     3.55     3.55  void 
> Map::updateGlobalGradient
>  64.01      3.45     3.45     1011     3.41     3.41  void 
> Map::updateGlobalGradient
>  69.57      3.75     3.75     1011     3.71     3.71  void 
> Map::updateGlobalGradient
>  65.92      3.54     3.54     1011     3.50     3.50  void 
> Map::updateGlobalGradient
>  63.69      3.42     3.42     1011     3.38     3.38  void 
> Map::updateGlobalGradient
>  65.41      3.46     3.46     1011     3.42     3.42  void 
> Map::updateGlobalGradient
>
> ------------------------------------ simon 
> ------------------------------------
>  65.45      3.60     3.60     1011     3.56     3.56  void 
> Map::updateGlobalGradient
>  67.40      3.70     3.70     1011     3.66     3.66  void 
> Map::updateGlobalGradient
>  68.12      3.76     3.76     1011     3.72     3.72  void 
> Map::updateGlobalGradient
>  66.07      3.70     3.70     1011     3.66     3.66  void 
> Map::updateGlobalGradient
>  64.01      3.61     3.61     1011     3.57     3.57  void 
> Map::updateGlobalGradient
>  61.34      3.38     3.38     1011     3.34     3.34  void 
> Map::updateGlobalGradient
>  63.07      3.57     3.57     1011     3.53     3.53  void 
> Map::updateGlobalGradient
>  65.03      3.70     3.70     1011     3.66     3.66  void 
> Map::updateGlobalGradient
>  65.21      3.58     3.58     1011     3.54     3.54  void 
> Map::updateGlobalGradient
>
> ---------------------------------------- new 
> ----------------------------------
>  52.09      1.99     1.99     1011     1.97     1.97  void 
> Map::updateGlobalGradient
>  51.57      1.97     1.97     1011     1.95     1.95  void 
> Map::updateGlobalGradient
>  54.57      2.03     2.03     1011     2.01     2.01  void 
> Map::updateGlobalGradient
>  52.32      2.03     2.03     1011     2.01     2.01  void 
> Map::updateGlobalGradient
>  52.71      2.04     2.04     1011     2.02     2.02  void 
> Map::updateGlobalGradient
>  52.08      2.00     2.00     1011     1.98     1.98  void 
> Map::updateGlobalGradient
>  53.42      2.03     2.03     1011     2.01     2.01  void 
> Map::updateGlobalGradient
>  52.24      1.98     1.98     1011     1.96     1.96  void 
> Map::updateGlobalGradient
>  52.31      2.04     2.04     1011     2.02     2.02  void 
> Map::updateGlobalGradient
>
>
> I don't know why Simons implementation reached such good values in his test,
> but I guess it is because he messured updateGlobalGradientSmall.
> Near there sources the gradient front might often differ from a line.
> Or the ratio of edge-points to inner-line-points is higher.
>
> Patch for the Map.cpp (cvs) is attached.
> I tried to test on other maps but glob2 is not stable on my computer.
> Maybe someone else could do it?
>
>
> I checked if my changes could result in wrong gradients:
> If for example the upper left and upper right field already have gradient 
> values
> but are not marked to become active:  the change would cause the upper field 
> to
> not get active and so the upper field of the upper field might not get its 
> legitimate
> value.
>
> But this is not so, because for the upper right (call it A) to have a 
> gradient value
> and not getting actived would mean that it is not a resource and that there 
> has to be
> a nondiagonal neighbour with two diagonal neighbours next to A.
>
> _|_|_|_
> .|_|.|*
>  |0| |
>
> _|_|.|_
> .|_|A|*
>  |0|.|
>
> For the upper neighbour (B) of A to be inactivatable there must be an 
> nondiagonal neighbour ...
> leading to either:
>
> _|_|B|*
> .|_|A|*
>  |0|.|
>
> or
>
> _|_|*|_
> _|.|B|.
> .|_|A|*
>  |0|.|
>
> In the first case A or B must be active at some time, since both * were 
> active.
> In the second case we no longer have to worry about the field above the field 
> above 0.
>
>
> I hope this is comprehensible.
>
>
> ps: I like Simons algorithm
>
>
>
>
>
> --
> Kai Antweiler
>
>
> _______________________________________________
> glob2-devel mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/glob2-devel
>
>
>
>


I guess no-one is paying attention, I'll look into it, thanks allot
for the help.