yet another navmesh implementation

[pendra]

I've been working on a navigation system for WoW for awhile now, got far enough this weekend that I figured I'd post my progress. I'm not sure if I'll make anything public or not yet, not sure if anyone would even be interested. I figured at a minimum I can supply my experience and maybe answer some questions for others working on the same sort of stuff.

All of the code for this I've written myself, except for libmpq, but I've borrowed a lot of ideas from others, so here's some credits:

-- These forums. I found quite a bit of info by searching existing posts, particularly on figuring out the memory offsets needed for controlling a character to test my paths.

-- The wow.dev wiki. This is where I got all the info about how to parse the WoW data files.

-- The Recast navigation project. code.google.com/recastnvigation. I read his code to get a rough idea of how to start mine.

-- The libmpq library. I'm using it to read MPQs.

The basic idea is to voxelize the collision data into a compact volume representation and then extract movable areas from it. Two polygon meshes are created, one for the area that can be walked on and one for the area that can be ridden on with a mount. Both meshes are decimated to eliminate areas that have insufficient clearance or are too close to walls.

Swimming and flying will be added later by extracting a polyhedral mesh describing the area filled with air/water in the same way. Basically just extract the hull of "no collision" voxels, simplify it in the same way planar contours are simplified, and then partition it into convex pieces. Lots of hand waving there for now, but I know other commercial navigation implementations do it so it must be possible.

About 90% of my time so far has been on tuning to get the nav mesh as clean as possible. Currently I can generate a mesh for eastern kingdoms in about 20 minutes, and that mesh is about 60MB in memory. Even very long paths can be found almost instantly.

The navmesh is tiled into ADT MCNK size pieces [33.3x33.x3]. Tiles can be swapped out live so adding of dynamic M2s and such is possible at run time. Tiles are also qualified by an instance ID and a phase, so multiple characters can use the nav system simultaneously and each can see a different view of the world depending on their particulars. I haven't written the code to actually insert dynamic objects yet, but the hard part is supporting swapping the tiles and that's done...

The architecture supports point to point jump links but I haven't added the code to actually do anything with them yet. Once I'm happy with the basics I'll add flight paths and instance portals between maps.

I'll attach some screenshots of the meshes in the next post.

[pendra]

Here's a screenshot of stormwind and part of elwynn from a high level. You can see the holes punched for tree trunks and fences and such. WMO/M2 derived stuff is white and terrain is green. Water is culled out for now since I'm planning to add a volumetric mesh for it later.

[pendra]

Here's a close-up of the building [northshire abbey i think] right by the human starting area.

You can see how multiple floors of the building are dealt with.

[pendra]

One of the things you might notice is that it shows ground under stormwind. That's an artifact from the fact that there are some WMO faces in the stormwind docks that I must not be handling right as a section of wall that is there IRL is not coming out in my data, letting the reachability flood go under stormwind and fill out that whole area...

[namreeb]

Wow. Very impressive. +rep to you, sir.

[pendra]

Here's another status update.

I fixed a bunch of bugs and made some major performance improvements. D1 cache miss is now <5% and the generator is fully multi-threaded, so it screams. I can generate meshes with 0.05 meter cell size and 4 meter tiles for the entire game in 45 minutes on a dell r710 server. The smaller cell and tile size makes for some really nice looking meshes.

I experimented with ways to mark paths using road textures but was not able to get anything I was happy with, so I decided to forget about it and solve the inverse problem instead. The nav mesh can now be attached to a radar that indicates all the known mob locations. All the tiles in the mesh are then tagged based on their distance from known spawn locations, and the transveral cost of the polys for path finding purposes increases as they get closer to a known mob location. In other words, rather than mark paths, we mark dangerous areas and try to avoid them. Not quite as clean as running straight down a road, but at least I'm not running through murloc camps.

