pathfinder is an MIT-licensed, clean-room pathfinding and navigation service
for Atrinik. It loads an authored content checkout and answers movement
queries over gRPC, so any program can share one implementation: the Classic
server, the playtester bot, or the next-generation server. Talking to it over
the network keeps its MIT code separate from GPL clients that consult it.
The service is being built in stages:
- Precise pathfinding: exact tile-by-tile paths for one agent, across tiled-map seams, exits and stairs, honouring terrain, static blockers, locked doors, diagonal-corner rules and temporary obstacles.
- Offline atlas and road planner: a precomputed, versioned world graph of connectors (exits, arrivals and seam crossings) joined by road-weighted walks, searched like a car navigation system that prefers highways for most of a long journey, and returning waypoints instead of every tile.
- Group movement (next): flow fields shared by many monsters or NPCs heading for one goal.
The contract is proto/atrinik/pathfinder/v1/pathfinder.proto
(package atrinik.pathfinder.v1). Generated Go bindings are committed under
gen/go/. The service also implements the standard grpc.health.v1 health
protocol.
FindPath(start, goal_tile | goal_map, agent, blocked, max_expanded)returns the shortest steps (START,WALK,SEAM,EXIT) and their cost. Every move costs one, diagonal or not; so do a seam crossing and an exit. An automatic exit (triggered by stepping on it) is reported as the walk onto its tile followed by the exit; an applied exit is used from the tile the agent stands on. Nobody can stop on an automatic exit, so it is never a goal tile (ask for its destination map instead); a path that starts on one, or arrives on one through another exit, continues through it.AgentProfileselects the terrain bits the agent can stand on (walking by default), the keys it carries, the diagonal corner policy (STRICTby default: both orthogonal neighbours must be passable), whether it must stay on its map (monsters and NPCs), and maps to avoid.Plan(start, goal_tile | goal_map, avoided_maps, spacing)returns a route as sparse waypoints for a plain walker (walking terrain, no keys, strict corners):START, thenWALKpoints to click-to-move between,EXITtiles to apply (or step onto, whenautomatic),SEAMborder tiles to step across,ARRIVEwhere those land, andGOAL. Consecutive waypoints on one map are at mostspacingtiles apart (7 by default), and walking straight between them stays within a tile of the planned route (half a tile on roads, whose entry and exit points are always kept), and every segment between two waypoints can be walked in a straight line. A plan that starts on an automatic exit begins by taking it, and one that starts on an exit inside a wall can still use it.max_expandedbounds a plan's work, counting each connector expanded, edge examined, tile searched and waypoint returned (capped by the server's-max-expanded); hitting it returnsLIMIT_REACHED. Roads cost two thirds of a plain step, so the route follows them where the detour pays;costis in thirds of a move andtilescounts the moves. Agents with other abilities (keys, swimming, staying on one map) useFindPath.GetAtlasInforeports the atlas' connectors, edges, road tiles, content digest and whether it was built at startup or loaded from a file.DescribeMaplists a map's size, walkable tiles, seams and exits.GetWorldInforeports the loaded maps, tiles, transitions and a SHA-256 digest of the content files.
The reader parses the authored text formats directly: archetypes from
arch/**/*.arc (Object … end blocks, More multipart parts) and maps
from extension-less files under maps/ (an arch map header, then arch …
end objects with nested inventories). A map object's attributes override its
archetype's. The movement model compiles:
- terrain: the union of every object's
terrain_typebits on a tile; a tile without any is void; - blockers:
no_pass 1objects, including every part of a multipart archetype, except doors (types 20 and 64) and exits (type 66), which can be passed; - locks: a door's
slayingnames the key that opens it; - exits (type 66):
slayingnames the destination (relative to the map's directory unless absolute) andhp/spthe arrival tile, defaulting to the destination'senter_x/enter_y;walk_on/fly_onmake it automatic. A destination-less stair withlast_heal9 (up) or 10 (down) leads to the same tile oftile_path_9/tile_path_10or of the coordinate map one level up or down; - seams:
tile_path_1…tile_path_8(north, east, south, west, then the four diagonals), and for coordinate-named maps such asworld_1_50orworld_6_48_-2(two or three integers of at most three digits ending the name) the existing neighbours of the same level.
A map without a positive width and height fails the load with its path.
The atlas (internal/atlas) is the planner's road network:
- roads are tiles holding a floor archetype from
floors/flagstone/,floors/bridge_wood/orfloors/snow/snow_path/; - connectors are the tiles where travel leaves or enters an area: exit tiles, exit arrivals, and one crossing per run of border tiles that joins the same two walkable components across a seam (diagonal crossings need both corner tiles passable, and a crossing onto an automatic exit is its own connector);
- edges are exits and seam crossings (cost 3), and walks between every pair of connectors in one walkable component of a map, priced by a road-weighted Dijkstra search (2 per step between road tiles, 3 otherwise).
A plan searches only the connector graph, starting from the connectors the start can walk to and finishing at the goal (or at any connector on the goal map), then re-derives the tile path of each walk it uses and simplifies it into waypoints (Ramer-Douglas-Peucker with a one-tile tolerance, split to the requested spacing). Without roads and seams it finds exactly the precise search's routes at the same cost; a seam is crossed at the middle of its run.
pathfinderd builds the atlas at startup unless -atlas names a prebuilt
file from the atlas command (format
proto/atrinik/pathfinder/atlas/v1/atlas.proto).
A file is stamped with the content digest and map list and is refused for any
other content, and carries a SHA-256 digest of its connector graph that loading
verifies. Loading also recomputes the connectors, exits and seams (they
follow cheaply from the content) and requires the file to match them exactly;
only the costly walks are read: exactly one from each connector to every
other connector walkable from its component, so a damaged file is refused
rather than silently losing or inventing routes.
A plan also checks each walk it re-derives against its edge's cost and fails
with DATA_LOSS on a mismatch. These checks detect damage, not forgery: an
atlas file is trusted operator input, like the content checkout and the
binary, since proving every stored walk cost exact would cost as much as
building the atlas. Serve a file only from where the content comes from, or
let the daemon build the atlas. Files are byte-for-byte reproducible. Like path searches, at most
-max-concurrent plans run at once, each reusing its own scratch space, and
a canceled request stops its plan.
Go 1.26.9 (see .go-version) is the only build requirement.
go build ./cmd/pathfinderd ./cmd/atlas
./atlas -content ../content -out content.atlas # optional
./pathfinderd -content ../content -atlas content.atlas -listen 127.0.0.1:7843The server listens on loopback by default. Each search uses scratch space
proportional to the world (about 17 bytes per tile, roughly 35 MB for the
current content). At most -max-concurrent searches (the CPU count by
default) run at once, each with its own retained scratch; further requests
are rejected with RESOURCE_EXHAUSTED rather than allocating more. A
canceled or expired request stops its search.
sh tools/install-ci-dependencies.sh # pinned buf, protoc plugins, linters
sh tools/generate.sh # after editing proto/
sh tools/validate.sh # everything CI checks
PATHFINDER_CONTENT=../content go test ./internal/search ./internal/atlas -run RealContent -vOn the current content (3,660 maps, 2.08 million tiles), loading takes about a second; the 149-step walk from the Asteria inn to the Strakewood Island farm takes about 6 ms. The atlas has 8,915 connectors, 74,277 edges and 35,960 road tiles. Building it takes 35 ms on 32 cores and 250 ms on one; loading its 900 KB file takes 29 ms and 50 ms. Planning the inn-to-farm trip takes about 0.6 ms (72 waypoints over 163 tiles), and the 447-step walk from Strakewood town to the farm about 1.8 ms instead of 28 ms for the precise search, with 14 allocations from a reused planner slot; roads lengthen these walks by 5 to 10 %.
Contributions follow CONTRIBUTING.md. Provenance is recorded in PROVENANCE.md and dependencies in THIRD_PARTY_NOTICES.md. The project is MIT licensed (LICENSE).