So I've been developing an FPS bot framework for the last couple years as my hobby. It is an engine/mod independant bot framework that currently supports Half-life 2, Quake4, and Enemy Territory. I've been using a simple waypoint based navigation graph all along so far, and while it is a decent navigation system I'm about ready to move to something better, namely a navigation mesh type system. I've been experimenting with some methods for a few days now with damn good results so far, however there are some issues that I'm not sure how I should address. First, to give a rundown on the situation. My bot is in a seperate dll from the game engine, and because it is independant of the game engine, and because a modder typically doesn't have access to the raw map geometry, and because I have no desire to hack map formats to pull the raw geometry I have the limitation that the navigation mesh I generate pretty much needs to be generated another way. Also since my bot is engine/mod independant, using one of the navigation solutions built into a particular engine isn't an option. This rules out using AAS for Q4 and the HL2 nav mesh. The generation technique I'm using has very similar results to the HL2 nav mesh that was built into CS:S with the bots. Their sectors are axis aligned rectangular areas as well. For anyone interested load up a CS:S map and type nav_edit 1 in the console. I'm pretty sure they do most of their work by directly examining the walkfaces of the map, so my situation will probably need an alternate solution. The technique I'm currently using is a 3d flood fill method, where the map is flood filled with collision checked AABB grid cells about 1/4 the size of the character. This provides excellent coverage, and I can rather easily set up the grid cells to tolerate vertical discrepencies that coincide with the players stepheight and jumpheight. In addition I automatically detect water nodes and nodes that touch ladders for later use. I can exchange speed for smaller grid cells if more accuracy is desired. Here is a picture of a section of a map after this initial step. Keep in mind this is a pre-processing step, and this gets optimized down. Step 2 is what I call the sectorization process. This process is essentially the merging of the above generated grid cells into large rectangular sectors. Here is the same area after sectorization. The results are pretty good. The entire map is sectorized from a little over 50,000 flood fill nodes to 630 sectors, which is pretty good number wise. Anyways, on to the questions. I'm not happy with the handling of slopes, ramps, and non axis aligned areas. Obviously since the technique is primarily axis aligned, the sectors generated for a non axis aligned room is pretty sloppy. Typically non AA rooms are filled with many long thin sectors. The main issues I'm trying to overcome now is: 1) How to generate more optimal room sectors. The pics are pretty good examples, but in some cases a longer sector can be generated that extends through one room through another. Ideally a sector will only belong to 1 'room'. How do you detect 'rooms' for this purpose? Also, how would one detect the small hallways or portals that connect larger rooms? If I can identify a 'room' and begin the sectorization in the corner of the room, I think it would provide larger room covering sectors that have a better chance of staying in the room. My sectorization algorithm alternates expanding each edge of the AABB until it cant anymore, North, East, South, West, rinse repeat until we cant expand any of them anymore. Depending on the starting node of the sectorization, it might extend into the hallway and keep going into the next room before it has a chance to trap itself into the starting room. Somehow detecting the corner of the room seems like the best way to get it to flood only the room. 2) How to handle non axis aligned map geometry. For non axis aligned rooms, they seem to mostly generate long thin diagonal sectors, so I'm looking for ideas to either merge them into more optimal ones, or to better generate them to begin with. It seems like for non axis aligned rooms, starting sectorization as close to middle of the room as possible should potentially build the biggest inner room sector. I get a feeling that simply picking better sectorization start nodes can go a long way toward generating better sectors, but I'm not quite sure how to do so, since I'm not quite sure how to detect what one might consider a 'room'. One idea I had is to choose sectorization start nodes by looping through all of the flood fill nodes and doing 4 raycasts along each axis, and choose the node with the highest accumulated distances of the rays, as a simple detection of the middle of a room. Perhaps this can be varied to detect corners as well. Another idea I had is to loop through all the nodes again, and do an in-place volume raycast, and expand the AABB volume until it hits something, and choose the node with the largest expansion as the start node to sectorize. Since it would expand in all 4 directions this should be a rather reliable method of middle of the room detection with the added benefit of having a good idea of the room corners as well from the resulting AABB. Basically before each sectorization node is chosen this would happen, so as to always start the next sector from the middle/corner of what this check might consider a 'room'. I've also considered rather than the axis aligned node generation technique, to build a fully connected mesh by extruding the edges of the nodes rather than placing new nodes. By extruding edges to maintain an arbitrary mesh it might then be possible to run it through some complex mesh smoother that would then merge all room triangles into an optimized convex polygon. For simplicity sake however, I would kinda like to maintain the AABB route if these problems can be addressed, since a true mesh approach seems like a significant increase in difficulty and having to worry about a whole new set of issues like a broken mesh, optimizing the mesh, etc... Keep in mind this is a pre-processing step, so I'm cool with doing a ton of collision checks and stuff. HL2 does them rather efficiently anyways, as the flood fill itself, which results in over 50,000 nodes is generated from 1-1.5x that amount of volume raycasts, in about 70 seconds for this typically sized multiplayer map, and sectorizes in about 30 seconds, and this is in debug builds. So anyways, I welcome any and all ideas on how I might address these problems. Thanks in advance.

