path planning implementations?

[Philippe Sigaud]

On Sun, May 13, 2012 at 3:05 AM, H. S. Teoh <hsteoh at quickfur.ath.cx> wrote:
> On Sat, May 12, 2012 at 11:07:41PM +0200, Philippe Sigaud wrote:
> [...]
>> Anyway, here is what I would like a graph module to have:
>>
>> - directed and undirected graphs
>> - templated nodes
>> - templated edges: I want the possibility to start from a weighted
>> graph and to create a graph with no info in edges, for example.
> [...]
>
> I don't know if this is overly ambitious, but I was thinking along the
> lines of a completely generic duck-typed graph interface for graph
> algorithms, so the algorithms will work for any kind of structs/classes
> that implement the right methods for graph access.

I don't think that's overly ambitious. IIRC, that's what I did. I have
isNode!(T) and isEdge!(T) templates and the algorithms accept any type
that fulfils the conditions.

The idea is that some algorithms just ask for the standard
run-of-the-mill graph 'interface' (à la range):

* give me the value of the current node (or "give me the node with
this identifier")
* give me outgoing edges (possibly a range instead of an array, hence
possibly infinite, btw)
(optionally: * give me the ingoing edges)
and an edge is any type that exposes '.from' and '.to' members that
returns nodes, and possibly other fields.

Have a look at

https://github.com/PhilippeSigaud/dranges/blob/master/graph.d
https://github.com/PhilippeSigaud/dranges/blob/master/graphalgorithm.d
https://github.com/PhilippeSigaud/dranges/blob/master/graphrange.d

The main question you must ask yourself is: "what kind of inner
storage do I use to represent the graph?".

>
> For example, say I have a grid of voxels representing some kind of game
> world, where adjacent voxels within a certain height difference are
> considered "reachable" and voxels with greater height difference are
> considered "unreachable". I'd like to be able to invoke graph
> reachability algorithms on the grid directly, by defining methods that
> expose a kind of graph-like interface to the grid (e.g., enumerate edges
> given a particular location, enumerate locations, etc.) without having
> to explicitly construct a separate graph object to represent
> reachability.

Yes, that's quite doable. It's a reachability algorithm, with a passed
predicate. The default predicate would be to test for edge existence,
whereas in your above case, one must test for height difference
between nodes.


> Graph algorithms generally tend to assume a particular kind of
> representation for the graph; we may classify graphs into different
> types depending on what kind of operations are expected (analogous to
> std.range where we have input ranges, output ranges, forward ranges,
> etc.).

Is a graph a container or a range? A graph may *expose* a particular
(linear or otherwise) range, but it's a container, for me.