Find path between points. Maze algorithm too slow

Question

I am creating an algorithm to find the shortest path between two points in a maze but my current solution is too slow.

This is what I did:

Helper classes:

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;
}

I have added a third paramether minDistance so I can compare with previous paths calculations to different points but this should not be relevant here.

How could I improve the performance of this algorithm?

Answer 1

Thanks for the recommendations.

I ended with this solution:

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;
}

Answer 2

You might want read up on Dijkstra's algorithm. It seems like what you have implemented is kind of similar but more complicated. You don't need to keep track of the entire path to each point, just the minimum distance to each position. You get the shortest path simply by going to to the neighboring cell with the lowest distance value.

Edit: looks like somebody beat me to it!

Answer 3

If you are asking about path finding alghortims. Dijkstra is way to go. Look up this great open source library : Javascript-alghoritms . Essentialy what you want to do, is to create weighted graph representation. (You need to know basics of "Graph theory".) Your weight between points will be in this case. Euclidian distance between points. And what keyword you should use for each point. (I used Mac Adress in my scenario). In your case it should be the unique id of each point.