Game Development Stack Exchange is a question and answer site for professional and independent game developers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
This question needs work. 1. What do you mean by pixel-based, not tile-based? Tiles typically are pixel-based. Do you mean they are free-floating, not snapped to the tile grid? 2. You jump from talking about 2D and pixels, to vertex data, I guess you mean for the navmesh? 4. You are not making sense in your third paragraph at all, apologies, but that's the only way I can express this. 3. Your question is about AI, nav meshes, and generation, so why are you talking about 2D, pixels, color? These are render-related and have no bearing on nav meshes. Suggest you try to make the question concise. – Arcane Engineer Oct 28 '12 at 21:35

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.

share|improve this answer
I have rephrased my initial question a bit. Hopefully its a little more understandable at this point. Introducing variatons to the center of each tile is actually a really good idea and would help in improving 45 or 90 degree turns to look a little bit better. Going the grid based A* would definitely be a lot easier and I can easily get my head around it, but there are still the problems described in my initial question. – J2V Oct 29 '12 at 13:04

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.

share|improve this answer

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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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