All day and no thoughts above and beyond the ideas that I mentioned?

I think that the axis-aligned constraints on your current method are the biggest problem. I think it would be worth your time to examine different ways to convert to a non-aligned mesh. Your bot would be able to handle more radical level design much more easily that way.


Let's take your rectangular room with rounded corners for example. Using a common pattern from your pictures, it looks like there will often be thin strips along the walls because of the rounded corners. If you raycast each vertex of the AABB sectors against the vertices of the other sectors and throw away rays that cross the existing edges of the AABBs, you would generate extra edges that could be used to merge the AABBs into a single octagonal mesh. Same thing would happen on ramps and stairs - you would generate a sloped feature.

The preference for keeping it AA is for simplicity, and because small zones like that won't really ever be used anyways so I could probably just delete them if I really wanted. The AA constraint doesn't really apply to the vertical axis, as a later step will drop the sectors to the floor, forming a contour on ramps and stuff. That's the idea at least. I'm not adamantly against a convex mesh approach, I'm just not yet convinced it's that much better. I welcome thoughts and ideas on that approach as well though. Given that the CS:S bots are able to navigate pretty well with a AA nav mesh I figured it would be good to try my own version of that first off. Going to an arbitrary mesh or convex meshes it a whole other problem. I thought about using the AABB grid after the first step as triangles for a tri-mesh, and then run it through a processor to optimize the dense mesh into convex shapes. Anyone know of an algorithm that does this?

Personally, I found creating navigation meshes out of arbitrary planar polygons with a shared vertex list to be the simplest and cleanest option for most scenarios. In one effort I worked on, I also tagged edges with different kinds of information; whether the polygon borders on a solid and vertical wall, for instance (situation; a monster that can scrabble partially up a wall when running and taking a hallway corner at speed), whether or not the adjoining polygon is a climbable wall (situation; ladders, vines), and a bit more.

Axis-aligned areas are well and good, but I find it harder to get information about the adjacent areas; arbitrary polygonal meshes are a simpler matter, since they always meet at edges. I also found mesh-based navigation to give a cleaner solution to the rounded-corner problem.

But that's just my ¢2.

Mind sharing how you ended up generating your mesh for it? I'm looking for ideas for mesh generation in the situation where you don't have access to the map geometry. The flood fill seems like the best solution for step 1, whether the target is an arbitrary mesh or an AABB based mesh. I can dial down the grid size more to get finer detail but the part I'm unsure how to handle best is how to turn the resulting flood filled grid into the actual mesh. Any ideas? Or if you have ideas that don't involve the initial flood fill I'd love to hear those too. With the restriction of not having direct access to the map geometry the flood fill is the best I've come up with so far for building a nice map of my own.

Assuming my flood cells end up as quads on a smooth mesh what sort of algorithms are used to smooth it and turn a room for example from a many triangle cell into a convex room.

I'm interested in building an actual mesh instead of the AABB mesh if I can figure out some of these questions. I'm not locked into the AABB method.

I considered building the mesh by extruding the edge of each flood fill node as it floods the map, in theory ending with a continuous mesh which could then be optimized into large convex sectors, but I'm not familiar with good algorithms to do the merging and optimization part.

Anyone with nav mesh experience please see this thread and share any info you may have.

Linky