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 – 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.  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 working
recastnavigation 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.

Comments

12 responses to “Navigation Mesh path finding in MMORPG Bots (updated)”

  1. botter avatar
    botter

    Hi
    What revision of recast where you using when building?
    Regards

  2. cvccbum avatar
    cvccbum

    Is it possible you could post the navmesh file you used in the video? and the source of the recast/detour you used. I cannot get any newer navmesh files I’ve created to work with your method, just your mesh you gave with the file.
    Any help would be awesome!

  3. Millow avatar
    Millow

    Same question as botter.
    I can’t find the functions that you call in the detour code.
    Some of them I could, but not all.
    Any help ?

  4. Michael Cutler avatar
    Michael Cutler

    It could be that the recastnavigation project has moved on since I wrote this code. It was built and tested against Revision 162 and the latest is 299.

  5. Michael Cutler avatar
    Michael Cutler

    I’ve updated the post to add a link to the navmesh tile used in the example :O)

  6. Michael Cutler avatar
    Michael Cutler

    It was built and tested against Revision 162 and the latest is 299.

  7. Tanaris4 avatar
    Tanaris4

    Any chance you could post how you generated the nav mesh?

  8. Millow avatar
    Millow

    Same as tanaris4, that would be awesome.

  9. dook123 avatar
    dook123

    Nice work, I have been down this road as well. Its pretty fun to see results 🙂

  10. nerexis avatar
    nerexis

    Bump, how you generated navmesh data? Using recastdemo or by recast api, what was your config?

  11. […] read more about this? Possibly similar to BW/SWTOR meshes? Google "navigation mesh" eg Navigation Mesh path finding in MMORPG Bots (updated) | Michael Cutler's personal website Try this link for a good starting point for Recast& Detour – an open-source toolkit for […]

  12. Krlitoz avatar
    Krlitoz

    This is awesome! Is it possible for you to share the test bot using the dll used in the video?

Leave a Reply

Your email address will not be published. Required fields are marked *