astar-mumu 0.2.0-rc.4

// FILE: astar/src/maze.rs
//
// Provides two bridging functions for the Lava runtime
//     * astar:maze      – return a keyed‑array description of a maze
//     * astar:maze_png  – same, plus a PNG file saved to disk
//
// Arguments (positional, optional after the seed)
//
//   (seed,
//    width    = 21,
//    height   = 21,
//    startX   = 0,
//    startY   = 0,
//    endX     = width ‑ 1,
//    endY     = height ‑ 1,
//    [filename])          ← only for *_png variant
//
// **Important restriction:** `width` **and** `height` must be **odd**
// (the classic perfect‑maze requirement).  Even sizes are rejected.
//

use mumu::parser::interpreter::Interpreter;
use mumu::parser::types::Value;
use indexmap::IndexMap;
use fastrand;
use image::{ImageBuffer, Rgba};
use std::env;

// ───────────────────────────────────────────────────────────────────────────
//  Exported bridge functions
// ───────────────────────────────────────────────────────────────────────────

/// astar:maze
pub fn astar_maze_bridge(
    _interp: &mut Interpreter,
    args: Vec<Value>,
) -> Result<Value, String> {
    let debug_verbose = _interp.is_verbose() || env::var("MAZE_DEBUG").is_ok();
    let (seed, width, height, sx, sy, ex, ey) = parse_maze_args(&args, false)?;

    let (cells, tries, path_len, open_count) =
        generate_solvable_maze(seed, width, height, sx, sy, ex, ey, debug_verbose)?;

    if debug_verbose {
        eprintln!(
            "[maze] Success after {} attempt(s); open cells: {}, path_len: {}",
            tries, open_count, path_len
        );
    }

    let obstacles = cells_to_obstacles(&cells, width, height);

    let mut out = IndexMap::new();
    out.insert("dimension".into(), Value::IntArray(vec![width, height]));
    out.insert("start".into(),     Value::IntArray(vec![sx, sy]));
    out.insert("end".into(),       Value::IntArray(vec![ex, ey]));
    out.insert("obj".into(),       Value::Int2DArray(obstacles));

    Ok(Value::KeyedArray(out))
}

/// astar:maze_png
pub fn astar_maze_png_bridge(
    _interp: &mut Interpreter,
    args: Vec<Value>,
) -> Result<Value, String> {
    let debug_verbose = _interp.is_verbose() || env::var("MAZE_DEBUG").is_ok();
    if args.len() < 2 {
        return Err("astar:maze_png ⇒ needs at least a seed and filename".into());
    }
    let (seed, width, height, sx, sy, ex, ey) = parse_maze_args(&args[..args.len() - 1], true)?;
    let filename = parse_filename_arg(&args[args.len() - 1])?;

    let (cells, tries, path_len, open_count) =
        generate_solvable_maze(seed, width, height, sx, sy, ex, ey, debug_verbose)?;

    if debug_verbose {
        eprintln!(
            "[maze_png] Success after {} attempt(s); open cells: {}, path_len: {}",
            tries, open_count, path_len
        );
    }

    let obstacles = cells_to_obstacles(&cells, width, height);

    // ── write PNG ───────────────────────────────────────────────────────
    let mut img = ImageBuffer::<Rgba<u8>, Vec<u8>>::new(width as u32, height as u32);
    for y in 0..height {
        for x in 0..width {
            let idx   = (y * width + x) as usize;
            let pixel = if cells[idx] { Rgba([255, 255, 255, 255]) }
                        else          { Rgba([0,   0,   0,   255]) };
            img.put_pixel(x as u32, y as u32, pixel);
        }
    }
    img.save(&filename)
        .map_err(|e| format!("astar:maze_png ⇒ cannot write '{}': {}", filename, e))?;

    // ── return keyed array ──────────────────────────────────────────────
    let mut out = IndexMap::new();
    out.insert("dimension".into(), Value::IntArray(vec![width, height]));
    out.insert("start".into(),     Value::IntArray(vec![sx, sy]));
    out.insert("end".into(),       Value::IntArray(vec![ex, ey]));
    out.insert("obj".into(),       Value::Int2DArray(obstacles));

    Ok(Value::KeyedArray(out))
}

