type index = {
    x: number,
    y: number
}

/**
 * AStar类用于实现A*寻路算法。
 */
export class AStar {
    private map: any[][] = []; // 地图数组
    private weightMap: number[][] = null; // 权重地图数组
    private openlist: index[] = []; // 开放列表，存储待评估的节点
    private closelist: index[] = []; // 封闭列表，存储已评估的节点
    private parentMap: Map<index, index>; // 父节点映射，用于回溯路径
    private gcostMap: Map<index, number>; // g成本映射，记录从起点到当前节点的成本
    private hcostMap: Map<index, number>; // h成本映射，记录从当前节点到终点的估算成本
    private startValue: number = 0;
    private endValue: number = 0;
    private pathValue: number = 0;
    private isEightDirections: boolean = false;
    private neighborMap: Map<index, index[]>;

    constructor() {
        this.openlist = [];
        this.closelist = [];
        this.parentMap = new Map();
        this.gcostMap = new Map();
        this.hcostMap = new Map();
    }

    /**
     * 设置地图。
     * @param map 二维数组表示的地图
     */
    setMap(map: number[][]) {
        this.map = map;
    }

    /**
     * 设置权重地图。
     * @param weightMap 二维数组表示的权重地图
     */
    setWeightMap(weightMap: number[][]) {
        this.weightMap = weightMap;
    }

    setValue(startValue: number, endValue: number, pathValue: number) {
        this.startValue = startValue;
        this.endValue = endValue;
        this.pathValue = pathValue;
    }

    setEightDirections(isEightDirections: boolean) {
        this.isEightDirections = isEightDirections;
    }

    setNeighborMap(neighborMap: Map<index, index[]>) {
        this.neighborMap = neighborMap;
    }

    /**
     * 在给定范围内根据指定类型搜索从起点到终点的路径。
     * @param start 起点索引
     * @param end 终点索引
     * @param type 搜索类型（可能影响启发式函数的选择）
     * @returns 返回找到的路径数组，如果无路径则返回空数组
     */
    search(start: index, end: index, type: number) {
        this.init(); // 初始化搜索环境

        if (this.map[start.y][start.x] !== this.startValue ||
            this.map[end.y][end.x] !== this.endValue) {
            console.log("Invalid start or end point");
            return [];
        }

        // 初始化起点信息，并将其加入开放列表
        this.openlist.push(start);
        this.gcostMap.set(start, 0); // 起点到起点的距离为0
        this.hcostMap.set(start, this.getHeuristicCost(start, end, type)); // 起点到终点的启发式成本
        this.parentMap.set(start, null); // 起点的父节点设置为null

        // 循环直到开放列表为空，即所有可能的路径都被考虑
        while (this.openlist.length > 0) {
            const current = this.getMinCostNode(this.openlist); // 从开放列表中选择成本最小的节点

            if (!current) {
                this.openlist.splice(this.openlist.indexOf(current), 1);
                continue;
            }

            // 判断是否到达终点
            if (this.isArrived(current, end)) {
                return this.reconstructPath(end); // 如果到达终点，返回路径重构的结果
            } else {
                // 从开放列表移除当前节点，将其加入封闭列表
                this.openlist.splice(this.openlist.indexOf(current), 1);
                this.closelist.push(current);

                // 遍历当前节点的所有邻居节点
                const neighbors = this.getNeighbors(current);
                for (const neighbor of neighbors) {
                    const hCost = this.getHeuristicCost(neighbor, end, type); // 计算邻居节点到终点的启发式成本
                    const gCost = this.gcostMap.get(current) + this.getGCost(current, neighbor, type); // 计算当前节点到邻居节点的实际成本
                    const totalCost = gCost + hCost; // 计算总成本

                    // 根据邻居节点的状态进行处理
                    if (!this.isInClosedList(neighbor)) {
                        if (!this.isInOpenList(neighbor)) {
                            this.openlist.push(neighbor); // 如果邻居未在开放列表中，将其加入
                            this.updateCost(neighbor, gCost, hCost); // 更新邻居节点的成本信息
                            this.updateParent(neighbor, current); // 更新邻居节点的父节点信息
                        } else {
                            // 如果邻居已在开放列表中，但通过当前节点发现更优路径
                            if (totalCost < this.getCost(neighbor)) {
                                this.updateCost(neighbor, gCost, hCost); // 更新成本信息
                                this.updateParent(neighbor, current); // 更新父节点信息
                            }
                        }
                    }
                }
            }
        }

        console.log("No path found.");
        return []; // 如果无法找到路径，返回空数组
    }

    /**
     * 初始化算法状态。
     */
    private init() {
        // 重置所有列表和映射
        this.openlist = [];
        this.closelist = [];
        this.parentMap = new Map();
        this.gcostMap = new Map();
        this.hcostMap = new Map();
    }

