Navigation Meshes Overview <!-- omit in toc -->

A JS plugin for fast pathfinding using navigation meshes, with optional wrappers for the Phaser v2 and Phaser v3 game engines.

<img src="./doc-source/single-following-agent.gif" width="400">

Interactive demo

(Note: if you are viewing this on GitHub or NPM, you might want to check out the HTML documentation here.)

Table of Contents:

• Introduction
• Installation
  • As a Script
  • As a Module
• Creating a Navigation Mesh
• Usage
  • navmesh (API reference)
  • phaser-navmesh (API reference)
  • phaser2-navmesh (API reference)
• Performance Comparison
• Community Examples
• Development
• Changelogs
• References
• To Dos

Introduction

Pathfinding is essentially the problem of solving a maze, finding a path between points while avoiding obstacles. When pathfinding in games, we need to:

1. Represent the game world in a way that defines what areas are walkable.
2. Search that representation for the shortest path.

When it comes to 2D pathfinding, a common approach is to represent the world using tiles (a grid) and then search for a path using the A* algorithm (e.g. Phaser AStar). If you have a 50 x 50 tile world, searching for a path involves searching through a representation of the world with up to 2500 locations/nodes (50 x 50 = 2500).

This plugin uses navigation meshes to simplify that search. Instead of representing the world as a grid of tiles, it represents the walkable areas of the world as a mesh. That means that the representation of the world has far fewer nodes, and hence, can be searched much faster than the grid approach. This approach is 5x - 150x faster than Phaser's A* plugin (see performance section), depending on the mesh.

The example map below (left) is a 30 x 30 map. As a grid, there are 900 nodes, but as a navmesh (right) there are 27 nodes (colored rectangles).

<img src="./doc-source/combined.png" width="700">

Installation

This repository contains 3 related JS packages:

• navmesh - core logic, game-engine agnostic, usable outside of Phaser.
• phaser-navmesh - Phaser v3 wrapper around navmesh that creates a Phaser 3 Scene plugin. Phaser 3 is expected to be a dependency in your project.
• phaser2-navmesh - Phaser v2 wrapper around navmesh that creates a Phaser 2 game plugin. Phaser 2 or Phaser-ce is expected to be in the global scope.

You can use any of them as a script or as a module in your bundler of choice.

As a Script

You can drop in any of the transpiled code into your project as a standalone script. Download the version that you want from the GitHub release.

E.g. if you wanted phaser-navmesh, you would add this to your HTML:

<script src="phaser-navmesh.min.js"></script>

Inside of your own script, you can now use the global variable PhaserNavMeshPlugin (see library name in the above table), e.g.

const game = new Phaser.Game({
  type: Phaser.AUTO,
  width: 750,
  height: 750,
  plugins: {
    scene: [
      { key: "NavMeshPlugin", plugin: PhaserNavMeshPlugin, mapping: "navMeshPlugin", start: true }
    ]
  }
});

See usage for more information on how to use each of the three modules in this repository.

As a Module

Install the appropriate dependency:

• npm install --save navmesh for usage outside of Phaser
• npm install --save phaser-navmesh for Phaser 3
• npm install --save phaser2-navmesh for Phaser 2

To use the transpiled and minified distribution of the library (recommended for most users):

// Phaser 3
import { PhaserNavMeshPlugin } from "phaser-navmesh";

// Phaser 2
import { Phaser2NavMeshPlugin } from "phaser2-navmesh";

// NavMesh (commonjs or es import)
const { NavMesh } = require("navmesh");
import { NavMesh } from "navmesh";

To use the raw TypeScript source code so you can optimize the bundle yourself:

import { PhaserNavMeshPlugin } from "phaser-navmesh/src";

Creating a Navigation Mesh

Creating a navigation mesh is the process of defining the walkable areas within you world as a series of polygons. If you are using a tilemap, then you can probably get away with just auto-generating the mesh using buildMeshFromTilemap in Phaser 3 (or if you are using NavMesh without the Phaser wrapper, see buildPolysFromGridMap).

If you've got a more complex situation, you can use a tilemap editor like Tiled to create your mesh and load it into the game. See guide.

