Pathfinding NavMesh

[Rick]

So my question is, even if I have a navigation mesh, what would I use for pathfinding through it? I've done A* before in 2D where it was a perfect 2D grid, but how would I implement A* in 3D where the navigation mesh has all different sizes and placed all over the place. Another question along those lines is do the navigation meshes all need to be touching each other? Can you have gaps between navigation meshes and still be ok?

[Pixel Perfect]

As far as I'm aware Rick A* is still used to find your way through the nodes. The navmesh polys represent individual nodes and A* iterates through the list of linked nodes. Chris will probably give you a much fuller explanation.

 

In terms of do they need to touch, I'd say probably not so long as your logic links them where its deemed appropriate ... such as the steps on a flight of stairs for instance. If an area of nav mesh is totally isolated from the main section, such as on top of the roof of a container, then that may be also quite valid as although there is no way to link to it as your NPCs couldn't jump that high, they still might fall of a building and land on it.

 

A* in theory should work with any number of dimensions, the traditional 2D square grid is just a special case.

[Rick]

The navmesh polys represent individual nodes and A* iterates through the list of linked nodes.

 

So there is a question. Do you have to make links between nodes? When I did the 2D grid I didn't have to make links between the tiles since they were all lined up perfectly.

[Pixel Perfect]

Yes, that's why its a special case. In the square grid it's assumed each tile is linked to the 8 surrounding tiles (or nodes).

[Rick]

I was thinking about creating a very simplistic navmesh thingoid. You drag it into your scene and it creates a plane object. You can resize it via properties and rotate it. You place it where you want, then make links between them (now that I know they need to be linked). When the game runs it would find these thingoids and store the plane information and then hide/remove the planes so they aren't visible. Then you could place a pathfinding thingoid in your scene to work with that data. This would of course be a very manual process but it would be something easier to create than the automatic detection. Plus it gives me a good reason to learn how navmeshes work.

 

I can't seem to find any good tutorials on how to use a pathfinding process with the navmesh though. I understand I can use A* but that would return the navigation meshes that I can walk on. That's all fine and good, but those meshes could be rather large, and ideally you want points to move the object between. So once I get the meshes that could get me to the goal, how do you break that down further to points within that mesh that are the shortest?

[Pixel Perfect]

As in theory all nav mesh nodes are walkable I think the next phase having returned the list of nodes you need to walk through is to produce curved path through them so it looks natural (its referred to as string pulling I think). Again, I've not worked directly with nav meshes so I'm trying my best to remember what Chris had described when talking about his implementation. My system of navAreas is more akin to the old 2D grid system so I have fixed sized nodes.

 

I suspect it doesn't help to allow your nodes to extend beyond a certain maximum size or as you say you will be needing to pathfind through the nodes themselves

[Rick]

I suspect it doesn't help to allow your nodes to extend beyond a certain maximum size or as you say you will be needing to pathfind through the nodes themselves

 

But it seems it doesn't matter. It seems you can have any size of mesh for a node. If your environment is static then there wouldn't be much to worry about, I guess you could pick any point in a mesh node that is in your path randomly and it would work (although would give strange but funny results ). It feels like if your scene can be dynamic you might run into issues where you would need to do more within a mesh node. If a large mesh node was picked as part of the path and a box was placed inside that mesh node, then I would assume you'd have to do something to avoid that box. You wouldn't want it to invalidate your entire path that you found because the box could be really small inside this one large mesh node.

 

I tried looking for string pulling but didn't find much.

[Chris Paulson]

Hi,

 

I know I like a sound like a stuck record....

 

but recast has the A* algorithm in it so this is already done. I've also written a version that worked with my own abandoned navmesh stuff which is in blitzmax. Along with a A* algorithm you usally need a string pulling algorithm, which again is in recast and I've also wrote in blitz.

 

If you want all the info on navmesh's A* etc read this blog

http://digestingduck.blogspot.com/

 

it will have all you'll ever want to know.

 

Or/and read this PDF:-

 

https://8655380626601746424-a-1802744773732722657-s-sites.googlegroups.com/site/recastnavigation/MikkoMononen_RecastSlides.pdf?attachauth=ANoY7co69z1vjPcvn42QIdX2cYY6w5Qp9HYA8pZiMXS7sWSGoe--OONRdNsxY8F9UUIFFHf2HUBKaYOtxGrfWN6EboojcXsXjnxVyFF-bm2wHBe4tHsq_wYbEYudxkhsiDgEYHQ7biqhOAlawYp6hMP9bwawtKkAw2Qy-gXWs32P0Iym3dkL3TM4ebWiGynr2OU7n1bh6ws1c3xt2ABTT3mQXm94_z0IE8a07kiLoQV4z6_SnZFLLOY%3D&attredirects=0

