A Phaser plugin for fast pathfinding using navigation meshes.

Article by Richard Davey. Posted on 28th Jul 2017.   @photonstorm

image

Pathfinding is essentially solving a maze, finding a path between two 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 in Phaser, the packaged solution represents the world using tiles (a grid) and then searchs for a path using the A* algorithm. 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).

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).

Read More