How to create a path root like google maps

Hello guys,

I really need your help :frowning:
I want to create a path (visible) between point A and B, for example I want to help a user to exit my sation so we suppose he is in the quai and I want to generate a path to the exit of my station, and also I can make my camera in the path and I can walk through this path to the exit (moving forward, back, rotate).
here is the PG : https://playground.babylonjs.com/index.html#KI8BJH#35
you can click hide level 0,1,2 and 3 to see inside the station I want to create a path for example from the level 0 to the stair of 3d level, like that an operator can help the user (go forward take escalator … etc)

Hi Anes. Pretty model. Pathfinding is not easy. Old forum search for ‘pathfinding’. that’s all I got right now. Talk more soon. Stay tuned for more comments, maybe.

Also… check this out: https://www.babylonjs-playground.com/#1SOEHQ#2

Although it isn’t working, that “stuff” in there (top 80% of editor code)… is probably pathfinding code.

Looks “deep”. :slight_smile:

@Cedric implemented the navmesh babylon extension, perhaps he can help approach visualizing pathfinding on a navmesh?

Hi!
Navmesh is not merged yet in master (should be shortly). Agents can move on the navmesh but I didn’t add the interface to get the path points. So it’s not possible to display it. I’m going to improve that and will test with you PG. I’ll let you know when I get something :slight_smile:

4 Likes

I will be merging today the navmesh and crowd navigation feature. With that, you will be able to compute path between 2 points on the navmesh.

4 Likes

Hello @Cedric,
thank u alot for ur effort, just a question :
the path I talk about is a path with a “meaning”, in other words, if I choose “the technical local” and "the exit 2 " as my two points , it will give me a logical path to help a human inside to exit the station

This is a starting point you might be able to use for finding the shortest path between two points https://www.babylonjs-playground.com/#7YCXAI#2

From Best way to "Measure" a Surface of a model between a set of points

@Cedric did u find any idea to build this path, for me I try to apply A* algorithm but I don’t know how to do it in 3d and how to make my station like a maze in order to apply A* algo :frowning:

The playground I suggested above use Dijkstra a variant of A*. They both work in 3D as the locations of the nodes will be in 3D. Use the distance between nodes as all or part of the weighting on the edge between nodes.

For the ‘maze’ it looks like @Cedric’s navmesh Create Navigation Mesh - Babylon.js Documentation could be used. If you prefer you could code your own - set a node at the entrance to your building at any choice of directions set new nodes in those directions until all possible routes have been covered.

@JohnK suppose that I set my entrence nodes , I need also to make a broken roads in my station in order to build a meaningful paths like this picture :
PNG

The problem is I don’t see how to hide all inaccessible roads from my station (in 3D) :frowning:

I’m LOST

The path nodes are a data set, mathematical not meshes. In my PG I create a graph using graphFrom a mesh. In your case your nodes with just be vector3s and you need a list of edges for example [1, 3, 2,4.……] meaning node 1 and node 3 are joined, node 2 and node 4 are joined etc. Then you will create a graph from the list of nodes and edges.

I think @Cedric’s navmesh works in a similar way. I may be wrong but I think the navmesh vertices form the nodes and the edges determined by the indices. Meshes are first placed to form barriers (holes) in the navmesh so the navmesh when created forms an area that an object (agent) has to stick to when moving about. So giving two points A and B on the navmesh the agent has to stay within the navmesh area.

@JohnK understand, suppose that I have a liste of nodes ( corresponding to the points that I should pass to like stairs, doors, escalators, elevators …etc), now the edges if I want to join stair 1 (node 1) with stair 2 (node 2), it is necessary to show a logical path between them not just a simple link, it must be a path that reflect reality, so how to show it and if yes so it is necessary to build a logical path of all possible edges !

You have to place nodes whenever there is a change of direction or a choice of more than one direction.

@JohnK yea but if I place two nodes one in one road and then there is an intersection, the other node is in the other road there is a small garden in the corner, if I want to go from node 1 to node 2 it will draw a path through the garden and it is not a logical path, so in my station I need to hide every mesh that there is no a path through it (walls for example), in order to have something like a maze in 3D, something like this :
a_-search-algorithm-1

I think that I should hide every inaccessible path in my 3d station (so make 3d maze) (I don’t know how) and then arrive the creation of nodes and edges cuz if I create them and I don’t have a 3d maze with logical paths it won’t work (I think)

help please

You design your maze (or set of buildings) first and then add nodes.

Hi @Anes, just to understand your problem statement.

It is unclear to me whether the place to navigate around is fixed and known before hand (e.g. you want it for the station.babylon mesh you’ve created yourself and for that mesh only, so a fixed set of levels for example), or you want to navigate through any imported mesh by anyone not known beforehand?

If the model is fixed beforehand you could embed the navigation nodes/routes right into the model, instead of the need to dynamically generate/compute the nodes at runtime. This is actually quite a common practise.

In the image above I painted blue circles as nodes and green lines as valid routes to choose from. Red circle is the user position at the moment. User wants to move to blue circle noted ‘EXIT’. Now if the model (or set of models) you use are “fixed” (‘you made them yourself’), you could put those kind of waypoints right into your model, hide them for the user but use them as the points and routes for a standard path finding algorithm. So into the algorithm put blue circles and green routes, as starting position closest blue circle to player. Algorithm will give you the array of nodes to traverse to get to EXIT. This approach is referred to as waypoint navigation.

Another strategy sometimes used is to load a simplified model (with easy planes, less detail than original mesh) that is used for collision and compute all nodes/routes at runtime.

Q

2 Likes

@JohnK I try :frowning:

@QuintusHegie If I want to make a generic solution I need to draw path on any imported station, but now I want just to test the A* algorithm, but I’ve a problem in the implementation , I can initialize nodes in open list of the algo but how about edges, I didn’t see any information about edges in the A* algo

@Cedric @JohnK @Wingnut, I starting making small-cubes every where in my station in order to build a maze where I can make walls and logical paths (so I make black cubes where there is wals and inaccessible paths and a white cubes where there is a path) and then Implement the a* algo to find the optimal path between two points.

tired to make small cubes every where and then I noticed that if I submerge my station with this small cubes, even if I hide them I w’ont be able to click to the groun for example :sneezing_face::sneezing_face::sneezing_face::sneezing_face:
so If I want to create a path between two points in ground of level1 I can’t select them cuz cubes are everywhere

Ideas please I’l submerge with this station soon :stuck_out_tongue:

1 Like