Mazes

use maze.qweruse maze_generate, maze_solve from maze      // Quillo 0.6: only these

serde_json = { version = "1", features = ["preserve_order"] }

// Mazes: one made from a seed by each algorithm, solved, measured, loosened with loops, and drawn// as text and as an SVG in a page.////   quillo run maze.qwe//   then open http://localhost:8080/maze.svg?seed=7, /text, /algorithms, /solve, /braid and /refuseduse "maze.qwer"route GET /maze.svg ? { seed: int = 1, width: int = 24, height: int = 16 } {    let m = maze_generate(width, height, { seed: seed, algorithm: "wilson" })?    respond(200, maze_svg(m, { path: true, cell: 18 })?, { "content-type": "image/svg+xml" })}route GET /text {    let m = maze_generate(6, 4, { seed: 3 })?    respond(200, maze_text(m, { path: true })?, { "content-type": "text/plain; charset=utf-8" })}let names = ["backtracker", "prim", "kruskal", "wilson", "aldous_broder", "binary_tree", "sidewinder", "hunt_and_kill"]// Every algorithm must give one path between any two cells; how they differ shows in the numbers.route GET /algorithms = names | map((n) => {    let m = maze_generate(30, 30, { algorithm: n, seed: 5 })?    let s = maze_stats(m)?    let solved = maze_solve(m, {})?    { algorithm: n, perfect: s.perfect, passages: s.passages, solved: solved.solved, visited_all: solved.visited == 900, dead_ends: s.dead_ends, longest: s.longest.length }})route GET /solve {    let a = maze_generate(20, 20, { seed: 9, algorithm: "prim" })?    let p = maze_solve(a, {})?    let across = maze_solve(a, { from: [19, 0], to: [0, 19] })?    {        same_seed: maze_generate(20, 20, { seed: 9, algorithm: "prim" })? == a,        other_seed: maze_generate(20, 20, { seed: 10, algorithm: "prim" })?.cells == a.cells,        starts: first(p.path),        ends: last(p.path),        steps_match: len(p.path) == p.length + 1,        across: last(across.path),        svg: starts_with(maze_svg(a, {})?, "<svg"),        one_cell: maze_solve(maze_generate(1, 1, {})?, {})?,    }}route GET /braid {    let m = maze_generate(30, 30, { seed: 4, braid: 1.0 })?    let s = maze_stats(m)?    { loops_made: s.loops > 0, perfect: s.perfect, connected: s.connected, dead_ends: s.dead_ends }}route GET /refused = {    algorithm: maze_generate(4, 4, { algorithm: "magic" }).error,    size: maze_generate(0, 4, {}).error,    braid: maze_generate(4, 4, { braid: 2.0 }).error,    outside: maze_solve(maze_generate(4, 4, {})?, { from: [9, 9] }).error,    bad_maze: maze_solve({ width: 2, height: 1, cells: [[2, 0]] }, {}).error,    walled: maze_solve({ width: 2, height: 1, cells: [[0, 0]] }, {})?,    color: maze_svg(maze_generate(2, 2, {})?, { color: "\"/><script>" }).error,}

