Developer Tools: AI Navigation Mesh Toolset for Unity

Navigation Mesh Toolset

More Update: This thing is officially very out of date.  I made it several major versions of Unity ago, and Unity has since added navigation meshes as a built in feature (though, sadly, Pro only).  If you’ve stumbled upon this page from a google search, fear not!  There are plenty of places to go for the knowledge you seek!  This is just not one of them, unfortunately.  Best of luck!

The game this was going to be used for sadly never made it past the first playable stage, and things listed as “upcoming features” are now more accurately “features I would have added if we’d kept going.”  This was still a great learning experience and reinforced by love for tool programming in a big way.

Update: Looks like this page is crawling upwards in the Google search results. I was originally thinking about selling this toolset in the Unity Asset Store, but once they announced that pathfinding would be built in to Unity 3.5, it became clear that wouldn’t work out so well. As a result, I no longer have any reason to be sneaky about this! If there’s interest, I’d be more than happy to talk about the specifics of my implementation, share some of the useful hidden features I discovered along the way, and even share code. Please get in touch if you’d like to see this kind of stuff, or if you’d just like to chat about it!

As part of a AI-heavy game I’m making with some friends, I’ve been building a navigation mesh creator and editor in Unity (v 3.4).  It generates weighted navigation meshes at design time based on the colliders of the level geometry and a set of user-specified parameters.  This toolset also includes a custom editor for the meshes, allowing the designer to freely move, modify, add, and delete nodes.  The end result is a graph of nodes perfect for use with A* or other pathfinding algorithms.

While it’s fully functional and is already being used by my team, I’m still adding extra features and improving the interface when I have time.

Features

  • Automatically calculates bounds of the scene and allows the user to modify them.
  • Allows distinction between static and dynamic level geometry if desired.
  • Creates mesh based on the traveler, taking into account its height, its width, and the maximum slope it can ascend.
  • Nodes can be weighted so that travelers will favor certain areas over others.
  • Graph is drawn over the level in the inspector.
  • Custom editor interface for refining the graph after it’s generated.
  • Add, delete, move, modify, connect, and disconnect nodes or groups of nodes.
  • While editing nodes, only that portion of the graph is drawn to prevent lag from large or complex meshes.
  • Almost all actions are undoable.

Upcoming Features

  • 3D graphs for travelers that can fly.
  • Allow for other directions to be treated as “up,” and multiple “ups” for travelers with wall-climbing abilities.
  • Soft select for node modification.
  • Allow for saving and reloading mesh creation settings.
  • Don’t display nodes or edges that are on the far side of level geometry.
  • Interface improvements, including tooltips and hotkeys.
  • Finish adding undo support.

The Tools

Here’s the mesh creation pane that I built with Unity’s editor customization scripting.

Navigation Mesh Creation Pane

The scene’s bounding box is automatically calculated based on the colliders present, but can be modified if the designer wants to restrict the areas of the level included in the mesh. If there are some items in the level which will move during gameplay, the designer can choose to ignore all colliders that aren’t marked as static, and the movable items won’t stop nodes or edges from being created.  You can also specify how densely spaced you want the nodes to be and the maximum distance allowed before two nodes can’t be connected.

This is an example of a mesh generated with the above settings on a simple “level” built from some of Unity’s primitive shapes.  The scene’s bounding box is shown as a white outline, but this can be turned off.

Navigation Mesh

I haven’t implemented occlusion culling for the graph yet, so things are cluttered up a bit by the nodes showing through from the far sides of shapes.  You can see, thought, that the green ramp is a gentle enough slope that my traveler can walk up it, so it’s been populated by edges.  The red ramp, on the other hand, is too steep, so it’s not traversable.  The traveler is too tall to fit under the sphere or under the base of the ramps, so no nodes are placed in these areas.  The graph generation also takes overlapping colliders into account – there aren’t any nodes on the blue floor inside the purple box.

Lastly, here’s a little bit of what my custom mesh editor can do.  This is far from everything, of course, but should give a good idea of the actions you can take and how the tool responds.

Navigation Mesh Node Movement

Navigation Mesh Node Disconnect

Project Details

When did I make it?

The fall semester of my senior year (2011).

How long did it take to make?

About three weeks for core functionality, but it’s still being improved.

What parts did I make?

All of it except, oddly enough, for the A* pathfinding itself.  All of the design-time stuff was me.

Who else helped make it?

The game this was made for is being built by myself and five friends: two other programmers, one artist, one designer, and one project manager/jack of all trades.

Comments

This has been an amazingly fun project.  It’s an excuse to build a nice development tool and play with graph theory at the same time – there’s no way I couldn’t love it.

Of course, about two weeks after I finished the core functionality for this, Unity 3.5’s feature list was announced… and it includes native support for navigation meshes.  Oh, well.  I still liked building this and plan to finish it anyway.

I plan on making a little demo video of this soon.  I’ll post it as soon as it’s done!

Advertisements