navmesh-generator
v1.0.3
Published
A JS library for generating navigation meshes from obstacles
Downloads
10
Readme
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.
A scan-line polygon fill algorithm
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
An isometric example
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.
An AI example
This is a modified version of an official example of GDevelop where enemies follow the player.
Squares at random positions
Two sizes of moving objects and obstacle dragging
How to use it
The algorithm builds a mesh from a given area and a list of polygon obstacles.
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.
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.
import { NavMesh } from "navmesh";
Changelog
Version 1.0.3
- ES5 compatibility
Version 1.0.0
- First version