// ───────────────────────────────────────────────────────────────────────────
//  Core generation logic
// ───────────────────────────────────────────────────────────────────────────

/// Generate a maze guaranteed to be solvable.  Tries up to 1 000 seeds.
/// Now deterministic: the *user-supplied seed* and (sx,sy) select the maze.
fn generate_solvable_maze(
    user_seed: u64,
    width:  i32,
    height: i32,
    sx: i32,
    sy: i32,
    ex: i32,
    ey: i32,
    debug_verbose: bool,
) -> Result<(Vec<bool>, i32, usize, usize), String> {

    let max_tries = 1_000;

    // --- Deterministic base seed:
    let base_seed = user_seed
        .wrapping_add(((sx as u64) << 32) | ((sy as u64) << 16));

    for tries in 1..=max_tries {
        let maze_seed = base_seed.wrapping_add(tries as u64);

        // Set the global RNG seed for each attempt
        fastrand::seed(maze_seed);

        let mut cells = vec![false; (width * height) as usize];
        carve_passages_dfs(sx, sy, width, height, &mut cells);

        // ensure start / end are open
        let sidx = (sy * width + sx) as usize;
        let eidx = (ey * width + ex) as usize;
        cells[sidx] = true;
        cells[eidx] = true;

        let open_count = cells.iter().filter(|b| **b).count();

        let (solved, path_len) = match find_path(&cells, width, height, sx, sy, ex, ey) {
            Some(path) => (true, path.len()),
            None       => (false, 0),
        };

        if debug_verbose {
            eprintln!(
                "[maze attempt {}/{}] seed={} open={}/{} {} path={} ({:.1} %)",
                tries,
                max_tries,
                maze_seed,
                open_count,
                width * height,
                if solved { "✓" } else { "✗" },
                if solved { path_len.to_string() } else { "-".into() },
                open_count as f64 * 100.0 / (width * height) as f64
            );
        }

        if solved {
            return Ok((cells, tries, path_len, open_count));
        }
    }

    Err(format!(
        "astar:maze ⇒ could not generate a solvable maze in {} attempts",
        max_tries
    ))
}

// ───────────────────────────────────────────────────────────────────────────
//  Maze carving & helpers
// ───────────────────────────────────────────────────────────────────────────

fn carve_passages_dfs(x: i32, y: i32, w: i32, h: i32, cells: &mut [bool]) {
    let idx = (y * w + x) as usize;
    cells[idx] = true;

    let mut dirs = vec![(1, 0), (-1, 0), (0, 1), (0, -1)];
    fastrand::shuffle(&mut dirs);

    for &(dx, dy) in &dirs {
        let nx = x + dx * 2;
        let ny = y + dy * 2;
        if nx >= 0 && nx < w && ny >= 0 && ny < h {
            let nidx = (ny * w + nx) as usize;
            if !cells[nidx] {
                // knock the wall between (x,y) and (nx,ny)
                let mx   = x + dx;
                let my   = y + dy;
                let midx = (my * w + mx) as usize;
                cells[midx] = true;
                carve_passages_dfs(nx, ny, w, h, cells);
            }
        }
    }
}

