Maze algorithm to find path between points

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?

UPDATE implementing BFS algorithm

-- Important! I need to check not only the shortest path, but in case there are several paths within the same distance, the one with my step 1 being the "first in reading order")

function getLengthMazePointResult(result: MazePoint) {
 let distance = 0;
 while(result.parent != null) {
 distance++;
 result = result.parent;
 }
 return distance;
}
function getNextStepMazePointResult(result: MazePoint) {
 let invertedResult = Array<Coord>();
 invertedResult.push(result.position);
 while(result.parent != null) {
 invertedResult.push(result.position);
 result = result.parent;
 }
 invertedResult = invertedResult.reverse();
 return invertedResult.shift();
}
function move (player: Player) {
 let coordToMove: Coord = new Coord(0, 0);
 let minDistance = 0;
 let doMove = false;
 player.EnemiesPositions = player.EnemiesPositions.sort(sortByPosition);
 for (let idx = 0; idx < player.EnemiesPositions.length; idx++) {
 let positionToCheck = player.EnemiesPositions[idx];
 // let pointsToCheck = [player.position, positionToCheck].sort(sortByPosition);
 // let foundPath = findBFSPath(player.position, positionToCheck);
 let foundPath = findBFSPath(player.position, positionToCheck);
 let tmpDistance = 0;
 if (foundPath) { 
 tmpDistance = getLengthMazePointResult(foundPath);
 let tmpNextCoord = getNextStepMazePointResult(foundPath); 
 if (idx == 0 || !doMove) {
 doMove = true;
 minDistance = tmpDistance;
 if (tmpNextCoord != undefined) {
 coordToMove = tmpNextCoord;
 }
 } else if (tmpDistance < minDistance) {
 minDistance = tmpDistance;
 if (tmpNextCoord != undefined) {
 coordToMove = tmpNextCoord;
 }
 }
 }
 }
 if (doMove && coordToMove != undefined) {
 let newPosition = mapPositions.find(_p => _p.coordX == coordToMove.coordX && _p.coordY == coordToMove.coordY);
 if (newPosition != undefined) {
 player.NextPosition = newPosition;
 } 
 }
}
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);
 let minLength = 0;
 while(resultPath.length > 0) {
 let currentPoint = resultPath.shift();
 if (currentPoint != undefined && 
 currentPoint.position.coordX == target.coordX && currentPoint.position.coordY == target.coordY) {
 return currentPoint;
 }
 if (currentPoint != undefined && 
 visistedMazePoints.find(_v => _v.coordX == currentPoint.position.coordX && _v.coordY == currentPoint.position.coordY) == undefined) {
 let neighbourMazePoint: MazePoint;
 let xCord: Array<number>;
 let yCord: Array<number>;
 xCord = [-1, 0, 0, 1];
 yCord = [0, -1, 1, 0];
 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.coordX == currentPoint.position.coordX && _v.coordY == currentPoint.position.coordY) == undefined) {
 visistedMazePoints.push(currentPoint.position);
 }
 resultPath.push(neighbourMazePoint);
 }
 }
 }
 }
 return null;
}

Answer 1

Use the OOP

If you are going to use objects, then use them to simplify your code. As an example, there are several places in your code where you check to see if two coordinates are equal using code like this:

if (currentPoint.position.coordX == target.coordX && currentPoint.position.coordY == target.coordY) {
 ...
}

Add an equal() method to Coord so you can use something like:

if (currentPoint.position.equals(target)) {
 ...
}

Easier to read and less typing.

Check easy things first

In isValid() it takes a lot of processing to determine isVisited. But takes neglible processing to make sure the X and Y values are in the maze. So it would be more efficient to check them first and then check isVisited only if needed.

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

Path

You don't need to keep the whole path with each point in the maze. You only need to keep the previous point, and maybe the path length. When you get to the finish, you can trace the path backwards using the previous points.

Visited

I believe typescript has a set type. Use that to store visited nodes. Then checking to see if a node was visited is much easier and faster:

visited.has(position)

visited could be preloaded with the nodes that are just outside the maze (e.g. a coord of -1 or line.length). Then you could skip the position.X>= 0 type tests too.

• blfuentes: thanks for the tips. the isValid method improved significantly and the equals methods makes it more readable.