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

[Andrew Sayers]

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