Adding and removing known mobs is fairly fast since it's just a linear distance check against all the polygons in the mesh, therefore I'm expecting that I'll be able to adjust the mesh, and thus the path, on the fly as my character is moving and avoid spawns as needed.

I also wrote a GUI tool in Qt to visualize the mesh, find paths, etc, few more screenshots to follow.

[pendra]

Here's a shot of elwynn forest showing areas tagged as dangerous per known mobs in orange. The radar scan I'm using is includign some critters and excluding some hostile mobs with factions so it's not totally right, but you get the idea.

[pendra]

Here's a path across stormwind from the cellar of that inn where the warlock trainer is to the throne room. The path is jagged because I haven't put any kind of smoothing code in the GUI yet, it just draws lines between the centers of the polys on the path for now.

[pendra]

Here's a path all the way across azeroth from booty bay to undercity. Time to compute this path was about 50ms w/o taking any speed ups into account. I expect prepopulating the mob radar from a server emu database or something will speed it up quite a bit.

[Flowerew]

Seriously awesome stuff.

[audible83]

Very interesting approach by flagging known mob spawn locations.
Nice work.

Do you implement this post or pre-building the mesh ?

[pendra]

The tile marking is done dynamically on the finished mesh. The pre-build computations are strictly where you can and cannot physically go, ignoring everything about cost, danger, faction, etc, as I'm trying to add all that as overlaps in real time.

The mobs really have to be done dynamically, since they move around, and what is hostile depends on your alliance/horde faction, your reputation with various other factions, even whether or not you are on some particular quest, etc.

I also don't trust that I'm going to find any single source of 100% accurate mob location info, so it's better to just get a rough idea and then let the agent firm it up using their own radar information as they move around, me thinks.

[pendra]

As far as marking roads goes, if I decide it's still necessary despite having mob marking [probably yes], my intent would be to do the following:

1) Manually lay out a tree of line segments that lie on the center of all roads and other paths that I want my agent to use preferentially. Save this in a separate file as a set of polylines.

2) After I generate my mesh, mark all polygons in the mesh that have a vertex within say 2 yds of the polyline tree and mark them as roads using the same technique I use now for mob spawns.

This would only mark the "middle" of the road, which is desirable, and wouldn't depend on any particular texture or anything being under the road, so it could go over/through WMOs and such.

[Xarg0]

well this is truely awesome work, and I guess it was quite a lot of work if you were doing everything on your own except for mpq's and the adt/wmo information you can get at wow.dev.
I'd be interested in how your region graph is actually implemented, are you using a simple convex polygon class as Nodes and is your graph directed or undirected, how do you prevent your code from jumping done cliffs, etc, there are so much questions I want you to ask
But I'll give you the opertunity to answere some before I'll start to ask even more.

[pendra]

Thanks. Here's a rough outline of my pipeline. Feel free to ask questions about any details, my whole point of posting is to provide design help to the community. My approach is pretty similar to recast at a high level, it's just the details are pretty different, so if you wanted to get started I'd get started in the same way and look at recast.

The basic initial data structure is a compact volume representation that I ripped off from recast. Mikko calls it a "multi-level height field". Lots of commercial AI middleware packages do the same thing.

Basically I have an NxN height field where each <x,y> point, called a cell, consists of one or more [min,max] ranges called spans. Each span represents an area of space that is occupied by either a solid object or a liquid, or fly-able air.

N is some small value, say 0.05 meters, so each ADT would have a 10666x10666 height field. Initially, the entire multi level height map is occupied by air, so every cell has a single span [-inf,inf] for air.

We then need to add the geometry data from the game into it.

For the ADT data, we already have it represented as a height field, so we just interpolate it and insert spans directly. For each point <x,y> in the image, we figure out where the center of it would be in world space and then interpolate the height from that point from the ADT data. Say it's 530.2 at some point. We know that we can't fly under the terrain, so the cell ends up with two spans, one for terrain at [530.2,530.2, type=terrain], and one for the air above it, [530.2, inf, type=air]

