Using a navmesh for pathfinding

[olivehehe_03]

I'm starting off a new project and I'm assembling all the tools and techniques I'll need to do it. I'm looking at using A* pathfinding on a navmesh, but there's a few gaps in my understanding that I need a bit of help with.

First of all, I understand the basics of A* and a navmesh, but I'm not sure on the details of how the two work together. I'm able to create a navmesh by doing it manually based off the level mesh, but I'm not sure what information I need to give A* and how to get it from the mesh. So I have a few questions:

1) I know I need to calculate the G and H scores, but what other information would I need? How much can be read from the mesh itself and how much do I need to set manually?

2) All the A* examples I've seen are based on 2D grids and the path is created in the game world by drawing a line which passes through the center point of each square. Is this similar to how it would work on a navmesh?

3) Do I need to know how each polygon connects to the ones around it? As far as I know I do need to know that polygon A connects to B, poly B connects to C and D and so on, but do I need to know the points where they connect?

4) How do I check if an AI entity is on the navmesh? Do I simply do a raytrace downwards against my navmesh to see if it's there? Do I check the same way to see if my path is on the navmesh and not cutting any corners?

I hate to ask so many questions but I have answered a few for myself trying to type this up. I'm just a bit baffled about how to take the step from a square 2d grid to a 3d navmesh. Thanks in advance

[CuteAlien]

I'm starting off a new project and I'm assembling all the tools and techniques I'll need to do it. I'm looking at using A* pathfinding on a navmesh, but there's a few gaps in my understanding that I need a bit of help with.

First of all, I understand the basics of A* and a navmesh, but I'm not sure on the details of how the two work together. I'm able to create a navmesh by doing it manually based off the level mesh, but I'm not sure what information I need to give A* and how to get it from the mesh. So I have a few questions:

1) I know I need to calculate the G and H scores, but what other information would I need? How much can be read from the mesh itself and how much do I need to set manually?

For A* that's all you need. Think of G and H as real distance from origin and estimation of the distance to the target from each point. You should always underestimate the the target distance to get optimal paths. But "optimal" does not necessarily mean "shortest". Your G and (and maybe also your H, though usually not) can also care about more factors than just the way-length. For example you can increase costs for sharp turns to smoothen out paths, or you can give certain parts of your way different factors for example making roads easier to travel than mountains or making already used paths less attractive for a while.

2) All the A* examples I've seen are based on 2D grids and the path is created in the game world by drawing a line which passes through the center point of each square. Is this similar to how it would work on a navmesh?

You will need some graph - A* works on graphs. Using center points of each polygon als graph-nodes makes sense, so you probably want that.

3) Do I need to know how each polygon connects to the ones around it? As far as I know I do need to know that polygon A connects to B, poly B connects to C and D and so on, but do I need to know the points where they connect?

Yes, your graph for A* should consist of polygons which are adjacent. And usually you even want to have both direction,from A to B and also B to A. Knowing the points where they connect is usually practical. It will make it easier to shortcut lines after the A* calculation because you don't have to travel straight lines between polygon centers.

4) How do I check if an AI entity is on the navmesh? Do I simply do a raytrace downwards against my navmesh to see if it's there? Do I check the same way to see if my path is on the navmesh and not cutting any corners?

Hm, yes I think so.

I hate to ask so many questions but I have answered a few for myself trying to type this up. I'm just a bit baffled about how to take the step from a square 2d grid to a 3d navmesh. Thanks in advance

Good luck.

[olivehehe_03]

Cool, theres a few things I don't need to ask about any more.

I was aware that I can add in terrain costs and any other movement related costs onto the G score to help A* work out the optimal path, it's something I was planning on using a little bit, or at least making sure I have the means to use it. That sort of data would be part of my graph if I'm correct, especially since a navmesh would let me define different areas really easily.

