I need to perform path finding on a large landscape (10KM x 10KM). I first implemented an a star solution but found I would need way too many nodes for reasonable movement. I''ve now implemented the methods described in game programming gems using a navigation mesh. This allows my npcs to walk anywhere in the navmesh polys (although they slide along the edges of unconnected polys). Why does the method in game programmning gems use astar and this movement method together ? Also just so my understanding is correct, if I go for a navmesh method do I only need the minimum number of polys ? For example if I had no objects on my terrain the navmesh could consist of 2 polys, then each object I add that I need to navigate around I need to chop out and recreate the navmesh adding extra polys. NB. I just need the penny to drop with this stuff, I''ve been a graphics programmer for 6 years and have now moved over to the wonderful world of AI

There are many ways to improve the performance depending on your game and the approach you take.

There are various ways to tweak the algorithm and different approaches to take to avoid using too much memory. A big part of how A* behaves is the heuristics you use and how much you choose to remember. You can get A* to work in real-time with an infinite number of nodes if you don''t use it the right (or best) way..

Remember A* is greedy and always wants to take what looks like the best path. If you can discriminate your terrain in a way to take advantage of it A* will fly through it very fast. It depends very much on your map and whether you need optimal paths or not.

There are also other kinds of search methods you can try too. A* is the creamy one because when you use it the right way it always finds the best path everytime (if there is a path to the goal). But in a game that isn''t always necessary and you might be able to use some other technique that is faster and uses less memory at the expense of not having a perfect path.

I don''t know off hand about the navigation mesh you are using but it sounds like a technique to optimize the search space of your terrain for the A* in some way.

A.I. A Modern Approach by Peter Norvig is a good reference on A* and other techniques.

quote:Original post by PeterTarkus A.I. A Modern Approach by Peter Norvig is a good reference on A* and other techniques.

...was actually written by Stuart Russell AND Peter Norvig.