Jump to content
  • Advertisement
Sign in to follow this  
moeen k

Techniques Used In Navigation Of Games

This topic is 876 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts




im researching on game navigation and path finding. I need some questions to be answered.



really navigation mesh is simply a A* behind it? just that? so navigation mesh is only places agent can go and only graph of empty objects that agent can move from one to another?


are grid A* so big that covers all the place or they are less?


is a matrix really good data structure to save info ofconnections and distance into them? for example calculating in every frame distance of every element of graph in matrix from player cat be very efficient.


im searching to use ACO algorithm in some part of my implementations for less predictablity and more realism. don't know it can be a good approach.

please give me some information you know about optimized implementation of navigation in games.

thank you for helping.


Share this post

Link to post
Share on other sites

The Navigation mesh relies on just a bit more than A* when you near the end of your point, or for optimizations. But yes, that's pretty much all there is to it. A* or what ever other graph search method you use is what drives it.

Grid A*'s are infinitely spanning grids that details the map. Normally the grids have uniform costs, but they can also have adjusted costs. Grids are generally more popular for point and click games, or stratergy based games as they make it incredibly easy to query data about the world.


By Matrix I assume you mean the adjacency matrix. There's no good answer here. It's just it depends. The cost of the adjacency matrix is more significant than the cost of an adjacency list. Or other graphing structures. The adjacency matrix is not designed to be sparse. But it does have it's uses. Memory look up on it is fast and predictable so cache misses are not so likely. But it's probable that you'd rather take the cost of speed than memory complexity.

But generally, before you think about efficiency. Just remember that standard A* generally isn't efficient to begin with with larger sets of data. The algorithm searches radially outwards... which means it's checking a lot more data than some other search queries for far away points.

As far as ACO algorithms go... it's implementation is worthless if you're not dealing with swarms of agents.


For optimizations. Generally Navigation is expensive all on it's own. Which is why it's often not so uncommon for developers to take short cuts.

For a lot of games that uses pure A*, it's because the actors do not have to travel far. This is seen a majority of the time with FPS games. The targets are mostly stationary... or only moving short distances. Their life span is only a few seconds.

For your games with more complex levels or larger worlds... they usually break it up. Forgo the use of A* completely and use a different search algorithm (The shortest path is often times not the best or the most realistic path). Or very literally teleport agents around the map.

Edited by Tangletail

Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!