Navigation Grid and Flow Field

What it does

A grid runs A* between two world points and then string-pulls the result, so a route reads as a straight line wherever it can instead of a staircase of cells. NavGrid2d takes a tile map, as an array of walkable cells or a blocked(x, y) test, over world x and y, and returns plain { x, y } points for a top-down game. NavGrid samples a height function over world x and z for a 3D game on terrain, marks cliffs, water and blocked footprints unwalkable and prefers flat routes. Open or close a cell with setWalkable when a door shuts or a crate drops, and the next route goes round.

A flow field floods the whole grid outward from one goal and leaves a direction in every cell. Each follower then reads dirAt where it stands, a single lookup rather than a search, which is how a horde chases the player or a crowd pours towards an exit.

The part that is easy to get wrong is size. Give a grid, or a single call, a radius, and A* refuses gaps narrower than the body, string pulling keeps a straight leg only where the whole body fits, and a flow field floods only cells the body can stand in. A 20-unit guard is never sent through a 16-unit gap or routed so close to a door jamb that it catches, yet it still fits through any gap that is wide enough, exactly. One grid serves guards, a thief and an ogre, each planned at its own size.

Features

• A with string pulling* — direct routes as world points, or [] when there is none, or the nearest reachable point with partial.
• 2D and 3D grids — grid2d over a tile map in x and y, grid over a height function in x and z.
• Walkers with a size — a radius per grid or per call, exact against the grid's walls.
• Flow fields — one flood per goal, a direction in every cell, sized for the body.
• Straight-line checks — clear says whether a body can slide straight between two points.
• Terrain rules — cliffs by step height, a slope penalty, water below a level and blocked footprints.
• Weighted flow grids — flowGrid with costly cells, several goals, smooth steering and canBuild.
• Live edits — open and close cells as doors move, with cached clearance rebuilt only when a cell changes.
• Off-thread routes — pathAsync plans on a worker and can be cancelled.
• Headless — no objects, no drawing, the same in a worker or a test as in a frame.

Good for

• Top-down stealth and dungeon games, where guards of different sizes chase through doors and corridors.
• Horde and survival games, where hundreds of enemies flow towards the player through one field.
• Tower defence, with weighted cells, several goals and a check that a new tower leaves every spawn a route.
• 3D games on terrain, where walkers avoid cliffs and water and prefer flat ground.
• Colony and management sims, where workers walk between stores and sites.
• Strategy and tactics, where units are told where to go and must find their own way.

Make it yours

A 2D grid takes its columns and rows, the cell size, an origin and a walkable array or a blocked test, or both. A map whose walls are not whole tiles, a round pillar or a diagonal wall, can be sampled at a finer cell through blocked. A 3D grid takes the height function, its size, centre and resolution, a water level, a blocked test, the highest step a walker can climb and how much slope costs. Every grid takes a default radius, and every query can override it.

Two different uses: a top-down heist where 12-unit guards plan on a 16-unit tile map with path, and a smaller thief plans on the same grid with a 4-unit radius; and a 3D zombie game where one flow field towards the player steers a whole crowd of 1.2-unit walkers across hilly terrain, round cliffs and out of the water.

A quick look

A tile map for guards 12 units across, a route, and a door that shuts:

const map = ['##########', '#....#...#', '#....#...#', '#........#', '##########'];
const grid = game.nav.grid2d({
    cols: map[0].length, rows: map.length, cell: 16,
    walkable: [...map.join('')].map(c => c !== '#'),
    radius: 6,                                     // every guard is a 12-unit disc
});
const route = grid.path(guard, thief);             // [{x, y}, …] clear of every wall by 6
grid.setWalkable(grid.idx(5, 3), false);           // a door shuts; the next path goes round
const field = game.nav.flow(grid, player);         // a horde reads field.dirAt(x, y)

Works with

• steering — moves bodies along these routes and fields, with avoidance, flocking and arrival.
• nav-mesh — for 3D levels a height grid cannot hold: bridges, arches and a floor above a floor.
• track — for authored routes such as rails and circuits rather than searched ones.
• grid-move and grid-walker — for movement locked to a grid's lanes.
• jobs — work yards whose workers walk routes planned here.
• levelgen — mazes, dungeons and caves whose tile grids can become the walkable map.

Good to know

• The 3D grid holds one height per cell, so bridges and overhangs need nav-mesh.
• A flow field serves one goal; a second goal is a second field. The weighted flow grid takes several goals but plans for points, not bodies.
• Neither knows about moving obstacles: change a cell and plan again, or let steering's avoidance handle what moves.
• A route is clear for the body, but a follower that cuts corners early or swings wide on momentum can still clip a wall; turn early only when clear says so.
• Walls are whole cells, so curved and diagonal walls need a cell small enough to follow them.