Grid paths

use grid_paths.qweruse grid_path, grid_reachable from grid_paths      // Quillo 0.6: only these

pathfinding = "4"

// A warehouse robot's way from the dock to a shelf, around the racks, and how far it can get// on what is left of its battery; the floor plan is text.////   quillo run grid_paths.qwe      then open http://localhost:8080/routeuse "grid_paths.qwer"let FLOOR = [    "S.........",    ".####.###.",    ".#.......3",    ".#.####.#.",    "...#..#.#.",    "####..#..G",]route GET /route ? { diagonal: bool = false } {    let start = grid_find(FLOOR, "S")?[0]    let goal = grid_find(FLOOR, "G")?[0]    let p = grid_path(FLOOR, start, goal, diagonal)?    if p == null { reply 404 { error: "the shelf cannot be reached" } }    { steps: p.steps, cost: p.cost, drawn: grid_draw(FLOOR, p.path, "*")? }}route GET /battery ? { left: float = 4.0 } = { cells: len(grid_reachable(FLOOR, [0, 0], left, false)?) }route GET /blocked = { path: grid_path(["S#.", "##.", "..G"], [0, 0], [2, 2], true)? }

//! Paths on a grid with walls, by A*: for games, warehouse robots, floor plans and tile maps. The grid is text rows (`#` a wall, `.` open, digits 1-9 slower ground); paths, movement ranges and drawings of them.//! version: 1.0.0//!//! [dependencies]//! pathfinding = "4"use serde_json::{json, Value};const MAX_CELLS: usize = 4_000_000;struct Grid {    cells: Vec<Vec<char>>,    w: usize,    h: usize,}/// The cost of stepping onto a cell, in tenths, or None for a wall (`#`) or outside the grid.fn cost(g: &Grid, x: i64, y: i64) -> Option<u32> {    if x < 0 || y < 0 || x as usize >= g.w || y as usize >= g.h {        return None;    }    let row = &g.cells[y as usize];    let c = *row.get(x as usize).unwrap_or(&'#');    match c {        '#' => None,        '1'..='9' => Some(c.to_digit(10).unwrap_or(1)),        _ => Some(1),    }}fn grid(rows: &[String]) -> Result<Grid, String> {    let h = rows.len();    let w = rows.iter().map(|r| r.chars().count()).max().unwrap_or(0);    if h == 0 || w == 0 {        return Err("the grid is empty".into());    }    if w * h > MAX_CELLS {        return Err("a grid has at most 4 million cells".into());    }    Ok(Grid { cells: rows.iter().map(|r| r.chars().collect()).collect(), w, h })}fn xy(p: &[i64], what: &str) -> Result<(i64, i64), String> {    match p {        [x, y] => Ok((*x, *y)),        _ => Err(format!("{} is [x, y], from 0 at the top left", what)),    }}fn moves(g: &Grid, (x, y): (i64, i64), diagonal: bool) -> Vec<((i64, i64), u32)> {    let mut out = Vec::with_capacity(8);    for (dx, dy) in [(1, 0), (-1, 0), (0, 1), (0, -1)] {        if let Some(c) = cost(g, x + dx, y + dy) {            out.push(((x + dx, y + dy), c * 10));        }    }    if diagonal {        for (dx, dy) in [(1, 1), (1, -1), (-1, 1), (-1, -1)] {            // No cutting corners: both cells beside the diagonal must be open.            if cost(g, x + dx, y).is_some() && cost(g, x, y + dy).is_some() {                if let Some(c) = cost(g, x + dx, y + dy) {                    out.push(((x + dx, y + dy), c * 14));                }            }        }    }    out}/// The cheapest path from `from` to `to` (`[x, y]`, 0 at the top left): `{ path: [[x, y], ...], cost, steps }`, or null when walls cut them off./// Steps are up, down, left and right, and also diagonal when `diagonal` (costing 1.4, never across a wall's corner). Entering a digit cell costs that digit.pub fn grid_path(rows: Vec<String>, from: Vec<i64>, to: Vec<i64>, diagonal: bool) -> Result<Value, String> {    let g = grid(&rows)?;    let (s, t) = (xy(&from, "from")?, xy(&to, "to")?);    if cost(&g, s.0, s.1).is_none() || cost(&g, t.0, t.1).is_none() {        return Err("from and to must be open cells inside the grid".into());    }    let h = |p: &(i64, i64)| -> u32 {        let (dx, dy) = ((p.0 - t.0).unsigned_abs() as u32, (p.1 - t.1).unsigned_abs() as u32);        if diagonal { 10 * dx.max(dy) + 4 * dx.min(dy) } else { 10 * (dx + dy) }    };    Ok(match pathfinding::prelude::astar(&s, |p| moves(&g, *p, diagonal), h, |p| *p == t) {        Some((path, c)) => json!({ "path": path.iter().map(|p| vec![p.0, p.1]).collect::<Vec<_>>(), "cost": c as f64 / 10.0, "steps": path.len() - 1 }),        None => Value::Null,    })}/// Every cell reachable from `from` for at most `max_cost` (a unit's move range, a robot's battery): `[[x, y, cost], ...]`, cheapest first, `from` included at 0.pub fn grid_reachable(rows: Vec<String>, from: Vec<i64>, max_cost: f64, diagonal: bool) -> Result<Vec<Vec<Value>>, String> {    let g = grid(&rows)?;    let s = xy(&from, "from")?;    if cost(&g, s.0, s.1).is_none() {        return Err("from must be an open cell inside the grid".into());    }    let limit = (max_cost.max(0.0) * 10.0).round() as u32;    let all = pathfinding::prelude::dijkstra_all(&s, |p| moves(&g, *p, diagonal).into_iter().collect::<Vec<_>>());    let mut out: Vec<((i64, i64), u32)> = all.into_iter().map(|(p, (_, c))| (p, c)).filter(|(_, c)| *c <= limit).collect();    out.sort_by_key(|(p, c)| (*c, p.1, p.0));    let mut res = vec![vec![json!(s.0), json!(s.1), json!(0.0)]];    res.extend(out.into_iter().filter(|(p, _)| *p != s).map(|(p, c)| vec![json!(p.0), json!(p.1), json!(c as f64 / 10.0)]));    Ok(res)}/// The positions `[[x, y], ...]` of a character in the grid, row by row: where the `S`tart, the `G`oal or the coins are.pub fn grid_find(rows: Vec<String>, ch: &str) -> Result<Vec<Vec<i64>>, String> {    let c = ch.chars().next().ok_or("give one character")?;    Ok(rows.iter().enumerate().flat_map(|(y, r)| r.chars().enumerate().filter(move |(_, x)| *x == c).map(move |(x, _)| vec![x as i64, y as i64])).collect())}/// The grid with a path drawn on it in `mark` (one character, such as "*"), the start and end cells left as they were: to show or log a route.pub fn grid_draw(rows: Vec<String>, path: Vec<Vec<i64>>, mark: &str) -> Result<Vec<String>, String> {    let m = mark.chars().next().unwrap_or('*');    let mut cells: Vec<Vec<char>> = rows.iter().map(|r| r.chars().collect()).collect();    let n = path.len();    for (i, p) in path.iter().enumerate() {        if i == 0 || i + 1 == n {            continue;        }        if let [x, y] = p.as_slice() {            if let Some(c) = cells.get_mut(*y as usize).and_then(|r| r.get_mut(*x as usize)) {                *c = m;            }        }    }    Ok(cells.into_iter().map(|r| r.into_iter().collect()).collect())}