How to create a path root like google maps

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.

1 Like

@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

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. :slight_smile: 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.

You are correct. I like to keep it simple, like me. A here is a maze find all possible routes, save as a network graph then do paths between points is an all together different ball game.

I was definitely thinking of here is my model and its not going to change for some time situation.

I think Anes’ metro station is not going to change quickly Feasibility of a 3D interactive visualization under babylon.js

@JohnK even if I made clickable meshes I can’t click them if I “Submerge” my station with small cubes like this :

where the yellow path is from the start to goal node, so I said that I will “cover” my station with small cubes like magic cube and then mark the places where there is no possibility to draw paths with black color and I make the roads and stairs where I can walk with white color and then hide this big magic cube, the a* algo is implemented inside.

the problems are :

  • it is not pratical to cover all the hole station with small cubes (the idea with small cubes that there is no edges or in other words each time the edge is the currentNode + 1, because the nighbors in 3d are 6 at x+1, x-1, y+1, y-1,z+1,z-1 so the nighbors g is always the current g + 1 and then the drawing path will be a liste of the nodes themeselves, there is no edges between them or let us said that there is unitary edges).
  • the second problem is that if I cover all the station with cubes, even if I hide them all, I wont be able to click the ground because hiding meshes exist physicaly in the station

Anes, I think John implied earlier, that you use NO boxes/cubes… but store an array of vector2’s or vector3’s… of the POSITION where each yellow path-box was located. (Ya really only need to store X and Z values, and always keep Y at zero or at center-height of player.)

So, no boxes/cubes… but instead, build a database (array) of “nodes”… positions. Now your floor can be clicked again.

When floor is clicked, grab the position of the click, and then iterate (for/next) thru your list of nodes… to find the one that is closest to the player (Vector3.Distance()?). Just after the floor-click, you might need a thing… um… unProject() ? … to convert a scene pick-location (x/y)… into a world coordinate (x/y/z). Not sure.

Then animate the player to that closest node (which COULD take the player thru a wall or two, if not careful, unfortunately), and then the “moving sidewalk” system takes the player the rest of the way. Once the player gets-to a node on the highway (in your array)… the highway itself moves the player to the wanted location.

But, if I remember correctly, you want to SHOW the user… which way to walk, to get-to their wanted new location. So, no auto-moving highway/sidewalk, but lines-mesh or similar… could “show the highway”. I would use floor-dots/markers… instead of lines. One marker per stored position in the positions array.

At least I THINK that’s what John implies. Work with an array of positions, and not actually mesh.

Perhaps decals… would work nice… if you want to “show highway nodes” for player or self. Decals put a decent image… onto the surface of another mesh, even if that mesh is already textured. So, being able to activate a “decal dot” (marker) at every position in your highway array… might be handy for you, and useful for player, later.

These decals MIGHT be clickable or actionManager-able, but… I doubt it. It’s not in their nature… not without putting a thin "disk mesh " beneath. And if you need a little disk-mesh, might as well say goodbye to decals, and just make a bunch of instances of a low-height cylinder/box… to place on the floor as node-dots. That might be a better idea than decals, but IF dots are pickable, floor beneath dots won’t be pickable without using “multi-pick” operations.

This is similar to your many-cubes idea, Anes… but just little boxes/disks, very very low-height… with some space between them. :slight_smile: A good SPACING rule-of-thumb might be: When user stands upon ANY marker/node, user should be able to “see” at least ONE other marker/node.

Spot on.

Hi again @Anes, hopefully you may have found a solution to you path problem using the navigation mesh.

For future clarification on the method I was suggested I have produced a PG. It is rough and ready and for proper use it will need refinement.

https://www.babylonjs-playground.com/#BC8IWV#9

Set the start and end points (0 to 10) on lines 278, 279

The design process is

Create the buildings (or maze or whatever) with access points - red objects in the PG.

Number the access points.

Draw a plan of access points and possible paths. Number the corners, (way points, junctions, decision points or whatever you want to call them). The are the nodes for the Dijkstra’s algorithm.

Form a list of nodes.

image

Using the node points form a list of edges, ie pairs of adjoining neighbours.

Form the graph from the nodes and edges, set a start node and end node and build a path from node to node.

2 Likes

@JohnK thank u so much for ur effort,

Yes, so I build a graph and I use A* algorithm to find the optimal path here is the PG : https://playground.babylonjs.com/#3KUQ1L#18

don’t be angry if I used spheres :stuck_out_tongue: just to see them in 3d.

now since it works fine, I’ll update the nodes in my station and see what it will done.

Thank you guys

1 Like

Glad you found a solution. Fine to use markers (spheres) for testing :relaxed:. Well done.