[glob2-devel] gradient improvement

[Kai Antweiler]

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

Map.cpp.patch
Description: Patch for Map.cpp

-- 
Kai Antweiler