Raindrop Method

So how do you take background scene and turn it into a navmesh? I use a technique we call the “Raindrop Method”. Pretend like raindrops are falling on the background every 2.5 feet in a grid pattern. I shoot a ray through the scene’s octree to find where all the raindrops land. This will make a simple heightmap style nav mesh.

The background artists specify the “walkable” flag for each “subobject”. A subobject is what we call the collection of similar polygons that you can draw in one draw call. So an artists turn off the walkable flag on subobjects that are purely visible and not meant to change the nav mesh. A good example is to mark a small root as non-walkable so that the player doesn’t pop up and down when they walk over it.

It is a little odd that the navmesh and the graphics both use the same subobjects for different purposes. Every now and then you have to cut a subobject into two so you can have a walkable and non-walkable part. This adds an extra draw call which effects render performance. But having done this for a while, it seems like a reasonable simplification. The bigger problem is that our scenes have hundreds of subobjects in them, so it’s actually a pain to set all these flags. We have a pretty complicated tool dialog box that let you find subjects and mark them all at once. The other really useful thing we did is to have a mode where we draw the scene with subjects highlighted that have certain flags sets. This is a really easy way to see if the flags are set wrong in an area.

For a lot of the nav meshes in our game this is exactly what we do. But we also support full 3D situations with things like bridges that you can walk over and under. A simple heightmap navmesh will not work for this.

So what I do is have the raindrop not only hit the first polygon but also hit everyone polygon below. Now things get a little more complicated. I have this concept of “head bump height”. This is the height above a walkable surface that must be clear of other polygons. Since my game has mostly human-sized characters I used 8 feet for my head bump height. Here’s an example with a bridge:

The left and right raindrops won’t create a navmesh point on the lower ground. You’ll end up with one navmesh square between the two center navmesh points under the bridge. You’ll also get three navmesh squares on the top of the bridge. But wait… you might get some navmesh squares on the inside of the bridge too. That’s not what we want.

To fix this little problem, we have another flag on subobjects called “collidable”. Collidable subobjects will block navmesh points from getting created below them without allowing a navmesh point to be created on them.

I’m a coder, so I think in algorithms. Here’s where we are so far:

1. For each grid point


• Find raindrop intersections


• Remove all the intersections where you bump your head.


• Remove all the intersections with non-walkable (collidable) subobjects.


2. For each grid square


• Make navmesh squares...

It’s not hard to make navmesh squares from the intersection points. I just find 4 nearby points that aren’t too far vertically from each other. I use 45 degrees as my limit, which is 2.5 feet between points.

Now this is all good except that some navmesh squares have collidable stuff in them that the raindrops missed. Calvin, my sneaky background artist, once put one of those old fashioned radiators in the middle of two navmesh nodes. The characters can’t walk through the radiator, but the raindrops didn’t hit it.

Now I could tell Calvin to move the radiator, but I don’t like telling Calvin to take his pretty art and change it for technical reasons. So instead I remove navmesh squares that have collidable polygons above. I use the octree again, but this time I use a box (green in the picture) to intersect the scene. I have to pull the box a little off the ground because I don’t want it intersecting with rolling ground. I make the box 1 foot above the highest corner and 8 feet tall.

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.

Navigation Meshes and Artists that Love Me

I really hate it when I see guys z-clipping against each other in a game. We’ve been doing 3D games for a long time now and we have some good solutions for this problem. I use a thing called a navigation mesh. It’s a surface that guys walk on. I run A* path finding on the nav mesh so the guys can walk around each other without walking on top of each other.

Nav meshes are really fascinating things. Well, they fascinate me anyway. One reason for that is the complete lack of published information about them. There are a few tidbits here and there, but I’d be much happier with a full chapter in a Game Gems book. I’m writing about my experiences with nav meshes with the hope that some of you reading this will do the same.

Ok, so how do I make the nav mesh surface? That’s a good question. Let me start by explaining some ways bad ways to go about making a nav mesh. My favorite background artist at work is a guy named Calvin. He makes pretty things. Some of those things characters walk on. So why don’t we just use his 3D models as a nav mesh?

Reason #1: Calvin is good at making pretty things. He is bad at making technical things. Calvin knows what T-junctions are but has them all over his pretty backgrounds anyway. Now renderers hardly skip a beat with T-junctions, but I can’t keep my path finding algorithm from puking on them. I could tell Calvin to: quit making T-junctions, make all triangles about the same size, and have no vertical triangles. But I want Calvin to like me.

Reason #2: I’d rather have more art. Maybe you’re fortunate enough to be working on a game that has enough art. Man, I’m jealous of you. But I’m working on a 4+ year project that has plenty of programmers and not enough artists. Pretty much all new AAA titles are having this problem now. So I’m not gonna waste my artist’s time making crappy old nav meshes.

Reason #3: I have a lot of control if I auto-generate the nav mesh. I’ve gone through so many iterations of different types of nav meshes, it’s nice to be able to completely redo it without bugging Calvin much.

So at the end of the day, I’d rather let Calvin work on art and I’ll make the nav meshes myself.