I have been researching path-finding for 2D games and would like to create a system that allows A* to perform as best as possible over a near infinite world. This system is intended to manage not only the player's character but other AI that would wander the world in search of resources.

So far I have made grid based A* that I then modified into Theta* to smooth out the path. But I would like to change that to use navmeshes so I can reduce as many nodes as possible. I have looked in to delaunay triangulation and fortune's algorithm for voronoi but am unsure how that works on a large scale where I would want to generate more navmesh as the world is explored.

I have also considered quadtrees but they seem slower then navmeshes.

So my main question is, what would work on a near infinite procedurally generated world? And what is fastest quadtrees or navmeshes? If navmeshes are faster, are polygons better than triangles?

Thanks for any help!


As you shall see, the spirit of this answer is that, in game programming, there is rarely a dead-on answer like A is always better than B. But let's dive a bit more into the details.

So my main question is, what would work on a near infinite procedurally generated world?

Any would work. It depends on many other characteristics of your game, for example (but not exhaustively): will it have big open areas or will it be always packed with obstacles? Do you need information about the traversal cost of terrains everywhere or nowhere at all? As you see, that question is way too general to be answered.

And what is fastest quadtrees or navmeshes?

First things first: quadtrees are not a specific path-finding search space type. They are, in your context, a spatial partitioning technique. It means, in your tile-based search space type, they allow you to group similar tiles into greater areas, to reduce the number of similar tiles.

So, whether searching trough quadtrees of nodes or navmeshes will be faster, it depends on how much reduction of the search space the quadtrees will achieve in your particualr types of maps. I.e. which will leave you with fewer nodes in the graph where path will be searched for. In practice, in my experience, it will be very rare that quadtrees will end up with fewer nodes than navmeshes, because where quadtrees offer their biggest advantage over simple tile-maps, i.e. open areas, is precisely where nvameshes excel too.

However, in the case of a procedural map where navmeshes have to be built on the fly, you have to also consider the cost of building it. That is particularly important because you will be erasing parts of the map from memory when they are out of scope and rebuilding them again when player gets closer. Which means, you will be generating and probably regenerating the path-finding maps (no matter if using tiles or navmeshes) all the time.

In that regard, quadtrees are much faster, no doubt. It will be much faster to construct the quadtree of tiles in the new map areas being generated than it will be to calculate the navmesh for such new area. That means, you have to take both things into account: the time it takes to build each solution on the fly and the time it takes to use each solution when finding paths. Both things can become a bottle-neck.

Which means that, ultimately, there is no a priori answer to that. It both depends on how the characteristics of your maps, so as always, you will have to try both and profile. Always profile! That is the only way you can be assure of what works best for your specific game.

If navmeshes are faster, are polygons better than triangles?

If you are storing only the center triangles/polygons, than polygons will give you much smaller search spaces (i.e. faster to traverse when searching for a path) than triangle-based navmeshes. However, when storing just the centers, it becomes harder to smooth the path after searching the path (like Theta* does in relation to A*).

So, often other points are stored, like the vertices of triangles/polygons and even the middle point of triangles/polygons' edges. In these cases, it becomes unclear whether polygon-based navmeshes will still give you the desired less nodes than polygon-based navmeshes. It begins to depend on the characteristics of your map again. My personal experience is that, if you are storing vertices, middle-edges and centers of the triangles/polygons, than the narrower are the walkable areas, the better the navmeshes become. Conversely, the broader these areas are, the better the polygon based become.

But in general, polygon-based nvmeshes end up giving less nodes (i.e. being faster to serach for paths). On the other hand, again, in a procedually generated map, you can't forget the cost of bulding the navmesh. And it is much faster to generate triangle-based navmeshes than polygon-based.

I would want to generate more navmesh as the world is explored

This will be particularly harder to implement with navmeshes than with tiles and quadtrees. Because than it becomes not only a problem of generating navmesh, but of updating dynamically the navmeshes that were already generated. It is feasible, but not easy to program (for instance, Unity's and Unreal's navmesh system do not come with the possibility of dynamic updates).

I am unsure how that works on a large scale where I would want to generate more navmesh as the world is explored

No matter which technique you end up choosing, you will likely end up needing to implement it hierarchically. I mean, when maps currently on screen get bigger, the better way of making it faster to find a path is to give the algorithm less area to search. Take a look at this similar question and at its answers: What is the most appropriate path-finding solution for a very large proceduraly generated environment?

  • \$\begingroup\$ I was thinking each one would have advantages and disadvantages, but I wasn't sure if one would stand out among the rest. I'm thinking of going with a navmesh and saving the mesh in chunks so it can be loaded instead of being generated again. \$\endgroup\$ – Sterling Feb 24 '16 at 22:39
  • \$\begingroup\$ @Sterling Try and see if the navmesh generation does not harm performance. If not, and if you have large open areas, then probably navmesh will be the right tool. Also, if you choose the navmesh, you should certainly follow the "per chunck" approach. As for saving the generated navmesh, the problem is that then, your infinite world is not infinite anymore: it gets bounded by the practical limitation of how much hard disk memory it will cost for a player to have those stored after hours of gameplay. I'm not saying it won't work, just that you have to keep that in mind. \$\endgroup\$ – MAnd Feb 24 '16 at 22:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.