On 3/9/06, Kai Antweiler <[EMAIL PROTECTED]> 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 > [email protected] > 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. _______________________________________________ glob2-devel mailing list [email protected] http://lists.nongnu.org/mailman/listinfo/glob2-devel
