Maze solving: Difference between revisions

=={{header|JavaScript}}==

Animated: generating and solving.<br />To start solving, click to choose a 'start' and an 'end' points.

<br />Go [http://webgames.paulo-jorente.de/mazesolver here] to see it in action.

<lang javascript>

var ctx, wid, hei, cols, rows, maze, stack = [], start = {x:-1, y:-1}, end = {x:-1, y:-1}, grid = 8;

function drawMaze() {

for( var i = 0; i < cols; i++ ) {

for( var j = 0; j < rows; j++ ) {

switch( maze[i][j] ) {

case 0: ctx.fillStyle = "black"; break;

case 1: ctx.fillStyle = "green"; break;

case 2: ctx.fillStyle = "red"; break;

case 3: ctx.fillStyle = "yellow"; break;

case 4: ctx.fillStyle = "#500000"; break;

}

ctx.fillRect( grid * i, grid * j, grid, grid );

}

}

}

function getFNeighbours( sx, sy, a ) {

var n = [];

if( sx - 1 > 0 && maze[sx - 1][sy] == a ) {

n.push( { x:sx - 1, y:sy } );

}

if( sx + 1 < cols - 1 && maze[sx + 1][sy] == a ) {

n.push( { x:sx + 1, y:sy } );

}

if( sy - 1 > 0 && maze[sx][sy - 1] == a ) {

n.push( { x:sx, y:sy - 1 } );

}

if( sy + 1 < rows - 1 && maze[sx][sy + 1] == a ) {

n.push( { x:sx, y:sy + 1 } );

}

return n;

}

function solveMaze() {

if( start.x == end.x && start.y == end.y ) {

for( var i = 0; i < cols; i++ ) {

for( var j = 0; j < rows; j++ ) {

switch( maze[i][j] ) {

case 2: maze[i][j] = 3; break;

case 4: maze[i][j] = 0; break;

}

}

}

drawMaze();

return;

}

var neighbours = getFNeighbours( start.x, start.y, 0 );

if( neighbours.length ) {

stack.push( start );

start = neighbours[0];

maze[start.x][start.y] = 2;

} else {

maze[start.x][start.y] = 4;

start = stack.pop();

}

drawMaze();

requestAnimationFrame( solveMaze );

}

function getCursorPos( event ) {

var rect = this.getBoundingClientRect();

var x = Math.floor( ( event.clientX - rect.left ) / grid ),

y = Math.floor( ( event.clientY - rect.top ) / grid );

if( maze[x][y] ) return;

if( start.x == -1 ) {

start = { x: x, y: y };

} else {

end = { x: x, y: y };

maze[start.x][start.y] = 2;

solveMaze();

}

}

function getNeighbours( sx, sy, a ) {

var n = [];

if( sx - 1 > 0 && maze[sx - 1][sy] == a && sx - 2 > 0 && maze[sx - 2][sy] == a ) {

n.push( { x:sx - 1, y:sy } ); n.push( { x:sx - 2, y:sy } );

}

if( sx + 1 < cols - 1 && maze[sx + 1][sy] == a && sx + 2 < cols - 1 && maze[sx + 2][sy] == a ) {

n.push( { x:sx + 1, y:sy } ); n.push( { x:sx + 2, y:sy } );

}

if( sy - 1 > 0 && maze[sx][sy - 1] == a && sy - 2 > 0 && maze[sx][sy - 2] == a ) {

n.push( { x:sx, y:sy - 1 } ); n.push( { x:sx, y:sy - 2 } );

}

if( sy + 1 < rows - 1 && maze[sx][sy + 1] == a && sy + 2 < rows - 1 && maze[sx][sy + 2] == a ) {

n.push( { x:sx, y:sy + 1 } ); n.push( { x:sx, y:sy + 2 } );

}

return n;

}

function createArray( c, r ) {

var m = new Array( c );

for( var i = 0; i < c; i++ ) {

m[i] = new Array( r );

for( var j = 0; j < r; j++ ) {

m[i][j] = 1;

}

}

return m;

}

function createMaze() {

var neighbours = getNeighbours( start.x, start.y, 1 ), l;

if( neighbours.length < 1 ) {

if( stack.length < 1 ) {

drawMaze(); stack = [];

start.x = start.y = -1;

document.getElementById( "canvas" ).addEventListener( "mousedown", getCursorPos, false );

return;

}

start = stack.pop();

} else {

var i = 2 * Math.floor( Math.random() * ( neighbours.length / 2 ) )

l = neighbours[i]; maze[l.x][l.y] = 0;

l = neighbours[i + 1]; maze[l.x][l.y] = 0;

start = l

stack.push( start )

}

drawMaze();

requestAnimationFrame( createMaze );

}

function createCanvas( w, h ) {

var canvas = document.createElement( "canvas" );

wid = w; hei = h;

canvas.width = wid; canvas.height = hei;

canvas.id = "canvas";

ctx = canvas.getContext( "2d" );

ctx.fillStyle = "black"; ctx.fillRect( 0, 0, wid, hei );

document.body.appendChild( canvas );

}

function init() {

cols = 73; rows = 53;

createCanvas( grid * cols, grid * rows );

maze = createArray( cols, rows );

start.x = Math.floor( Math.random() * ( cols / 2 ) );

start.y = Math.floor( Math.random() * ( rows / 2 ) );

if( !( start.x & 1 ) ) start.x++; if( !( start.y & 1 ) ) start.y++;

maze[start.x][start.y] = 0;

createMaze();

}

</lang>

HTML to test.

<pre>

<!DOCTYPE html>

<html><head><meta charset="UTF-8">

<title>Maze</title>

<script src="maze.js"></script></head><body onload="init()"></body></html>

</pre>