//! Mazes generated from a seed by eight algorithms, solved, measured, loosened with loops, and drawn to text and SVG.//! version: 1.0.0//!//! [dependencies]//! serde_json = { version = "1", features = ["preserve_order"] }use serde_json::{json, Value};use std::collections::VecDeque;const N: u8 = 1;const E: u8 = 2;const S: u8 = 4;const W: u8 = 8;const DIRS: [(u8, i64, i64, u8); 4] = [(N, 0, -1, S), (E, 1, 0, W), (S, 0, 1, N), (W, -1, 0, E)];const MAX_CELLS: i64 = 4_000_000;struct Rng(u64);impl Rng {    fn next(&mut self) -> u64 {        self.0 = self.0.wrapping_add(0x9E3779B97F4A7C15);        let mut z = self.0;        z = (z ^ (z >> 30)).wrapping_mul(0xBF58476D1CE4E5B9);        z = (z ^ (z >> 27)).wrapping_mul(0x94D049BB133111EB);        z ^ (z >> 31)    }    fn below(&mut self, n: usize) -> usize {        (self.next() % n as u64) as usize    }    fn pick<T: Copy>(&mut self, v: &[T]) -> T {        v[self.below(v.len())]    }}struct Grid {    w: i64,    h: i64,    cells: Vec<u8>, // Bits for the open sides.}impl Grid {    fn at(&self, x: i64, y: i64) -> usize {        (y * self.w + x) as usize    }    fn inside(&self, x: i64, y: i64) -> bool {        x >= 0 && y >= 0 && x < self.w && y < self.h    }    fn xy(&self, i: usize) -> (i64, i64) {        (i as i64 % self.w, i as i64 / self.w)    }    fn carve(&mut self, a: usize, d: usize) -> usize {        let (bit, dx, dy, back) = DIRS[d];        let (x, y) = self.xy(a);        let b = self.at(x + dx, y + dy);        self.cells[a] |= bit;        self.cells[b] |= back;        b    }    fn near(&self, a: usize) -> Vec<(usize, usize)> {        let (x, y) = self.xy(a);        let mut o = Vec::with_capacity(4);        for (i, (_, dx, dy, _)) in DIRS.iter().enumerate() {            if self.inside(x + dx, y + dy) {                o.push((i, self.at(x + dx, y + dy)));            }        }        o    }    fn open(&self, a: usize) -> Vec<usize> {        let (x, y) = self.xy(a);        DIRS.iter().filter(|d| self.cells[a] & d.0 != 0).map(|d| self.at(x + d.1, y + d.2)).collect()    }}fn backtracker(g: &mut Grid, r: &mut Rng) {    let n = g.cells.len();    let mut seen = vec![false; n];    let mut stack = vec![r.below(n)];    seen[stack[0]] = true;    while let Some(&c) = stack.last() {        let free: Vec<(usize, usize)> = g.near(c).into_iter().filter(|x| !seen[x.1]).collect();        if free.is_empty() {            stack.pop();        } else {            let (d, b) = r.pick(&free);            g.carve(c, d);            seen[b] = true;            stack.push(b);        }    }}fn prim(g: &mut Grid, r: &mut Rng) {    let n = g.cells.len();    let mut seen = vec![false; n];    let s = r.below(n);    seen[s] = true;    let mut front: Vec<(usize, usize)> = g.near(s).into_iter().map(|x| (s, x.0)).collect();    while !front.is_empty() {        let i = r.below(front.len());        let (a, d) = front.swap_remove(i);        let (x, y) = g.xy(a);        let b = g.at(x + DIRS[d].1, y + DIRS[d].2);        if seen[b] {            continue;        }        g.carve(a, d);        seen[b] = true;        front.extend(g.near(b).into_iter().filter(|e| !seen[e.1]).map(|e| (b, e.0)));    }}fn find(p: &mut Vec<usize>, x: usize) -> usize {    let mut a = x;    while p[a] != a {        p[a] = p[p[a]];        a = p[a];    }    a}fn kruskal(g: &mut Grid, r: &mut Rng) {    let n = g.cells.len();    let mut edges = vec![];    for c in 0..n {        for (d, _) in g.near(c) {            if d == 1 || d == 2 {                edges.push((c, d));            }        }    }    for i in (1..edges.len()).rev() {        edges.swap(i, r.below(i + 1));    }    let mut p: Vec<usize> = (0..n).collect();    for (a, d) in edges {        let (x, y) = g.xy(a);        let b = g.at(x + DIRS[d].1, y + DIRS[d].2);        let (ra, rb) = (find(&mut p, a), find(&mut p, b));        if ra != rb {            p[ra] = rb;            g.carve(a, d);        }    }}// Loop-erased random walks: unbiased among all spanning trees, slow to start.fn wilson(g: &mut Grid, r: &mut Rng) {    let n = g.cells.len();    let mut inside = vec![false; n];    inside[r.below(n)] = true;    let mut left: Vec<usize> = (0..n).filter(|c| !inside[*c]).collect();    let mut way = vec![usize::MAX; n];    while let Some(start) = left.pop() {        if inside[start] {            continue;        }        let mut c = start;        while !inside[c] {            let (d, b) = r.pick(&g.near(c));            way[c] = d;            c = b;        }        let mut c = start;        while !inside[c] {            inside[c] = true;            c = g.carve(c, way[c]);        }    }}fn aldous_broder(g: &mut Grid, r: &mut Rng) {    let n = g.cells.len();    let mut seen = vec![false; n];    let mut c = r.below(n);    seen[c] = true;    let mut left = n - 1;    while left > 0 {        let (d, b) = r.pick(&g.near(c));        if !seen[b] {            g.carve(c, d);            seen[b] = true;            left -= 1;        }        c = b;    }}fn binary_tree(g: &mut Grid, r: &mut Rng) {    for c in 0..g.cells.len() {        let (x, y) = g.xy(c);        let mut o = vec![];        if y > 0 {            o.push(0);        }        if x + 1 < g.w {            o.push(1);        }        if !o.is_empty() {            let d = r.pick(&o);            g.carve(c, d);        }    }}fn sidewinder(g: &mut Grid, r: &mut Rng) {    for y in 0..g.h {        let mut run = vec![];        for x in 0..g.w {            let c = g.at(x, y);            run.push(c);            let close = x + 1 == g.w || (y > 0 && r.below(2) == 0);            if close {                if y > 0 {                    let m = r.pick(&run);                    g.carve(m, 0);                }                run.clear();            } else {                g.carve(c, 1);            }        }    }}fn hunt_and_kill(g: &mut Grid, r: &mut Rng) {    let n = g.cells.len();    let mut seen = vec![false; n];    let mut c = r.below(n);    seen[c] = true;    let mut scan = 0;    loop {        let free: Vec<(usize, usize)> = g.near(c).into_iter().filter(|x| !seen[x.1]).collect();        if !free.is_empty() {            let (d, b) = r.pick(&free);            g.carve(c, d);            seen[b] = true;            c = b;            continue;        }        // The hunt: the first unseen cell beside a seen one.        while scan < n && seen[scan] {            scan += 1;        }        let mut found = None;        for i in scan..n {            if !seen[i] {                let ns: Vec<(usize, usize)> = g.near(i).into_iter().filter(|x| seen[x.1]).collect();                if !ns.is_empty() {                    found = Some((i, r.pick(&ns).0));                    break;                }            }        }        match found {            Some((cell, d)) => {                g.carve(cell, d);                seen[cell] = true;                c = cell;            }            None => return,        }    }}const ALGORITHMS: [&str; 8] = ["backtracker", "prim", "kruskal", "wilson", "aldous_broder", "binary_tree", "sidewinder", "hunt_and_kill"];fn to_value(g: &Grid, algorithm: &str, seed: i64) -> Value {    json!({        "width": g.w, "height": g.h, "algorithm": algorithm, "seed": seed,        "start": [0, 0], "goal": [g.w - 1, g.h - 1],        "cells": g.cells.chunks(g.w as usize).map(|r| r.to_vec()).collect::<Vec<_>>(),    })}fn from_value(m: &Value) -> Result<Grid, String> {    let w = m.get("width").and_then(|v| v.as_i64()).ok_or("a maze has `width`, as maze_generate gives")?;    let h = m.get("height").and_then(|v| v.as_i64()).ok_or("a maze has `height`")?;    let rows = m.get("cells").and_then(|v| v.as_array()).ok_or("a maze has `cells`")?;    if rows.len() as i64 != h {        return Err(format!("the maze says {} rows and has {}", h, rows.len()));    }    let mut cells = Vec::with_capacity((w * h) as usize);    for r in rows {        let r = r.as_array().ok_or("each row of `cells` is a list")?;        if r.len() as i64 != w {            return Err(format!("the maze says {} columns and a row has {}", w, r.len()));        }        for c in r {            let v = c.as_u64().filter(|x| *x < 16).ok_or("a cell is 0 to 15: 1 north, 2 east, 4 south, 8 west")?;            cells.push(v as u8);        }    }    let g = Grid { w, h, cells };    // Walls must agree from both sides, and none may lead off the grid.    for c in 0..g.cells.len() {        let (x, y) = g.xy(c);        for (bit, dx, dy, back) in DIRS {            if g.cells[c] & bit != 0 {                if !g.inside(x + dx, y + dy) {                    return Err(format!("cell {},{} opens off the grid", x, y));                }                if g.cells[g.at(x + dx, y + dy)] & back == 0 {                    return Err(format!("cell {},{} opens onto a wall", x, y));                }            }        }    }    Ok(g)}/// A perfect maze, one path between any two cells: { width, height, algorithm, seed, start, goal, cells }. Each cell is 1 north + 2 east + 4 south + 8 west for its open sides. `options`: { algorithm, seed, braid }; algorithms are backtracker (long corridors), prim, kruskal, wilson and aldous_broder (unbiased), binary_tree, sidewinder and hunt_and_kill. `braid` from 0 to 1 removes that share of dead ends, making loops.pub fn maze_generate(width: i64, height: i64, options: serde_json::Value) -> Result<Value, String> {    if width < 1 || height < 1 || width.saturating_mul(height) > MAX_CELLS {        return Err(format!("a maze is at least 1 by 1 and at most {} cells, not {} by {}", MAX_CELLS, width, height));    }    let alg = options.get("algorithm").and_then(|v| v.as_str()).unwrap_or("backtracker");    let seed = options.get("seed").and_then(|v| v.as_i64()).unwrap_or(1);    let braid = options.get("braid").and_then(|v| v.as_f64()).unwrap_or(0.0);    if !(0.0..=1.0).contains(&braid) {        return Err(format!("braid is 0 to 1, not {}", braid));    }    if matches!(alg, "wilson" | "aldous_broder") && width * height > 250_000 {        return Err(format!("{} takes far too long past 250000 cells", alg));    }    let mut g = Grid { w: width, h: height, cells: vec![0; (width * height) as usize] };    let mut r = Rng(seed as u64);    if g.cells.len() > 1 {        match alg {            "backtracker" => backtracker(&mut g, &mut r),            "prim" => prim(&mut g, &mut r),            "kruskal" => kruskal(&mut g, &mut r),            "wilson" => wilson(&mut g, &mut r),            "aldous_broder" => aldous_broder(&mut g, &mut r),            "binary_tree" => binary_tree(&mut g, &mut r),            "sidewinder" => sidewinder(&mut g, &mut r),            "hunt_and_kill" => hunt_and_kill(&mut g, &mut r),            o => return Err(format!("no algorithm `{}`; there are {}", o, ALGORITHMS.join(", "))),        }    }    if braid > 0.0 {        for c in 0..g.cells.len() {            if g.cells[c].count_ones() == 1 && (r.next() as f64 / u64::MAX as f64) < braid {                let shut: Vec<(usize, usize)> = g.near(c).into_iter().filter(|(d, _)| g.cells[c] & DIRS[*d].0 == 0).collect();                if !shut.is_empty() {                    // Better to join two dead ends, which removes both.                    let pick = shut.iter().find(|x| g.cells[x.1].count_ones() == 1).copied().unwrap_or_else(|| r.pick(&shut));                    g.carve(c, pick.0);                }            }        }    }    Ok(to_value(&g, alg, seed))}fn point(v: Option<&Value>, g: &Grid, fallback: (i64, i64)) -> Result<usize, String> {    let (x, y) = match v {        Some(p) => (p.get(0).and_then(|a| a.as_i64()).ok_or("a point is [x, y]")?, p.get(1).and_then(|a| a.as_i64()).ok_or("a point is [x, y]")?),        None => fallback,    };    if !g.inside(x, y) {        return Err(format!("[{}, {}] is outside the {} by {} maze", x, y, g.w, g.h));    }    Ok(g.at(x, y))}fn bfs(g: &Grid, from: usize) -> (Vec<i64>, Vec<usize>) {    let mut dist = vec![-1; g.cells.len()];    let mut prev = vec![usize::MAX; g.cells.len()];    let mut q = VecDeque::from([from]);    dist[from] = 0;    while let Some(c) = q.pop_front() {        for n in g.open(c) {            if dist[n] < 0 {                dist[n] = dist[c] + 1;                prev[n] = c;                q.push_back(n);            }        }    }    (dist, prev)}fn route(g: &Grid, m: &Value, opts: &Value) -> Result<Option<Vec<usize>>, String> {    let start = opts.get("from").or(m.get("start"));    let goal = opts.get("to").or(m.get("goal"));    let (a, b) = (point(start, g, (0, 0))?, point(goal, g, (g.w - 1, g.h - 1))?);    let (dist, prev) = bfs(g, a);    if dist[b] < 0 {        return Ok(None);    }    let mut path = vec![b];    let mut c = b;    while c != a {        c = prev[c];        path.push(c);    }    path.reverse();    Ok(Some(path))}/// The shortest way through, by breadth-first search: { solved, length, path, visited }, `path` a list of [x, y], `length` its steps. `options`: { from, to }, else the maze's start and goal.pub fn maze_solve(maze: serde_json::Value, options: serde_json::Value) -> Result<Value, String> {    let g = from_value(&maze)?;    let visited = bfs(&g, point(options.get("from").or(maze.get("start")), &g, (0, 0))?).0.iter().filter(|d| **d >= 0).count();    Ok(match route(&g, &maze, &options)? {        Some(p) => json!({ "solved": true, "length": p.len() - 1, "visited": visited, "path": p.iter().map(|c| { let (x, y) = g.xy(*c); json!([x, y]) }).collect::<Vec<_>>() }),        None => json!({ "solved": false, "length": null, "visited": visited, "path": [] }),    })}/// How a maze is built: { cells, passages, dead_ends, junctions, corridors, loops, connected, perfect, longest }, `longest` the length of the longest shortest path and [from, to] its ends, found by two sweeps where the maze is perfect.pub fn maze_stats(maze: serde_json::Value) -> Result<Value, String> {    let g = from_value(&maze)?;    let n = g.cells.len();    let deg: Vec<u32> = g.cells.iter().map(|c| c.count_ones()).collect();    let passages: i64 = deg.iter().map(|d| *d as i64).sum::<i64>() / 2;    let (d0, _) = bfs(&g, 0);    let connected = d0.iter().all(|d| *d >= 0);    let far = (0..n).max_by_key(|i| d0[*i]).unwrap_or(0);    let (d1, _) = bfs(&g, far);    let end = (0..n).max_by_key(|i| d1[*i]).unwrap_or(0);    Ok(json!({        "cells": n, "passages": passages, "dead_ends": deg.iter().filter(|d| **d == 1).count(),        "corridors": deg.iter().filter(|d| **d == 2).count(), "junctions": deg.iter().filter(|d| **d > 2).count(),        "loops": passages - n as i64 + 1, "connected": connected, "perfect": connected && passages == n as i64 - 1,        "longest": { "length": d1[end], "from": g.xy(far).0.to_string() + "," + &g.xy(far).1.to_string(), "to": g.xy(end).0.to_string() + "," + &g.xy(end).1.to_string() },    }))}/// A maze drawn in text with `+--+` walls: S at the start, G at the goal, and dots along the path when `options.path` is true.pub fn maze_text(maze: serde_json::Value, options: serde_json::Value) -> Result<String, String> {    let g = from_value(&maze)?;    let path = if options.get("path").and_then(|v| v.as_bool()).unwrap_or(false) { route(&g, &maze, &options)?.unwrap_or_default() } else { vec![] };    let (a, b) = (point(maze.get("start"), &g, (0, 0))?, point(maze.get("goal"), &g, (g.w - 1, g.h - 1))?);    let mut o = String::new();    for y in 0..g.h {        for x in 0..g.w {            o.push('+');            o.push_str(if g.cells[g.at(x, y)] & N != 0 { "  " } else { "--" });        }        o.push_str("+\n");        for x in 0..g.w {            let c = g.at(x, y);            o.push(if g.cells[c] & W != 0 { ' ' } else { '|' });            o.push_str(if c == a {                "S "            } else if c == b {                "G "            } else if path.contains(&c) {                ". "            } else {                "  "            });        }        o.push_str("|\n");    }    for _ in 0..g.w {        o.push_str("+--");    }    o.push_str("+\n");    Ok(o)}fn color(v: Option<&Value>, fallback: &str) -> Result<String, String> {    match v.and_then(|x| x.as_str()) {        Some(c) if c.chars().all(|x| x.is_ascii_alphanumeric() || x == '#') => Ok(c.to_string()),        Some(c) => Err(format!("`{}` is not a colour: a name or #hex", c)),        None => Ok(fallback.to_string()),    }}/// A maze as an SVG document. `options`: { cell (pixels, default 16), wall (stroke width), color, background, path (draw the solution), path_color }. Walls are one path element, so a 200 by 200 maze stays small.pub fn maze_svg(maze: serde_json::Value, options: serde_json::Value) -> Result<String, String> {    let g = from_value(&maze)?;    let cell = options.get("cell").and_then(|v| v.as_i64()).unwrap_or(16).clamp(2, 200);    let wall = options.get("wall").and_then(|v| v.as_f64()).unwrap_or(2.0);    let (ink, bg, line) = (color(options.get("color"), "#222")?, color(options.get("background"), "#fff")?, color(options.get("path_color"), "#e0483e")?);    let m = cell / 2 + 1;    let (w, h) = (g.w * cell + 2 * m, g.h * cell + 2 * m);    let mut d = format!("M{} {}h{}v{}h{}v{}", m, m, g.w * cell, g.h * cell, -g.w * cell, -g.h * cell);    for y in 0..g.h {        for x in 0..g.w {            let c = g.cells[g.at(x, y)];            let (px, py) = (m + x * cell, m + y * cell);            if c & E == 0 && x + 1 < g.w {                d.push_str(&format!("M{} {}v{}", px + cell, py, cell));            }            if c & S == 0 && y + 1 < g.h {                d.push_str(&format!("M{} {}h{}", px, py + cell, cell));            }        }    }    let mut o = format!("<svg xmlns=\"http://www.w3.org/2000/svg\" width=\"{}\" height=\"{}\" viewBox=\"0 0 {} {}\"><rect width=\"100%\" height=\"100%\" fill=\"{}\"/>", w, h, w, h, bg);    o.push_str(&format!("<path d=\"{}\" fill=\"none\" stroke=\"{}\" stroke-width=\"{}\" stroke-linecap=\"square\"/>", d, ink, wall));    if options.get("path").and_then(|v| v.as_bool()).unwrap_or(false) {        if let Some(p) = route(&g, &maze, &options)? {            let pts: Vec<String> = p.iter().map(|c| { let (x, y) = g.xy(*c); format!("{},{}", m + x * cell + cell / 2, m + y * cell + cell / 2) }).collect();            o.push_str(&format!("<polyline points=\"{}\" fill=\"none\" stroke=\"{}\" stroke-width=\"{}\" stroke-linejoin=\"round\"/>", pts.join(" "), line, (cell as f64 / 4.0).max(1.0)));        }    }    o.push_str("</svg>");    Ok(o)}