    /**
     * 获取当前节点的邻居。
     * @param current 当前节点坐标
     * @returns 邻居节点数组
     */
    private getNeighbors(current: index) {
        if (this.neighborMap.size === 0) {
            const neighbors: index[] = [];

            // 尝试获取四个方向的邻居节点
            const upindex = { x: current.x, y: current.y + 1 };
            const downindex = { x: current.x, y: current.y - 1 };
            const leftindex = { x: current.x - 1, y: current.y };
            const rightindex = { x: current.x + 1, y: current.y };

            const upleftindex = { x: current.x - 1, y: current.y + 1 };
            const uprightindex = { x: current.x + 1, y: current.y + 1 };
            const downleftindex = { x: current.x - 1, y: current.y - 1 };
            const downrightindex = { x: current.x + 1, y: current.y - 1 };

            // 如果合法则加入邻居列表
            if (this.isValidIndex(upindex) && (this.map[upindex.y][upindex.x] == this.pathValue ||
                this.map[upindex.y][upindex.x] == this.endValue)) {
                neighbors.push(upindex);
            }
            if (this.isValidIndex(downindex) && (this.map[downindex.y][downindex.x] == this.pathValue ||
                this.map[downindex.y][downindex.x] == this.endValue)) {
                neighbors.push(downindex);
            }
            if (this.isValidIndex(leftindex) && (this.map[leftindex.y][leftindex.x] == this.pathValue ||
                this.map[leftindex.y][leftindex.x] == this.endValue)) {
                neighbors.push(leftindex);
            }
            if (this.isValidIndex(rightindex) && (this.map[rightindex.y][rightindex.x] == this.pathValue ||
                this.map[rightindex.y][rightindex.x] == this.endValue)) {
                neighbors.push(rightindex);
            }

            if (this.isEightDirections) {
                if (this.isValidIndex(upleftindex) && (this.map[upleftindex.y][upleftindex.x] == this.pathValue ||
                    this.map[upleftindex.y][upleftindex.x] == this.endValue)) {
                    neighbors.push(upleftindex);
                }
                if (this.isValidIndex(downleftindex) && (this.map[downleftindex.y][downleftindex.x] == this.pathValue ||
                    this.map[downleftindex.y][downleftindex.x] == this.endValue)) {
                    neighbors.push(downleftindex);
                }
                if (this.isValidIndex(downrightindex) && (this.map[downrightindex.y][downrightindex.x] == this.pathValue ||
                    this.map[downrightindex.y][downrightindex.x] == this.endValue)) {
                    neighbors.push(downrightindex);
                }
                if (this.isValidIndex(uprightindex) && (this.map[uprightindex.y][uprightindex.x] == this.pathValue ||
                    this.map[uprightindex.y][uprightindex.x] == this.endValue)) {
                    neighbors.push(uprightindex);
                }
            }

            return neighbors;
        } else {
            const _neighbors = this.neighborMap.get(current);
            const neighbors: index[] = [];
            for (const neighbor of _neighbors) {
                if (this.map[neighbor.y][neighbor.x] == this.pathValue ||
                    this.map[neighbor.y][neighbor.x] == this.endValue) {
                    neighbors.push(neighbor);
                }
            }
            return neighbors;
        }
    }

    /**
     * 计算从当前节点到邻居节点的实际成本
     * @param current 当前节点
     * @param neighbor 邻居节点
     * @param type 距离计算类型
     * @returns 返回从当前节点到邻居节点的成本
     */
    private getGCost(current: index, neighbor: index, type: number = 0) {
        let baseCost = 0;

        // 计算基础距离成本
        switch (type) {
            case 0: {
                // 计算曼哈顿距离
                baseCost = Math.abs(current.x - neighbor.x) + Math.abs(current.y - neighbor.y);
                break;
            }
            case 1: {
                // 计算欧几里得距离
                baseCost = Math.sqrt(Math.pow(current.x - neighbor.x, 2) + Math.pow(current.y - neighbor.y, 2));
                break;
            }
            case 2: {
                // 计算切比雪夫距离
                const x = Math.abs(current.x - neighbor.x);
                const y = Math.abs(current.y - neighbor.y);
                const minxy = Math.min(x, y);
                baseCost = x + y + (Math.sqrt(2) - 2) * minxy;
                break;
            }
        }

        // 如果存在权重地图，应用权重
        if (this.weightMap && this.isValidIndex(neighbor)) {
            const weight = this.weightMap[neighbor.y][neighbor.x];
            return baseCost * weight;
        }

        return baseCost;
    }

