www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - path planning implementations?

reply Trass3r <un known.com> writes:
Are there any D path planning implementations?
May 11 2012
parent reply Gor Gyolchanyan <gor.f.gyolchanyan gmail.com> writes:
Do you mean heuristic graph traversal algorithms?

On Fri, May 11, 2012 at 7:27 PM, Trass3r <un known.com> wrote:

 Are there any D path planning implementations?




-- 
Bye,
Gor Gyolchanyan.
May 11 2012
parent reply Trass3r <un known.com> writes:
 Do you mean heuristic graph traversal algorithms?


Yep. There's a generic implementation of Dijkstra and Bellman    
https://github.com/PhilippeSigaud/dranges
But no A*, D* Lite etc.
May 11 2012
next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Sat, May 12, 2012 at 02:53:24PM +0400, Gor Gyolchanyan wrote:

 I've been trying to find a D* lite too, but with no luck.
 Having a fast graph traversal algorithms are useful for a ton of very
 powerful use cases, besides path planning.
 I'm starting to think, that we're gonna have to implement it ourselves.
 Which in turn will require us to implement a graph data structure.
 Right now I need a good graph data structure for my project, so I have
 a direct interest in getting this done.
 How about we chip in and develop an std..graphs module for Phobos with
 different traversal and shortest-path algorithms?


[...]

+1. With D's generic programming abilities, we *should* have a generic
graph interface. Perhaps something along the lines of the range
interface (compile-time duck-typing). It'd be nice to have advanced
graph algorithms implemented in a generic way that can be used for a
variety of applications.

Personally I'd love to have a generic graph-coloring algorithm.


T

-- 
"Outlook not so good." That magic 8-ball knows everything! I'll ask about
Exchange Server next. -- (Stolen from the net)
May 12 2012
prev sibling next sibling parent Gor Gyolchanyan <gor.f.gyolchanyan gmail.com> writes:
What do you think about this, The Phobos Crew?

On Sat, May 12, 2012 at 9:06 PM, H. S. Teoh <hsteoh quickfur.ath.cx> wrote:


 On Sat, May 12, 2012 at 02:53:24PM +0400, Gor Gyolchanyan wrote:

 I've been trying to find a D* lite too, but with no luck.
 Having a fast graph traversal algorithms are useful for a ton of very
 powerful use cases, besides path planning.
 I'm starting to think, that we're gonna have to implement it ourselves.
 Which in turn will require us to implement a graph data structure.
 Right now I need a good graph data structure for my project, so I have
 a direct interest in getting this done.
 How about we chip in and develop an std..graphs module for Phobos with
 different traversal and shortest-path algorithms?


 [...]

 +1. With D's generic programming abilities, we *should* have a generic
 graph interface. Perhaps something along the lines of the range
 interface (compile-time duck-typing). It'd be nice to have advanced
 graph algorithms implemented in a generic way that can be used for a
 variety of applications.

 Personally I'd love to have a generic graph-coloring algorithm.


 T

 --
 "Outlook not so good." That magic 8-ball knows everything! I'll ask about
 Exchange Server next. -- (Stolen from the net)




-- 
Bye,
Gor Gyolchanyan.
May 12 2012
prev sibling next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Sat, May 12, 2012 at 09:16:21PM +0400, Gor Gyolchanyan wrote:

 What do you think about this, The Phobos Crew?


Doesn't matter, just write the code and submit a pull request. :-)



 On Sat, May 12, 2012 at 9:06 PM, H. S. Teoh <hsteoh quickfur.ath.cx> wrote:
 

 On Sat, May 12, 2012 at 02:53:24PM +0400, Gor Gyolchanyan wrote:

 I've been trying to find a D* lite too, but with no luck.
 Having a fast graph traversal algorithms are useful for a ton of very
 powerful use cases, besides path planning.
 I'm starting to think, that we're gonna have to implement it ourselves.
 Which in turn will require us to implement a graph data structure.
 Right now I need a good graph data structure for my project, so I have
 a direct interest in getting this done.
 How about we chip in and develop an std..graphs module for Phobos with
 different traversal and shortest-path algorithms?


 [...]

 +1. With D's generic programming abilities, we *should* have a generic
 graph interface. Perhaps something along the lines of the range
 interface (compile-time duck-typing). It'd be nice to have advanced
 graph algorithms implemented in a generic way that can be used for a
 variety of applications.

 Personally I'd love to have a generic graph-coloring algorithm.


 T

 --
 "Outlook not so good." That magic 8-ball knows everything! I'll ask about
 Exchange Server next. -- (Stolen from the net)


 
 
 
 -- 
 Bye,
 Gor Gyolchanyan.


