【记录】使用 JavaScript（Typescript） 实现AStar 寻路算法

export type CompareFn<T> = (a: T, b: T) => number;

export function appendToOrderList<T>(orderList: T[], item: T, compare: CompareFn<T>) {
    if (orderList.length > 0) {
        if (compare(item, orderList[0]) <= 0) {
            orderList.splice(0, 0, item);
        } else {
            let index;
            for (index = 0; index < orderList.length - 1; index++) {
                let compareToPrev = compare(item, orderList[index]);
                let compareToNext = compare(item, orderList[index + 1]);
                if (compareToPrev >= 0 && compareToNext <= 0) {
                    break;
                }
            }
            orderList.splice(index + 1, 0, item);
        }
    } else {
        orderList[0] = item;
    }
}

export type AStarPos = {
    row: number;
    col: number;

    step: number;      // 0
    searched: boolean; // false
    opened: boolean;   // false
    closed: boolean;   // false

    weight?: number;
    prev?: AStarPos;
}

export type AStarMap = AStarPos[][];

export const AStarConfig = {
    toStartWeight: 1,
    toEndWeight: 1
}

export function findRoad(gameMap: boolean[][], startPos: [number, number], endPos: [number, number]) {
    // create astar map
    let aStarMap: AStarMap = [];
    gameMap.forEach((row, rowIndex) => {
        aStarMap[rowIndex] = [];
        row.forEach((col, colIndex) => {
            let aStarPos: AStarPos = {

                row: rowIndex,
                col: colIndex,
                step: 0,

                searched: false, // false
                opened: false,   // false
                closed: !col,    // false
            };

            aStarMap[rowIndex][colIndex] = aStarPos;
        });
    });

    let aStarRoad = aStarFindRoad(aStarMap, startPos, endPos);

    return aStarRoad.map(aStarpos => [aStarpos.row, aStarpos.col]);
}

export function aStarFindRoad(map: AStarMap, [startRow, startCol]: [number, number], [endRow, endCol]: [number, number]) {
    let road: AStarPos[] = [];
    let openList: AStarPos[] = [];
    let testList: AStarPos[] = [];

    let startPos = map[startRow][startCol];
    let endPos = map[endRow][endCol];

    startPos.searched = true;
    startPos.opened = true;

    startPos.weight = calWeight(0, calDistance(startPos, endPos));

    openList.push(startPos);

    let testPos = openList.shift();
    while (testPos) {
        testPos.opened = false;
        testList.push(testPos);

        if (equalsPos(testPos, endPos)) {
            let roadPos: AStarPos | undefined = endPos;
            while (roadPos) {
                road.push(roadPos);
                roadPos = roadPos.prev;
            }
            return road.reverse();
        }

        let notSearchedPosList = getNotSearchedPosList(map, testPos);
        if (notSearchedPosList.length > 0) {
            for (let index = 0; index < notSearchedPosList.length; index++) {
                let notSearchedPos = notSearchedPosList[index];
                notSearchedPos.step = testPos.step + 1;
                notSearchedPos.weight = calWeight(notSearchedPos.step, calDistance(notSearchedPos, endPos));
                notSearchedPos.prev = testPos;
                addToOpenList(openList, notSearchedPos);
            };
        } else {
            testList.forEach(testPos => {
                testPos.closed = true;
            });
            testList = [];
        }

        testPos = openList.shift();
    }

    throw new Error("road not found");
}

function calWeight(toStart: number, toEnd: number) {
    return AStarConfig.toStartWeight * toStart + AStarConfig.toEndWeight * toEnd;
}

function calDistance(pos0: AStarPos, pos1: AStarPos) {
    let dRow = pos0.row - pos1.row;
    let dCol = pos0.col - pos1.col;
    return Math.abs(dRow) + Math.abs(dCol);
}

function getNotSearchedPosList(map: AStarMap, pos: AStarPos) {
    let aroundPosList: [number, number][] = [
        [pos.row + 1, pos.col],
        [pos.row - 1, pos.col],
        [pos.row, pos.col + 1],
        [pos.row, pos.col - 1],

        [pos.row + 1, pos.col + 1],
        [pos.row + 1, pos.col - 1],
        [pos.row - 1, pos.col + 1],
        [pos.row - 1, pos.col - 1],
    ];

    let notSearchedPosList: AStarPos[] = [];

    aroundPosList.forEach(aroundPos => {
        let [row, col] = aroundPos;
        if ((row >= 0 && row < map.length) &&
            (col >= 0 && col < map[row].length) &&
            (!map[row][col].searched) &&
            (!map[row][col].opened) &&
            (!map[row][col].closed)) {
            map[row][col].searched = true;
            notSearchedPosList.push(map[row][col]);
        }
    });

    return notSearchedPosList;
}

function addToOpenList(openList: AStarPos[], pos: AStarPos) {
    pos.opened = true;
    appendToOrderList(openList, pos, (pos0, pos1) => {
        if (pos0.weight !== undefined &&
            pos1.weight !== undefined) {
            return pos0.weight - pos1.weight;
        }
        return 0;
    });
}

function equalsPos(pos0: AStarPos, pos1: AStarPos) {
    return pos0.row === pos1.row && pos0.col === pos1.col;
}