(Note: the current version of the library only supports convex polygons. There are libraries like poly-decom.js for decomposing a concave polygon into easier to manage convex polygons. It's on the to do list to handle any polygon, but I've found that automatically decomposing polygons leads to worse performance than hand-mapping the levels with convex polygons.)

Usage

You can find code snippets for the different use cases below. You can also jump directly to a few example projects in this repository for:

• phaser 3
• phaser 2
• navmesh in a node environment

navmesh (API reference)

If you don't need the Phaser wrappers, you can construct navmeshes directly from points using the navmesh package:

import { NavMesh } from "navmesh";

/*
  Imaging your game world has three walkable rooms, like this:

    +-----+-----+
    |     |     |
    |  1  |  2  |
    |     |     |
    +-----------+
          |     |
          |  3  |
          |     |
          +-----+
*/

// The mesh is represented as an array where each element contains the points for an indivdual
// polygon within the mesh.
const meshPolygonPoints = [
  [{ x: 0, y: 0 }, { x: 10, y: 0 }, { x: 10, y: 10 }, { x: 0, y: 10 }], // Polygon 1
  [{ x: 10, y: 0 }, { x: 20, y: 0 }, { x: 20, y: 10 }, { x: 10, y: 10 }], // Polygon 2
  [{ x: 10, y: 10 }, { x: 20, y: 10 }, { x: 20, y: 20 }, { x: 10, y: 20 }] // Polygon 3
];
const navMesh = new NavMesh(meshPolygonPoints);

// Find a path from the top left of room 1 to the bottom left of room 3
const path = navMesh.findPath({ x: 0, y: 0 }, { x: 10, y: 20 });
// ⮡  [{ x: 0, y: 0 }, { x: 10, y: 10 }, { x: 10, y: 20 }]

If your world is a grid (e.g. a tilemap), NavMesh also has a utility buildPolysFromGridMap that can automatically generate meshPolygonPoints from a 2D array.

phaser-navmesh (API reference)

If you are working with Phaser 3, you can use the phaser-navmesh package, which provides a Scene plugin. Play with a live example on CodeSandbox here, or peek at the examples in this repository for more complete usage.

import Phaser from "phaser";
import { PhaserNavMeshPlugin } from "phaser-navmesh";

const game = new Phaser.Game({
  type: Phaser.AUTO,
  parent: "game-container",
  width: 750,
  height: 750,
  plugins: {
    scene: [
      {
        key: "PhaserNavMeshPlugin", // Key to store the plugin class under in cache
        plugin: PhaserNavMeshPlugin, // Class that constructs plugins
        mapping: "navMeshPlugin", // Property mapping to use for the scene, e.g. this.navMeshPlugin
        start: true
      }
    ]
  },
  scene: {
    preload: preload,
    create: create
  }
});

function preload() {
  this.load.tilemapTiledJSON("map", "tilemaps/map.json");
  this.load.image("tiles", "tilemaps/tiles.png");
}

function create() {
  // Set up a tilemap with at least one layer
  const tilemap = this.add.tilemap("map");
  const tileset = tilemap.addTilesetImage("tiles", "tiles");
  const wallLayer = tilemap.createStaticLayer("walls", tileset);
  wallLayer.setCollisionByProperty({ collides: true }); // Or, however you set tiles to collide.

  // Automatically generate mesh from colliding tiles in a layer or layers: 
  const navMesh = this.navMeshPlugin.buildMeshFromTilemap("mesh", tilemap, [wallLayer]);
  const path = navMesh.findPath({ x: 0, y: 0 }, { x: 300, y: 400 });
  // ⮡  path will either be null or an array of Phaser.Geom.Point objects

  // Alternatively, you can load a navmesh created by hand in Tiled that is stored in an object 
  // layer. See the creating a navmesh guide for more info on this.
  // const objectLayer = tilemap.getObjectLayer("navmesh");
  // const navMesh = this.navMeshPlugin.buildMeshFromTiled("mesh1", objectLayer, 12.5);
}

The plugin comes with some methods for visually debugging your navmesh:

navMesh.enableDebug(