RecursiveMazeSolver

mazeSolver.js

/*
	Mazes to solve
	-----------------
	0 = wall
	1 = cleared path
	2 = start point
	3 = end point
*/

// bi-dimensional maze
var maze01 = [			// solvable
	[2,1,1,1,1,0,0],
	[0,0,0,0,1,0,0],
	[0,1,1,1,1,1,1],
	[0,1,0,0,0,0,1],
	[0,1,0,1,0,0,1],
	[0,1,0,1,1,1,0],
	[0,1,1,1,0,1,3]
];
var maze02 = [			// uncomplete info
	[2,1,1,1,1,0,0],
	[0,0,0,0,1,0,0],
	[0,1,1,1,1,1,1],
	[0,1,0,0,0,0,1],
	[0,1,0,1,0,0,1],
	[0,1,0,1,1,1,0],
	[0,1,1,1,0,1,1]
];
var maze03 = [			// unsolvable
	[1,1,1,1,1,2,1],
	[0,0,1,0,0,0,1],
	[0,0,1,1,1,1,1],
	[0,1,0,0,0,0,0],
	[0,1,1,1,1,0,0],
	[0,1,0,0,1,0,0],
	[0,1,1,1,3,0,0]
];

// tri-dimensional maze

var maze04 = [
	[
		[1,1,1,1,0],
		[1,0,0,1,0],
		[1,1,2,1,1],
		[1,0,0,0,1],
		[1,1,1,1,1]
	],
	[
		[0,0,0,0,0],
		[0,0,0,1,0],
		[0,0,0,1,0],
		[0,1,1,1,0],
		[0,0,0,0,0]
	],
	[
		[0,0,1,1,1],
		[0,0,1,0,1],
		[0,0,3,0,1],
		[0,1,0,0,1],
		[0,1,1,1,1]
	],
];

/**
 * Goes through any-dimensional array representation of maze recursively untill finds "end point" (starting in "start point") or fails to do so ...
 * @param {Array} maze - Maze to be solved
 * @param {Object} definitions - currently only has one definition which is maxRunSize (= maximun number of steps given in maze)
 * @returns {Array[]} Array with all available steps to complete the maze!
 * @returns {null} If no maze, start point or end point given!
 */
function solveMaze( maze, { maxRunSize = 100 } = {} ){
	
	// check if the maze is given
	if( !maze ) return null ; // this is needed !!!
			
	// method to count start points and end points (give them according to dimension, so this can be used in unlimited dimensions)
	const mazePoints = ( maze, depth = 0, index = -1 ) => {
		let startPoints = [] ;
		let endPoints = [] ;
		
		if( Array.isArray( maze ) ){
			for( let i=0 ; i<maze.length ; i++ ){
				let curr = maze[i];
				let mazePointsObj = mazePoints( curr, depth+1, i );
				startPoints.push( ...mazePointsObj.startPoints.map( p => {
					if( index != -1 ) p[ "dim"+depth ] = index ;
					return p ;
				} ) );
				endPoints.push( ...mazePointsObj.endPoints.map( p => {
					if( index != -1 ) p[ "dim"+depth ] = index ;
					return p ;
				} ) );
			}
		} else {
			let newPoint = {};
			newPoint[ "dim" + depth ] = index ;
			
			if( maze == 2 ) startPoints.push( newPoint );
			if( maze == 3 ) endPoints.push( newPoint );
		}
		
		return {
			startPoints : startPoints ,
			endPoints : endPoints
		};
	};
	
	// checks if position already visited
	const bIsVisited = ( arrVisited, pos ) => {
		return arrVisited.filter( p => { 
			let bVisited = true ;
			for( let currDim in pos ){
				if( pos[currDim] != p[currDim] ){
					bVisited = false ;
					break;
				}
			}
			if( bVisited ) return p;
		} ).length != 0 ;
	};
	
	// recursive implementation of maze solving
	const findMazePath = ( maze, currPos, maxDepth = 100, arrVisited = [] ) => {
		
		let arrPaths = [];
		let bSuccess = false ;
		
		if( maxDepth > 0 && !bIsVisited( arrVisited, currPos ) ){			
		
			// this point is marked as visited ...
			arrVisited.push( currPos );
			
			let currValue = maze ;
			let currDimension = 0 ; // dimension count starts at one ! 
			do {
				currDimension++ ;
				currValue = currValue[ currPos["dim"+currDimension] ];
			} while( Array.isArray( currValue ) );
			
			if( typeof currValue == "number" ){
				switch( currValue ){
					case 1 : // it's a path
					case 2 : // it's a start point
						// keep going ...
						
						// goes through all dimensions possible navigations (back & forward)
						for( let currDim in currPos ){
							for( let currDir of [-1,1] ){ // -1 = back, 1 = forward
								let nextPos = Object.assign( {}, currPos );
								nextPos[ currDim ] += currDir ;
								let nextPosResult = findMazePath( maze, nextPos, maxDepth-1, [].concat( arrVisited ) );
								if( nextPosResult.bSuccess ){
									bSuccess = true ;
									for( let currPath of nextPosResult.arrPaths ){
										let newDirection = {};
										newDirection[ currDim ] = currDir ;
										currPath.unshift( newDirection );
										arrPaths.push( currPath );
									}
								}
							}							
						}
						
					break ;
					case 3 : // it's a end point
						bSuccess = true ;
						arrPaths.push([0]); // So it can build the path array 
					break ;
					
					case 0 : // it's a wall
					default : // isn't valid path
						// do nothing !
					break ;
				}
			}
		}
		
		return {
			arrPaths : arrPaths,
			bSuccess : bSuccess
		};
	};
		
	// check if maze has start/end points
	let allMazePoints = mazePoints( maze );
	if( allMazePoints.startPoints.length != 1 && allMazePoints.endPoints.length < 1 ) return null ;
		
	// SOLVE THE MAZE ! ;) 
	let solution = findMazePath( maze, allMazePoints.startPoints[0], maxRunSize );
		
	return solution ;
}