Jump to content

  • Log In with Google      Sign In   
  • Create Account


Navigation Mesh Generation


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
10 replies to this topic

#1 zar2012   Members   -  Reputation: 137

Like
0Likes
Like

Posted 14 September 2012 - 09:04 AM

I've designed a grid-based pathfinding system for a terrain but when the agents on the terrin grows in number, the pathfinding performance falls down. so I decided to generate a navigation mesh. I studied some articles in AI books and search on the internet, read forums but the problem is that I've not figure it out yet where I should start to generate a navigation mesh.

should it be generated automatically or manually? what does it have to do with delaunay triangulation? what is the first step to generate a navigation mesh at all?

now if anybody could help me on this I will be very grateful. I really need to know about these things.

thanks anyway.

Sponsor:

#2 saejox   Members   -  Reputation: 714

Like
0Likes
Like

Posted 14 September 2012 - 10:02 AM

http://code.google.c...castnavigation/

very fast, highly accurate and zlib license.

#3 zar2012   Members   -  Reputation: 137

Like
0Likes
Like

Posted 14 September 2012 - 10:35 AM

http://code.google.c...castnavigation/

very fast, highly accurate and zlib license.


thanks saejox. I know about recastnavigation. but what if I want to programm my own navmesh generator? that is what I would exactly like to do and that is what I need help for. programming a navmesh generator from scratch.

#4 snowmanZOMG   Members   -  Reputation: 807

Like
0Likes
Like

Posted 14 September 2012 - 01:00 PM

Are you sure the grid representation is the cause of slow performance? I'm not convinced that going to a navigation mesh just on the grounds of performance is the wisest idea. The performance of your graph search depends on many factors, and people often assume it is their representation that is at fault, when it may not be the case. The layout of your data structures for the graph can have an enormous influence on the performance of your graph initialization. Your underlying data structure for the priority queue can also have a large effect on performance.

The nav mesh may be a better choice if you notice that performance degrades significantly as the pathable area increases, since nav meshes can be less sensitive to area. But your observation of the performance being reduced when the number of agents increases, makes me believe that a nav mesh will not necessarily improve performance. This implies that your graph initialization is slow or your graph search is slow due to a poor choice in a key data structure. Possibly even the heuristic.

Bottom line is, I'm not sure it is worth switching over to a nav mesh. Unless you have prior experience, you'll spend a significant amount of time trying to set up the navigation mesh and then altering the search portion to account for the nav mesh. When you finally have it done, you may come to discover it's not that much faster than your original implementation since it may still have the root problems that cause slow performance as your original.

#5 zar2012   Members   -  Reputation: 137

Like
0Likes
Like

Posted 14 September 2012 - 02:08 PM

Are you sure the grid representation is the cause of slow performance? I'm not convinced that going to a navigation mesh just on the grounds of performance is the wisest idea. The performance of your graph search depends on many factors, and people often assume it is their representation that is at fault, when it may not be the case. The layout of your data structures for the graph can have an enormous influence on the performance of your graph initialization. Your underlying data structure for the priority queue can also have a large effect on performance.

The nav mesh may be a better choice if you notice that performance degrades significantly as the pathable area increases, since nav meshes can be less sensitive to area. But your observation of the performance being reduced when the number of agents increases, makes me believe that a nav mesh will not necessarily improve performance. This implies that your graph initialization is slow or your graph search is slow due to a poor choice in a key data structure. Possibly even the heuristic.

Bottom line is, I'm not sure it is worth switching over to a nav mesh. Unless you have prior experience, you'll spend a significant amount of time trying to set up the navigation mesh and then altering the search portion to account for the nav mesh. When you finally have it done, you may come to discover it's not that much faster than your original implementation since it may still have the root problems that cause slow performance as your original.


Well since a navmesh's nodes are much less in comparison to a grid's, I thought it will be more useful to spend time on it to generate. actually we are a team programming a 3d game engine and we don't want to step in the wrong way.

I think you're right about the performance. I exmined the situation and found out that we run the pathfinding on the same thread as the game and AI was running and I suppose we should have it being run on a separate thread.

But again, as we are designing a 3d game engine we do not want to start our work with a grid representation and in the middle of the work (maybe some months later) we notice that we should change our pathfinding system.

So I take your advice and will examine the current situation more accurately but I think you agree with me that a navmesh would be really really faster than a grid representation in similar circumstances.

#6 zar2012   Members   -  Reputation: 137

Like
0Likes
Like

Posted 14 September 2012 - 02:11 PM


