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

Question

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

这是我所做的：

帮手类:

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，这样我就可以与之前对不同点的路径计算进行比较，但这在这里应该不相关。

我怎样才能提高这个算法的性能？

Answer 1

如果您询问路径查找算法。 Dijkstra 是要走的路。查找这个很棒的开源库：Javascript-alghoritms。本质上你想做的是创建加权图形表示。（您需要了解 "Graph theory" 的基础知识。）在这种情况下，您在点之间的权重将是。点之间的欧几里得距离。以及每个点应该使用什么关键字。（我在场景中使用了 Mac 地址）。在您的情况下，它应该是每个点的唯一 ID。

Answer 2

您可能需要阅读 Dijkstra's algorithm。看起来你已经实现的有点相似但更复杂。您不需要跟踪到每个点的整个路径，只需跟踪到每个位置的最小距离。只需转到具有最低距离值的相邻单元格，即可获得最短路径。

编辑：看来有人先于我！

Answer 3

感谢推荐。

我以这个解决方案结束：

let resultPath: Array<MazePoint>;
let visistedMazePoints: Array<Coord>;
function findBFSPath(origin: Coord, target: Coord) {
    resultPath = new Array<MazePoint>();
    visistedMazePoints = new Array<Coord>();
    availablePaths = new Array<MazePoint>();
    let tmpMazePoint = new MazePoint(origin, null);
    resultPath.push(tmpMazePoint);
    while(resultPath.length > 0) {
        let currentPoint = resultPath.shift();
        if (currentPoint != undefined && 
            currentPoint.position.isEqual(target)) {
                return currentPoint;
        }
        if (currentPoint != undefined && 
            visistedMazePoints.find(_v => _v.isEqual(currentPoint.position)) == undefined) {
            let neighbourMazePoint: MazePoint;
            let xCord: Array<number>;
            let yCord: Array<number>;
            xCord = [0, -1, 1, 0];
            yCord = [-1, 0, 0, 1];
            for (let idx = 0; idx < 4; idx++) {
                neighbourMazePoint = new MazePoint(new Coord(currentPoint.position.coordX + xCord[idx], currentPoint.position.coordY + yCord[idx]), currentPoint);
                if (isValid(visistedMazePoints, neighbourMazePoint.position)) {
                    if (visistedMazePoints.find(_v => _v.isEqual(currentPoint.position)) == undefined) {
                        visistedMazePoints.push(currentPoint.position);
                    }
                    resultPath.push(neighbourMazePoint);
                }
            }
        }
    }

    return null;
}

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

Find path between points. Maze algorithm too slow

javascript

typescript

path-finding

maze