-- 
What do you get if you drop a piano down a mineshaft? A flat minor.
May 12 2012
prev sibling next sibling parent Gor Gyolchanyan <gor.f.gyolchanyan gmail.com> writes:
Ok. I gotta implement it anyway - I need it for my project. Might as well
submit it.
Are you gonna work on this too? If so - we should coordinate our efforts.

On Sat, May 12, 2012 at 9:20 PM, H. S. Teoh <hsteoh quickfur.ath.cx> wrote:


 On Sat, May 12, 2012 at 09:16:21PM +0400, Gor Gyolchanyan wrote:

 What do you think about this, The Phobos Crew?


 Doesn't matter, just write the code and submit a pull request. :-)



 On Sat, May 12, 2012 at 9:06 PM, H. S. Teoh <hsteoh quickfur.ath.cx>


 wrote:

 On Sat, May 12, 2012 at 02:53:24PM +0400, Gor Gyolchanyan wrote:

 I've been trying to find a D* lite too, but with no luck.
 Having a fast graph traversal algorithms are useful for a ton of very
 powerful use cases, besides path planning.
 I'm starting to think, that we're gonna have to implement it






 ourselves.

 Which in turn will require us to implement a graph data structure.
 Right now I need a good graph data structure for my project, so I






 have

 a direct interest in getting this done.
 How about we chip in and develop an std..graphs module for Phobos






 with

 different traversal and shortest-path algorithms?


 [...]

 +1. With D's generic programming abilities, we *should* have a generic
 graph interface. Perhaps something along the lines of the range
 interface (compile-time duck-typing). It'd be nice to have advanced
 graph algorithms implemented in a generic way that can be used for a
 variety of applications.

 Personally I'd love to have a generic graph-coloring algorithm.


 T

 --
 "Outlook not so good." That magic 8-ball knows everything! I'll ask




 about

 Exchange Server next. -- (Stolen from the net)




 --
 Bye,
 Gor Gyolchanyan.


 --
 What do you get if you drop a piano down a mineshaft? A flat minor.




-- 
Bye,
Gor Gyolchanyan.
May 12 2012
prev sibling next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Sat, May 12, 2012 at 10:25:15PM +0400, Gor Gyolchanyan wrote:

 Ok. I gotta implement it anyway - I need it for my project. Might as
 well submit it.
 Are you gonna work on this too? If so - we should coordinate our
 efforts.


Well, I'd _like_ to work on it, but I'm supposed to be working on the
new AA implementation as well, and time hasn't been on my side. :-(

Having said that, though, putting the code up on github should be
helpful -- you'll be able to find other volunteers who can help.


--T


 On Sat, May 12, 2012 at 9:20 PM, H. S. Teoh <hsteoh quickfur.ath.cx> wrote:
 

 On Sat, May 12, 2012 at 09:16:21PM +0400, Gor Gyolchanyan wrote:

 What do you think about this, The Phobos Crew?


 Doesn't matter, just write the code and submit a pull request. :-)



 On Sat, May 12, 2012 at 9:06 PM, H. S. Teoh <hsteoh quickfur.ath.cx>


 wrote:

 On Sat, May 12, 2012 at 02:53:24PM +0400, Gor Gyolchanyan wrote:

 I've been trying to find a D* lite too, but with no luck.
 Having a fast graph traversal algorithms are useful for a ton of very
 powerful use cases, besides path planning.
 I'm starting to think, that we're gonna have to implement it






 ourselves.

 Which in turn will require us to implement a graph data structure.
 Right now I need a good graph data structure for my project, so I






 have

 a direct interest in getting this done.
 How about we chip in and develop an std..graphs module for Phobos






 with

 different traversal and shortest-path algorithms?


 [...]

 +1. With D's generic programming abilities, we *should* have a generic
 graph interface. Perhaps something along the lines of the range
 interface (compile-time duck-typing). It'd be nice to have advanced
 graph algorithms implemented in a generic way that can be used for a
 variety of applications.

 Personally I'd love to have a generic graph-coloring algorithm.


 T

 --
 "Outlook not so good." That magic 8-ball knows everything! I'll ask




 about

 Exchange Server next. -- (Stolen from the net)




 --
 Bye,
 Gor Gyolchanyan.


 --
 What do you get if you drop a piano down a mineshaft? A flat minor.


 
 
 
 -- 
 Bye,
 Gor Gyolchanyan.


