Creating a nav mesh for a WebVR scene

SUMMARY: This tutorial shows how to create a navigation mesh for a scene with Blender, and use it in A-Frame to do basic pathfinding. For the short version, watch this video at 6:08. The key parts are covered in only 1 minute.

From the Unity documentation,

“The NavMesh is a class can be used to do spatial queries, like pathfinding and walkability tests, set the pathfinding cost for specific area types, and to tweak global behavior of pathfinding and avoidance.”

In the easiest case, a nav mesh can just be a simple mesh covering parts of the scene where characters are allowed to travel. Stairs become ramps, and obstacles are holes in the mesh.

Nav mesh screenshot in Unity.

As a someone who has never done game development, I assumed setting up a whole new mesh for navigation would be a painful, time-consuming process. Nope! Here’s what we’ll use:

• Blender, a free 3D modeling tool, that can generate a navigation mesh from an existing model.
• A-Frame, a web framework for building virtual reality experiences.
• The new pathfinding module in A-Frame Extras, using PatrolJS for navigation.

This tutorial assumes a working knowledge of A-Frame, and some understanding of Blender basics: moving, scaling, and tweaking vertices.

Finding a scene

I’ll be using a Fantasy Game Inn, by pepedrago on Sketchfab, as my scene. Use any scene you want, with two rules:

First, the model must work in A-Frame. All models on Sketchfab are available in glTF format, which is a good choice. Before investing time anywhere else, test the model on my glTF Viewer, and pay attention to the performance tab. If your frame rate is < 60 FPS in the viewer, you’re not going to be able to use it with WebVR without optimizing it first. That’s out of scope for this guide, but you can find some performance advice here.

Second, the model — or at least the geometry — must work in Blender. Blender is pretty flexible, and you won’t need the materials to create your nav mesh. If you’ve already created a scene in A-Frame, you also can export that as an OBJ or glTF from the browser and import it into Blender.

Setting up your scene in Blender

After importing your scene in Blender, spend some time getting the scale right. By convention in WebVR, 1 unit = 1 meter. A 1.65m x 0.5m box should look human-sized. These dimensions are important for getting a good nav mesh, and detecting spaces that are or are not walkable.

Bare scene in Blender, without materials.

Creating the nav mesh

In the header, switch to Blender Game mode.

Use Blender Game mode.

Then, select the model and open the Scene Panel.

The scene panel.

Expand the Navigation mesh section, and choose settings for the agent. This determines the size of character Blender will use when deciding where you can walk. A height of `1.0` and a radius of `0.2` might be reasonable places to start. My scene is crowded, so I’ll also bring down the `Cell Size` and `Max Slope` a bit. Then, press Build navigation mesh. Result:

Our first navigation mesh, before cleanup.

As it is, we could drop this into A-Frame and try it out. But for a real scene, you may want to spend some time cleaning the mesh up. Delete the nav mesh if it’s really off, and try again with different settings. Once you have something close enough, you can use Edit Mode in Blender to tweak individual vertices, add bridges, or delete unwanted areas.

Keep in mind that using PatrolJS, the center of a character can go anywhere within this mesh. So there should be some space between the edges of the nav mesh and the actual obstacles, so that a character can’t end up halfway into a wall.

Select the nav mesh, and export to `.gltf` using the glTF Blender exporter choosing Export selected only. For a 2MB scene, this navigation mesh is about 8KB. Here’s my result in the glTF Viewer:

Final navigation mesh, exported to glTF.

Using the nav mesh in A-Frame

Now, we’re ready to try this out in A-Frame. Load up original mesh, the nav mesh, and a simple NPC:

<a-scene>
  <!-- Scene -->
  <a-entity gltf-model="scene.gltf"></a-entity>
  <!-- Nav Mesh -->
  <a-entity gltf-model="navmesh.gltf"></a-entity>
  <!-- NPC -->
  <a-entity id="npc" gltf-model="npc.gltf"></a-entity>
</a-scene>

Everything should be visible at this point, but nothing is happening. I’ve created a basic set of pathfinding components, based on PatrolJS, which we’ll use to send our NPC around the scene:

<a-scene>
  <!-- Scene -->
  <a-entity gltf-model="scene.gltf"></a-entity>
  <!-- Nav Mesh -->
   <a-entity gltf-model="navmesh.gltf"
             nav-mesh></a-entity>
  <!-- NPC -->
  <a-entity id="npc"
            gltf-model="npc.gltf"
            nav-agent="speed: 1.5"></a-entity>
</a-scene>

The `nav-mesh` component is a way of telling the navigation system which model to use for pathfinding. The `nav-agent` component adds behaviors to the NPC entity, allowing it to search for paths and move toward a destination.

Finally, we’ll add ourselves to the scene with a custom pointer that tells the NPC where to go. Add this snippet to the scene above:

<a-entity id="rig"
          movement-controls="constrainToNavMesh: true"
          position="0 0 5">
  <a-entity camera
            position="0 1.6 0"
            look-controls="pointerLockEnabled: true">
    <a-cursor nav-pointer
              raycaster="objects: [nav-mesh]"></a-cursor>
  </a-entity>
</a-entity>

That `nav-pointer` component is not one of the pre-bundled components, so we’ll have to define it ourselves:

AFRAME.registerComponent('nav-pointer', {
  init: function () {
    const el = this.el;
// On click, send the NPC to the target location.
    el.addEventListener('click', (e) => {
      const ctrlEl = el.sceneEl.querySelector('[nav-agent]');
      ctrlEl.setAttribute('nav-agent', {
        active: true,
        destination: e.detail.intersection.point
      });
    });
    // When hovering on the nav mesh, show a green cursor.
    el.addEventListener('mouseenter', () => {
      el.setAttribute('material', {color: 'green'});
    });
    el.addEventListener('mouseleave', () => {
      el.setAttribute('material', {color: 'crimson'})
    });
 
    // Refresh the raycaster after models load.
    el.sceneEl.addEventListener('object3dset', () => {
      this.el.components.raycaster.refreshObjects();
    });
  }
});

That’s it! The nav mesh doesn’t need to be shown anymore, so hide it by adding `visible=”false”`. Click anywhere to guide the NPC around. If you want to use `teleport-controls` for roomscale VR locomotion, this same nav mesh can be reused:

<a-entity teleport-controls="hitEntity: [nav-mesh];"
          vive-controls="hand: left;"></a-entity>

UPDATE 3/31/2018: Corrected A-Frame examples to match pathfinding and locomotion syntax in aframe-extras v4+.