use mumu::parser::interpreter::Interpreter;
use mumu::parser::types::Value;
use indexmap::IndexMap;
use std::collections::{VecDeque, HashSet};
pub fn astar_path_bridge(_interp: &mut Interpreter, args: Vec<Value>) -> Result<Value, String> {
if args.len() != 3 {
return Err("astar:path ⇒ expected exactly (descriptor, [sx,sy], [ex,ey])".into());
}
let desc = match &args[0] {
Value::KeyedArray(m) => m.clone(),
_ => return Err("astar:path ⇒ first argument must be keyed array".into()),
};
let (w, h) = match desc.get("dimension") {
Some(Value::IntArray(xs)) if xs.len() == 2 => (xs[0], xs[1]),
_ => return Err("astar:path ⇒ 'dimension' must be [w,h]".into()),
};
let obstacle_list = match desc.get("obj") {
Some(Value::Int2DArray(rows)) => rows.clone(),
_ => Vec::new(),
};
let mut obstacles = HashSet::new();
for pair in obstacle_list {
if pair.len() == 2 {
obstacles.insert((pair[0], pair[1]));
}
}
let (requested_sx, requested_sy) = match &args[1] {
Value::IntArray(xs) if xs.len() == 2 => (xs[0], xs[1]),
_ => return Err("astar:path ⇒ start must be [x,y]".into()),
};
let (requested_ex, requested_ey) = match &args[2] {
Value::IntArray(xs) if xs.len() == 2 => (xs[0], xs[1]),
_ => return Err("astar:path ⇒ end must be [x,y]".into()),
};
let mut cells = vec![true; (w*h) as usize];
for &(ox, oy) in &obstacles {
let idx = (oy*w + ox) as usize;
cells[idx] = false;
}
let is_passable = |x: i32, y: i32| x >= 0 && x < w && y >= 0 && y < h && cells[(y*w + x) as usize];
let (sx, sy, snapped_start) = if is_passable(requested_sx, requested_sy) {
(requested_sx, requested_sy, false)
} else {
match nearest_passable(w, h, &cells, requested_sx, requested_sy, 10) {
Some((x, y)) => (x, y, true),
None => return empty_output(&desc, requested_sx, requested_sy, requested_ex, requested_ey, Vec::new()),
}
};
let (ex, ey, snapped_end) = if is_passable(requested_ex, requested_ey) {
(requested_ex, requested_ey, false)
} else {
match nearest_passable(w, h, &cells, requested_ex, requested_ey, 10) {
Some((x, y)) => (x, y, true),
None => return empty_output(&desc, requested_sx, requested_sy, requested_ex, requested_ey, Vec::new()),
}
};
let path = find_path_bfs(&cells, w, h, sx, sy, ex, ey, 300_000);
let found = !path.is_empty() && path.last() == Some(&(ex, ey));
if found {
return Ok(assemble_output(&desc, requested_sx, requested_sy, requested_ex, requested_ey, sx, sy, ex, ey, snapped_start, snapped_end, path, true));
} else {
return empty_output(&desc, requested_sx, requested_sy, requested_ex, requested_ey, Vec::new());
}
}
fn assemble_output(
desc: &IndexMap<String, Value>,
requested_sx: i32, requested_sy: i32,
requested_ex: i32, requested_ey: i32,
sx: i32, sy: i32, ex: i32, ey: i32,
snapped_start: bool, snapped_end: bool,
path: Vec<(i32, i32)>, found: bool,
) -> Value {
let mut out = desc.clone();
out.insert("requested_start".into(), Value::IntArray(vec![requested_sx, requested_sy]));
out.insert("requested_end".into(), Value::IntArray(vec![requested_ex, requested_ey]));
out.insert("start".into(), Value::IntArray(vec![sx, sy]));
out.insert("end".into(), Value::IntArray(vec![ex, ey]));
if snapped_start { out.insert("snapped_start".into(), Value::Bool(true)); }
if snapped_end { out.insert("snapped_end".into(), Value::Bool(true)); }
let mut path2d = Vec::new();
for &(px, py) in &path { path2d.push(vec![px, py]); }
out.insert("path".into(), Value::Int2DArray(path2d));
out.insert("success".into(), Value::Bool(found));
out.insert("cost".into(), Value::Float(path.len() as f64));
out.insert("pathLength".into(), Value::Int(path.len() as i32));
Value::KeyedArray(out)
}
fn empty_output(
desc: &IndexMap<String, Value>,
requested_sx: i32, requested_sy: i32,
requested_ex: i32, requested_ey: i32,
path: Vec<(i32, i32)>
) -> Result<Value, String> {
let mut out = desc.clone();
out.insert("requested_start".into(), Value::IntArray(vec![requested_sx, requested_sy]));
out.insert("requested_end".into(), Value::IntArray(vec![requested_ex, requested_ey]));
out.insert("start".into(), Value::IntArray(vec![]));
out.insert("end".into(), Value::IntArray(vec![]));
let mut path2d = Vec::new();
for &(px, py) in &path { path2d.push(vec![px, py]); }
out.insert("path".into(), Value::Int2DArray(path2d));
out.insert("success".into(), Value::Bool(false));
out.insert("cost".into(), Value::Float(0.0));
out.insert("pathLength".into(), Value::Int(0));
Ok(Value::KeyedArray(out))
}
fn find_path_bfs(cells: &[bool], w: i32, h: i32, sx: i32, sy: i32, ex: i32, ey: i32, step_limit: usize) -> Vec<(i32,i32)> {
let start_idx = (sy*w + sx) as usize;
let end_idx = (ey*w + ex) as usize;
let mut visited = vec![false; cells.len()];
let mut from = vec![None; cells.len()];
let mut queue = VecDeque::new();
visited[start_idx] = true;
queue.push_back(start_idx);
let mut steps = 0;
while let Some(idx) = queue.pop_front() {
if steps > step_limit { break; }
steps += 1;
if idx == end_idx {
let mut path = Vec::new();
let mut cur = idx;
while let Some(prev) = from[cur] {
path.push(idx_to_xy(cur, w));
cur = prev;
}
path.push(idx_to_xy(cur, w));
path.reverse();
return path;
}
let (x,y) = idx_to_xy(idx, 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 {
let nidx = (ny*w + nx) as usize;
if cells[nidx] && !visited[nidx] {
visited[nidx] = true;
from[nidx] = Some(idx);
queue.push_back(nidx);
}
}
}
}
Vec::new()
}
fn nearest_passable(w: i32, h: i32, cells: &[bool], x: i32, y: i32, max_r: i32) -> Option<(i32, i32)> {
for r in 0..=max_r {
for dx in -r..=r {
let dy1 = r - dx.abs();
for &dy in &[-dy1, dy1] {
let xx = x + dx;
let yy = y + dy;
if xx >= 0 && xx < w && yy >= 0 && yy < h && cells[(yy*w + xx) as usize] {
return Some((xx, yy));
}
}
}
}
None
}
fn idx_to_xy(idx: usize, w: i32) -> (i32,i32) {
let x = (idx as i32)%w;
let y = (idx as i32)/w;
(x,y)
}