前提摘要

---

小王同学写了个寻路算法，发现rust版本的wasm反而比原生js还慢，于是我丢给AI帮他排查了一下

AI分析结果

没有使用优先队列（Min-Heap）

# A* 使用 优先队列（heap） 管理 open list 才能保证高效搜索。否则时间复杂度变成接近 O(n^2)，即使 WASM 速度快，也会被这种结构抵消掉。
use std::collections::BinaryHeap;
// AStarNode 需要实现 Ord
impl Ord for AStarNode {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        other.f.partial_cmp(&self.f).unwrap() // 注意：f 是浮点数，可能出错
    }
}
impl PartialOrd for AStarNode {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        other.f.partial_cmp(&self.f)
    }
}
impl PartialEq for AStarNode {
    fn eq(&self, other: &Self) -> bool {
        self.f == other.f
    }
}
impl Eq for AStarNode {}
let mut openList = BinaryHeap::new();

大量 clone 操作

• 每次设置父节点时都需要 clone() 整个结构体
• 在 WASM 环境下频繁 clone 昂贵的对象时，反而可能 不如 JS 快度。

不合理的数据结构与序列化成本

• JS 版本虽然没用堆结构优化，但语言层面对数组操作做了很多 JIT 编译优化，在小规模地图中反而跑得更快。

优化后的代码

use std::collections::{BinaryHeap, HashMap, HashSet};
use wasm_bindgen::prelude::*;
use serde::{Deserialize, Serialize};
#[derive(Debug, Clone, PartialEq, Eq)]
struct AStarNode {
    x: i32,
    y: i32,
    g: f64,
    h: f64,
    f: f64,
    parent: Option<(i32, i32)>,
}
impl Ord for AStarNode {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        other.f.partial_cmp(&self.f).unwrap_or(std::cmp::Ordering::Equal)
    }
}
impl PartialOrd for AStarNode {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}
impl AStarNode {
    pub fn new(x: i32, y: i32) -> Self {
        AStarNode {
            x,
            y,
            g: 0.0,
            h: 0.0,
            f: f64::MAX,
            parent: None,
        }
    }
    pub fn calculate_h(&mut self, end_x: i32, end_y: i32) {
        self.h = calculate_heuristic(self.x, self.y, end_x, end_y);
    }
    pub fn update_f(&mut self) {
        self.f = self.g + self.h;
    }
    pub fn is_goal(&self, end_x: i32, end_y: i32) -> bool {
        self.x == end_x && self.y == end_y
    }
}
#[derive(Serialize, Deserialize)]
pub struct PathPoint {
    pub x: i32,
    pub y: i32,
}
#[derive(Serialize, Deserialize)]
pub struct AStarResult {
    pub path: Vec<PathPoint>,
    pub found: bool,
    pub executionTime: f64,
}
fn calculate_heuristic(x: i32, y: i32, end_x: i32, end_y: i32) -> f64 {
    let dx = (x - end_x).abs() as f64;
    let dy = (y - end_y).abs() as f64;
    dx.max(dy)
}
fn get_directions() -> Vec<(i32, i32, f64)> {
    vec![
        (0, 1, 1.0),
        (1, 0, 1.0),
        (0, -1, 1.0),
        (-1, 0, 1.0),
        (1, 1, 2.0_f64.sqrt()),
        (1, -1, 2.0_f64.sqrt()),
        (-1, 1, 2.0_f64.sqrt()),
        (-1, -1, 2.0_f64.sqrt()),
    ]
}
fn is_diagonal_blocked(grid: &Vec<Vec<bool>>, x: i32, y: i32, dx: i32, dy: i32) -> bool {
    if dx != 0 && dy != 0 {
        if grid[(y + dy) as usize][x as usize] || grid[y as usize][(x + dx) as usize] {
            return true;
        }
    }
    false
}
fn reconstruct_path(mut node_map: HashMap<(i32, i32), AStarNode>, goal: (i32, i32)) -> Vec<PathPoint> {
    let mut path = vec![];
    let mut current = goal;
    while let Some(node) = node_map.get(&current) {
        path.push(PathPoint { x: node.x, y: node.y });
        if let Some(parent) = node.parent {
            current = parent;
        } else {
            break;
        }
    }
    path.reverse();
    path
}
#[wasm_bindgen]
pub fn find_path_astar(
    grid: &JsValue,
    start_x: i32,
    start_y: i32,
    end_x: i32,
    end_y: i32,
) -> JsValue {
    let start_time = js_sys::Date::now();
    let grid: Vec<Vec<bool>> = serde_wasm_bindgen::from_value(grid.clone()).unwrap();
    let height = grid.len() as i32;
    let width = grid[0].len() as i32;
    let start = (start_x, start_y);
    let goal = (end_x, end_y);
    if start.0 < 0 || start.0 >= width || start.1 < 0 || start.1 >= height ||
       goal.0 < 0 || goal.0 >= width || goal.1 < 0 || goal.1 >= height ||
       grid[start.1 as usize][start.0 as usize] || grid[goal.1 as usize][goal.0 as usize] {
        let result = AStarResult {
            path: vec![],
            found: false,
            executionTime: js_sys::Date::now() - start_time,
        };
        return serde_wasm_bindgen::to_value(&result).unwrap();
    }
    let mut open_list = BinaryHeap::new();
    let mut closed_set = HashSet::new();
    let mut node_map: HashMap<(i32, i32), AStarNode> = HashMap::new();
    let mut start_node = AStarNode::new(start_x, start_y);
    start_node.calculate_h(end_x, end_y);
    start_node.update_f();
    node_map.insert(start, start_node.clone());
    open_list.push(start_node);
    let directions = get_directions();
    while let Some(current_node) = open_list.pop() {
        let current_pos = (current_node.x, current_node.y);
        if closed_set.contains(&current_pos) {
            continue;
        }
        closed_set.insert(current_pos);
        if current_node.is_goal(end_x, end_y) {
            let path = reconstruct_path(node_map, current_pos);
            let result = AStarResult {
                path,
                found: true,
                executionTime: js_sys::Date::now() - start_time,
            };
            return serde_wasm_bindgen::to_value(&result).unwrap();
        }
        for &(dx, dy, cost) in &directions {
            let new_x = current_node.x + dx;
            let new_y = current_node.y + dy;
            if new_x < 0 || new_x >= width || new_y < 0 || new_y >= height
                || grid[new_y as usize][new_x as usize]
                || is_diagonal_blocked(&grid, current_node.x, current_node.y, dx, dy) {
                continue;
            }
            let new_pos = (new_x, new_y);
            let tentative_g = current_node.g + cost;
            if closed_set.contains(&new_pos) {
                continue;
            }
            let need_update = if let Some(existing_node) = node_map.get(&new_pos) {
                tentative_g < existing_node.g
            } else {
                true
            };
            if need_update {
                let mut neighbor = AStarNode::new(new_x, new_y);
                neighbor.calculate_h(end_x, end_y);
                neighbor.g = tentative_g;
                neighbor.parent = Some(current_pos);
                neighbor.update_f();
                node_map.insert(new_pos, neighbor.clone());
                open_list.push(neighbor);
            }
        }
    }
    let result = AStarResult {
        path: vec![],
        found: false,
        executionTime: js_sys::Date::now() - start_time,
    };
    serde_wasm_bindgen::to_value(&result).unwrap()
}