navmesh

stable

Create walkability grids and polygon meshes for game navigation, with A* pathfinding, point-in-mesh testing, and area calculation utilities.

use plugin navmesh::{create_grid, set_walkable, is_walkable, …}

13 functions Game

/ filter jk navigate Esc clear

Functions (13)

create_grid Create a walkability grid of given dimensions
set_walkable Set a cell's walkable flag and return updated grid
is_walkable Check if a grid cell is walkable
find_path Find shortest path using A* on a grid
create_mesh Create an empty polygon mesh
add_triangle Add a triangle to a polygon mesh
point_in_mesh Test if a point lies inside any mesh triangle
nearest_point Find nearest point on mesh boundary to a point
triangle_area Compute area of a triangle from its vertices
mesh_area Compute total area of all triangles in a mesh
triangle_count Get the number of triangles in a mesh
heuristic Compute Manhattan distance heuristic
grid_neighbors Get valid grid neighbors for a cell

Overview

navmesh provides two complementary navigation primitives for 2D games: tile grids for A* pathfinding and polygon meshes for free-form walkable regions. There are no opaque handles — a grid is a plain table of 1-indexed boolean cells (plus width/height metadata) and a mesh is a table holding a triangles list, so both are ordinary values you can store, inspect, and pass around. Use the grid side when your world is tile-based and you need a concrete path of waypoints; use the mesh side when you need to test containment, measure walkable area, or snap an agent back onto the navigable surface.

Every function is pure: builders like set_walkable and add_triangle return a new table rather than mutating their input, so you chain them by threading the result forward. Grid coordinates are integers and 4-directional (no diagonals); mesh coordinates are floats.

Common patterns

Build a grid, carve out obstacles, then pathfind across it:

use plugin navmesh::{create_grid, set_walkable, find_path}

let grid = create_grid(5, 5)
let g2 = set_walkable(grid, 2, 0, false)
let g3 = set_walkable(g2, 2, 1, false)
let path = find_path(g3, 5, 5, 0, 0, 4, 0)
print("waypoints: {path}")

Assemble a polygon mesh and query it for containment and area:

use plugin navmesh::{create_mesh, add_triangle, point_in_mesh, mesh_area}

let mesh = create_mesh()
let m2 = add_triangle(mesh, 0.0, 0.0, 4.0, 0.0, 0.0, 3.0)
let m3 = add_triangle(m2, 4.0, 0.0, 4.0, 3.0, 0.0, 3.0)
print("inside: {point_in_mesh(m3, 1.0, 1.0)}")
print("area: {mesh_area(m3)}")

Snap an off-mesh agent back onto the navigable surface:

use plugin navmesh::{create_mesh, add_triangle, point_in_mesh, nearest_point}

let mesh = create_mesh()
let m2 = add_triangle(mesh, 0.0, 0.0, 10.0, 0.0, 5.0, 10.0)

if !point_in_mesh(m2, 12.0, 0.0) {
  let snap = nearest_point(m2, 12.0, 0.0)
  print("snapped to {snap["x"]},{snap["y"]} (dist {snap["distance"]})")
}

create_grid(width, height) → table

Create a walkability grid of given dimensions

Creates a flat walkability grid of width × height cells, all initially walkable (true). The returned table includes width and height metadata entries alongside the 1-indexed boolean cell values.

use plugin navmesh::{create_grid, set_walkable, is_walkable}

let grid = create_grid(10, 10)
let grid2 = set_walkable(grid, 5, 5, false)
print(is_walkable(grid2, 5, 5))
print(is_walkable(grid2, 0, 0))

set_walkable(grid, x, y, walkable) → table

Set a cell's walkable flag and return updated grid

Returns a new grid with the cell at (x, y) set to the given walkable flag. This function is pure — it does not modify the original grid in place.

use plugin navmesh::{create_grid, set_walkable}

let grid = create_grid(5, 5)
let grid2 = set_walkable(grid, 2, 2, false)
let grid3 = set_walkable(grid2, 3, 2, false)

is_walkable(grid, x, y) → bool

Check if a grid cell is walkable

Returns true if the cell at (x, y) in the grid is walkable.

use plugin navmesh::{create_grid, set_walkable, is_walkable}

let grid = create_grid(4, 4)
let g2 = set_walkable(grid, 1, 1, false)
print(is_walkable(g2, 1, 1))
print(is_walkable(g2, 2, 2))

find_path(grid, width, height, start_x, start_y, end_x, end_y) → table

Find shortest path using A* on a grid

Runs A* on the grid to find the shortest walkable path from (start_x, start_y) to (end_x, end_y). Returns a table of {x, y} waypoints in order, or an empty table if no path exists. Movement is 4-directional (no diagonals).

use plugin navmesh::{create_grid, set_walkable, find_path}

let grid = create_grid(5, 5)
let g2 = set_walkable(grid, 2, 0, false)
let g3 = set_walkable(g2, 2, 1, false)
let g4 = set_walkable(g3, 2, 2, false)

let path = find_path(g4, 5, 5, 0, 0, 4, 0)
let step = path[1]
print("Start: {step["x"]},{step["y"]}")
print("Path length: {path}")

