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++)
_______________________________________________
glob2-devel mailing list
[email protected]
http://lists.nongnu.org/mailman/listinfo/glob2-devel
