Re: [glob2-devel] my experiments on pathfinding and gradients (huge)

[Nuage]

* resource gradients:

I am not sure to undersand your idea.

You want to update the gradient localy each time a small resource is created or
removed ? I don't think this is necessary, because the non-updated gradient is
most likely (very) to be good enough to find the resources.

Case 1: a resource growth:
Well, the new resource is laying at a "254" spot, a globule will head the "255"
spot and enounter the "254" on the way.
If, there is more growth, this is never a problem. The globule will always find
the resource. If the gradient is not updated often enough, it will only be
sub-optimal.

Case 2: a resource shrink:
The missing resource has created an empty "255" spot. The globule can still
"climb" the gradient up to the "255" spot and find the resource next to it.

If there is a 2nd resource removed, then there is a special algorithm case, and
the unit will use an "invert-gradient" algorithm. If an unit is laying at a
"255" spot, it will look for the smallest gradient value around, and go to the
opposite, if it is heading to a "255" spot. If there is no more information,
then the unit will just continue in the same direction than previously used. If
there are more than 2 level or resource removed, then the unit may go the wrong 
way.


* summary:

So, my idea is that gradient are naturaly flexible. Somehow, a localy-updated
gradient does not worth much more than the non-updated one. This is what is
actualy already happening: the algorithm tries to use a gradient, which can
definiely be out-of date, but still usable in allot of cases.

What is badly implemented now is that deleting a building lead to all gradient
desctruction.


* optimisations:

Improving computaion time is always welcome. But I don't see how the STL way you
describe will improve it. Unless the compiler knows more avout the CPU than we
do, which can actualy happen.


Do you mind making more precise tests to know how much your last changes actualy
improve the computation speed ? All tools are here : "--nox" and "Engine.log".
thx


* last change:

I think your last change has a small bug:

inline void updateGradientLine(const Map& m, const Uint8* gradient, Uint8**&
listedAddrWrite, const Uint8 g, Uint8* topLine, Uint8* middleLine, Uint8*
bottomLine)

At lines 2135, 2136, 2137: this is "+1-width" instead of "-width".
For instance if your "middleLine" is at y=255, and width=256, then you want to
get the y=0 emplacement.

At lines 2142, 2143, 2144: this is "-1+width" instead of "+width".
For instance if your "middleLine" is at y=0, and width=256, then you want to get
the y=255 emplacement.


Well, and I have to say that I am amazed that you can uderstand our crapy code!
Thank you for your work!


Luc-Olivier


Andrew Sayers wrote:
> Welcome back!  How much time do you have to talk?  There are lots of
> things I need to ask you, and if your time is short, I'll stick to
> those.
> 
> As we're talking about gradients for now though, I'll stick to my
> thoughts about that.
> 
> I've not really discussed this on the ML, but my work on optimising
> gradients has mainly been based around finding computational
> efficiencies such as ways to encourage programmers to use pointers where
> appropriate, and building an infrastructure that makes it easier to
> slot in efficiency savings.
> 
> I really like your convex/concave distinction, but the problem is
> even more complex than that, because as well as obstacles and
> non-obstacles, you can also add and remove goals.  These distinctions
> allow you to split the problem up into distinct groups (e.g. all convex
> changes are easy), but it's also very useful to look at messier special
> cases that happen to be very common.  For example, a very common
> situation is to have a large area of resources, and for one resource to
> be removed (i.e. to go from goal to non-obstacle).  That will often have
> little or no effect on the wider map, as the nearby resources will just
> fill in.  Spotting and handling this special case could save a lot of
> processor time.
> 
> To encourage more efficient iteration over the map (and to allow us to
> easily add efficiencies later), I've come up with a system of STL-style
> iterators that takes a while to understand, but is very easy to use once
> you do.  Basically, you do something like:
> 
> for (MapType::iterator<BOX, MapType::width, MapType::height> i=m.begin();
>       i!=m.end(); ++i)
> {
>       // blah blah
> }
> 
> And a complex series of template inheritances gives you the most
> efficient iterator class for iterating around a box-shaped section of
> the entire map (which happens to be pointer-based).  If instead you did:
> 
> for (MapType::iterator<CW_OUTLINE, 3, 3> i=m.begin(); i!=m.end(); ++i)
> {
>       // blah blah
> }
> 
> You'd get a class that efficiently iterates clockwise around the edge of
> a 3x3 grid (which happens to be array-based).  This is based on the idea
> of maps whose width and height are set as template parameters:
> 
> typedef Map<someWidth, someHeight> MapType;
> 
> 
> To handle different types of update, I'm designing a general-purpose
> update mechanism, which passes a list of recent changes to various
> "update" functions and expects them to handle the updates appropriately.
> At present, the gradient update function makes an incremental update
> if all the changes are convex, or recalculates the entire grid otherwise.
> Although this is far from an optimal solution, it's a good test of the
> general design theories.
> 
>       - Andrew
> 
> 
> _______________________________________________
> glob2-devel mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/glob2-devel
>