Skip to content

Paths and Travel

m4bwav edited this page Nov 16, 2026 · 4 revisions

Routes and reach on a recipe (since 0.10.0). path and travel write their files into the recipe folder unless --out names another; check --chokepoints and check --fair analyse a grid map.

path

The cheapest route by A* (or jump point search with --jps) from --from to --to, on dungeons, battle maps (square and hex), deck plans, worlds and regions. It writes path.json, path.geojson and path.svg. Coordinates are squares or hexes as X,Y, DECK,X,Y on decks (decks from 1), and map km on worlds and regions.

python scripts/mpw.py path crypt.map --from 2,2 --to 30,20
path: cost 62.1421 steps, 58 steps, 500 cells expanded -> crypt.map

Square grids move 8 ways by default: a diagonal costs the square root of 2, never cuts past a wall corner and never enters or leaves a door diagonally. --moves 4 gives plain 4-way moves:

python scripts/mpw.py path crypt.map --from 2,2 --to 30,20 --moves 4
path: cost 68.0000 steps, 68 steps, 462 cells expanded -> crypt.map

On a deck plan a lift step costs 3 m and a square is 1.5 m:

python scripts/mpw.py path ship.map --from 1,2,3 --to 2,19,10
path: cost 36.3640 m, 22 steps, 53 cells expanded -> ship.map

A start or goal that is not floor stops with exit 2 and names the square (mpw: deck D square X,Y is not floor).

On a world or region the step cost is the road router's (km times slope times terrain, bridges charged on the cell entered), so costs are directed and A to B can differ from B to A:

python scripts/mpw.py path isles.map --from 200,200 --to 400,300
path: cost 471.8830 road cost (km x slope x terrain), 39 steps, 927 cells expanded -> isles.map

Cyclic dungeons keep their one-way doors. Since 0.11.0 path fetches each key before its lock (0.10 treated locks as open); path.json lists the locks and where each key was picked up. --ignore-locks gives the old search.

python scripts/mpw.py path keep.map --from 10,32 --to 17,17
python scripts/mpw.py path keep.map --from 10,32 --to 17,17 --ignore-locks
path: cost 127.5563 steps, 123 steps, 636 cells expanded -> keep.map
path: cost 21.4142 steps, 21 steps, 62 cells expanded -> keep.map

From the first run, path.json holds:

locks 1 keys [{'cell': [24.5, 17.5], 'key': 'k1', 'step': 52}]

Jump point search

--jps (since 0.11.0) finds a route of the same cost as A* on square dungeon and battle grids, expanding fewer cells. In pure Python it is slower than A* all the same, so it is not the default. It refuses hex maps, decks, worlds and --moves 4.

python scripts/mpw.py path crypt.map --from 2,2 --to 30,20 --jps
python scripts/mpw.py path hexes.map --from 1,1 --to 10,8 --jps
path: cost 62.1421 steps, 58 steps, 96 cells expanded -> crypt.map
mpw: --jps needs a uniform-cost square grid (dungeon or square battle map); hex graphs have six neighbours per cell
[exit 2]

Same cost and 58 steps as the A* run above, 96 cells expanded against 500.

Agent size (since 0.20.0)

--agent N routes a body N squares wide on square dungeon and battle grids. It uses the same top-left anchored erosion as export --nav --agent N: a square is a legal position only when the N x N block with its top-left corner there is all floor or door, and --from and --to name that top-left square. Hex grids, decks and worlds are refused; --agent 1 (the default) is the old search. From a real run on v0.20.0 (gen dungeon --seed 3 --w 40 --h 30):

$ mpw.py path d3 --from 2,2 --to 8,9 --agent 2 --out o2
path: cost 9.4853 steps, 7 steps, 14 cells expanded -> o2
$ mpw.py path d3 --from 2,2 --to 30,20 --agent 2 --out o3
mpw: no route: the goal cannot be reached from the start

The second route fails because this generator's doors are one square wide, so a 2-wide body cannot leave its room. Since 0.21.0, gen dungeon --corridor 2 makes a map it can cross (Generate places). The JSON output carries "agent": {"squares": N, "anchor": "top-left"}.

Dijkstra field

--field gives the cost to the nearest goal from every cell, with a flow step per cell (repeat --to for several goals). It writes field.json and field.svg.

python scripts/mpw.py path crypt.map --field --to 30,20
field: 1 goal(s), 854 cells reached, 0 unreachable, max 73.627 steps -> crypt.map

travel

Hours to every cell of a world or region from --from (map km), by Tobler's hiking function, in bands (--band, default 6 hours). --mode walk|offpath|horse; --to also reports the fastest route there. Writes travel.json and travel.svg.

python scripts/mpw.py travel isles.map --from 200,200 --to 400,300 --mode walk
travel (walk): 6436 cells reached, farthest 224.55 h, bands of 6.0 h: [39, 82, 103, 132, 188, 182, 157, 127, 71, 89, 141, 137, 158, 166, 163, 193, 230, 190, 238, 256, 221, 235, 276, 238, 205, 254, 313, 349, 355, 268, 155, 121, 100, 73, 78, 92, 46, 15] -> isles.map; to goal 64.246561433 h
python scripts/mpw.py travel isles.map --from 200,200 --to 400,300 --mode horse
travel (horse): 6436 cells reached, farthest 179.64 h, bands of 6.0 h: [55, 115, 152, 222, 222, 194, 105, 105, 177, 178, 211, 199, 248, 298, 240, 321, 279, 311, 335, 250, 325, 418, 447, 349, 188, 146, 101, 92, 106, 47] -> isles.map; to goal 51.397249147 h

The list counts cells per band: 39 cells within 6 hours on foot, 82 in the next 6, and so on. The same trip takes about 64 hours on foot and 51 by horse.

check --chokepoints

Cells whose loss cuts a grid map in two, what each cuts off, and the minimum cut between the entrance and the goal, checked against brute force. Writes chokepoints.json.

python scripts/mpw.py check keep.map --chokepoints
chokepoints: 0 cells, 0 bridges, 373 passable, min cut entrance to goal 2, equals brute force: True

A cyclic dungeon has none, by design: every part is on a loop, and cutting the entrance from the goal takes two cells.

check --fair

Per-start distances to resources and the area each start reaches first. --starts X,Y;X,Y (default: the entrance and the cell farthest from it) and --resources X,Y;X,Y (default: lights, else room centres). Writes fair.json.

python scripts/mpw.py check crypt.map --fair
fair: areas [424, 430] (ratio 1.014151), tied 0, unreached 0 of 854; resources reached first [8, 6]

Navigation export for an engine is export --nav (Export).

Clone this wiki locally