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

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 。本质上，您想要做的是创建加权图形表示。 (您需要了解“图论”的基础知识。) 在这种情况下，您的点之间的重量就是这样。点之间的欧几里得距离。以及每个点应该使用什么关键字。 (我在我的场景中使用了 Mac 地址)。在你的情况下，它应该是每个点的唯一ID。