# How to create a path root like google maps

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

@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

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

@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

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 :

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

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 :

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)

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

@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
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

1 Like

Where there are important places like entrances, exits, stairs you will need clickable meshes. Corners and splits in the path just need vector3s for there position. These meshes will have positions. Form your nodes as a list of vector3s including clickable meshes positions plus corners and splits.

Hi guys. John, that would be a “pre-ordained” path follow…pre-determined “pathways” between important nodes.

One problem with that… is… if you change the model, you must update the pre-made “highway” paths.

Other problem with that… scene-code will need to find the path… to GET-TO the highway, too (an on-ramp). We never know where the nav-mesh will be standing. It could be far from the highway, standing upon a desk, in some back-office somewhere.

Better… to have “arbitrary” system, one would suspect. Not easy, I assume.

Let’s say… all walls… had actionManagers… checking for onIntersectEnter… of an invisible sphere that surrounded the player. Then anytime that triggered, the “smart-wall” would push-away the player… somehow. Possibly surround player with 4 invisible spheres, and smart walls watch for intersect on all 4 spheres… so it knows which direction to push player “away” from wall.

SO, when standing-on-a-desk-in-some-back-office user … says “take me to the foyer”… the navMesh simply heads-off in the bee-line direction… but the walls keep forcing the player-in-an-invisible-bubble… (or surrounded by 4-8 intersect sensors) along ONLY “hallways”. The player would NOT appear to be bouncing off the walls the entire trip, because the surrounding “intersect encasement bubble” is larger than the player, yet still not too large to travel hallways/doorways.

Still might be problem for low-height and hanging-from-ceiling obstacles… as the surround-the-player intersect sensors… would probably be “around their waist” and maybe spherical. But maybe better… 4-sided cylinders (vertical sticks). Then a low street-curb could be seen as an obstacle, and so could a hanging planter. 8 invisible sticks, and each wall has 8 onIntersectEnter triggers on its actionManager… for knowing which way to push-away player… in its executeCodeAction intersect-handler. Wow!

Likely over-kill for Anes’ project.

Nah, that would never work, but it’s fun to think-about. Ray-radar, I suppose. erf. Ray-radar really gets perf-expensive when navMesh must go over and under things, and not only lateral path-finding. I don’t want to think about it. sigh.

MeshDoppler 1.0 erf. Use Jerome’s basic-intersect power for SPS… and spray invisible SPS triangles (facets) out in-front-of the moving player, and watch them for intersect with obstacles? heh. hmm. Maybe just a “burst” of particles at move-start-time and at change-room times… to get a “virtual model” of the room? I dunno.