When the goal is fully walled off, find_path returns an empty table — check it before walking the result:

use plugin navmesh::{create_grid, set_walkable, find_path}

let grid = create_grid(3, 3)
let g2 = set_walkable(grid, 1, 0, false)
let g3 = set_walkable(g2, 1, 1, false)
let g4 = set_walkable(g3, 1, 2, false)

let path = find_path(g4, 3, 3, 0, 0, 2, 0)
print("blocked: {path}")

create_mesh() → table

Create an empty polygon mesh

Creates an empty polygon mesh table with an empty triangles list. Use add_triangle to populate it.

use plugin navmesh::{create_mesh, add_triangle, triangle_count}

let mesh = create_mesh()
let m2 = add_triangle(mesh, 0.0, 0.0, 1.0, 0.0, 0.5, 1.0)
print(triangle_count(m2))

add_triangle(mesh, x1, y1, x2, y2, x3, y3) → table

Add a triangle to a polygon mesh

Adds a triangle defined by three 2D float vertices to the mesh and returns the updated mesh. This function is pure — it does not modify the input mesh.

use plugin navmesh::{create_mesh, add_triangle, mesh_area}

let mesh = create_mesh()
let m2 = add_triangle(mesh, 0.0, 0.0, 4.0, 0.0, 0.0, 3.0)
let m3 = add_triangle(m2, 4.0, 0.0, 4.0, 3.0, 0.0, 3.0)
print("Total area: {mesh_area(m3)}")

point_in_mesh(mesh, px, py) → bool

Test if a point lies inside any mesh triangle

Tests whether the 2D point (px, py) lies inside any triangle in the mesh. Uses the sign method for fast triangle containment testing.

use plugin navmesh::{create_mesh, add_triangle, point_in_mesh}

let mesh = create_mesh()
let m2 = add_triangle(mesh, 0.0, 0.0, 10.0, 0.0, 5.0, 10.0)

print(point_in_mesh(m2, 5.0, 3.0))
print(point_in_mesh(m2, 20.0, 20.0))

nearest_point(mesh, px, py) → table

Find nearest point on mesh boundary to a point

Finds the nearest point on the mesh boundary (vertices and edges) to the given point (px, py). Returns {x, y, distance}. Useful for snapping agents to the navmesh.

use plugin navmesh::{create_mesh, add_triangle, nearest_point}

let mesh = create_mesh()
let m2 = add_triangle(mesh, 0.0, 0.0, 10.0, 0.0, 5.0, 10.0)

let result = nearest_point(m2, 12.0, 0.0)
print("nearest: {result["x"]},{result["y"]} dist={result["distance"]}")

For a point already inside the mesh, the nearest boundary point is whichever edge or vertex sits closest, and its distance measures how far the agent is from leaving the walkable region:

use plugin navmesh::{create_mesh, add_triangle, nearest_point}

let mesh = create_mesh()
let m2 = add_triangle(mesh, 0.0, 0.0, 10.0, 0.0, 5.0, 10.0)

let edge = nearest_point(m2, 1.0, 1.0)
print("clearance: {edge["distance"]}")

triangle_area(x1, y1, x2, y2, x3, y3) → number

Compute area of a triangle from its vertices

Computes the absolute area of a triangle from its three 2D vertices using the cross-product formula.

use plugin navmesh::{triangle_area}

let area = triangle_area(0.0, 0.0, 4.0, 0.0, 0.0, 3.0)
print(area)

mesh_area(mesh) → number

Compute total area of all triangles in a mesh

Returns the total area of all triangles in the mesh by summing each triangle's individual area.

use plugin navmesh::{create_mesh, add_triangle, mesh_area}

let mesh = create_mesh()
let m2 = add_triangle(mesh, 0.0, 0.0, 2.0, 0.0, 0.0, 2.0)
let m3 = add_triangle(m2, 2.0, 0.0, 2.0, 2.0, 0.0, 2.0)
print(mesh_area(m3))

triangle_count(mesh) → int

Get the number of triangles in a mesh

Returns the number of triangles currently in the mesh.

use plugin navmesh::{create_mesh, add_triangle, triangle_count}

let mesh = create_mesh()
print(triangle_count(mesh))
let m2 = add_triangle(mesh, 0.0, 0.0, 1.0, 0.0, 0.0, 1.0)
print(triangle_count(m2))

heuristic(x1, y1, x2, y2) → number

Compute Manhattan distance heuristic

Computes the Manhattan distance between two integer grid points. This is the heuristic used internally by find_path and can be used independently for cost estimation.

use plugin navmesh::{heuristic}

let h = heuristic(0, 0, 5, 3)
print(h)

grid_neighbors(x, y, w, h) → table

Get valid grid neighbors for a cell

Returns all valid 4-directional neighbors of cell (x, y) within a grid of dimensions w × h. Each entry is a {x, y} table. Boundary cells return fewer than 4 neighbors.

use plugin navmesh::{grid_neighbors}

let neighbors = grid_neighbors(0, 0, 10, 10)
let n = neighbors[1]
print("{n["x"]},{n["y"]}")

let center = grid_neighbors(5, 5, 10, 10)
print(center)

View source code