navplugin
Ways through a grid: windowed A*, distance fields, line of sight, routes pulled straight.
Putting it in a scene
nav has no row, no settings and nothing drawn. A rule imports it and hands it the map, the window and the costs.
import { grid, at, centre, path, pull } from '#plugins/nav/nav.sim.ts'
const g = grid(64, 48, (c, r) => blocked(c, r), 2, 24)
const route = path(g, at(g, [me.pos[0], me.pos[1]]), at(g, goal)).map(c => centre(g, c, 0.4))
const way = pull([[me.pos[0], me.pos[1]], ...route], (c, r) => blocked(c, r), 0.4)Points are [x, y] in map cells, x along a row and y down the rows. Nav cells are numbered along each row and then down, c = y × w + x.
Methods
From #plugins/nav/nav.sim.ts.
grid( across, down, blocked, sub, window ) : Nav
A nav grid over a map of across × down cells. blocked(c, r) says whether map cell [c, r] blocks, as tilemap's blocked does. Each map cell is cut into sub × sub nav cells, all blocked when it blocks. window is in map cells.
A step goes to any of the eight neighbours and costs 1 along a row or column and √2 on a diagonal. A diagonal step is taken only when both cells beside it are open, so no route cuts a corner.
path( g, from, to ) : number[]
The nav cells of the cheapest route from from to to, by A*, leaving out from. The search looks only inside a square window cells across centred on from: a goal outside it is clipped to the window's edge along the way it lies, and the mover asks again when it gets there.
An unreachable goal gives the route to the reached cell closest to it, so a walled-off mover walks up to the wall. The route is empty when from is the goal or nothing nearer can be reached. The same grid and question give the same route on every machine.
g can also be any grid of your own: { w, h, window, around(c) }, where around yields [cell, cost] for every step a mover may take from c.
at( g, [x, y] ) : number
The nav cell under a point of the map, or -1 off the map.
centre( g, c, radius = 0 ) : [x, y]
The middle of nav cell c, in map cells. Given a radius, it is the point nearest the middle where a body of that radius touches none of the blocked map cells round it, so a body steering for a cell along a wall is not held against the wall.
field( g, goal, limit ) : { g, cost }
The cost from every nav cell to goal, in map cells, by Dijkstra from the goal. cost is Infinity where the goal cannot be reached within limit map cells, and everywhere when the goal is blocked or off the map. One field serves every mover heading for the same goal.
down( f, c ) : number
The neighbour of c one step downhill on the cheapest way to the field's goal. -1 at the goal and where the field never reached.
sight( blocked, from, to, radius = 0 ) : boolean
Whether the straight line between two points of the map crosses no blocked cell. A line through a corner where four cells meet passes only when both cells beside it are open. Given a radius under a half, it is whether a body of that radius passes: the line through its middle and the two along its sides, radius off either way, must all pass. The side lines run the full length, so a point by a corner can be refused that the body would just pass.
pull( route, blocked, radius = 0 ) : [x, y][]
A route of points pulled straight. The first point is the mover's own. From each point kept, the next kept is the furthest one on that sight reaches for a body of radius, down to the last.