The Navigation Challenge

One of the biggest challenges in writing a Bot (autonomous character) for an MMORPG is the navigation. You have a few choices, ordered by complexity:

• Steering: Quite simply, given a destination you steer the character towards that point. If it gets stuck you try jumping, reversing, strafing left/right. This is obviously the most primitive form of navigation and looks very 'bottish' to real players.

• Breadcrumbs: A hard coded 'path' of waypoints to navigate between A & B. If you haven't created a path yet the character cant go there. If for whatever reason (attacked) the character deviates from the path they may get stuck behind scenery.

• Graph: If you take a number of overlapping Breadcrumb paths and merge them into a graph you can create new routes across a network of paths. Say for example a path is made for A to B, and another overlapping path from B to C. The Bot character can run from A to C without having an explicit path between the two.

• Navigation Mesh: Last but not least, a Navigation Mesh contains a map of all the 'walkable surfaces' in the virtual world. Given a start & end point it can determine the best route to take whilst avoiding obstacles like scenery & water.

Why Navigation Meshes Are Superior

It's clear that navigation meshes are far superior than the other options. However implementing them efficiently can be very hard to do for your own small-time hobby project — enter recastnavigation.

Recast & Detour is an open-source toolkit for building and using navigation meshes. In order to use it you must first use Recast against the terrain data within the MMOPRG to generate the meshes for the virtual world.

Building Navigation Meshes for World of Warcraft

In the case of World of Warcraft this process is roughly:

1. Parse the game datafiles (MPQ's) and extract the terrain data files.
2. Create a merged view of the terrain data and any objects (buildings, trees etc.).
3. Feed the merged data into Recast which then generates a mesh of the walkable areas.

The output of this process is a bunch of ".navmesh" files ready for use with Detour. You can import and map an entire virtual continent into a single navmesh, but it might be very memory intensive.

Since most virtual worlds are 'tiled' anyway it makes sense to tile the navmesh's in the same way.

Visualizing the Navigation Mesh

The image below shows an example of the navmesh generated for the "Azeroth_32_48" tile in the World of Warcraft. The software displaying this tile is "RecastDemo" and is included in recastnavigation.

The polygons coloured Blue are 'walkable' areas, those coloured Beige were considered while generating the path and those coloured Dark Beige display the final route. All other polygons shown in Grey are obstacles, buildings and non-walkable areas.

It's clear to see how Detour can use this navigation mesh data to generate paths.

Implementation with CapekNav

So how do you go about using it? You need to write a simple client that uses Detour to do your path finding. Since I was primarily running my Bot's on Windows I opted to wrap a simple C++ class in a DLL making integration of the navigation functions easy for my Bot software.

I've just posted the CapekNav code on GitHub. It's been a while since I was actively using it — but it will give you the general idea. One compiled navmesh is included allowing you to run the "CapekNavTest" program to confirm its working.

The Makefile assumes you have a working recastnavigation tree available under "../Contrib/recastnavigation".

Results in Action

When you piece it all together you can get some very impressive results. This video shows a Bot character navigating around some tough obstacles to get to key points necessary to complete Quests. Achieving this with any of the other navigation techniques would have been near impossible.

Update (4th August 2011)

To answer a couple of questions:

• I developed and tested my CapekNav code on a 64-bit Linux PC, however I compiled the DLL on Windows 7 in Visual Studio 2008 and although its been a while it should still all work.

• It was built and tested against Revision 162 of recastnavigation

• The idea behind the small "CapekNav.dll" DLL is that you an hook it up to your existing project pretty much regardless of the language. It's just a DLL that exports a couple of handy functions. Here I was actually using it from my C# code, but it could have just as easily been used from a C++, Delphi, VB or god-forbid even an AutoIT script.

• You can download the navmesh tile referenced in CapekNavTest.cpp from here.