Implementing an automatic navigation mesh generation for 2d top down map?

Question

I am currently in the middle of implementing an A* pathfinding for enemies. In order to implement the actual A* logic, I need a navigation mesh for my map.

I am working on a 2D top down rpg map. The world is static, meaning there is no requirement for dynamic runtime mesh generation. My world objects are freely placed (not snapped to grid), rotated and scaled, which means that using a grid based A* is going to be a little complicated.

For example, how would I know a grid tile contains a collidable object? Lets say that object is actually located on the tile next to this, but is rotated and scaled such that it is still blocking the way?

I could check for the middle pixel of the grid tile to see if it contains any of the nearby objects color data, but it still wouldn't be all that accurate and occasionally enemies could get stuck in between objects.

Answer 1

From what I understand of your question, you are trying to figure out how to make a navmesh out of a tile-/grid-based terrain.

Well in fact, tiles/grids are inherently easier to work with, and one way or another you are going to have to apply A*, but you can apply it just as easily to a grid as you can to a navmesh. The point being that A*, like any graph search algorithm, operates on graphs. A navmesh is a graph, and so is a tile grid (although more densely and regularly connected).

I'd suggest that you simply focus on doing pathfinding in a grid, unless you believe there is some substantial gain to be had by using a navmesh (I don't).

And if you do, then a possible way is to generate a navmesh first, then rasterise its polygons by filling them in with tiles of different types (you'd use point-in-polygon checks for this). Now you'd have a tile based world, but you'd also have a nice navmesh already present and in agreement with the tiles. It's harder to do this the other way around, IMO (produce navmesh from tiles, which I think you are suggesting). Caveat: The problem here is, well, creating a planar navmesh graph. Not really that easy, I'm afraid, unless you have some ideas of your own. The graph planarity problem is one of the hardest problems in computer science. Hence: Use a grid.

EDIT I am guessing (I have to guess a lot here!) that the reason you might prefer a navmesh over a grid is because you want creatures / objects to be placed or to roam "pixel-freely" rather than snapping to grid cells. Well I would still recommend sticking with the grid, but maybe flood-filling certain areas with a code to say, "this is zone 1", "this is zone 2" etc. That way you can limit your entities to ranging about in a given zone. To remove the aliasing effect of a grid, you can also introduce minor variations to the centre point of each tile, so that it looks less regular when you entities move. Just a thought.

Answer 2

If you want to precalculate the paths (and it fits in memory), you might want to check out some kind of all pairs shortest paths algorithm, like the Johnsons algorithm and stock away all paths in a container where the key is the start and end positions.

Reading the edit Nick Wiggill posted, this won't help you make 'pixel perfect' paths though.

If you want to do a true 2D-Navmesh (and not precalculate the rotation etc and set those overlapped grids to pass or block, which I would suggest) you need to:

Rotate, Scale and Transform your blocking rectangles/meshes, to new 'meshes' and then use Boolean unions on all the overlapping ones and there you are, a nav mesh in 2D.

Answer 3

The key premise to maintain is that navigable regions should not contain collidable objects. In a tile based representation, this means that if a tile contains any collidable object, that tile is impassable to all game entities. Collide against this navigation map, rather than the objects that were inserted into the map, and you avoid your problem.

You will encounter efficiency problems, as tiles may end up being marked as impassable when only a small part of the tile is obscured by a collidable object. Decreasing the size of your tiles will improve this, at the cost of more tiles, and with that higher memory usage and search times.

Depending on the size of your world, distribution of obstacle sizes and rotations, this may make a purely tile based solution impractical, but remember, you can always adjust your world design to fit your technical constraints.