Navigation Mesh path finding in MMORPG Bots (updated)

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.

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 – enterrecastnavigation.

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.  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.  Single most
virtual worlds are ’tiled’ anyway it makes sense to tile the navmesh’s
in the same way.

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.  

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 workingrecastnavigation tree available under
“../Contrib/recastnavigation”.

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.