Triangles or Squares?

I used triangles for the nodes in my first nav mesh. This was very instructive because triangles don't make a very good nav mesh. Let me give you a few reasons to use squares over triangles.

Nav mesh nodes should be about the same size. If you use various size triangles and run A* from the centers, you don't always get the shortest path. Weird huh?

Look at the picture and find shortest path from you to your destination between triangle centers (the red dots). Did you go left around the tree? That’s what the A* path finder will do. The shortest path from you to your destination is obviously a straight line, not the long way around the tree. At first I though this issue was mostly theoretical, but you actually notice guys taking the wrong path when you see them walking on a mesh like this.

Triangles don’t tessellate evenly. Even if you make all the triangles the same size, the line between triangle centers isn’t straight. It zigzags:

Triangles don’t approximate guys very well. Since we want to run A* around guys they need to mark nav mesh nodes as occupied. If you mark the one triangle under the guy you end up with a jaggy pattern that is very unintuitive. It would be hard to explain to my testers what was going on.

In my current nav mesh implementation I use 2.5 ft squares. This seems to work ok. Human-sized guys occupy one node, which keep them reasonable far apart. The background artists complain that they have to align their art to a 2.5 foot grid, but they are getting the hang of it. Diagonal and curved walls are a little annoying, but the grid is small enough that you don’t really notice when playing.