Cut out a whole paragraph here cos I answered my own question again, but I've been poking around the tutorial code regarding triangle selectors and just had a bit of a eureka moment. Rather than manually defining connections with an editor, I could create a triangle selector for the scene node and mesh that represent my navmesh, then loop through the array of core::triangle3df that I would get from ITriangleSelector::getTriangles (core::triangle3df *triangles, s32 arraySize, s32 &outTriangleCount, const core::matrix4 *transform=0) to find any triangles that share two points (or where a single line could pass through 2 points from each triangle which would be the case where a smaller triangle meets a larger one) and generate my connections that way. That information could then be saved into a file and loaded into a struct or something similar at load time. The only part I'm not sure about (and I'm at my work computer so I can't test it just yet) is whether the function I mentioned above will give me consistant data, that is, will the 10th triangle in the array always be the 10th triangle in the array, or will it be the 20th the next time I create a triangle selector for it? If not, is there another way for me to identify each triangle uniquely and consistantly? Thanks again.

[aanderse]

i've been doing path finding with a star lately as well and I thought i'd share my approach/experiences.

using the triangles of the level mesh ended up being pretty inefficient and way too much data i found. for even a basic level mesh i was at 13,000 triangles and using those as the nodes in the a star algorithm became way too computationally heavy. connecting the triangles was also not great because of floating point precision. the resulting data (which had to be pre computed and stored because it took a while to generate everything for a star) was pretty big too. it became obvious pretty quickly this wasn't a very great idea.

so instead i decided to take a different approach. I took my level mesh and then cut out all parts of the mesh where the player/ai was not allowed to walk (any obstruction). i was left with a mesh which had a bunch of holes in it. i made the decision that the smallest possible size of an obstructing object would be 1 unit by 1 unit (this number was arbitrary, could be anything). if the smallest possible obstruction was 1x1 then i could project the grid onto a 2d plane and i would have a grid made up of 1x1 squares which were either obstructed on not obstructed for path finding. at this point i created a little program to iterate through the entire grid and find large collections of non obstructed grid points which form a rectangle. i keep creating these rectangles of non obstructed grid points until the entire grid is covered in non obstructed rectangles (and of course obstructed rectangles). i use these rectangles as my a star path nodes. ai can now find its way between these non obstructed rectangles using a star, and within the non obstructed rectangles by using the rule that the shortest distance between 2 points is a straight line (there are never any obstructions in the non obstructed rectangle). simple levels can have as few as 5 or 10 a star path nodes which means your path finding is basically free on the cpu.

in this image the black filled rectangles are areas i've cut out of the level mesh for path finding - no one can walk there. the red areas are the non obstructed rectangles (which i created from slicing up the level mesh). the blue lines represent a connection between 2 of the rectangles (a star needs to know how 2 nodes are connected of course).


this image is an actual screenshot of the implementation which i've added some marks to. you see an actor standing on grass but you also see some holes in the world. i'm displaying the path finding mesh, not the level mesh. the level mesh will have a big box, or some other obstructing object instead of a giant hole in the world. i drew blue lines around some of the non obstructing rectangles. the beginning of the yellow curse is where my player started, and the end is where they clicked. the player only had 2 path finding nodes so this was dead simple for a star to solve. the yellow line is how the player would move after i smooth their movement (so the player doesn't just run in a straight line, looks a little more realistic, etc...).


i hope this post was informative.

[olivehehe_03]

Yeah I understand what you mean. The level mesh as a whole has a whole bunch of polygons that A* doesn't really care about. To make the navmesh I was look at just taking everything except the 'floor' polygons out of my level mesh then getting rid of any extra polys that I don't need out of that.

All I have to do now is actually sit down and code some of this

[aanderse]

All I have to do now is actually sit down and code some of this

not all of it. stlastar is an awesome implementation of the a star algorithm in c++ using templates. incredibly easy to use:

http://code.google.com/p/a-star-algorit ... mentation/

[link3rn3l]

Yeah I understand what you mean. The level mesh as a whole has a whole bunch of polygons that A* doesn't really care about. To make the navmesh I was look at just taking everything except the 'floor' polygons out of my level mesh then getting rid of any extra polys that I don't need out of that.

All I have to do now is actually sit down and code some of this

NAVMesh and Astar simple..

please use a great Inexin Library... Opensource

http://inexin.sourceforge.net/


Argortha Lib

http://sourceforge.net/projects/argorha/

OpenPf Lib

http://openpf.svn.sourceforge.net/viewvc/openpf/


I try to implement to irrlicht but not have time, please
share the code when you finished .. thanks!!!

[link3rn3l]

Recast Nav

http://code.google.com/p/recastnavigation/


..