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.