    /**
     * 根据给定的起始点和目标点，以及类型参数，计算启发式成本。
     * @param start 起始点的索引，包含 x 和 y 坐标。
     * @param end 目标点的索引，包含 x 和 y 坐标。
     * @param type 计算成本的类型，0 表示曼哈顿距离，1 表示欧几里得距离，2 表示切比雪夫距离，默认为 0。
     * @returns 返回根据指定类型计算出的启发式成本。
     */
    private getHeuristicCost(start: index, end: index, type: number = 0) {
        switch (type) {
            case 0: {
                // 计算曼哈顿距离
                return Math.abs(start.x - end.x) + Math.abs(start.y - end.y);
            }
            case 1: {
                // 计算欧几里得距离
                return Math.sqrt(Math.pow(start.x - end.x, 2) + Math.pow(start.y - end.y, 2));
            }
            case 2: {
                // 计算切比雪夫距离
                const x = Math.abs(start.x - end.x);
                const y = Math.abs(start.y - end.y);
                const minxy = Math.min(x, y);
                return x + y + (Math.sqrt(2) - 2) * minxy;
            }
        }
    }

    /**
     * 检查节点是否在封闭列表中。
     * @param node 节点坐标
     * @returns {boolean} 如果节点在封闭列表中返回true，否则返回false
     */
    private isInClosedList(node: index): boolean {
        // 遍历封闭列表查找节点
        let _index = -1;
        for (let i = 0; i < this.closelist.length; i++) {
            if (this.closelist[i].x == node.x && this.closelist[i].y == node.y) {
                _index = i;
                break;
            }
        }
        return _index != -1;
    }

    /**
     * 检查节点是否在开放列表中。
     * @param node 节点坐标
     * @returns {boolean} 如果节点在开放列表中返回true，否则返回false
     */
    private isInOpenList(node: index): boolean {
        // 遍历开放列表查找节点
        let _index = -1;
        for (let i = 0; i < this.openlist.length; i++) {
            if (this.openlist[i].x == node.x && this.openlist[i].y == node.y) {
                _index = i;
                break;
            }
        }
        return _index != -1;
    }

    /**
     * 获取节点的成本。
     * @param node 节点坐标
     * @returns 节点的总成本
     */
    private getCost(node: index): number {
        let gcost = 0;
        let hcost = 0;
        this.gcostMap.forEach((value, key) => {
            if (key.x == node.x && key.y == node.y) {
                gcost = value;
            }
        });
        this.hcostMap.forEach((value, key) => {
            if (key.x == node.x && key.y == node.y) {
                hcost = value;
            }
        });
        return gcost + hcost;
    }

    /**
     * 获取开放列表中成本最小的节点。
     * @param list 开放列表
     * @returns 成本最小的节点
     */
    private getMinCostNode(list: index[]): index {
        let _minindex = -1;
        let _mincost = Number.MAX_SAFE_INTEGER;
        // 寻找成本最小的节点
        for (let i = 0; i < list.length; i++) {
            const cost = this.getCost(list[i]);
            if (cost < _mincost) {
                _minindex = i;
                _mincost = cost;
            }
        }
        return list[_minindex];
    }

    /**
     * 更新节点的成本和父节点信息。
     * @param node 节点坐标
     * @param gcost 从起点到当前节点的实际成本
     * @param hcost 从当前节点到终点的估算成本
     */
    private updateCost(node: index, gcost: number, hcost: number) {
        this.gcostMap.set(node, gcost);
        this.hcostMap.set(node, hcost);
    }

    /**
     * 更新节点的父节点。
     * @param node 节点坐标
     * @param parent 父节点坐标
     */
    private updateParent(node: index, parent: index) {
        const existingparent = this.parentMap.get(node);
        // 仅当新的父节点成本更低时更新
        if (!existingparent || this.getCost(parent) < this.getCost(existingparent)) {
            this.parentMap.set(node, parent);
        }
    }

    /**
     * 根据父节点映射重构路径。
     * @param endPoint 终点坐标
     * @returns 从起点到终点的路径
     */
    private reconstructPath(endPoint: index) {
        const path = [endPoint];
        let currentnode = endPoint;

        // 逆向回溯路径
        while (currentnode) {
            let parent = null;
            this.parentMap.forEach((value, key) => {
                if (currentnode.x == key.x && currentnode.y == key.y) {
                    parent = value;
                }
            })
            if (parent) {
                path.unshift(parent);
                currentnode = parent;
            } else {
                currentnode = null;
            }
        }

        return path;
    }


    /**
     * 检查给定的索引是否为有效索引。
     * @param index 一个包含x和y属性的对象，代表要检查的索引位置。
     * @returns 返回一个布尔值，如果索引位置有效，则为true；否则为false。
     */
    private isValidIndex(index: index): boolean {
        return index.x >= 0 && index.x < this.map[0].length && index.y >= 0 && index.y < this.map.length;
    }

    /**
     * 判断当前节点是否到达了目标节点。
     * @param node 一个包含x和y属性的对象，代表当前节点的位置。
     * @param end 一个包含x和y属性的对象，代表目标节点的位置。
     * @returns 返回一个布尔值，如果当前节点已到达目标节点，则为true；否则为false。
     */
    private isArrived(node: index, end: index) {
        // 比较当前节点和目标节点的坐标，判断是否已经到达目标位置
        return node.x == end.x && node.y == end.y;
    }
}