astar-mumu

A fast, pragmatic grid-search & map-generation plugin for the Lava/MuMu language:

• Path-finding on 2D grids (unit-cost BFS)
• Deterministic maze & “boulders” field generators
• PNG renderers for maps and solution paths

What this plugin provides

This crate builds a dynamic plugin library (libmumuastar.*) that the Lava/MuMu runtime can extend("astar"). It registers a small, cohesive toolbox for 2D grid work:

Generators

• astar:maze(seed, [width=21], [height=21], [sx=0], [sy=0], [ex=width-1], [ey=height-1]) -> descriptor
  Generates a perfect maze by randomized DFS carve. Width and height must be odd and ≥ 3. Returns a descriptor (keyed array) with:

  • dimension : [width, height]
  • start : [sx, sy]
  • end : [ex, ey]
  • obj : [[x,y], ...] // walls/obstacles (closed cells)

• astar:boulders([ seed, width, height, count, start?, end? ]) -> descriptor
  Samples several filled ellipses (“boulders”) with a deterministic RNG (via fastrand) to create a natural-looking obstacle field. Returns the same descriptor shape as astar:maze.

Solvers

• astar:path(descriptor, [sx,sy], [ex,ey]) -> descriptor'
  Computes a unit-cost BFS from start to end. If the requested start/end are blocked, it will snap each to the nearest passable cell within a small radius (10), otherwise it fails gracefully. Returns the input map augmented with:

  • requested_start : [rx, ry]
  • requested_end : [rx, ry]
  • start : [sx, sy] // possibly snapped
  • end : [ex, ey] // possibly snapped
  • snapped_start : true (optional)
  • snapped_end : true (optional)
  • path : [[x,y], ...] // present when a route exists
  • success : bool
  • cost : float // == path length for unit cost
  • pathLength : int

• astar:astar(descriptor) -> descriptor'
  Accepts a single descriptor (with dimension, start, end, obj). Runs a BFS and returns the same map extended with:

  • path, success, cost, pathLength
  • steps : int // node expansions
  • timeMs : int // wall-clock time at this call site

Note on the name: This crate is named astar-mumu, but the current search implementation is a fast, simple BFS for unit-weight grids. For weighted costs, an A* variant can be introduced later without changing the descriptor format.

PNG renderers

• astar:png(descriptor, "file.png") -> descriptor'
  Renders a black/white image (walls black, open cells white). If path is present, it is over-painted in green. Returns the descriptor plus:

  • png_file : "file.png"

• astar:maze_png(seed, [width], [height], [...], "file.png") -> descriptor
  Convenience for “generate + save”: produces the maze image and returns the descriptor.

• astar:path_png(descriptor, "file.png") -> descriptor
  Computes a path (BFS) for the provided descriptor and draws it directly to disk in green.

Data model (descriptor schema)

All functions in this plugin speak the same compact keyed-array schema:

[
  dimension: [width:int, height:int],    // 0 ≤ x < width, 0 ≤ y < height
  start:     [sx:int,   sy:int],         // optional on generators
  end:       [ex:int,   ey:int],
  obj:       [[x:int, y:int], ...],      // obstacles (closed cells)

  // solver/renderer outputs may add:
  path:        [[x:int, y:int], ...],
  success:     bool,
  cost:        float,        // == path length for unit grids
  pathLength:  int,

  // solver bookkeeping:
  steps:       int,          // node expansions (astar:astar)
  timeMs:      int,          // runtime in ms (astar:astar)
  requested_start: [rx:int, ry:int],
  requested_end:   [rx:int, ry:int],
  snapped_start:   true,
  snapped_end:     true,

  // renderer bookkeeping:
  png_file: "file.png"
]

Coordinate system & invariants

• Grid is 0-indexed: 0 ≤ x < width, 0 ≤ y < height.
• obj is a list of blocked coordinates (walls).
• path is a list of coordinates from start to end (inclusive).
• For maze generation, (width, height) must be odd to satisfy perfect-maze carving rules.
• astar:path will not mutate your obj; it only augments fields in the descriptor it returns.

Quick examples

These are Lava/MuMu snippets showing typical flows. They assume your host has loaded the plugin with extend("astar"). No install steps are shown here.

Maze → path → PNG

extend("astar")

// Create a perfect 41x41 maze and solve from top-left to bottom-right:
m = astar:maze(42, 41, 41, 0, 0, 40, 40)
s = astar:path(m, [0,0], [40,40])
astar:png(s, "maze.png")       /* path painted green */

Boulders field → path → PNG

extend("astar")

desc = astar:boulders([
  seed:   1337,
  width:  60,
  height: 40,
  count:  12
])

solved = astar:path(desc, [1,1], [58,38])
astar:png(solved, "boulders.png")

Single-call solver with runtime stats

extend("astar")

input = [
  dimension: [50, 30],
  start:     [1, 1],
  end:       [48, 28],
  obj:       [[10,10],[10,11],[10,12]]   // etc...
]
out = astar:astar(input)
slog(out.steps, out.timeMs, out.success, out.pathLength)

Behavior & design notes

• Determinism: Maze and boulders generators use fastrand seeded by your seed (and, for mazes, the carve also incorporates (sx, sy) to avoid trivial bias). Given the same inputs you get identical outputs.
• Performance model: Solvers use BFS on unit-cost grids. For large maps, expansions grow with reachable area. The steps field in astar:astar is the expansion count; timeMs is wall-clock at the Rust call site.
• Snapping semantics (astar:path): If either requested endpoint is blocked, the solver tries to snap it to the nearest passable cell within a small radius (10). It records requested_* and sets snapped_* flags when that happens. If no passable cell is found within the radius, it returns success=false with an empty path.
• PNG colors: open cells are white, obstacles black, solution green (0,255,0). Renderers do not modify the input descriptor beyond adding png_file.

API summary (cheat-sheet)

Compatibility & features

• Engine compatibility: Built and tested against core-mumu = 0.9.0-rc.4 (see Cargo.toml).
• Targets:
  • Native (host): links the engine with the host feature; the produced dynamic library is discoverable by Lava’s loader (extend("astar") looks for libmumuastar.*).
  • Wasm: the crate toggles the engine’s wasm feature for compilation. (Dynamic loading is a host concern; renderer functions rely on the image crate and are intended for native use.)
• Dependencies: indexmap for stable descriptor key order, fastrand for generation, and image for PNG output. Optional libloading is present for parity in host builds.

Error reporting

Functions return descriptive errors when inputs are invalid. Typical messages include:

• maze ⇒ width and height must be odd numbers ≥ 3
• astar:path ⇒ start must be [x,y]
• path_png ⇒ second arg must be single string
• astar:png ⇒ descriptor missing 'dimension'

At the Lava level these are surfaced as runtime errors.

Contributing

Contributions that add weighted costs, true A* heuristics, diagonal move policies, or alternative map generators are welcome. The grid descriptor is intentionally minimal so extensions remain straightforward.

• Repository: https://gitlab.com/tofo/mumu-astar
• Please include focused tests and keep the descriptor schema stable.

Acknowledgements

• Tom Fotheringham and the Lava/MuMu community for the host runtime and plugin ecosystem.
• All contributors who reported issues, proposed features, and reviewed patches.

License

Dual-licensed under either of:

• MIT license
• Apache-2.0 license

at your option.

See the crate’s Cargo.toml for canonical metadata and the repository for license texts.