For water from the ADT, we simply find any cells that have water, and then insert a span going from the terrain in that point up to the water level in that point and mark it water. You can then fly above the water, so we add an air span for that.

We can then add WMOs by rasterizing the triangles. For each triangle, you figure which <x,y> height field samples it intersects, then figure out the lowest and highest point on the triangle in that cell. If the triangle is completely horizontal at z=54.3, then you'd just insert a span [54.3,54.3,type=Building] in each cell where it exists. If the triangle is completely vertical, then you could get spans that are much longer, say [-100,50.3], all from the same triangle.

M2s are done in the same way.

BTW for each terrain or building/model span we insert, we check the slope of the face against the vertical. If it is more than 45 degrees, we mark the span as 'STEEP'. This will come into play later.

Inserting all this data just requires a linear scan through it, but since you're just voxelizing everything anyway it's really easy to split into tiles and run the tiles in parallel.

Once we have the height field, we need to figure out where it is OK to walk. We'll ignore swimming and flying for now, but they can be done in much the same way.

We scan through the height field, and for each Terrain or Building span we check if the following is true:

a) is it not STEEP
b) The amount of space between the top of this span and the bottom of the next terrain/building span is more than the height of our character, say 2.1 meters.
c) There is not more than ~1 meter of water directly above the span.

If all these are true, we say the span is STANDABLE, meaning the agent can stand on that point without hitting their head on anything, without standing on a surface that is too steep to stand on, or standing under too much water that we're actually swimming.

We then compute which spans you can walk between. For each span, look at the spans in adjacent cells. Any two spans which are both standable, and where the 'step' between them is less than the amount our unit can step up/down without jumping, and there is enough clearance to move between them without hitting ones head on a ledge, then we mark in each cell that the unit can walk between them.

Finally, we scan through the spans and compute 'distance from wall' at each point. This is simply how far any given span is from a span that has less than four neighbors, using the neighbor connections. This can be found in two linear passes through the height field, one in the X+,Y+ direction, one in the X-, Y- direction.

We can then mark any spans where the distance to wall is less than the radius of the agent as non-STANDABLE, preventing the agent from trying to go through gaps that are too narrow.

We now know which spans are OK to stand on, and which spans can be moved between.

Next step is to break the height field into continuous walkable regions. This is done in my case using monotone partitioning.

Here's the algorithm in pseudocode, skipping some technical details to make it readable:

for y in height dimension
for x in width dimension
for span in cell at x,y
if span is not already in a region
if span has neighbor to the left, mark it same region as that one.
else if span has neighbor above, mark it same region as that one
else make it the first span in a new region
end
end
end

Caveat: You don't want any 'holes' in a region, so never inherit a region from the span above you in the y dimension unless no other span in your current x strip already has that region. This the regions are monotone with respect to the X dimension.

Once we have all the regions, we find their contours by simply walking the outer edge of the region. Each point on the contour which is adjacent to another region or to the edge of the tile is marked as such. We can then throw out the height field and keep just the contours.

We then merge together contours where the merge would not introduce any holes, and would not create any contours which overlap themselves in the XY plane. E.g., you wouldn't want one region that contains two floors of the same building. This can be done really quickly, as it translates into two rules:

1) Don't merge contours that intersect each other
2) Don't merge contours that don't contain any adjacent contour points.
3) Don't merge contours that contain more than one stretch of adjacent points [this will introduce a hole].

Merge all contours that can be merged, then simplify the contours to contain a more reasonable number of points, rather than one point per cell, which might mean your points are only 0.05 meters apart.

Once you've simplified the contour, you can partition it into convex pieces, record the connections between the pieces using the connections on the contour, and then throw away the contours and forget about the regions. You now have a mesh of convex polygons that tell you where to go....

I'm hand waving around a whole ton of details but hopefully you get the idea.