path planning implementations?

[jerro]

On Sunday, 13 May 2012 at 19:14:18 UTC, Trass3r wrote:
> Do you think it is possible to conceive an interface that 
> allows a rectangular array to be handled as a graph 
> transparently?
> (i.e. a regular grid, e.g. for path planning)

At least for some stuff it is. For example A* search could work 
on nodes which would have a property estimate (a lower bound for 
the shortest path length from this node to goal node) and a 
property neighbors. Property neighbors would return something 
iterable (either a range or an instance of a type with opApply 
defined). Each element of neighbors would have two members: 
distance from current node to a neighbor node and a neighbor 
node. The search function would than take a start node, a goal 
node and an optional predicate. To find a path through a 
rectangular array of booleans to position (i0, j0) you would 
write a node type like this:

struct Node
{
     RectArray a;
     int i;
     int j;
     int i0;
     int j0;

     @property auto estimate()
     {
         return abs(i0 - i) + abs(j0 - j);
     }

     @property neighbors()
     {
         Tuple!(int, Node)[] r;

         if(i > 0 && a[i - 1, j])
             r ~= tuple(1, Node(a, i - 1, j, i0, j0));

         ... take care of the other three possible neighbors here

         return r;
     }
}

I'm not saying we should choose this particular interface for
A* search, but an interface that lets you treat rectangular
array as a graph is certainly possible at least for A* search,
and probably for other searches too.