[Chris Paulson]

Sorry forgot to mention A* is used for walking any sort of graph, the graph could be representing lots of different things such as:-

 

Navmesh

Waypoint graph

Motion graphs

Covermaps

 

Anywhere where you have a node with a link to another node and you can calc getting from A to B using a cost heuristic.

 

Check out http://theory.stanford.edu/~amitp/GameProgramming/ for a good explanation.

[Rick]

Hey Chris, I know the code has this in it, but I guess I would be first looking for a high level description of what things are and why we do them a certain way. I can get the how things are from code, but there is no detail on why generally in code, and it's also a big pain to decode things.

 

 

Along with a A* algorithm you usally need a string pulling algorithm

 

Why? What is a string pulling algorithm?

 

 

I'm almost more wanting to do this myself to learn about what it's doing. I'm also looking for a manual way to place mesh nodes myself in a map and link them and run my algo on it just for learning and testing, but I haven't seen much literature on using path finding methods with a nav mesh explained. Just code.

 

Was hoping someone could give the high level basic idea with nav mesh and A*. Not 10k high, but more like 1k high level. If we go to high I already know that, but looking for a higher level than code at the moment.

[Chris Paulson]

String pulling:-

 

Imagine a 2d square grid and you did a path from one point to another, the path would have zig zags in if you used the centre of each square. String pulling smooths out the zig zags.

 

To help with this, imagine a string tied to a peg and it works its way between lots of other pegs in a loose zig zag way. Now imagine pulling the string so the string is tight against all the pegs. Ta da - string pulling.

[Rick]

OK that makes sense. So now my question would be given each mesh node can be any size, once you find the meshes that you can walk through to get to your goal, how do you get specific points in these meshes to move to that would produce the fastest route and or most realistic route? I can't imagine you would use center points or anything because if you have a large mesh by a T hallway, the center of that could be in the middle of the T and you would get a very 90 degree turning. Is that where the string pulling comes in? It doesn't seem like it from your description that it would provide a more realistic cutting of the corner to turn around the corner.

 

So how do you determine the actual point(s) in a mesh node that is part of your path?

[Chris Paulson]

Actually my description may have been a bit misleading.

 

In a square 2d grid the links to each square is the centre of each edge.

 

Instead of square a navmesh is made of convex polygons, where the polygons touch (the edge) the centre is used.

 

 

This page:-

 

http://theory.stanford.edu/~amitp/GameProgramming/MapRepresentations.html#S9

 

does lots better than me at describing it.

[Rick]

In a square 2d grid the links to each square is the centre of each edge.

 

?? maybe I look at it differently but when I did 2D A* with 2D squares all the same size with the grid being 5x5 for example, I didn't worry about the links between them because you had the information already to know where it's possible to go. I also didn't use any edges. Once I found the 2D squares I simply took each middle point of each square and that was the points I traveled along. So that is where my thinking is coming from.

 

So why would I need to make the edges of the convex polygons the links between them? Could I actually give the information in each polygon where I want it linked to? I would basically link it to the immediate surrounding polygons, but manually via giving it information, or using the LE link system in the editor. I guess the reason I say this is because I'm thinking of just using rectangle planes as the polygons and just place them next to each other and assign the links between them manually. So once I find my list of polygons I use the center of the edge from the previous polygon to the next as my points?

[Pixel Perfect]

I'd say that’s about right Rick, how you store the navmesh nodes and the linking data is pretty much up to you. So long as you can feed it into an A* routine to get your final node traversed list and then retrieve sufficient information to ascertain the mid points of the connecting faces then the simplest route is done. You can apply math to curve through these angle changes if you want to make them slightly more natural but that’s another level of refinement.

 

You can go on then to apply heuristics/costs to apply bias to the path finding. So if an enemy is known to be in a certain area and you want to avoid them or if you wanted to represent traversing high ground as less desirable than low ground then applying values to these areas would make the A* routine less likely to pick them. It's not always about the shortest route

 

If you're looking for a generic A* solver take a look at MicroPather

[Rick]

So if the size of my rectangles are all different sizes and don't share exactly the same edges, how could you get the center point of each rectangle edge to figure out where you need to go?

 

MicroPather, looks sweet btw. Thanks for that!

[Pixel Perfect]

I guess you have to do the math. If you know the size of your rectangle and the position and orientation you should be able to calculate the center edge positions for every edge on every rectangle. This is static data and can be calculated up front so there is little cost in looking this up in real time.

[Rick]

OK, now that I draw some examples out I see that it would be the center point of the next mesh node in the path which is linked to the current node in the path.

 

This will be interesting to see if I can get this working Seems like a cool idea.