I'm in the process of developing an algorithm to identify the most efficient route between two points within a maze, but I've hit a snag with its current speed.
Here's what I've done so far:
Auxiliary 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>>();
// Newly explored points:
// storing the position and the previous steps taken
// beginning with the start point and a path consisting solely of that point
let tmpElement = new MazeResult(origin, [origin]);
queue.push(tmpElement);
while (queue.length > 0) {
// retrieve next position to explore potential 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;
}
// evaluating all possible directions
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]);
// checking if 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;
// verifying if it reaches the destination
if (newTarget.coordX != target.coordX || newTarget.coordY != target.coordY) {
// storing the position along with the associated path
tmpElement = new MazeResult(newTarget, newPath);
queue.push(tmpElement);
} else {
// recording the shortest path found
validpaths.push(newPath);
// stop here for only one shortest path
}
}
}
}
validpaths = validpaths.sort(sortByArrayPosition);
let result = validpaths.shift();
return result;
}
I have introduced a third parameter minDistance for comparing calculations of paths to different points, although its relevance may be minimal in this case.
How can I enhance the efficiency of this algorithm?