/// Simple BFS path‑finder (orthogonal moves, unit cost)
fn find_path(
    cells: &[bool],
    w: i32,
    h: i32,
    sx: i32,
    sy: i32,
    ex: i32,
    ey: i32,
) -> Option<Vec<(i32, i32)>> {
    use std::collections::VecDeque;

    let mut visited = vec![false; (w * h) as usize];
    let mut prev    = vec![None;  (w * h) as usize];

    let start_idx = (sy * w + sx) as usize;
    let end_idx   = (ey * w + ex) as usize;

    let mut q = VecDeque::new();
    q.push_back(start_idx);
    visited[start_idx] = true;

    while let Some(idx) = q.pop_front() {
        if idx == end_idx { break; }

        let x = (idx as i32) % w;
        let y = (idx as i32) / w;

        for &(dx, dy) in &[(1,0), (-1,0), (0,1), (0,-1)] {
            let nx = x + dx;
            let ny = y + dy;
            if nx < 0 || nx >= w || ny < 0 || ny >= h { continue; }
            let nidx = (ny * w + nx) as usize;
            if cells[nidx] && !visited[nidx] {
                visited[nidx] = true;
                prev[nidx]    = Some(idx);
                q.push_back(nidx);
            }
        }
    }

    if !visited[end_idx] { return None; }

    // back‑track
    let mut path = Vec::<(i32, i32)>::new();
    let mut cur  = end_idx;
    loop {
        let x = (cur as i32) % w;
        let y = (cur as i32) / w;
        path.push((x, y));
        if cur == start_idx { break; }
        cur = prev[cur]?;          // safe: path exists
    }
    path.reverse();
    Some(path)
}

/// Convert the boolean cell grid into a list of obstacle coordinates
fn cells_to_obstacles(cells: &[bool], w: i32, h: i32) -> Vec<Vec<i32>> {
    let mut out = Vec::new();
    for y in 0..h {
        for x in 0..w {
            let idx = (y * w + x) as usize;
            if !cells[idx] {
                out.push(vec![x, y]);
            }
        }
    }
    out
}

// ───────────────────────────────────────────────────────────────────────────
//  Argument parsing utilities
// ───────────────────────────────────────────────────────────────────────────

fn parse_maze_args(
    args: &[Value],
    is_png: bool,
) -> Result<(u64, i32, i32, i32, i32, i32, i32), String> {
    if args.is_empty() {
        return Err("astar:maze ⇒ must pass at least a seed".into());
    }

    let max_n = if is_png { 7 } else { 7 };
    let n     = args.len().min(max_n);

    let seed = match &args[0] {
        Value::Int(i)  => *i as u64,
        Value::Long(l) => *l as u64,
        other          => return Err(format!("maze ⇒ seed must be int/long, got {:?}", other)),
    };

    let mut width  = 21;
    let mut height = 21;
    let mut sx     = 0;
    let mut sy     = 0;
    let mut ex     = -1;
    let mut ey     = -1;

    if n >= 2 { width  = parse_int_arg(&args[1], "width")?;  }
    if n >= 3 { height = parse_int_arg(&args[2], "height")?; }
    if n >= 4 { sx     = parse_int_arg(&args[3], "startX")?; }
    if n >= 5 { sy     = parse_int_arg(&args[4], "startY")?; }
    if n >= 6 { ex     = parse_int_arg(&args[5], "endX")?;   }
    if n >= 7 { ey     = parse_int_arg(&args[6], "endY")?;   }

    if ex < 0 { ex = width  - 1; }
    if ey < 0 { ey = height - 1; }

    if width < 3 || height < 3 || width % 2 == 0 || height % 2 == 0 {
        return Err("maze ⇒ width and height must be odd numbers ≥ 3".into());
    }
    if sx < 0 || sx >= width || sy < 0 || sy >= height {
        return Err("maze ⇒ (sx,sy) must be within the grid".into());
    }
    if ex < 0 || ex >= width || ey < 0 || ey >= height {
        return Err("maze ⇒ (ex,ey) must be within the grid".into());
    }

    Ok((seed, width, height, sx, sy, ex, ey))
}

fn parse_int_arg(v: &Value, name: &str) -> Result<i32, String> {
    match v {
        Value::Int(i)  => Ok(*i),
        Value::Long(l) => Ok(*l as i32),
        other          => Err(format!("maze ⇒ {} must be int/long, got {:?}", name, other)),
    }
}

fn parse_filename_arg(v: &Value) -> Result<String, String> {
    match v {
        Value::SingleString(s)          => Ok(s.clone()),
        Value::StrArray(a) if a.len() == 1 => Ok(a[0].clone()),
        o => Err(format!("maze_png ⇒ filename must be a single string, got {:?}", o)),
    }
}