This maze is generated using Wilson’s algorithm and then solved using breadth-first search. Compare to best-first search.
-
-
Save StuartFeldt/11373674 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| <!DOCTYPE html> | |
| <meta charset="utf-8"> | |
| <style> | |
| body { | |
| background: #000; | |
| } | |
| </style> | |
| <body> | |
| <script src="http://d3js.org/d3.v3.min.js"></script> | |
| <script> | |
| var width = 960, | |
| height = 960; | |
| var N = 1 << 0, | |
| S = 1 << 1, | |
| W = 1 << 2, | |
| E = 1 << 3, | |
| visited = 1 << 4; | |
| var cellSize = 4, | |
| cellSpacing = 4, | |
| cellWidth = Math.floor((width - cellSpacing) / (cellSize + cellSpacing)), | |
| cellHeight = Math.floor((height - cellSpacing) / (cellSize + cellSpacing)), | |
| cells = generateMaze(cellWidth, cellHeight); | |
| var parent = d3.range(cellHeight * cellWidth).map(function() { return NaN; }), | |
| previous = (cellHeight - 1) * cellWidth, | |
| goalX = cellWidth - 1 - !((cellWidth & 1) | (cellHeight & 1)), | |
| goalY = 0, | |
| goalIndex = goalX + goalY * cellWidth, | |
| frontier = [previous]; | |
| var canvas = d3.select("body").append("canvas") | |
| .attr("width", width) | |
| .attr("height", height); | |
| var context = canvas.node().getContext("2d"); | |
| context.translate( | |
| Math.round((width - cellWidth * cellSize - (cellWidth + 1) * cellSpacing) / 2), | |
| Math.round((height - cellHeight * cellSize - (cellHeight + 1) * cellSpacing) / 2) | |
| ); | |
| context.fillStyle = "#fff"; | |
| for (var j = 0; j < cellHeight; ++j) { | |
| for (var i = 0; i < cellWidth; ++i) { | |
| if (cells[j * cellWidth + i] >= 0) context.fillRect(i * cellSize + (i + 1) * cellSpacing, j * cellSize + (j + 1) * cellSpacing, cellSize, cellSize); | |
| if (cells[j * cellWidth + i] & E) context.fillRect((i + 1) * (cellSize + cellSpacing), j * cellSize + (j + 1) * cellSpacing, cellSpacing, cellSize); | |
| if (cells[j * cellWidth + i] & S) context.fillRect(i * cellSize + (i + 1) * cellSpacing, (j + 1) * (cellSize + cellSpacing), cellSize, cellSpacing); | |
| } | |
| } | |
| context.lineWidth = cellSize; | |
| context.lineCap = "square"; | |
| context.strokeStyle = "#777"; | |
| context.translate(cellSize / 2, cellSize / 2); | |
| d3.timer(function() { | |
| var done, k = 0; | |
| while (++k < 10 && !(done = exploreFrontier())); | |
| return done; | |
| }); | |
| function exploreFrontier() { | |
| if ((i0 = popRandom(frontier)) == null) return true; | |
| var i0, | |
| x0 = i0 % cellWidth, | |
| y0 = i0 / cellWidth | 0, | |
| s0 = score(i0), | |
| i1; | |
| cells[i0] |= visited; | |
| context.strokeStyle = "#777"; | |
| strokePath(previous); | |
| context.strokeStyle = "magenta"; | |
| strokePath(previous = i0); | |
| if (!s0) return true; | |
| if (cells[i0] & N && !(cells[i1 = i0 - cellWidth] & visited)) parent[i1] = i0, frontier.push(i1); | |
| if (cells[i0] & S && !(cells[i1 = i0 + cellWidth] & visited)) parent[i1] = i0, frontier.push(i1); | |
| if (cells[i0] & W && !(cells[i1 = i0 - 1] & visited)) parent[i1] = i0, frontier.push(i1); | |
| if (cells[i0] & E && !(cells[i1 = i0 + 1] & visited)) parent[i1] = i0, frontier.push(i1); | |
| } | |
| function strokePath(index) { | |
| context.beginPath(); | |
| moveTo(index); | |
| while (!isNaN(index = parent[index])) lineTo(index); | |
| context.stroke(); | |
| } | |
| function moveTo(index) { | |
| var i = index % cellWidth, j = index / cellWidth | 0; | |
| context.moveTo(i * cellSize + (i + 1) * cellSpacing, j * cellSize + (j + 1) * cellSpacing); | |
| } | |
| function lineTo(index) { | |
| var i = index % cellWidth, j = index / cellWidth | 0; | |
| context.lineTo(i * cellSize + (i + 1) * cellSpacing, j * cellSize + (j + 1) * cellSpacing); | |
| } | |
| function score(i) { | |
| var x = goalX - (i % cellWidth), y = goalY - (i / cellWidth | 0); | |
| return x * x + y * y; | |
| } | |
| function popRandom(array) { | |
| if (!(n = array.length)) return; | |
| var n, i = Math.random() * n | 0, t; | |
| t = array[i], array[i] = array[n - 1], array[n - 1] = t; | |
| return array.pop(); | |
| } | |
| function generateMaze(width, height) { | |
| var cells = new Array(width * height), // each cell’s edge bits | |
| remaining = d3.range(width * height), // cell indexes to visit | |
| previous = new Array(width * height); // current random walk | |
| // Add a random cell. | |
| var start = remaining.pop(); | |
| cells[start] = 0; | |
| // While there are remaining cells, | |
| // add a loop-erased random walk to the maze. | |
| while (!loopErasedRandomWalk()); | |
| return cells; | |
| function loopErasedRandomWalk() { | |
| var direction, | |
| index0, | |
| index1, | |
| i, | |
| j; | |
| // Pick a location that’s not yet in the maze (if any). | |
| do if ((index0 = remaining.pop()) == null) return true; | |
| while (cells[index0] >= 0); | |
| // Perform a random walk starting at this location, | |
| previous[index0] = index0; | |
| walk: while (true) { | |
| i = index0 % width; | |
| j = index0 / width | 0; | |
| // picking a legal random direction at each step. | |
| direction = Math.random() * 4 | 0; | |
| if (direction === 0) { if (j <= 0) continue walk; --j; } | |
| else if (direction === 1) { if (j >= height - 1) continue walk; ++j; } | |
| else if (direction === 2) { if (i <= 0) continue walk; --i; } | |
| else { if (i >= width - 1) continue walk; ++i; } | |
| // If this new cell was visited previously during this walk, | |
| // erase the loop, rewinding the path to its earlier state. | |
| // Otherwise, just add it to the walk. | |
| index1 = j * width + i; | |
| if (previous[index1] >= 0) eraseWalk(index0, index1); | |
| else previous[index1] = index0; | |
| index0 = index1; | |
| // If this cell is part of the maze, we’re done walking. | |
| if (cells[index1] >= 0) { | |
| // Add the random walk to the maze by backtracking to the starting cell. | |
| // Also erase this walk’s history to not interfere with subsequent walks. | |
| while ((index0 = previous[index1]) !== index1) { | |
| direction = index1 - index0; | |
| if (direction === 1) cells[index0] |= E, cells[index1] |= W; | |
| else if (direction === -1) cells[index0] |= W, cells[index1] |= E; | |
| else if (direction < 0) cells[index0] |= N, cells[index1] |= S; | |
| else cells[index0] |= S, cells[index1] |= N; | |
| previous[index1] = NaN; | |
| index1 = index0; | |
| } | |
| previous[index1] = NaN; | |
| return; | |
| } | |
| } | |
| } | |
| function eraseWalk(index0, index1) { | |
| var index; | |
| while ((index = previous[index0]) !== index1) previous[index0] = NaN, index0 = index; | |
| previous[index0] = NaN; | |
| } | |
| } | |
| d3.select(self.frameElement).style("height", height + "px"); | |
| </script> |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment