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.

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

very fast, highly accurate and zlib license.

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.

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.

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.

[quote name='snowmanZOMG' timestamp='1347649223' post='4980142']
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.
[/quote]

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.

[quote name='zar2012' timestamp='1347653301' post='4980158']
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.
[/quote]

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.

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.

thanks everyone. you were really helpfuhl.