javascript - 查找点之间的路径。迷宫算法太慢

我正在创建一种算法来查找迷宫中两点之间的最短路径，但是我目前的解决方案太慢了。

这是我所做的：

助手类：

import { Coord } from "./Coord";

export class MazeResult {
    position: Coord;
    path: Array<Coord>;

    constructor (_position: Coord, _path: Array<Coord>) {
        this.position = _position;
        this.path = _path;
    }
}

export class Coord {
    coordX: number;
    coordY: number;
    isFree: boolean;
    element: Element;
    distance: number;

    constructor (xpos: number, ypos: number) {
        this.coordX = xpos;
        this.coordY = ypos;
        this.distance = 0;
    }
}

function isValid(visited: Array<Coord>, position: Coord)
{
    let checkPosition = mapPositions.find(_p => _p.coordX == position.coordX &&
                                                _p.coordY == position.coordY);
    let isVisited = false;
    for (var j = 0; j < visited.length; j ++) {
            if ((visited[j].coordX == position.coordX && visited[j].coordY == position.coordY)) {
                isVisited = true;
                break;
        }
    }
    return (position.coordY >= 0) &&
            (position.coordY < lines.length) &&
            (position.coordX >= 0) &&
            (position.coordX < lines[0].length) &&
            (checkPosition != undefined && checkPosition.element.elementType == ElementType.FIELD) &&
            !isVisited;
}

function findPath(origin: Coord, target: Coord, minDistance: number) {
    let queue = Array<MazeResult>();
    let validpaths = Array<Array<Coord>>();

    // New points, where we did not check the surroundings:
    // remember the position and how we got there
    // initially our starting point and a path containing only this point
    let tmpElement = new MazeResult(origin, [origin]);
    queue.push(tmpElement);

    while (queue.length > 0) {
        // get next position to check viable directions
        let pointToReach = queue.shift();
        let position = new Coord(0, 0);
        let path = new Array<Coord>();
        if(pointToReach != undefined){
            position = pointToReach.position;
            path = pointToReach.path;
        }
        // all points in each direction
        let direction = [
                            [ position.coordX, position.coordY - 1 ],
                            [ position.coordX, position.coordY + 1 ],
                            [ position.coordX - 1, position.coordY ],
                            [ position.coordX + 1, position.coordY ]
                        ];
        for(var i = 0; i < direction.length; i++) {
            let newTarget = new Coord(direction[i][0], direction[i][1]);
            // is valid is just a function that checks whether the point is free.
            if (isValid(path, newTarget)) {
                //
                let newPath = path.slice(0);
                newPath.push(newTarget);

                if ((validpaths.length > 0 && validpaths.sort(_p => _p.length)[0].length < newPath.length) ||
                    (minDistance > 0 && newPath.length > minDistance))
                    continue;

                // check if we are at end
                if (newTarget.coordX != target.coordX || newTarget.coordY != target.coordY) {
                    // remember position and the path to it
                    tmpElement = new MazeResult(newTarget, newPath);
                    queue.push(tmpElement);
                } else {
                    // remember this path from start to end
                    validpaths.push(newPath);
                    // break here if you want only one shortest path
                }
            }
        }
    }

    validpaths = validpaths.sort(sortByArrayPosition);
    let result = validpaths.shift();

    return result;
}

我添加了第三个参数minDistance，因此我可以将以前的路径计算与不同点进行比较，但这在这里不重要。

如何改善此算法的性能？

最佳答案

如果您正在寻找寻路者。 Dijkstra是路要走。查找这个出色的开源库：Javascript-alghoritms。本质上，您要执行的操作是创建加权图表示。 （您需要了解“图论”的基础。）
在这种情况下，您的体重将介于两点之间。点之间的欧几里得距离。以及每个点应使用什么关键字。 （在我的方案中使用了Mac Adress）。在您的情况下，它应该是每个点的唯一ID。