function Seeker(startX,startY,targetX,targetY,direction="up"){ this.pos = { x: startX, y: startY } this.target = { x: targetX, y: targetY } this.direction = direction; } prototype:{ Seeker.prototype.possibleWays = function(){ var ways = 4; var walls = grid[index(this.pos.x,this.pos.y)].walls; if(walls.up){ ways--; } if(walls.right){ ways--; } if(walls.down){ ways--; } if(walls.left){ ways--; } return ways; }; Seeker.prototype.inDeadEnd = function(){ return this.possibleWays()<=1; }; Seeker.prototype.onBranch = function(){ return this.possibleWays()>=3; }; Seeker.prototype.chooseRandomWay = function(allowReturn=false){ var walls = grid[index(this.pos.x,this.pos.y)].walls; var ways = new Array(); if(!walls.up&&!(!allowReturn&&this.direction=="down")){ ways.push("up"); } if(!walls.right&&!(!allowReturn&&this.direction=="left")){ ways.push("right"); } if(!walls.down&&!(!allowReturn&&this.direction=="up")){ ways.push("down"); } if(!walls.left&&!(!allowReturn&&this.direction=="right")){ ways.push("left"); } rand = Math.floor(Math.random()*ways.length); this.direction = ways[rand]; }; Seeker.prototype.chooseLeftWay = function(){ var walls = grid[index(this.pos.x,this.pos.y)].walls; var ways = new Array(); if(!walls.up&&this.direction!="down"){ ways.push(0); } if(!walls.right&&this.direction!="left"){ ways.push(1); } if(!walls.down&&this.direction!="up"){ ways.push(2); } if(!walls.left&&this.direction!="right"){ ways.push(3); } var selectedDir; if(ways.length>=2){ var dirNum = 0; switch(this.direction){ case "left": dirNum++; case "down": dirNum++; case "right": dirNum++; } var indexLeft = ways.indexOf((dirNum+3)%4); var indexStrait = ways.indexOf(dirNum); if(indexLeft!=-1){ selectedDir = ways[indexLeft]; }else{ selectedDir = ways[indexStrait]; } }else{ selectedDir = ways[0]; } switch(selectedDir){ case 0: this.direction = "up"; break; case 1: this.direction = "right"; break; case 2: this.direction = "down"; break; case 3: this.direction = "left"; break; } }; Seeker.prototype.move = function(){ var walls = grid[index(this.pos.x,this.pos.y)].walls; switch(this.direction){ case "up": if(!walls.up){ this.pos.y--; } break; case "right": if(!walls.right){ this.pos.x++; } break; case "down": if(!walls.down){ this.pos.y++; } break; case "left": if(!walls.left){ this.pos.x--; } break; } }; Seeker.prototype.getNextCells = function(allowReturn=false){ var walls = grid[index(this.pos.x,this.pos.y)].walls; var nextCells = new Array(); if(!walls.up&&!(!allowReturn&&this.direction=="down")){ nextCells.push({ x: this.pos.x, y: this.pos.y-1, dir: "up" }); } if(!walls.right&&!(!allowReturn&&this.direction=="left")){ nextCells.push({ x: this.pos.x+1, y: this.pos.y, dir: "right" }); } if(!walls.down&&!(!allowReturn&&this.direction=="up")){ nextCells.push({ x: this.pos.x, y: this.pos.y+1, dir: "down" }); } if(!walls.left&&!(!allowReturn&&this.direction=="right")){ nextCells.push({ x: this.pos.x-1, y: this.pos.y, dir: "left" }); } return nextCells; }; Seeker.prototype.draw = function(color="green"){ var x = this.pos.x*size; var y = this.pos.y*size; ctx2.fillStyle = color; ctx2.fillRect(x,y,size,size); }; Seeker.prototype.drawTarget = function(color="red"){ var x = this.target.x*size; var y = this.target.y*size; ctx2.fillStyle = color; ctx2.fillRect(x,y,size,size); }; } function Cell(x,y,walls={up:true,right:true,down:true,left:true}){ this.x = x; this.y = y; this.walls = walls; this.visited = false; } prototype:{ Cell.prototype.draw = function(){ var x = this.x*size; var y = this.y*size; ctx.clearRect(x,y,size,size); this.drawWalls(); }; Cell.prototype.drawWalls = function(color="white",lineWidth=2){ var x = this.x*size; var y = this.y*size; if(this.walls.up){ ctx.drawLine(x,y,x+size,y,color,lineWidth); } if(this.walls.right){ ctx.drawLine(x+size,y,x+size,y+size,color,lineWidth); } if(this.walls.down){ ctx.drawLine(x,y+size,x+size,y+size,color,lineWidth); } if(this.walls.left){ ctx.drawLine(x,y,x,y+size,color,lineWidth); } }; Cell.prototype.getUnvisitedNeighbour = function(){ var neighbours = new Array(); if(this.y!=0){ if(!grid[index(this.x,this.y-1)].visited){ neighbours.push({index:index(this.x,this.y-1),direction:"up"}); } } if(this.x0){ var neighbour = neighbours.randomElement(); } return neighbour; }; Cell.prototype.removeWall = function(direction){ switch(direction){ case "up": this.walls.up = false; grid[index(this.x,this.y-1)].walls.down = false; break; case "right": this.walls.right = false; grid[index(this.x+1,this.y)].walls.left = false; break; case "down": this.walls.down = false; grid[index(this.x,this.y+1)].walls.up = false; break; case "left": this.walls.left = false; grid[index(this.x-1,this.y)].walls.right = false; break; } }; Cell.prototype.addWall = function(direction){ switch(direction){ case "up": this.walls.up = true; grid[index(this.x,this.y-1)].walls.down = true; break; case "right": this.walls.right = true; grid[index(this.x+1,this.y)].walls.left = true; break; case "down": this.walls.down = true; grid[index(this.x,this.y+1)].walls.up = true; break; case "left": this.walls.left = true; grid[index(this.x-1,this.y)].walls.right = true; break; } }; Cell.prototype.hasVisitedNeighbourToThe = function(direction){ if( (direction=="up" &&this.y>0)|| (direction=="right"&&this.x<(width-1))|| (direction=="down" &&this.y>0)|| (direction=="left" &&this.x<(height-1)) ){ return grid[index(this.x,this.y)+moveIndex(direction)].visited; }else{ return true; } }; Cell.prototype.hasNeighbourToThe = function(direction){ switch(direction){ case "up": return this.y>0; case "right": return this.x<(width-1); case "down": return this.y<(height-1); case "left": return this.x>0; } }; Cell.prototype.getWalls = function(){ var walls = new Array(); if(this.walls.up&&this.y>0){ walls.push({ index: index(this.x,this.y), direction: "up" }); } if(this.walls.right&&this.x<(width-1)){ walls.push({ index: index(this.x,this.y), direction: "right" }); } if(this.walls.down&&this.y<(height-1)){ walls.push({ index: index(this.x,this.y), direction: "down" }); } if(this.walls.left&&this.x>0){ walls.push({ index: index(this.x,this.y), direction: "left" }); } return walls; } } globals:{ var ctx,ctx2; var clock; var width = 30; var height = 30; var size = 10; var grid; var current; var clock; var stack; var fps = 100; var time; var walls; var sets; var boxes; var mazeReady = false; var mouse,searcher; var steps; var positions; var target; } utility:{ function index(x,y){ return x+y*width; } function moveIndex(direction){ switch(direction){ case "up": return -width; case "right": return 1; case "down": return width; case "left": return -1; } } Array.prototype.randomElement = function(){ return this[Math.floor(Math.random()*this.length)]; }; function startMazeAlgorithm(algorithm,walls=true){ clearInterval(clock); setupGrid(walls); ctx.clear(); ctx2.clear(); eval("mazeSetup."+algorithm+"();"); eval("clock = setInterval("+algorithm+",1000/fps);"); } function startPathAlgorithm(algorithm){ if(mazeReady){ clearInterval(clock); ctx2.clear(); eval("pathSetup."+algorithm+"();"); steps = 0; eval("clock = setInterval("+algorithm+",1000/fps);"); } } } setupFunctions:{ function setupCanvas(){ var canvas = document.getElementById('maze'); canvas.width = width*size; canvas.height = height*size; ctx = canvas.getContext('2d'); ctx.drawLine = function(x1,y1,x2,y2,color="white",lineWidth=2){ this.strokeStyle = color; this.lineWidth = lineWidth; this.beginPath(); this.moveTo(x1,y1); this.lineTo(x2,y2); this.stroke(); } ctx.clear = function(){ this.clearRect(0,0,width*size,height*size); } canvas = document.getElementById('path'); canvas.width = width*size; canvas.height = height*size; document.getElementById('canvasContainer').setAttribute("style","width:"+width*size+"px;height:"+height*size+"px"); ctx2 = canvas.getContext('2d'); ctx2.drawLine = function(x1,y1,x2,y2,color="white",lineWidth=2){ this.strokeStyle = color; this.lineWidth = lineWidth; this.beginPath(); this.moveTo(x1,y1); this.lineTo(x2,y2); this.stroke(); } ctx2.clear = function(alpha=0){ if(alpha==0){ ctx2.clearRect(0,0,width*size,height*size); }else{ ctx2.fillStyle = "rgba(0, 0, 0, "+alpha+")"; ctx2.fillRect(0,0,width*size,height*size); } } } function setupGrid(walls=true){ mazeReady = false; grid = new Array(); for(var y=0;y0){ grid[current].draw(); current = stack.pop(); }else{ clearInterval(clock); mazeReady = true; } } function primsAlgorithm(){ if(walls.length>0){ var rand = Math.floor(Math.random()*walls.length); var wall = walls[rand]; if(!grid[wall.index].hasVisitedNeighbourToThe(wall.direction)){ grid[wall.index].removeWall(wall.direction); var next = wall.index+moveIndex(wall.direction); grid[next].visited = true; grid[wall.index].draw(); grid[next].draw(); walls = walls.concat(grid[next].getWalls()); } walls.splice(rand,1); }else{ clearInterval(clock); mazeReady = true; } } function kruskalsAlgorithm(){ if(walls.length>0){ var rand = Math.floor(Math.random()*walls.length); var wall = walls[rand]; if(grid[wall.index].hasNeighbourToThe(wall.direction)){ var neighbour = wall.index+moveIndex(wall.direction); if(grid[wall.index].visited!=grid[neighbour].visited||grid[wall.index].visited==false){ //Remove the wall grid[wall.index].removeWall(wall.direction); //New set if wall.index has non if(grid[wall.index].visited===false){ sets.push([wall.index]); grid[wall.index].visited = sets.length; } var setNum = grid[wall.index].visited; //Change set if neighbour has no set if(grid[neighbour].visited===false){ sets[setNum-1].push(neighbour); grid[neighbour].visited = setNum; }else{ var set = sets[grid[neighbour].visited-1]; var del = grid[neighbour].visited-1; for(var i=0;i0){ var rand = Math.floor(Math.random()*(boxes.length-1)); //var rand = boxes.length-1; var box = boxes[rand]; box.bisect(); boxes.splice(rand,1); //box.highlight(); }else{ for(var i=0;i0){ var searcher = positions.shift(); if(searcher.pos.x==searcher.target.x&&searcher.pos.y==searcher.target.y){ clearInterval(clock); }else{ var nextCells = searcher.getNextCells(firstTime); for(var i=0;i1&&newBoxes[i].height>1){ boxes.push(newBoxes[i]); } } } Box.prototype.highlight = function(){ var x = this.x*size; var y = this.y*size; var w = this.width*size; var h = this.height*size; ctx.fillStyle = "hsla(0,100%,50%,0.1)"; ctx.fillRect(x,y,w,h); }

Ultimate Maze