Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
354 lines (324 sloc) 12 KB
/* eslint spaced-comment: 0 */
/* eslint no-redeclare: 0 */
/* eslint no-unused-vars: 0 */
const assert = require('assert');
/// title: Maze generation
/// type: rosetta-code
/// categories:
/// difficulty: ?
/// benchmark:
replaceWithActualFunctionHere;
/// description:
/// <div class="rosetta">
/// <br/><br>
/// <dl class="rosetta__description-list"><dt class="rosetta__description-title">Task:</dt></dl>
/// <p class="rosetta__paragraph">Generate and show a maze, using the simple <a class="rosetta__link--wiki" href="https://en.wikipedia.org/wiki/Maze_generation_algorithm#Depth-first_search" title="wp: Maze_generation_algorithm#Depth-first_search">Depth-first search</a> algorithm.</p><br/><p class="rosetta__paragraph"><!-- BEGIN TEXT FROM WIKIPEDIA --></p>
/// <ol class="rosetta__ordered-list"><li class="rosetta__list-item--ordered">Start at a random cell.</li>
/// <li class="rosetta__list-item--ordered">Mark the current cell as visited, and get a list of its neighbors. For each neighbor, starting with a randomly selected neighbor:</li>
/// <li class="rosetta__list-item--ordered">:If that neighbor hasn't been visited, remove the wall between this cell and that neighbor, and then recurse with that neighbor as the current cell.</li></ol><!-- END TEXT FROM WIKIPEDIA -->
/// <br><br><br/><dl class="rosetta__description-list"><dt class="rosetta__description-title"> Related tasks</dt></dl>
/// <ul class="rosetta__unordered-list"><li class="rosetta__list-item--unordered"><a class="rosetta__link--rosetta" href="http://rosettacode.org/wiki/Maze solving" title="Maze solving">Maze solving</a>.</li></ul><br><br><br/></div>
/// challengeSeed:
function replaceMe (foo) {
// Good luck!
return true;
}
/// solutions:
function maze(x,y) {
var n=x*y-1;
if (n<0) {alert("illegal maze dimensions");return;}
var horiz =[]; for (var j= 0; j<x+1; j++) horiz[j]= [],
verti =[]; for (var j= 0; j<x+1; j++) verti[j]= [],
here = [Math.floor(Math.random()*x), Math.floor(Math.random()*y)],
path = [here],
unvisited = [];
for (var j = 0; j<x+2; j++) {
unvisited[j] = [];
for (var k= 0; k<y+1; k++)
unvisited[j].push(j>0 && j<x+1 && k>0 && (j != here[0]+1 || k != here[1]+1));
}
while (0<n) {
var potential = [[here[0]+1, here[1]], [here[0],here[1]+1],
[here[0]-1, here[1]], [here[0],here[1]-1]];
var neighbors = [];
for (var j = 0; j < 4; j++)
if (unvisited[potential[j][0]+1][potential[j][1]+1])
neighbors.push(potential[j]);
if (neighbors.length) {
n = n-1;
next= neighbors[Math.floor(Math.random()*neighbors.length)];
unvisited[next[0]+1][next[1]+1]= false;
if (next[0] == here[0])
horiz[next[0]][(next[1]+here[1]-1)/2]= true;
else
verti[(next[0]+here[0]-1)/2][next[1]]= true;
path.push(here = next);
} else
here = path.pop();
}
return {x: x, y: y, horiz: horiz, verti: verti};
}
function display(m) {
var text= [];
for (var j= 0; j<m.x*2+1; j++) {
var line= [];
if (0 == j%2)
for (var k=0; k<m.y*4+1; k++)
if (0 == k%4)
line[k]= '+';
else
if (j>0 && m.verti[j/2-1][Math.floor(k/4)])
line[k]= ' ';
else
line[k]= '-';
else
for (var k=0; k<m.y*4+1; k++)
if (0 == k%4)
if (k>0 && m.horiz[(j-1)/2][k/4-1])
line[k]= ' ';
else
line[k]= '|';
else
line[k]= ' ';
if (0 == j) line[1]= line[2]= line[3]= ' ';
if (m.x*2-1 == j) line[4*m.y]= ' ';
text.push(line.join('')+'\r\n');
}
return text.join('');
}
/// rawSolutions:
=={{header|JavaScript}}==
{{trans|J}}
<lang javascript>function maze(x,y) {
var n=x*y-1;
if (n<0) {alert("illegal maze dimensions");return;}
var horiz =[]; for (var j= 0; j<x+1; j++) horiz[j]= [],
verti =[]; for (var j= 0; j<x+1; j++) verti[j]= [],
here = [Math.floor(Math.random()*x), Math.floor(Math.random()*y)],
path = [here],
unvisited = [];
for (var j = 0; j<x+2; j++) {
unvisited[j] = [];
for (var k= 0; k<y+1; k++)
unvisited[j].push(j>0 && j<x+1 && k>0 && (j != here[0]+1 || k != here[1]+1));
}
while (0<n) {
var potential = [[here[0]+1, here[1]], [here[0],here[1]+1],
[here[0]-1, here[1]], [here[0],here[1]-1]];
var neighbors = [];
for (var j = 0; j < 4; j++)
if (unvisited[potential[j][0]+1][potential[j][1]+1])
neighbors.push(potential[j]);
if (neighbors.length) {
n = n-1;
next= neighbors[Math.floor(Math.random()*neighbors.length)];
unvisited[next[0]+1][next[1]+1]= false;
if (next[0] == here[0])
horiz[next[0]][(next[1]+here[1]-1)/2]= true;
else
verti[(next[0]+here[0]-1)/2][next[1]]= true;
path.push(here = next);
} else
here = path.pop();
}
return {x: x, y: y, horiz: horiz, verti: verti};
}
function display(m) {
var text= [];
for (var j= 0; j<m.x*2+1; j++) {
var line= [];
if (0 == j%2)
for (var k=0; k<m.y*4+1; k++)
if (0 == k%4)
line[k]= '+';
else
if (j>0 && m.verti[j/2-1][Math.floor(k/4)])
line[k]= ' ';
else
line[k]= '-';
else
for (var k=0; k<m.y*4+1; k++)
if (0 == k%4)
if (k>0 && m.horiz[(j-1)/2][k/4-1])
line[k]= ' ';
else
line[k]= '|';
else
line[k]= ' ';
if (0 == j) line[1]= line[2]= line[3]= ' ';
if (m.x*2-1 == j) line[4*m.y]= ' ';
text.push(line.join('')+'\r\n');
}
return text.join('');
}</lang>
Variable meanings in function <code>maze</code>:
# <code>x</code>,<code>y</code> — dimensions of maze
# <code>n</code> — number of openings to be generated
# <code>horiz</code> — two dimensional array of locations of horizontal openings (true means wall is open)
# <code>verti</code> — two dimensional array of locations of vertical openings (true means wall is open)
# <code>here</code> — current location under consideration
# <code>path</code> — history (stack) of locations that might need to be revisited
# <code>unvisited</code> — two dimensional array of locations that have not been visited, padded to avoid need for boundary tests (true means location needs to be visited)
# <code>potential</code> — locations adjacent to <code>here</code>
# <code>neighbors</code> — unvisited locations adjacent to <code>here</code>
Variable meanings in function <code>display</code>:
# <code>m</code> — maze to be drawn
# <code>text</code> — lines of text representing maze
# <code>line</code> — characters of current line
Note that this implementation relies on javascript arrays being treatable as infinite in size with false (null) values springing into existence as needed, to support referenced array locations. (This significantly reduces the bulk of the necessary initialization code.)
{{out|Example use}}
<lang html><html><head><title></title></head><body><pre id="out"></pre></body></html>
<script type="text/javascript">
/* ABOVE CODE GOES HERE */
document.getElementById('out').innerHTML= display(maze(8,11));
</script></lang>
produced output:
<pre>+ +---+---+---+---+---+---+---+---+---+---+
| | | |
+---+---+ + +---+ + +---+---+ + +
| | | | | | | |
+ + + +---+ +---+ +---+---+ + +
| | | | | | |
+ +---+ +---+---+---+---+---+ + + +
| | | | | |
+---+ +---+ +---+---+ + +---+---+ +
| | | | | | |
+ + + +---+---+---+---+---+ + + +
| | | | | |
+ +---+---+ +---+---+ + +---+---+ +
| | | | | | |
+ + + +---+ +---+---+ + + +---+
| | | |
+---+---+---+---+---+---+---+---+---+---+---+</pre>
For an animated presentation of the progress of this maze creation process, you can use <code>display</code> in each iteration of the main loop. You would also need to take steps to make sure you could see each intermediate result.
For example, change replace the line <code>while (0<n) {</code> with:
<lang javascript> function step() {
if (0<n) {</lang>
And replace the closing brace for this while loop with:
<lang javascript> document.getElementById('out').innerHTML= display({x: x, y: y, horiz: horiz, verti: verti, here: here});
setTimeout(step, 100);
}
}
step();</lang>
To better see the progress, you might want a marker in place, showing the position being considered. To do that, replace the line which reads <code>if (0 == k%4) {</code> with
<lang javascript> if (m.here && m.here[0]*2+1 == j && m.here[1]*4+2 == k)
line[k]= '#'
else if (0 == k%4) {</lang>
Note however that this leaves the final '#' in place on maze completion, and that the function <code>maze</code> no longer returns a result which represents a generated maze.
Note also that this display suggests an optimization. You can replace the line reading <code>path.push(here= next);</code> with:
<lang javascript> here= next;
if (1 < neighbors.length)
path.push(here);</lang>
And this does indeed save a negligible bit of processing, but the maze algorithm will still be forced to backtrack through a number of locations which have no unvisited neighbors.
===HTML Table===
Using HTML, CSS and table cells for maze.
<lang html><html><head><title>Maze maker</title>
<style type="text/css">
table { border-collapse: collapse }
td { width: 1em; height: 1em; border: 1px solid }
td.s { border-bottom: none }
td.n { border-top: none }
td.w { border-left: none }
td.e { border-right: none }
td.v { background: skyblue}
</style>
<script type="application/javascript">
Node.prototype.add = function(tag, cnt, txt) {
for (var i = 0; i < cnt; i++)
this.appendChild(ce(tag, txt));
}
Node.prototype.ins = function(tag) {
this.insertBefore(ce(tag), this.firstChild)
}
Node.prototype.kid = function(i) { return this.childNodes[i] }
Node.prototype.cls = function(t) { this.className += ' ' + t }
NodeList.prototype.map = function(g) {
for (var i = 0; i < this.length; i++) g(this[i]);
}
function ce(tag, txt) {
var x = document.createElement(tag);
if (txt !== undefined) x.innerHTML = txt;
return x
}
function gid(e) { return document.getElementById(e) }
function irand(x) { return Math.floor(Math.random() * x) }
function make_maze() {
var w = parseInt(gid('rows').value || 8, 10);
var h = parseInt(gid('cols').value || 8, 10);
var tbl = gid('maze');
tbl.innerHTML = '';
tbl.add('tr', h);
tbl.childNodes.map(function(x) {
x.add('th', 1);
x.add('td', w, '*');
x.add('th', 1)});
tbl.ins('tr');
tbl.add('tr', 1);
tbl.firstChild.add('th', w + 2);
tbl.lastChild.add('th', w + 2);
for (var i = 1; i <= h; i++) {
for (var j = 1; j <= w; j++) {
tbl.kid(i).kid(j).neighbors = [
tbl.kid(i + 1).kid(j),
tbl.kid(i).kid(j + 1),
tbl.kid(i).kid(j - 1),
tbl.kid(i - 1).kid(j)
];
}
}
walk(tbl.kid(irand(h) + 1).kid(irand(w) + 1));
gid('solve').style.display='inline';
}
function shuffle(x) {
for (var i = 3; i > 0; i--) {
j = irand(i + 1);
if (j == i) continue;
var t = x[j]; x[j] = x[i]; x[i] = t;
}
return x;
}
var dirs = ['s', 'e', 'w', 'n'];
function walk(c) {
c.innerHTML = '&nbsp;';
var idx = shuffle([0, 1, 2, 3]);
for (var j = 0; j < 4; j++) {
var i = idx[j];
var x = c.neighbors[i];
if (x.textContent != '*') continue;
c.cls(dirs[i]), x.cls(dirs[3 - i]);
walk(x);
}
}
function solve(c, t) {
if (c === undefined) {
c = gid('maze').kid(1).kid(1);
c.cls('v');
}
if (t === undefined)
t = gid('maze') .lastChild.previousSibling
.lastChild.previousSibling;
if (c === t) return 1;
c.vis = 1;
for (var i = 0; i < 4; i++) {
var x = c.neighbors[i];
if (x.tagName.toLowerCase() == 'th') continue;
if (x.vis || !c.className.match(dirs[i]) || !solve(x, t))
continue;
x.cls('v');
return 1;
}
c.vis = null;
return 0;
}
</script></head>
<body><form><fieldset>
<label>rows </label><input id='rows' size="3"/>
<label>colums </label><input id='cols' size="3"/>
<a href="javascript:make_maze()">Generate</a>
<a id='solve' style='display:none' href='javascript:solve(); void(0)'>Solve</a>
</fieldset></form><table id='maze'/></body></html></lang>
/// tail:
const replaceThis = 3;
/// tests:
assert(typeof replaceMe === 'function', 'message: <code>replaceMe</code> is a function.');
/// id: 5a23c84252665b21eecc7f10
You can’t perform that action at this time.