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