NavMesh Generator

This JavaScript library allows to generate 2D navigation meshes for pathfinding.

It can be used, for instance, with this pathfinding implementation: mikewesthad/navmesh.

Used work

This implementation is strongly inspired from NMGen Study a Java one by Stephen A. Pratt.

This implementation differs a bit from the original:
- It's only 2D instead of 3D
- It uses objects for points instead of pointer-like in arrays of numbers
- The rasterization comes from other sources because of the 2d focus
- The partialFloodRegion function was rewritten to fix an issue
- An algorithm to filter vertices that are not on a border was added

The original Java implementation was also inspired from Recast itself.

$3

The original implementation was done by Darel Rex Finley.

The implementation used in this library differs with the following:
- It handles float vertices so it focusses on pixels center
- It is conservative to thin vertical or horizontal polygons

Demonstrations

$3

This is a modified version of an official example of GDevelop where a character moves to the pointer with a left click. The art was done by Mickael Hoarau.

Try it on itch.io

!GDevelopNavMeshTiny

$3

This is a modified version of an official example of GDevelop where enemies follow the player.

Try it on itch.io

$3

Try it on itch.io

$3

Try it on itch.io

How to use it

The algorithm builds a mesh from a given area and a list of polygon obstacles.
``JavaScript
import { NavMeshGenerator } from "NavMeshGenerator";

const areaLeftBound = 0;
const areaTopBound = 0;
const areaRightBound = 800;
const areaBottomBound = 600;
const rasterizationCellSize = 10;
const navMeshGenerator = new NavMeshGenerator(
areaLeftBound,
areaTopBound,
areaRightBound,
areaBottomBound,
rasterizationCellSize
);

const obstacles = [[
{ x: 300, y: 200 },
{ x: 500, y: 200 },
{ x: 500, y: 400 },
{ x: 300, y: 400 },
]];
const obstacleCellPadding = 0;
const navMeshPolygons = navMeshGenerator.buildNavMesh(
obstacles,
obstacleCellPadding
);
`
If you are using mikewesthad/navmesh, you can directly use the mesh to find paths.
`JavaScript
const navMesh = new NavMesh(navMeshPolygons);
const path = navMesh.findPath({ x: 100, y: 300 }, { x: 700, y: 300 });
`
In this case, you need this additional import.
`JavaScript
import { NavMesh } from "navmesh";
``

Changelog

$3

- ES5 compatibility

$3

- First version