Find optimal path in 3D station

hello guys,

so here you find level one of my station where I build a finding path algorithm : https://playground.babylonjs.com/#TBG7CU#2

if you click to “generate path”; it drows a path to the top of escalator.

you can change start and end point in line 411.

the problem is : the implementation of algorithm is fine (it’s A* algo with heuristics “h” and cost “g”) I calculate the optimal path minimazing the distance but :

when generate the path it use the escalator that is go down :stuck_out_tongue: so it’s not realisable

any ideas guys

thank u I’ll tag @JohnK, @Cedric, @Wingnut gladiators

Anes

You have give a direction to each connection between nodes and when you compute a path, reject links not going in the direction you want. Or you can set a high cost to the heuristic depending on the direction. But in any case, you have to add more datas to the graph.

g.addEdge(vertices[0], vertices[2]);

I guess it means you can go from [0] to [2] and from [2] to [0]. You can change that to mean “can go from [0] to [2] only”
and if you need to set it bi-directional, then:

g.addEdge(vertices[0], vertices[2]);
g.addEdge(vertices[2], vertices[0]);

@Cedric Yeaa cuz I implement all edges bidirectional (line 106 & 108) I think if I fix the direction it will work fine.

but if I want to play with heuristics, in my case heuristic is de distance from currentvertex to the goal and I calculate it in my while loop.

so if I want precise the heuristic of each node differently, then I need to define it out of while loop and I don’t see how :thinking:

I think there is a couple ways to make your path finder algorithm work with a directed graph.

You addEdge function line 103 make your graph undirected, remove line 108 and you will be working with a directed graph. There is now two ways to proceed.

When node A is at the bottom of the up escalator and node B at its top and node X is the top of the down escalator and node Y at its bottom then your list from line 368 would look like

g.addEdge(vertices[0], vertices[2]); 
g.addEdge(vertices[2], vertices[0]);
g.addEdge(vertices[0], vertices[3]);
g.addEdge(vertices[3], vertices[0]); 
g.addEdge(vertices[1], vertices[3]);
g.addEdge(vertices[3], vertices[1]);
.....
..... 

where direction between nodes does not matter

and where direction does matter add edge only once.

g.addEdge(vertices[A], vertices[B]); 
g.addEdge(vertices[X], vertices[Y]);

The alternative is to change the addEdge function to

addEdge(directed,src,dest)
        {
            
            this.AdjList.get(src).push(dest)
            if(!directed) {
                this.AdjList.get(dest).push(src);
            }
        }

and then

g.addEdge(false, vertices[0], vertices[2]); 
g.addEdge(false, vertices[0], vertices[3]);
g.addEdge(false, vertices[1], vertices[3]);
.....
..... 
g.addEdge(true, vertices[A], vertices[B]); 
g.addEdge(true,vertices[X], vertices[Y]);