var blockSize = 20, blockW, blockH; var canvas1, stage, canvas2, gui, width, height; var block; var tile = {none:0, wall:1, start:2, end:3, path:4}; var sprite = ["white", "#449", "orange", "yellow", "red"]; var guiColour = "#292", selColour = "#0F3", unselColour = "#0A3", guiTextColour = "white", stageTextColour = "black"; var btnW = 80, btnH = 25, btnY1 = 5, btnY2 = 35, selectedBtn = 0; var buttons = [{name:"Wall", x:5, y:btnY1, width:btnW, height:btnH}, {name:"Start", x:85, y:btnY1, width:btnW, height:btnH}, {name:"End", x:165, y:btnY1, width:btnW, height:btnH}, {name:"Random", x:255, y:btnY2, width:btnW, height:btnH}, {name:"Find", x:5, y:btnY2, width:btnW, height:btnH}, {name:"Help", x:415, y:btnY1, width:btnW, height:btnH}, {name:"Clear", x:165, y:btnY2, width:btnW, height:btnH}, {name:"Reset", x:335, y:btnY1, width:btnW, height:btnH}, {name:"Step", x:85, y:btnY2, width:btnW, height:btnH}, {name:"Auto", x:250, y:btnY1, width:btnW, height:btnH}, {name:"Fill", x:335, y:btnY2, width:btnW, height:btnH}, {name:"Empty", x:415, y:btnY2, width:btnW, height:btnH}]; var pathNum = 0, pathNow = 0, defId = -1, pathHolder = [], pathsHolder = [], hasPath = false, auto = true; var gX = [-1, -1], gY = [-1, -1]; window.onload=function() { init(); makeBlocks(); drawBlocks(); drawGui(); } function init() { canvas1 = document.getElementById("stage"); stage = canvas1.getContext("2d"); canvas2 = document.getElementById("gui"); gui = canvas2.getContext("2d"); width = canvas1.width; height = canvas1.height; blockW = Math.floor(width/blockSize); blockH = Math.floor(height/blockSize); } function makeBlocks() { block = new Array(blockW) for(var x = 0; x < block.length; x++) { block[x] = new Array(blockH) for(var y = 0; y < block[0].length; y++) { block[x][y] = {path:[],type:Dani.random(1), id:defId}; } } } function newBlocks(a) { for(var x = 0; x < block.length; x++) for(var y = 0; y < block[0].length; y++) if(a==="fill") block[x][y] = {path:[],type:tile.wall, id:defId}; else if(a==="empty") block[x][y] = {path:[],type:tile.none, id:defId}; else block[x][y] = {path:[],type:Dani.random(1), id:defId}; resetPath(); gX = [-1, -1], gY = [-1, -1]; drawBlocks(); } function clearPath(a, b) { var x, y; for(var i = 0; i < a.length; i++) { x = a[i].x; y = a[i].y; if(b===undefined) if(sameBlock(x, y, tile.start)||sameBlock(x, y, tile.end)) { setBlock(x, y, undefined, defId, []); drawBlock(x, y, undefined, defId, []); } else { setBlock(x, y, tile.none, defId, []); drawBlock(x, y, tile.none, defId, []); } else { setBlock(x, y, undefined, defId, []); drawBlock(x, y, undefined, defId, []); } } if(b===undefined) resetPath(); } function resetPath() { pathHolder = []; pathsHolder = []; pathNow = 0; pathNum = 0; hasPath = false; } function reset(a) { var x, y; for(var i = 0; i < a.length; i++) { x = a[i].x; y = a[i].y; if(!sameBlock(x, y, tile.wall)) { setBlock(x, y, tile.none, defId, []); drawBlock(x, y, tile.none, defId, []); } } if(gX[0]!==-1&&gY[0]!==-1) { setBlock(gX[0], gY[0], tile.none, defId, []); drawBlock(gX[0], gY[0], tile.none, defId, []); } if(gX[1]!==-1&&gY[1]!==-1) { setBlock(gX[1], gY[1], tile.none, defId, []); drawBlock(gX[1], gY[1], tile.none, defId, []); } resetPath(); gX = [-1, -1], gY = [-1, -1]; } function spreadPath(x, y, b, c, path) { if(x===b.x&&y===b.y) { setBlock(x, y, undefined, c); drawBlock(x, y, undefined, c); setPath(x, y, path); pathHolder[pathNow][pathHolder[pathNow].length] = {x:x, y:y}; pathsHolder[pathsHolder.length] = {x:x, y:y}; hasPath = true; pathNum=-10; } else if(sameBlock(x, y, tile.none, -1)||sameBlock(x, y, tile.start, -1)) { setBlock(x, y, undefined, c); drawBlock(x, y, undefined, c); setPath(x, y, path); pathHolder[pathNow][pathHolder[pathNow].length] = {x:x, y:y}; pathsHolder[pathsHolder.length] = {x:x, y:y}; pathNum++; } } function setPath(x, y, path) { try { block[x][y].path = Dani.cloneObject(path); block[x][y].path.push({x:x, y:y}); } catch(e) {} } function drawPath(xx, yy) { var x, y; var path = Dani.cloneObject(block[xx][yy].path); for(var i = 0; i < path.length; i++) { x = path[i].x; y = path[i].y; if(sameBlock(x, y, tile.none)) { setBlock(x, y, tile.path); } } clearPath(pathsHolder, 1); } function findPath(a, b, c, d, criteria) { if(!hasPath) { pathNum = 0; if(criteria==="steps" && pathNow===0) { pathHolder[0] = [{x:gX[0], y:gY[0]}]; a = pathHolder[0]; } pathNow++;pathHolder[pathNow] = []; var x, y; for(var i = 0; i < a.length; i++) { x = a[i].x; y = a[i].y; if(d!==undefined&&x===d.x&&y===d.y) spreadPath(x,y,b,c, block[x][y].path); spreadPath(x-1,y,b,c+1, block[x][y].path); spreadPath(x+1,y,b,c+1, block[x][y].path); spreadPath(x,y-1,b,c+1, block[x][y].path); spreadPath(x,y+1,b,c+1, block[x][y].path); } if(criteria!=="steps") { if(hasPath) drawPath(gX[1], gY[1]); else if(pathNum>0) findPath(pathHolder[pathNow], b, (c+1)); else if(!hasPath) { clearPath(pathsHolder, 1); if(!auto) alert("No path found."); } } else { if(pathNum <= 0 && !hasPath) { clearPath(pathsHolder, 1); if(!auto) alert("No path found."); } } } else { drawPath(gX[1], gY[1]); } } function hasPositions() { return gX[0]!==-1&&gX[1]!==-1&&gY[0]!==-1&&gY[1]!==-1; } function drawBlocks() { for(var x = 0; x < block.length; x++) for(var y = 0; y < block[0].length; y++) drawBlock(x, y, block[x][y].type, block[x][y].id); } function drawGui() { gui.fillStyle = guiColour; gui.fillRect(0, 0, canvas2.width, canvas2.height); drawButtons(); } function drawButtons() { var name, x, y, width, height, selected; for(var i = 0; i < buttons.length; i++) { name = buttons[i].name; x = buttons[i].x; y = buttons[i].y; width = buttons[i].width; height = buttons[i].height; selected = buttons[i].selected; gui.beginPath(); gui.fillStyle = (i===selectedBtn||(name==="Auto"&&auto))?selColour:unselColour; gui.rect(x, y, width, height); gui.fill(); gui.stroke(); gui.closePath(); drawText(name, x, y, width, height, gui, guiTextColour); } } function drawBlock(xx, yy, typee, s) { var x = xx * blockSize; var y = yy * blockSize; var type = typee===undefined? sprite[block[xx][yy].type] : sprite[typee]; stage.beginPath(); stage.fillStyle = type; stage.rect(x, y, blockSize, blockSize); stage.fill(); stage.stroke(); stage.closePath(); if(s!=defId) drawText(s, x, y, blockSize, blockSize, stage, stageTextColour); } function drawText(s, x, y, width, height, target, colour) { var h = height/2; target.font = h+"pt Arial"; var w = target.measureText(s).width; target.fillStyle = colour; target.fillText(s, x + width/2-w/2, y + height/2+h/2); } function stageClick(e, c) { e.preventDefault(); var mouse = blockCords(mouseCords(canvas1, c)); var x = mouse.x; var y = mouse.y; if(selectedBtn===0) { if(sameBlock(x,y,tile.wall)) { clearPath(pathsHolder); setBlock(x,y,tile.none); } else if(sameBlock(x,y,tile.none)||sameBlock(x,y,tile.path)) { clearPath(pathsHolder); setBlock(x,y,tile.wall); } drawBlock(x, y, block[x][y].type, block[x][y].id); } else if(selectedBtn===1) { if(sameBlock(x,y,tile.none)||sameBlock(x,y,tile.path)) { clearPath(pathsHolder); if(gX[0]!==-1&&gY[0]!==-1) { setBlock(gX[0],gY[0],tile.none); drawBlock(gX[0], gY[0], block[gX[0]][gY[0]].type, block[gX[0]][gY[0]].id); } gX[0] = x; gY[0] = y; setBlock(gX[0],gY[0],tile.start); drawBlock(gX[0], gY[0], block[gX[0]][gY[0]].type, block[gX[0]][gY[0]].id); } else if(sameBlock(x,y,tile.start)) { clearPath(pathsHolder); gX[0] = -1; gY[0] = -1; setBlock(x,y,tile.none); drawBlock(x, y, block[x][y].type, block[x][y].id); } } else if(selectedBtn===2) { if(sameBlock(x,y,tile.none)||sameBlock(x,y,tile.path)) { clearPath(pathsHolder); if(gX[1]!==-1&&gY[1]!==-1) { setBlock(gX[1],gY[1],tile.none); drawBlock(gX[1], gY[1], block[gX[1]][gY[1]].type, block[gX[1]][gY[1]].id); } gX[1] = x; gY[1] = y; setBlock(gX[1],gY[1],tile.end); drawBlock(gX[1], gY[1], block[gX[1]][gY[1]].type, block[gX[1]][gY[1]].id); } else if(sameBlock(x,y,tile.end)) { clearPath(pathsHolder); gX[1] = -1; gY[1] = -1; setBlock(x,y,tile.none); drawBlock(x, y, block[x][y].type, block[x][y].id); } } if(sameBlock(x,y,tile.wall)) selectedBtn = 0; else if(sameBlock(x,y,tile.start)) selectedBtn = 1; else if(sameBlock(x,y,tile.end)) selectedBtn = 2; drawButtons(); if(hasPositions() && auto) { clearPath(pathsHolder); findPath([{x:gX[0], y:gY[0]}], {x:gX[1], y:gY[1]}, 0, {x:gX[0], y:gY[0]}); } } function sameBlock(x, y, tile, id) { try { return block[x][y].type===(tile===undefined? block[x][y].type : tile) && block[x][y].id===(id===undefined? block[x][y].id: id); } catch(e) {} } function setBlock(x, y, tile, id, path) { try { block[x][y].type = tile===undefined? block[x][y].type : tile; block[x][y].id = id===undefined? block[x][y].id: id; block[x][y].path = path===undefined? block[x][y].path: path; } catch(e) {} } //Dani.trace("hi)"); function guiClick() { var mouse = mouseCords(canvas2); if(inButton(mouse, buttons[3])) { newBlocks(); } else if(inButton(mouse, buttons[4])) { if(hasPositions()) { clearPath(pathsHolder); findPath([{x:gX[0], y:gY[0]}], {x:gX[1], y:gY[1]}, 0, {x:gX[0], y:gY[0]}); } else alert("Please place a start and end tile"); } else if(inButton(mouse, buttons[5])) { help(); } else if(inButton(mouse, buttons[6])) { auto = false; clearPath(pathsHolder); //removeids } else if(inButton(mouse, buttons[7])) { reset(pathsHolder); //removeids } else if(inButton(mouse, buttons[8])) { if(hasPositions()) findPath(pathHolder[pathNow], {x:gX[1], y:gY[1]}, pathNow, {x:gX[0], y:gY[0]}, "steps"); else alert("Please place a start and end tile"); } else if(inButton(mouse, buttons[9])) { auto = !auto; if(auto&&hasPositions()) { clearPath(pathsHolder); findPath([{x:gX[0], y:gY[0]}], {x:gX[1], y:gY[1]}, 0, {x:gX[0], y:gY[0]}); } } else if(inButton(mouse, buttons[10])) { newBlocks("fill") } else if(inButton(mouse, buttons[11])) { newBlocks("empty") } else { for(var i = 0; i < 3; i++) if(inButton(mouse, buttons[i])) selectedBtn = i; } drawButtons(); } function inButton(mouse, button){ return mouse.x > button.x && mouse.x < button.x+button.width && mouse.y < button.y+button.height && mouse.y > button.y; } function blockCords(cords) { return { x: Math.floor(cords.x/blockSize), y: Math.floor(cords.y/blockSize) } } function mouseCords(target, c) { var bounds = target.getBoundingClientRect(); var xx = c==="touch"? event.touches[0].clientX : event.clientX; var yy = c==="touch"? event.touches[0].clientY : event.clientY; return { x: xx - bounds.left, y: yy - bounds.top }; } function help() { if(prompt("'Basic' help or 'Advanced' help?", "Basic")==="Advanced") { alert("[Advanced]\nEach tile represents an object. Click a tile to interact with it."); alert("=======OBJECTS=======\nWalls: blue\nGround: white\nStart Tile: orange\nEnd Tile: yellow\nPath: red"); alert("=======BUTTONS=======\nWall: Places/Removes walls.\nStart: Places/Changes the starting tile.\nEnd: Places/Changes the ending tile.\n\nAuto: Can be toggled.\nOn- Path is automatically found when both start and end tiles are placed.\nOff- Manually find path using 'Find', 'Step', and 'Clear' buttons.\n\nReset: Resets current grid.\nHelp: Gives you tons of information.\n\nFind: Manually finds a path. ('Auto' must be turned off)\nStep: Shows process of pathfinding one by one. (Click multiple times and observe/'Auto' must be turned off/Press 'Clear' before using)\nClear: Clears path.\n\nRandom: Creates a new grid.\nFill: Fills grid with walls.\nEmpty: Clears grid."); } else { alert("[Basic]\nUse 'Wall' to add/remove walls. Add a 'Start' and 'End' tile on the grid to see magic!\n\nType 'Advanced' next time to learn how it works."); } alert("Have fun!"); }

Dani Pathfinding Engine