pathfinding/astar/

astar.rs

use crate::errors::my_errors::RetResult;
use crate::map::{CloseList, IndexType, Map, MapType, Point};
use async_trait::async_trait;
use std::collections::BinaryHeap;
use std::sync::{Arc};
use tokio::fs::File;
use tokio::io::AsyncReadExt;
use serde::{Deserialize, Serialize};

pub struct AStar {
    pub col: usize,
    pub row: usize,
    pub map: Box<Vec<Vec<i32>>>,
}

#[derive(Serialize, Deserialize, Debug)]
struct AstarMapFile {
    #[serde(rename = "columnCount")]
    pub column_count: usize,
    #[serde(rename = "rowCount")]
    pub row_count: usize,
    #[serde(rename = "unWalkCells")]
    pub un_walk_cells: Vec<usize>
}

#[async_trait]
impl Map for AStar {
    fn new() -> MapType {
        Arc::new(tokio::sync::RwLock::new(AStar {
            col: 0,
            row: 0,
            map: Box::<Vec<Vec<i32>>>::default(),
        }))
    }

    fn load(&mut self, points: Vec<Vec<i32>>) -> RetResult<()> {
        self.col = points[0].len();
        self.row = points.len();
        self.map = Box::new(points);
        Ok(())
    }

    async fn load_from_file(&mut self, file_name: String) -> RetResult<()> {
        // 打开文件
        let mut file = File::open(file_name).await?;

        // 创建一个缓冲区来存储文件内容
        let mut buffer = Vec::new();

        // 通过异步读取文件内容到缓冲区
        file.read_to_end(&mut buffer).await?;

        let mut x = Vec::new();
        for i in buffer {
            x.push(i as i32);
            if x.len() == 16 {
                self.map.push(x.clone());
                x.clear();
            }
        }

        self.col = self.map[0].len();
        self.row = self.map.len();

        Ok(())
    }

    async fn load_from_string(&mut self, file_contend: String) -> RetResult<()> {

        // 打开文件
        let deser: AstarMapFile = serde_json::from_str(&file_contend)?;

        self.map = Box::new(vec![vec![0; deser.column_count]; deser.row_count]);

        self.col = deser.column_count;
        self.row = deser.row_count;

        for i in 0..deser.un_walk_cells.len() {
            self.map[deser.un_walk_cells[i] / self.col][deser.un_walk_cells[i] % self.col] = 1;
        }

        Ok(())
    }

    fn find_path(
        &self,
        start: (IndexType, IndexType),
        end: (IndexType, IndexType),
    ) -> Vec<(IndexType, IndexType)> {
        let (start_x, start_y) = start;
        let (end_x, end_y) = end;

        let mut open_list = BinaryHeap::with_capacity(self.col + self.row);
        let mut close_list = CloseList::new(self.col, self.row);
        let mut parent = vec![vec![(0, 0); self.col]; self.row];
        let mut g_score = vec![vec![i32::MAX; self.col]; self.row];
        let mut f_score = vec![vec![i32::MAX; self.col]; self.row];

        g_score[start_y as usize][start_x as usize] = 0;
        f_score[start_y as usize][start_x as usize] = dis(start_x, start_y, end_x, end_y);

        open_list.push(Point::new_other(
            start_x,
            start_y,
            f_score[start_y as usize][start_x as usize],
            0,
            f_score[start_y as usize][start_x as usize],
        ));

        while let Some(current) = open_list.pop() {
            if current.x == end_x && current.y == end_y {
                let mut path = Vec::with_capacity(128);
                let mut current = (end_x, end_y);
                while current != (start_x, start_y) {
                    path.insert(0,(current.0, current.1));
                    current = parent[current.1 as usize][current.0 as usize];
                }
                path.insert(0,(start_x, start_y));
                return path;
            }

            close_list.insert(&current);

            for neighbor in current.neighbors() {
                let ix = current.x + neighbor.0;
                let iy = current.y + neighbor.1;
                let x = ix as usize;
                let y = iy as usize;

                if !self.in_map(ix, iy) {
                    continue;
                }

                let tentative_g_score = g_score[current.y as usize][current.x as usize] + 1;
                if tentative_g_score <= g_score[y][x] {
                    parent[y][x] = (current.x, current.y);
                    g_score[y][x] = tentative_g_score;
                    f_score[y][x] = tentative_g_score + dis(ix, iy, end_x, end_y);
                    if !open_list.iter().any(|node| node.x == ix && node.y == iy) {
                        open_list.push(Point::new_other(
                            ix,
                            iy,
                            f_score[y][x],
                            g_score[y][x],
                            dis(ix, iy, end_x, end_y),
                        ));
                    }
                }
            }
        }

        vec![]
    }

    fn set_walkable(&mut self, point: (IndexType, IndexType), walkable: i32) {
        self.map[point.1 as usize][point.0 as usize] = walkable;
    }

    #[inline]
    fn in_map(&self, x: i32, y: i32) -> bool {
        let x_usize = x as usize;
        let y_usize = y as usize;

        match (x, y) {
            (x, y) if y < 0 || x < 0 => false,
            (_x, _y) if y_usize >= self.row || x_usize >= self.col => false,
            _ => self.map[y_usize][x_usize] == 0,
        }
    }
}

#[inline]
pub fn dis(x: IndexType, y: IndexType, x1: IndexType, y1: IndexType) -> IndexType {
    let xx = (x1 - x).abs();
    let xy = (y1 - y).abs();

    //第一种：用min来获取xx与xy较小的那一个，内部隐含match操作
    //(xx, xy) * 14 +  (xx + xy) * 10

    //第二种，不用if或者min函数，会非常快
    let sum = (xx + xy) * 10;
    let condition = (xx > xy) as i32; // 1 if xx > xy, 0 otherwise
    (xy * 14 + sum) * (1 - condition) + (xx * 14 + sum) * condition
}

impl Drop for AStar {
    fn drop(&mut self) {
        self.map.clear()
    }
}