-- 
Prosperity breeds contempt, and poverty breeds consent. -- Suck.com
May 12 2012
prev sibling next sibling parent Gor Gyolchanyan <gor.f.gyolchanyan gmail.com> writes:
ok, I'll fork from phobos and get down to busyness.

On Sat, May 12, 2012 at 10:39 PM, H. S. Teoh <hsteoh quickfur.ath.cx> wrote:


 On Sat, May 12, 2012 at 10:25:15PM +0400, Gor Gyolchanyan wrote:

 Ok. I gotta implement it anyway - I need it for my project. Might as
 well submit it.
 Are you gonna work on this too? If so - we should coordinate our
 efforts.


 Well, I'd _like_ to work on it, but I'm supposed to be working on the
 new AA implementation as well, and time hasn't been on my side. :-(

 Having said that, though, putting the code up on github should be
 helpful -- you'll be able to find other volunteers who can help.


 --T


 On Sat, May 12, 2012 at 9:20 PM, H. S. Teoh <hsteoh quickfur.ath.cx>


 wrote:

 On Sat, May 12, 2012 at 09:16:21PM +0400, Gor Gyolchanyan wrote:

 What do you think about this, The Phobos Crew?


 Doesn't matter, just write the code and submit a pull request. :-)



 On Sat, May 12, 2012 at 9:06 PM, H. S. Teoh <hsteoh quickfur.ath.cx>


 wrote:

 On Sat, May 12, 2012 at 02:53:24PM +0400, Gor Gyolchanyan wrote:

 I've been trying to find a D* lite too, but with no luck.
 Having a fast graph traversal algorithms are useful for a ton of










 very

 powerful use cases, besides path planning.
 I'm starting to think, that we're gonna have to implement it






 ourselves.

 Which in turn will require us to implement a graph data










 structure.

 Right now I need a good graph data structure for my project, so I






 have

 a direct interest in getting this done.
 How about we chip in and develop an std..graphs module for Phobos






 with

 different traversal and shortest-path algorithms?


 [...]

 +1. With D's generic programming abilities, we *should* have a








 generic

 graph interface. Perhaps something along the lines of the range
 interface (compile-time duck-typing). It'd be nice to have advanced
 graph algorithms implemented in a generic way that can be used for








 a

 variety of applications.

 Personally I'd love to have a generic graph-coloring algorithm.


 T

 --
 "Outlook not so good." That magic 8-ball knows everything! I'll ask




 about

 Exchange Server next. -- (Stolen from the net)




 --
 Bye,
 Gor Gyolchanyan.


 --
 What do you get if you drop a piano down a mineshaft? A flat minor.




 --
 Bye,
 Gor Gyolchanyan.


 --
 Prosperity breeds contempt, and poverty breeds consent. -- Suck.com




-- 
Bye,
Gor Gyolchanyan.
May 12 2012
prev sibling next sibling parent reply Philippe Sigaud <philippe.sigaud gmail.com> writes:
On Sat, May 12, 2012 at 8:39 PM, Gor Gyolchanyan
<gor.f.gyolchanyan gmail.com> wrote:

 ok, I'll fork from phobos and get down to busyness.


Maybe you should launch another thread on what features such a module
should contain. As was linked upstream in this thread, I wrote a small
generic Graph (+ algos + ranges) module on this a few years ago, so
I'm interested in hearing your take on this. All on all, I had great
fun in writing the algos and the factory function.That was my first
real dabbling in template constraints.

Also, seeing the crowd here, I guess Boost::Graph will be the
yardstick with which you'll be measured. Did you have a look at it?

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.
- a way to get a range on a graph, to as to leverage std.algorithm goodness.
- adding, deleting nodes and edges
- adding a entire graph to another graph
- merging or splitting of edges and nodes
- policies! Are multiple edges authorized? Dangling edges? How are the
nodes and edges stored (dense graph or sparse graph)
- bidirectional graphs (that is, given a node, gives access to all
ancestors, probably through a node property)
(- branching ranges)
- factory functions for standard graphs: linear, circle, grid, etc.
- standard graph operations: search and path algorithms of course,
transitive closure, metagraph,...


But, you know, you could say that a graph is a container (though we
are interested not only by what it contains, but also by its the
global 'shape'). This opens the same can of worms as for any other
containers: memory, element possession, relation to ranges, and so on.
We are still waiting for Andrei's design on D allocators.


Philippe
May 12 2012
parent reply Trass3r <un known.com> writes:
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)
May 13 2012
parent "jerro" <a a.com> writes:
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.
May 13 2012
prev sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
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.

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.

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.).


T

-- 
Why have vacation when you can work?? -- EC
May 12 2012