Re: [glob2-devel] Optimization suggestions (Map::updateLocalGradient())

[Erik Søe Sørensen]

Kai Antweiler skrev:

> > > 2) Alternatively, we can do a continuous update system, rather than a
> > > complete refresh. Basically, we keep track of changes on the map, where a
> > > change is from a path obstacle to a non obstacle, or vice versa.
> > >      
>
> I guess this itself would be the most significant advance.  When no changes
> happen, we don't need to update the gradient at all.  This would even work
> with current gradient algorithms.
>  
I came up with something which is a middle way: ULG itself checks 
whether the boundary conditions have changed, which is an indicator for 
whether the resulting gradient has changed, but can be checked early - 
before the propagation stage. My numbers indicate that change (and 
recalculation) occurs in 1-2% of the cases.

It is a relatively simple change, which moves ULG a few steps down on 
the list of bottlenecks; it is now at about 10-12% of the total time.
Only doing the work when something changes is of course a better 
approach - but the function is far less critical now. :-)

(Also included in the patch: Some comments outlining the steps of 
algorithm, and a refactoring of the propagation step into a separate 
function.)

/Erik

--- Map.cpp.patched1    2007-09-05 12:03:30.000000000 +0200
+++ Map.cpp     2007-09-05 15:58:46.000000000 +0200
@@ -3299,6 +3299,8 @@
 }
 
 
+void propagateLocalGradients(Uint8* gradient);
+
 void Map::updateLocalGradient(Building *building, bool canSwim)
 {
        localBuildingGradientUpdate++;
@@ -3314,9 +3316,15 @@
        Uint32 teamMask=building->owner->me;
        Uint16 bgid=building->gid;
        
-       Uint8 *gradient=building->localGradient[canSwim];
+       Uint8 *tgtGradient=building->localGradient[canSwim];
+
+       Uint8 gradient[1024];
 
+       // 1. INITIALIZATION of gradient[]:
+       // 1a. Set all values to 1 (meaning 'far away, but not inaccessable').
        memset(gradient, 1, 1024);
+
+       // 1b. Set values at target building to 255 (meaning 'very close'/'at 
destination').
        if (building->type->isVirtual)
        {
                assert(!building->type->zonableForbidden);
@@ -3326,8 +3334,8 @@
        else
                fillGradientRectangle(gradient, posW, posH);
 
+       // 1c. Set values at inaccessible areas to 0 (meaning, well, 
'inaccessible').
        // Here g=Global(map axis), l=Local(map axis)
-
        for (int yl=0; yl<32; yl++)
        {
                int wyl=(yl<<5);
@@ -3352,12 +3360,27 @@
                }
        }
        
+       // 1d. Set values at target building to 255 if this is not a building,
+       // but e.g. a flag (which has a circular area): 
        if (building->type->zonable[WORKER])
        {
                int r=building->unitStayRange;
                fillGradientCircle(gradient, r);
        }
        
+       // 2. NEED TO UPDATE? Check boundary conditions to see if they have 
changed.
+       bool change = false;
+       for (int i=0; i<1024; i++) {
+               // The boundary conditions - do they match?
+               if (gradient[i]==0 || gradient[i]==255 || tgtGradient[i]==0 || 
tgtGradient[i]==255) {
+                       if (gradient[i] != tgtGradient[i]) {
+                               change = true; break;
+                       }
+               }
+       }
+       if (!change) return; // No need to update; boundary conditions are 
unchanged.
+
+       // 3. Check that the building is REACHABLE.
        if (!building->type->isVirtual)
        {
                building->locked[canSwim]=true;
@@ -3407,8 +3430,16 @@
        else
                building->locked[canSwim]=false;
 
-       //In this algotithm, "l" stands for one case at Left, "r" for one case 
at Right, "u" for Up, and "d" for Down.
 
+       // 4. PROPAGATION of gradient values.
+       propagateLocalGradients(gradient);
+
+       // 5. WRITEBACK (because of the 'any change'-computation).
+       memcpy(tgtGradient, gradient, 1024);
+}
+
+void propagateLocalGradients(Uint8* gradient) {
+       //In this algorithm, "l" stands for one case at Left, "r" for one case 
at Right, "u" for Up, and "d" for Down.
        for (int depth=0; depth<2; depth++) // With a higher depth, we can have 
more complex obstacles.
        {
                for (int down=0; down<2; down++)