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.