Are you sure the grid representation is the cause of slow performance? I'm not convinced that going to a navigation mesh just on the grounds of performance is the wisest idea. The performance of your graph search depends on many factors, and people often assume it is their representation that is at fault, when it may not be the case. The layout of your data structures for the graph can have an enormous influence on the performance of your graph initialization. Your underlying data structure for the priority queue can also have a large effect on performance.

The nav mesh may be a better choice if you notice that performance degrades significantly as the pathable area increases, since nav meshes can be less sensitive to area. But your observation of the performance being reduced when the number of agents increases, makes me believe that a nav mesh will not necessarily improve performance. This implies that your graph initialization is slow or your graph search is slow due to a poor choice in a key data structure. Possibly even the heuristic.

Bottom line is, I'm not sure it is worth switching over to a nav mesh. Unless you have prior experience, you'll spend a significant amount of time trying to set up the navigation mesh and then altering the search portion to account for the nav mesh. When you finally have it done, you may come to discover it's not that much faster than your original implementation since it may still have the root problems that cause slow performance as your original.


Well since a navmesh's nodes are much less in comparison to a grid's, I thought it will be more useful to spend time on it to generate. actually we are a team programming a 3d game engine and we don't want to step in the wrong way.

I think you're right about the performance. I exmined the situation and found out that we run the pathfinding on the same thread as the game and AI was running and I suppose we should have it being run on a separate thread. But again, as we are designing a 3d game engine we do not want to start our work with a grid representation and in the middle of the work (maybe some months later) we notice that we should change our pathfinding system. So I take your advice and will examine the current situation more accurately but I think you agree with me that a navmesh would be really really faster than a grid representation in similar circumstances.



#7 snowmanZOMG   Members   -  Reputation: 807

Like
0Likes
Like

Posted 14 September 2012 - 03:10 PM

Well since a navmesh's nodes are much less in comparison to a grid's, I thought it will be more useful to spend time on it to generate. actually we are a team programming a 3d game engine and we don't want to step in the wrong way.

I think you're right about the performance. I exmined the situation and found out that we run the pathfinding on the same thread as the game and AI was running and I suppose we should have it being run on a separate thread.

But again, as we are designing a 3d game engine we do not want to start our work with a grid representation and in the middle of the work (maybe some months later) we notice that we should change our pathfinding system.

So I take your advice and will examine the current situation more accurately but I think you agree with me that a navmesh would be really really faster than a grid representation in similar circumstances.


Again, it depends. If the nav mesh results in a drastically smaller number of nodes to search (which is usually the case), you will of course gain some performance. But if you were to end up with a similar number of nodes, you may not see a performance improvement and have done a ton of work for effectively no gain.

I do agree that navigation meshes are "better" in some sense, but don't be so quick to drop your current implementation if they suit your needs already and your performance is the only thing that's an issue. A grid based approach has advantages due to their simplicity. The simplicity does have its own cost though, such as more sensitivity to area if you have a uniform grid and the need to have a higher number of nodes if you wish to have high accuracy.

When going to a navigation mesh, you'll often find that you have to do more than a graph search as well to get some decent results. When I switched my pathfinding to use a navigation mesh, I had to implement string pulling and add in some extra logic to detect when units of non-zero radius were pathing through the level (which is non-trivial, many people end up with multiple navigation meshes to handle this).

It sounds to me that you may benefit greatly from navigation meshes, but in ways other than performance. Unless you reduce the number of nodes you have drastically, you won't see that much of a performance improvement.

#8 zar2012   Members   -  Reputation: 137

Like
0Likes
Like

Posted 14 September 2012 - 11:21 PM


Well since a navmesh's nodes are much less in comparison to a grid's, I thought it will be more useful to spend time on it to generate. actually we are a team programming a 3d game engine and we don't want to step in the wrong way.

I think you're right about the performance. I exmined the situation and found out that we run the pathfinding on the same thread as the game and AI was running and I suppose we should have it being run on a separate thread.

But again, as we are designing a 3d game engine we do not want to start our work with a grid representation and in the middle of the work (maybe some months later) we notice that we should change our pathfinding system.

So I take your advice and will examine the current situation more accurately but I think you agree with me that a navmesh would be really really faster than a grid representation in similar circumstances.


Again, it depends. If the nav mesh results in a drastically smaller number of nodes to search (which is usually the case), you will of course gain some performance. But if you were to end up with a similar number of nodes, you may not see a performance improvement and have done a ton of work for effectively no gain.

I do agree that navigation meshes are "better" in some sense, but don't be so quick to drop your current implementation if they suit your needs already and your performance is the only thing that's an issue. A grid based approach has advantages due to their simplicity. The simplicity does have its own cost though, such as more sensitivity to area if you have a uniform grid and the need to have a higher number of nodes if you wish to have high accuracy.

