..................................................................................###........############.................###.###################.................###.#......############.................#####......############.................###.#......############.#####...####....###.#......############.#.###...####....#####......#....#.......#.###...####....###.#......#....#.......#.#####.####....###.#......##...#.......#.###.#.####....###.#.......#...#.......#.###.#.####....###.#.....###############.###.#.####....###.#.....##########......###.#.####....###.#.....##########......###.#.####....###.################......###.######....###.......##########......###...####..............##########..................................................................................................Example
I'll explain how to generate a rogue-like dungeon (maze) randomly.
First of all, get a 2-dimensional array, dungeon[40][80].
Then initialize it and show the zero-cleared dungeon.
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
<head>
<title>Dungeon</title>
<meta http-equiv="content-type" content="text/html; charset=utf-8" />
<script src="./lib/prototype.js" type="text/javascript"></script>
<script type="text/javascript" language="javascript">
// <![CDATA[
var dungeon_width = 80;
var dungeon_height = 40;
dungeon = new Array(dungeon_height);
for (j=0; j < dungeon_height; j++) {
dungeon[j] = new Array(dungeon_width)
for (i=0; i < dungeon_width; i++) {
dungeon[j][i] = '.';
}
}
function main() {
dungeon.each(function(x) {
var elt = document.createElement('code');
elt.appendChild(document.createTextNode(x.join('')));
$('main').appendChild(elt);
$('main').appendChild(document.createElement('br'));
});
}
window.onload = main;
// ]]>
</script>
</head>
<body>
<div id="main"></div>
</body>
</html>
Secondly, divides rectangles recursively to split the dungeon.
Example reload page to make new splitting.
function split(rect) {
if ((rect.x1 - rect.x0 < margin * 2) ||
(rect.y1 - rect.y0 < margin * 2) ||
(random_range(0,5) === 0)) {
//above is a ending condition.
return [rect];
} else {
if (random_range(0,2) === 0) {
//split vertical
var a = random_range(rect.y0 + margin, rect.y1 - margin);
return [new rectangle(rect.x0, rect.y0, rect.x1, a),
new rectangle(rect.x0, a, rect.x1, rect.y1)].map(split).flatten();
} else {
//split horizonal
var a = random_range(rect.x0 + margin, rect.x1 - margin);
return [new rectangle(rect.x0, rect.y0, a, rect.y1),
new rectangle(a, rect.y0, rect.x1, rect.y1)].map(split).flatten();
}
}
}
Recursively calls "split" divides rectangles more and more. And the last "flatten" makes them to a list of rects.
Make a room in each rects. These rects help to avoid overlapping rooms each other.
I'm going to connects them with corriders like this.
Now we get "Every rooms is always connected each other at least once".
From this, we can avoid a bad patten of below, it doesn't connected.
Finally, makes corrider between the rooms.
To connect rooms divided horizonal, Use a "N-letter" corrider, and for vertical one use "Z-letter" corrider.
Decide whether horizonal or vertical by their coordinate of rectangles.
Example (reloading page will generate a new dungeon.)
function make_corrider(partitions, rooms) {
var connect_list = new Array();
for (var i = 0; i < partitions.length - 1; i++)
connect_list.push([i, i + 1]);
var connect = function(p0,p1,r0,r1) {
if (p0.y1 == p1.y0) {
var a = random_range(r0.x0, r0.x1);
var b = random_range(r1.x0, r1.x1);
fill(new rectangle(a, half(p0.y0 + p0.y1), a, p0.y1));
fill(new rectangle(b, half(p1.y0 + p1.y1), b, p1.y0));
fill(new rectangle(a, p0.y1, b, p1.y0));
} else if (p0.x1 == p1.x0) {
var a = random_range(r0.y0, r0.y1);
var b = random_range(r1.y0, r1.y1);
fill(new rectangle(half(r0.x0 + r0.x1), a, p0.x1, a));
fill(new rectangle(half(r1.x0 + r1.x1), b, p1.x0, b));
fill(new rectangle(p0.x1, a, p1.x0, b));
}
};
connect_list.each(function(x){
connect(partitions[x[0]],partitions[x[1]],rooms[x[0]],rooms[x[1]])});
}
Additionaly, add corriders to give more randomness.
for (var i = 0; i < partitions.length; i++)
for (var j = i + 1; j < partitions.length; j++)
if (random_range(0,5) == 0)
if (partitions[i].x0 == partitions[j].x1 ||
partitions[i].x1 == partitions[j].x0 ||
partitions[i].y0 == partitions[j].y1 ||
partitions[i].y1 == partitions[j].y0)
connect_list.push([i,j]);
Complete.
Example