When going to a navigation mesh, you'll often find that you have to do more than a graph search as well to get some decent results. When I switched my pathfinding to use a navigation mesh, I had to implement string pulling and add in some extra logic to detect when units of non-zero radius were pathing through the level (which is non-trivial, many people end up with multiple navigation meshes to handle this).

It sounds to me that you may benefit greatly from navigation meshes, but in ways other than performance. Unless you reduce the number of nodes you have drastically, you won't see that much of a performance improvement.


What you said led me to the conclusion that we must fisrt implement a navigation mesh to see if it could be useful or not and there is no prediction. still, I need to know the great benefits of using navigation meshes because almost everywhere I've read that they are more efficient and I don't have any prior experiences about it.

#9 pandaa   Members   -  Reputation: 178

Like
0Likes
Like

Posted 16 September 2012 - 07:49 AM

I am developing a RTS game, and replaced the grid pathfing with navmesh for the performance reason. But the new problems comes, handling dynamic obstacle is not so effecient in navmesh.

#10 zar2012   Members   -  Reputation: 137

Like
0Likes
Like

Posted 17 September 2012 - 06:05 AM

thanks everyone. you were really helpfuhl.

#11 snowmanZOMG   Members   -  Reputation: 807

Like
0Likes
Like

Posted 17 September 2012 - 04:05 PM

If you're going to use a navigation mesh, you should definitely do some automatic generation. The automatic generation can be tricky depending on what your mesh actually uses, since the performance of your pathfinder will greatly depend on the quality of your mesh. If you already have a triangulation of the pathable area through a 3D level, you could probably use that as a starting point and then do a mesh simplification algorithm to reduce the number of triangles into a set of equivalent covering convex polygons. You can look for the Hertel-Melhorn algorithm which does such a thing (but not optimal).

You need to know the pathable area of your levels for you to be able to do this. Could be either marked up by a human or you have some procedure to generate your terrain in which you should be able to distinguish between walkable and unwalkable areas. Once you have this, you need to figure out what the 2 or 3 space representation is of this area actually looks like so you can extract out point data. Even in 3D games, you can usually just simplify this down to basically a 2D problem and build an abstract graph that still retains all of the traversable areas in the 3D space.

If you just have some point data which describes points within the walkable areas of your map, you could do a constrained Delaunay triangulation to get you first mesh and then simplify it later. The Delaunay triangulation, I've read is useful for a variety of reasons but I haven't actually used it myself for pathfinding, so I can't really say much of my own experience. The Delaunay triangulation provides certain properties which seem nice for pathfinding, such as avoiding really long and skinny triangles. The constrained Delaunay triangulation is different in that it allows you to specify edges which must be a part of your triangulation, but this also forgoes the guarantee of the Delaunay property since you may be forcing an edge which breaks the property.

To be quite frank, this seems like a lot of work just to get performance. I actually went down a similar road, and my navigation mesh doesn't use triangles at all. It's basically a grid based pathfinder where the grid cells can be an arbitrary size. The navigation mesh generation I do is very simple and can lead to bad edge cases, but I'm totally cool with what I've got for my game. It was much simpler than having to write up and test all of these other algorithms for triangulation (I have a 2D game and I have no triangle data for my levels; the levels themselves are built up from tiles).

To get a decent path out of your navigation mesh, you'll also need to do some string pulling. Check out the funnel algorithm for info on that if you don't know what that is (http://compgeom.cs.u...topic-paths.pdf section 2.2.4). Mikko Mononen also has an excellent, and simple implementation of the funnel algorithm described here: http://digestingduck...-algorithm.html.

Be sure you arrange your data structures in a way that you can initialize the graph in a fast way. I've found that often the slowest part of the A* pathfind isn't even the graph search. People seem to write their graph representation in a way that makes the graph initialization slow. I was one of those people. When I rewrote my pathfinder, I wrote my graph representation in a structure of arrays format which allowed for me to get super fast memcpy()/memset() initialization calls. That alone helped me improve reduce the initialization time for my pathfinding by a factor of 5 to 10. The improved data layout also undoubtedly helps in the graph search portion as well, but to a lesser degree. You can also do some tricks to make the graph initialization even faster (I still touch every single node in the graph). I'm aware of some tricks, but not the details, where you can consider graph nodes to be initialized by checking a count value and comparing it to another count value and depending on that comparison, the node is considered initialized or uninitialized.

Edited by snowmanZOMG, 17 September 2012 - 04:06 PM.





Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS