Difference between revisions of "Diffusion-limited aggregation"

From RogueBasin
Jump to navigation Jump to search
 
(20 intermediate revisions by 3 users not shown)
Line 1: Line 1:
(This page is under construction! More examples may be added soon)
'''Diffusion-limited aggregation''' is a natural phenomenon in which particles undergoing Brownian motion cluster into aggregates of such particles. The process can be simulated in map generation to create rough tree-like structures; the resulting dungeons can make nice caves.


Many [[roguelike]]s use rectangular rooms connected by straight corridors for their maps, which after a while might get boring (or might not). Relatively few alternatives have been documented (apart from [[Cellular Automata Method for Generating Random Cave-Like Levels|cellular automata]], an excellent article), so here's another radically different method.
== Introduction ==


[http://en.wikipedia.org/wiki/Diffusion-limited_aggregation Diffusion-limited aggregation] is a process which grows tree-like structures from a central seed "." . Particles "&" are placed at random on the grid, and go on a [http://en.wikipedia.org/wiki/Random_walk random walk] (they repeatedly move one step in a random direction) until they hit the seed or a "frozen" particle, at which point they "freeze" in place and become a floor grid:
The early [[roguelike]]s used rectangular rooms connected by straight corridors for their [[level|maps]], which can eventually become boring. Relatively few alternatives have been documented (apart from [[Cellular Automata Method for Generating Random Cave-Like Levels|cellular automata]], an excellent article), so here's another radically different method.
##### ##### ##### ##&## ##### ##&## ##### #####
&#### #&### ##### ##### ##&## ##### ##&## ##.##
##.## ##.## #&.## #..## #..## #..## #..## #..##
##### ##### ##### ##### ##### ##### ##### ####&
##### ##### ##### ##### ##### ##### ##### #####
etc.


Varying parameters and details of the algorithm can produce different-looking maps; for instance, here's one generated by random walkers who move both diagonally and orthogonally:
The basic idea of DLA dungeon generation is this:
 
# Create a grid full of walls.
# Carve out a "seed," a small cluster of floor tiles near the center of the map.
# Create a "walker" on the map that moves around randomly.
# Move the walker around until it collides with a floor tile; then carve out another floor tile where that walker was.
# Return to step 3 and repeat ad infinitum.
 
== Flexibility ==
 
Varying parameters and details of the algorithm can produce different-looking maps; for instance, here's one generated by random walkers who move both diagonally and orthogonally (like a chess king):


  ##########################################
  ##########################################
Line 99: Line 103:
  #############################################
  #############################################


Obviously, the orthogonal-only version produces much "neater" maps, and wider tunnels. You could also try freezing particles whenever they pass next to the dug-out section, rather than just when they try to walk into it (as was used in the above examples). This would probably speed execution up greatly.
The orthogonal-only version seems to produce much "neater" maps, and wider tunnels. You could also try freezing particles whenever they pass next to the dug-out section, rather than just when they try to walk into it (as was used in the above examples). This would probably speed execution up slightly.
A few other things are immediately noticeable (they may or may not be good things, depending on what you want from your gameplay):
A few other things are immediately noticeable (they may or may not be good things, depending on what you want from your gameplay):
* The algorithm is guaranteed to produce a connected map.
* The algorithm is guaranteed to produce a connected map.
* Loops are quite infrequent, large loops are generally not present, and dead ends are common.  
* Loops are quite infrequent, large loops are generally not present, and dead ends are common. If you want more loops, they can be added by placing a tunnelling random walker or forcing placement of extra corridors (according to the level's flavour).
* There are lots of places to corner a player or monster. (Or to hide in!)
* There are lots of places to corner a player or monster. (Or to hide in!)
* There are no well-defined rooms, but a vague impression of corridors
* There are no well-defined rooms, but a vague impression of corridors
* There are lots of obstacles to ranged combat
* There are lots of obstacles to ranged combat.
It's not visible in the above because I trimmed it, but there may be a lot of unused space on the perimeter of the level. You can fix this by tailoring the number of particles to your level size, or by running regular checks that the cave hasn't yet reached the edge.
It's not visible in the above because I trimmed it, but there may be a lot of unused space on the perimeter of the level. You can fix this by tailoring the number of particles to your level size, or by running regular checks that the cave hasn't yet reached the edge.


However, building a whole dungeon by putting every floor tile on its own random walk can take a lot of time, especially at the beginning when a particle won't stop until it hits the precise spot in the centre of the map. This can be reduced by:
However, building a whole dungeon by putting every floor tile on its own random walk can take a lot of time, especially at the beginning when a particle won't stop until it hits the precise spot in the centre of the map. This can be reduced by:
* making the program more eager to freeze particles,
* making the program more eager to freeze particles (waiting for adjacency rather than collision),
* beginning with a larger "seed", for instance a room,
* beginning with a larger "seed", for instance a room,
* weighting the random walk so that they drift towards the centre (this may change the look of your levels significantly!),
* weighting the random walk so that they drift towards the centre (this may change the look of your levels significantly!),
Line 115: Line 119:
* using blocks of tiles instead of single tiles as particles.
* using blocks of tiles instead of single tiles as particles.


This last option can have great effect on the appearance of the level, depending on the set of blocks used and the weights assigned to them; for instance, if all the blocks are relatively large rectangles, and long rows and columns, this method could be used to make traditional roguelike dungeons (and collision-checking would reduce to checking the edges of the block). Placing [[Angband]]-style vaults would also be easy in this model: simply make sure they have a wall surrounding them, and change the way particles are initially placed so that they don't interfere with the vault's innards. Block aggregation will be quite different depending on whether particles are allowed to spawn in a position where they would immediately freeze.
== Block Aggregation ==
 
This last option can have great effect on the appearance of the level, depending on the set of blocks used and the weights assigned to them; for instance, if the blocks are relatively large rectangles, long rows and columns, this method could be used to make traditional roguelike dungeons (and collision-checking would reduce to checking the edges of the block). Placing [[Angband]]-style vaults would also be easy in this model: simply make sure they have a wall surrounding them, and change the way particles are initially placed so that they don't interfere with the vault's innards. Block aggregation will look very different depending on whether particles are allowed to spawn in a position where they would immediately freeze.


Other ideas for block aggregation:
Some ideas for block aggregation:
* Circles and arcs
* Circles and arcs
* [[Irregular Shaped Rooms]]
* Outlines of rectangles
############################################################
#######################################..#.......###########
#####...###############################..#.#####.###########
#####.#.#########################........#.#####.###########
#####.#.###############.......###........#.#####.###########
#####.#.###############.#####.#####.##...#.#####.###########
#####.#.###############.#####.#####.##...#.#####.###########
#####.#.###############.#####.#####.##...#.#####.###########
#####.#.......#########.......#####......#.......###########
#####....####.################..######........##############
########.####.################..######.###....##############
########.####.#######........#..######.###.##.##############
########.####.#######.######.#..######.###.##.##############
########.####.#######.######.#..######.###....##############
########.####.#######.######.#..######...####.##############
########......#######....###.#..######........##############
##########.....#.............#..##.................#########
##########.....#.........#####...........##.######.#########
############......###.....####..............######.#########
############........#.###.######...##..#.##.######.#########
############.####.#.#.###.#..............##........#########
############......#.#.#...........###.....##################
############.######.#.#....#####..###.....##################
####.....###.######.#.....######..####.#..#####...##########
####.##.......#####.######........####.#..#####.#.##########
####.##........####.######.####...####.......##.#.##########
####.##....................####...##.........##.#.##########
####...........#####.##.........####.###........#.##########
######...##.......................##.###...###..#.##########
######.#.##.##.##..##.#...#.#..##.##.###...###....##########
######.#.##........##.#...#.#..................#############
######.#.#####.##.........#.#...#........###################
######...####.........#.#.#........#.#...###################
######..........................#........###################
######...###........##.##.....#..........###################
######.......#.....##.........#..........###################
##############.....##..#####....#........###########.....###
##############.....##........##.......#..#########....##.###
############.......###.###...##.##.##.#........###.#..##.###
############....#..###........#.##.##.....##.#.###.#..##.###
##########..............##.#..#....#####.....#.###.#.....###
##########.#...#...####.......####.................##.######
##########.#...#.#########.#.#####..##.##.###.###..##.######
##########.........#######.#.#####........###.###..##.######
########..##....##.#######...#####.###.######.........######
########..##.......###############.###.#####################
########..###.#.##################.###.#####################
########..###.#.######....########.....#####################
########..###.#........##.##################################
####...#..###.#........##.##################################
#.......#####...######.##.##################################
#.##.#..##############....##################################
#.##.#..####################################################
#.##.#..####################################################
#.##.#..####################################################
#.......####################################################
############################################################
* Corridors only
* Corridors only
############################################################
###############################################.############
######################################.########.############
###################################....########.############
######################################.########.############
###########...########################........#.############
###########......###################....####....############
###########.#####......###############.######.##############
###########.######.##########################.##############
###########.######.################.....##....##############
###########.#.####.#################.#.....##.##....###.....
###########.#.####.############.#.##.########.####.##.#.####
###########.#.####.############.#.##.....####.####.#..#.####
##########....#.#.#############.#.##..#######.####.#....####
#############.#.#.###.#########.#.##..#######.###....#..####
#############.#.#.###.##......#....#..#######.###..#.#...###
#############.#.#.###.########.........##########..###.#.###
#############.......#.##.......#...##........####..###....##
#############.######......#####.......######.####.####....##
#############.######...########...##########.####.####....##
#############.######...########...#.....###...............##
#############.##........####.##...###.#####.#####..#####..##
########.......#.....#.#####.##.#####.#####.#####..#.####.##
###############....#.......#.##.##.##.#####.####.....#######
####################.##.###..........####....#######.#######
####################.##.###.....#..#.###.#.......###.#######
#######################.#####........###.###########.#######
#######################......####....###.###########.#######
#######################.####.........###.###########.#######
############################.#####...###############.#######
############################.#####....##############.#######
############################.#####.#..##############.#######
############################.#####.#..##############.#######
############################.###......####.#################
#############################...##.#...###.#################
###########################........##...##.#################
##################################.####......###############
##################################.#########################
################################....########################
############################################################
* Diagonal corridors only (if you want to be evil - probably best used with [[Permissive Field of View]])
* Diagonal corridors only (if you want to be evil - probably best used with [[Permissive Field of View]])
* Outlines of rectangles
############################################################
########################################.###################
#######################################.####################
###################.##################.#####################
########.###########.################.######################
#########.#########.#..##.###.######.#######################
##########.#########...#.###.####...########################
######.####.########..#.###.####...#########################
#######.###..######.##.###.####...##########################
########.###..#######.#.#.#.##...###########################
#########.###..######.##.###..##############################
########.#####..######..###.#.##############################
#########.#####..######.##.###.########.####################
#########..#####..####.#..####..######.########.############
########.##.#####..##.##.####.#...###.##.#####.#.###########
#######.####.#####.###..######.#...#..###.###.###.##########
######..###.###.#.####..#######.###...##.#.#.#####.#########
###.#.##.#.##.##..###..#.#####.#.#...#.##.#.#######.########
##.#.####.####....#..##.#.###.#.#...#.#..#.#.#######.#######
#.######...###..##.####..###.###.....#..####..#######.######
#######.##..#..#..####.##.#.###.#.#.....#####.##############
######.####.......###.####.###.#.#.#..########..############
#.###.#####..#...#.#.##.#.###.#.#.##.##########..###########
##.#.#####.##.......##.#..##.#.##########.#######.##########
###.#####.###..#....#.###..##.#######.##.#########.#########
########.###.#####...###.##...######.##.###########.########
###########.#######...#.###..#.####.##.######.#####.########
##########.#######.##..##.###.#.##..#.######.##.##.#########
#########.#####.#.###.##.#####.#...#.#.####.####..######.###
################.###.#...######...###.#.#..#####..#####.####
##############..#.#.#...####.##..#.###.#.#..###.##.##..#####
##############..##.#...####.#...#.#.###.#.#..#.####..#.#.###
#############..#.##...####.##..#.###.##..###...####...#.####
############...###...###..##.##.#####.##.####...##.#...#####
############.##.#.#.#.#..##.##########.##.######..##########
###########.####...###..####.####.#####.##..####..##########
##########.######..#.#.####..#####.#####.#.#####.#.#########
#########.######......####.##.#####.#####.#####.##..########
##########.####......#.##.####.#####.###.#####.##.##########
#########..###.#......#..############.#.#####.##.###########
########..#####.#..#.#...#############.#.###.###############
######...#####.#..###..################.#.##################
##.###..##.####..#####.###.##############..#################
###.#.##..####..######..#..#############.##.################
#.##.###...#.#.######.##..#############.####.###############
##..#.#.#...#.######.###.#############.#####################
##..##.#.###.#.####.###.####################################
####..#.#####.#.##.#########################################
#####..#.#####.#..##.#######################################
###############.#.#.########################################
##################.#########################################
#################.##########################################
############################################################
 


== Code ==
== Code ==
=== Pseudocode for block aggregation ===
* Fill a level with wall
* Dig a seed tile or block, probably in the centre
* Do until the level is considered sufficiently full (predefined number of blocks, edge proximity or number of tiles dug):
** Choose a block, either from a given set or using a function
** Choose a location from which to begin the block's walk
*** If necessary, limit this choice to locations that don't interfere with already-dug sections
** Do until the block neighbours or collides with the dug-out section:
*** Move the block one step in a random direction
** Dig out the tiles covered by the block
* Add any other desired features, eg. extra corridors to increase connectivity


(pseudocode or python may appear here sooner or later)
=== Simple Javascript example ===
 
Most browsers hit 'f5' to refresh and regenerate the map. The map will have a random floor color to make it look interesting.
<div style="background-color: #EEEEEE; border-style: dotted; padding: 0.3em">
<syntaxhighlight lang="javascript">
<!DOCTYPE html>
<html>
<head>
<meta charset = "utf-8">
<title>Diffusion Limited Aggregation</title>
<style type = "text/css">
body {background-color:black;}
</style>
<script>
/* Main Mapping Variables & declarations */
var size = 24,x,y,cx,cy;
var map = new Array(size);
// Set the map array
for (var i = 0; i <= size * size; ++i){
map[i] = new Array(size);
}
// Initialize the Map Array to Zeros
for (x=1;x<=size;++x){
for (y=1;y<=size;++y){
map[x][y]=0;
} //end for
} //end for
/* Functional Variables */
var builderSpawned=0
var builderMoveDirection=0;
var allocatedBlocks=0 //variable used to track the percentage of the map filled
var rootX=12,rootY=12; //this is where the growth starts from. Currently center of map
var stepped=0; //this is how long corridors can be
var orthogonalAllowed=0; //Orthogonal movement allowed? If not, it carves a wider cooridor on diagonal
/* The Diffusion Limited Aggregation Loop */
while (allocatedBlocks<((size*size)/8)){ //quit when an eighth of the map is filled
if (builderSpawned!=1){
//Spawn at random position
cx = 2+Math.floor(Math.random()*size-2)
cy = 2+Math.floor(Math.random()*size-2)
//See if builder is ontop of root
if (Math.abs(rootX - cx)<=0 && Math.abs(rootY-cy)<=0){
//builder was spawned too close to root, clear that floor and respawn
if (map[cx][cy]!=1){
map[cx][cy]=1;
allocatedBlocks++;
} //end if
} else {
builderSpawned = 1;
builderMoveDirection = Math.floor(Math.random()*8);
stepped=0;
} //end if
} else { //builder already spawned and knows it's direction, move builder
/* North    */        if (builderMoveDirection==0 && cy>0              ){cy--;stepped++;
/* East      */ } else if (builderMoveDirection==1 && cx<size          ){cx++;stepped++;
/* South    */ } else if (builderMoveDirection==2 && cy<size          ){cy++;stepped++;
/* West      */ } else if (builderMoveDirection==3 && cx>0              ){cx++;stepped++;
/* Northeast */ } else if (builderMoveDirection==4 && cx<size && cy>0  ){cy--;cx++;stepped++;
/* Southeast */ } else if (builderMoveDirection==5 && cx<size && cy<size){cy++;cx++;stepped++;
/* Southwest */ } else if (builderMoveDirection==6 && cx>0 && cy<size  ){cy++;cx--;stepped++;
/* Northwest */ } else if (builderMoveDirection==7 && cx>0 && cy>0      ){cy--;cx--;stepped++;}
/* ensure that the builder is touching an existing spot */
if (cx<size && cy<size && cx>1 && cy>1 && stepped<=5){
/* East      */        if (map[cx+1][cy]==1  ){if (map[cx][cy]!=1){map[cx][cy]=1;allocatedBlocks++;}
/* West      */ } else if (map[cx-1][cy]==1  ){if (map[cx][cy]!=1){map[cx][cy]=1;allocatedBlocks++;}
/* South    */ } else if (map[cx][cy+1]==1  ){if (map[cx][cy]!=1){map[cx][cy]=1;allocatedBlocks++;}
/* North    */ } else if (map[cx][cy-1]==1  ){if (map[cx][cy]!=1){map[cx][cy]=1;allocatedBlocks++;}
/* Northeast */ } else if (map[cx+1][cy-1]==1){if (map[cx][cy]!=1){map[cx][cy]=1;allocatedBlocks++;
if (!orthogonalAllowed){map[cx+1][cy]=1;allocatedBlocks++;}}
/* Southeast */ } else if (map[cx+1][cy+1]==1){if (map[cx][cy]!=1){map[cx][cy]=1;allocatedBlocks++;
if (!orthogonalAllowed){map[cx+1][cy]=1;allocatedBlocks++;}}
/* Southwest */ } else if (map[cx-1][cy+1]==1){if (map[cx][cy]!=1){map[cx][cy]=1;allocatedBlocks++;
if (!orthogonalAllowed){map[cx-1][cy]=1;allocatedBlocks++;}}
/* Northwest */ } else if (map[cx-1][cy-1]==1){if (map[cx][cy]!=1){map[cx][cy]=1;allocatedBlocks++;
if (!orthogonalAllowed){map[cx-1][cy]=1;allocatedBlocks++;}}}
} else { builderSpawned=0; }
} //end if
} //end while
// Draw the map
document.writeln("<canvas id = 'map' width='800' height='800'><font color='FFFFFF'>Your browser does not support canvas.</font></canvas>");
var canvas = document.getElementById("map");
var context = canvas.getContext("2d");
document.writeln("<table><tr>");
// Generate random color for the floor so it looks pretty every time
var c1=Math.floor(Math.random()*255);
var c2=Math.floor(Math.random()*255);
var c3=Math.floor(Math.random()*255);
var roomsize=25;
for (x=1;x<=size;++x){
for (y=1;y<=size;++y){
if (map[x][y]==0){
context.fillStyle="rgb(22,22,22)";
context.fillRect(x*roomsize,y*roomsize,roomsize,roomsize);
} else if (map[x][y]==1){
context.fillStyle="rgb("+c1+","+c2+","+c3+")";
context.fillRect(x*roomsize,y*roomsize,roomsize,roomsize);
} //end if
} //end for
} //end for
context.strokeStyle='#444';
context.lineWidth=3;
context.strokeRect(roomsize,roomsize,x*roomsize-roomsize,y*roomsize-roomsize);
context.font="bold 18px sans-serif";context.textAlign="center";
context.fillStyle='rgb(200,200,200)';
context.fillText('Diffusion Limited Aggregation',x*roomsize/2,18);
</script>
</head>
<body></body>
</html>
</syntaxhighlight>
</div>


== Related articles ==
== Related articles ==
 
* [[Cellular Automata Method for Generating Random Cave-Like Levels]]
[[Cellular Automata Method for Generating Random Cave-Like Levels]]
* [[Irregular Shaped Rooms]]
[[Irregular Shaped Rooms]]
* [[Delving a connected cavern]]


== See also ==
== See also ==
 
* [http://en.wikipedia.org/wiki/Diffusion-limited_aggregation Diffusion-limited aggregation on wikipedia]
[http://en.wikipedia.org/wiki/Diffusion-limited_aggregation Diffusion-limited aggregation on wikipedia]
* [http://quendus.liero.be/aggregation.txt Examples of block aggregation with smallish blocks] (the disconnected one at the end is due to a bug)
 
* [http://quendus.liero.be/aggregation2.txt Semiconventional rooms]
[http://quendus.liero.be/aggregation.txt Examples of block aggregation with smallish blocks] (the disconnected one at the end is due to a bug)
* [http://quendus.liero.be/aggregation3.txt Width-2 diagonal corridors, much nicer than the example above]


[[Category:Articles]] [[Category:WorldGeneration]]
[[Category:Articles]] [[Category:WorldGeneration]]
[[Category:Maps]]

Latest revision as of 09:13, 12 October 2020

Diffusion-limited aggregation is a natural phenomenon in which particles undergoing Brownian motion cluster into aggregates of such particles. The process can be simulated in map generation to create rough tree-like structures; the resulting dungeons can make nice caves.

Introduction

The early roguelikes used rectangular rooms connected by straight corridors for their maps, which can eventually become boring. Relatively few alternatives have been documented (apart from cellular automata, an excellent article), so here's another radically different method.

The basic idea of DLA dungeon generation is this:

  1. Create a grid full of walls.
  2. Carve out a "seed," a small cluster of floor tiles near the center of the map.
  3. Create a "walker" on the map that moves around randomly.
  4. Move the walker around until it collides with a floor tile; then carve out another floor tile where that walker was.
  5. Return to step 3 and repeat ad infinitum.

Flexibility

Varying parameters and details of the algorithm can produce different-looking maps; for instance, here's one generated by random walkers who move both diagonally and orthogonally (like a chess king): 

##########################################
#######.#########.########################
#####.#.########.#############.#.#########
###.##.#.########.#############..#########
####.#....######.################.####.###
#####.##....##...##############.#..#.....#
######..##..##..################..##....##
#######.###...###############.#........###
######.#####....########..##....#..##...##
############.#.########...##.#...###..##.#
##########......#######..##.#..##..##.####
##########....#.#####.#.####...#..####.###
########...##..##.###....#.......#########
#######...#........###....#...#.##########
########..#.##.....####...#..##.##########
########...#######.#.....#....############
########..######.##.....##...#############
#######...#.####...#..#####..####.########
#######....###.#..#..#.#.##...##.#.#######
########.######.#####.#..#...#.......#####
#################.##...#.............#####
#################.....##...###.#..#.######
################....#..##.....#.#....#####
############.###...#...####...#.....######
#########.#.##.##..##...###...##.#########
#########.#.....#.###...###..#############
##.#####..#...#..#.#......#.##############
##..#.##......##.#..#.#.......############
####....#..###..#.####..#.....############
###..###.###..#.#####....#...#############
#######.####...#.####..##...##############
####..#......#....####.#..#....###..######
####.#.#..#..#.########...##....##..######
#######........#########.#.#.#....########
########.#...#.########.#.#..#.#.#########
######..#.###.##########.###.#..##########
##.#...#.####..###########################
#........###..############################
#.######.#################################
##########################################

And here's one produced by walkers who can only move orthogonally: 

#############################################
############################.################
#########################.##.################
########################..#..################
##############.#########.....################
##############..#######.......###############
#############....#######.......##############
###############..####........################
##############.#..##.....#.##################
#############........##..####################
###################..#...####################
###############......##..###.################
################......##..#..#...############
######.#.########.#...##.##..#...############
###..#....###.##.....##..##.###..##########.#
#...........#..##..#.#..........###.#.#.##..#
####...###.....###.........#.#....#.#......##
####.##........#.#...........#.#.........####
####.####..............##.##.....####...#####
########....#......##...#........############
######......#.#..##...#.##..##.##############
#######.....######.......#..#.###############
########...#####.#.............##############
#########.#####..#...#..##......##..#########
################........#..#######.##########
###############....##........#.##....#.######
##############...####.....#............######
##########......####...##.#.#....#...########
###########....####...#####.#..#.#....#######
###########...#######...##.....##..##.#######
##################....#.####...##...#########
##################..###..##.....#..##########
###################.###..###.#...#.##########
##################..###..###......###########
#######################.########.############
##################......#####################
#################....#..#####################
######################...####################
#####################...#####################
####################..#######################
#####################.#######################
#############################################

The orthogonal-only version seems to produce much "neater" maps, and wider tunnels. You could also try freezing particles whenever they pass next to the dug-out section, rather than just when they try to walk into it (as was used in the above examples). This would probably speed execution up slightly. A few other things are immediately noticeable (they may or may not be good things, depending on what you want from your gameplay):

  • The algorithm is guaranteed to produce a connected map.
  • Loops are quite infrequent, large loops are generally not present, and dead ends are common. If you want more loops, they can be added by placing a tunnelling random walker or forcing placement of extra corridors (according to the level's flavour).
  • There are lots of places to corner a player or monster. (Or to hide in!)
  • There are no well-defined rooms, but a vague impression of corridors
  • There are lots of obstacles to ranged combat.

It's not visible in the above because I trimmed it, but there may be a lot of unused space on the perimeter of the level. You can fix this by tailoring the number of particles to your level size, or by running regular checks that the cave hasn't yet reached the edge.

However, building a whole dungeon by putting every floor tile on its own random walk can take a lot of time, especially at the beginning when a particle won't stop until it hits the precise spot in the centre of the map. This can be reduced by:

  • making the program more eager to freeze particles (waiting for adjacency rather than collision),
  • beginning with a larger "seed", for instance a room,
  • weighting the random walk so that they drift towards the centre (this may change the look of your levels significantly!),
  • resizing the grid as the level grows (this could be difficult),
  • using blocks of tiles instead of single tiles as particles.

Block Aggregation

This last option can have great effect on the appearance of the level, depending on the set of blocks used and the weights assigned to them; for instance, if the blocks are relatively large rectangles, long rows and columns, this method could be used to make traditional roguelike dungeons (and collision-checking would reduce to checking the edges of the block). Placing Angband-style vaults would also be easy in this model: simply make sure they have a wall surrounding them, and change the way particles are initially placed so that they don't interfere with the vault's innards. Block aggregation will look very different depending on whether particles are allowed to spawn in a position where they would immediately freeze.

Some ideas for block aggregation: 

############################################################
#######################################..#.......###########
#####...###############################..#.#####.###########
#####.#.#########################........#.#####.###########
#####.#.###############.......###........#.#####.###########
#####.#.###############.#####.#####.##...#.#####.###########
#####.#.###############.#####.#####.##...#.#####.###########
#####.#.###############.#####.#####.##...#.#####.###########
#####.#.......#########.......#####......#.......###########
#####....####.################..######........##############
########.####.################..######.###....##############
########.####.#######........#..######.###.##.##############
########.####.#######.######.#..######.###.##.##############
########.####.#######.######.#..######.###....##############
########.####.#######.######.#..######...####.##############
########......#######....###.#..######........##############
##########.....#.............#..##.................#########
##########.....#.........#####...........##.######.#########
############......###.....####..............######.#########
############........#.###.######...##..#.##.######.#########
############.####.#.#.###.#..............##........#########
############......#.#.#...........###.....##################
############.######.#.#....#####..###.....##################
####.....###.######.#.....######..####.#..#####...##########
####.##.......#####.######........####.#..#####.#.##########
####.##........####.######.####...####.......##.#.##########
####.##....................####...##.........##.#.##########
####...........#####.##.........####.###........#.##########
######...##.......................##.###...###..#.##########
######.#.##.##.##..##.#...#.#..##.##.###...###....##########
######.#.##........##.#...#.#..................#############
######.#.#####.##.........#.#...#........###################
######...####.........#.#.#........#.#...###################
######..........................#........###################
######...###........##.##.....#..........###################
######.......#.....##.........#..........###################
##############.....##..#####....#........###########.....###
##############.....##........##.......#..#########....##.###
############.......###.###...##.##.##.#........###.#..##.###
############....#..###........#.##.##.....##.#.###.#..##.###
##########..............##.#..#....#####.....#.###.#.....###
##########.#...#...####.......####.................##.######
##########.#...#.#########.#.#####..##.##.###.###..##.######
##########.........#######.#.#####........###.###..##.######
########..##....##.#######...#####.###.######.........######
########..##.......###############.###.#####################
########..###.#.##################.###.#####################
########..###.#.######....########.....#####################
########..###.#........##.##################################
####...#..###.#........##.##################################
#.......#####...######.##.##################################
#.##.#..##############....##################################
#.##.#..####################################################
#.##.#..####################################################
#.##.#..####################################################
#.......####################################################
############################################################
  • Corridors only
############################################################
###############################################.############
######################################.########.############
###################################....########.############
######################################.########.############
###########...########################........#.############
###########......###################....####....############
###########.#####......###############.######.##############
###########.######.##########################.##############
###########.######.################.....##....##############
###########.#.####.#################.#.....##.##....###.....
###########.#.####.############.#.##.########.####.##.#.####
###########.#.####.############.#.##.....####.####.#..#.####
##########....#.#.#############.#.##..#######.####.#....####
#############.#.#.###.#########.#.##..#######.###....#..####
#############.#.#.###.##......#....#..#######.###..#.#...###
#############.#.#.###.########.........##########..###.#.###
#############.......#.##.......#...##........####..###....##
#############.######......#####.......######.####.####....##
#############.######...########...##########.####.####....##
#############.######...########...#.....###...............##
#############.##........####.##...###.#####.#####..#####..##
########.......#.....#.#####.##.#####.#####.#####..#.####.##
###############....#.......#.##.##.##.#####.####.....#######
####################.##.###..........####....#######.#######
####################.##.###.....#..#.###.#.......###.#######
#######################.#####........###.###########.#######
#######################......####....###.###########.#######
#######################.####.........###.###########.#######
############################.#####...###############.#######
############################.#####....##############.#######
############################.#####.#..##############.#######
############################.#####.#..##############.#######
############################.###......####.#################
#############################...##.#...###.#################
###########################........##...##.#################
##################################.####......###############
##################################.#########################
################################....########################
############################################################

############################################################
########################################.###################
#######################################.####################
###################.##################.#####################
########.###########.################.######################
#########.#########.#..##.###.######.#######################
##########.#########...#.###.####...########################
######.####.########..#.###.####...#########################
#######.###..######.##.###.####...##########################
########.###..#######.#.#.#.##...###########################
#########.###..######.##.###..##############################
########.#####..######..###.#.##############################
#########.#####..######.##.###.########.####################
#########..#####..####.#..####..######.########.############
########.##.#####..##.##.####.#...###.##.#####.#.###########
#######.####.#####.###..######.#...#..###.###.###.##########
######..###.###.#.####..#######.###...##.#.#.#####.#########
###.#.##.#.##.##..###..#.#####.#.#...#.##.#.#######.########
##.#.####.####....#..##.#.###.#.#...#.#..#.#.#######.#######
#.######...###..##.####..###.###.....#..####..#######.######
#######.##..#..#..####.##.#.###.#.#.....#####.##############
######.####.......###.####.###.#.#.#..########..############
#.###.#####..#...#.#.##.#.###.#.#.##.##########..###########
##.#.#####.##.......##.#..##.#.##########.#######.##########
###.#####.###..#....#.###..##.#######.##.#########.#########
########.###.#####...###.##...######.##.###########.########
###########.#######...#.###..#.####.##.######.#####.########
##########.#######.##..##.###.#.##..#.######.##.##.#########
#########.#####.#.###.##.#####.#...#.#.####.####..######.###
################.###.#...######...###.#.#..#####..#####.####
##############..#.#.#...####.##..#.###.#.#..###.##.##..#####
##############..##.#...####.#...#.#.###.#.#..#.####..#.#.###
#############..#.##...####.##..#.###.##..###...####...#.####
############...###...###..##.##.#####.##.####...##.#...#####
############.##.#.#.#.#..##.##########.##.######..##########
###########.####...###..####.####.#####.##..####..##########
##########.######..#.#.####..#####.#####.#.#####.#.#########
#########.######......####.##.#####.#####.#####.##..########
##########.####......#.##.####.#####.###.#####.##.##########
#########..###.#......#..############.#.#####.##.###########
########..#####.#..#.#...#############.#.###.###############
######...#####.#..###..################.#.##################
##.###..##.####..#####.###.##############..#################
###.#.##..####..######..#..#############.##.################
#.##.###...#.#.######.##..#############.####.###############
##..#.#.#...#.######.###.#############.#####################
##..##.#.###.#.####.###.####################################
####..#.#####.#.##.#########################################
#####..#.#####.#..##.#######################################
###############.#.#.########################################
##################.#########################################
#################.##########################################
############################################################


Code

Pseudocode for block aggregation

  • Fill a level with wall
  • Dig a seed tile or block, probably in the centre
  • Do until the level is considered sufficiently full (predefined number of blocks, edge proximity or number of tiles dug):
    • Choose a block, either from a given set or using a function
    • Choose a location from which to begin the block's walk
      • If necessary, limit this choice to locations that don't interfere with already-dug sections
    • Do until the block neighbours or collides with the dug-out section:
      • Move the block one step in a random direction
    • Dig out the tiles covered by the block
  • Add any other desired features, eg. extra corridors to increase connectivity

Simple Javascript example

Most browsers hit 'f5' to refresh and regenerate the map. The map will have a random floor color to make it look interesting. 

<!DOCTYPE html>
<html>
	<head>
		<meta charset = "utf-8">
		<title>Diffusion Limited Aggregation</title>
		<style type = "text/css">
			body {background-color:black;}
		</style>
		<script>
			/* Main Mapping Variables & declarations */
				var size = 24,x,y,cx,cy;
				var map = new Array(size);
				// Set the map array
				for (var i = 0; i <= size * size; ++i){
					map[i] = new Array(size);
				}
				// Initialize the Map Array to Zeros 
				for (x=1;x<=size;++x){
					for (y=1;y<=size;++y){
						map[x][y]=0;
					} //end for
				} //end for
			/* Functional Variables */
				var builderSpawned=0
				var builderMoveDirection=0;
				var allocatedBlocks=0 //variable used to track the percentage of the map filled
				var rootX=12,rootY=12; //this is where the growth starts from. Currently center of map
				var stepped=0; //this is how long corridors can be
				var orthogonalAllowed=0; //Orthogonal movement allowed? If not, it carves a wider cooridor on diagonal
			/* The Diffusion Limited Aggregation Loop */
			while (allocatedBlocks<((size*size)/8)){ //quit when an eighth of the map is filled
				if (builderSpawned!=1){
					//Spawn at random position
					cx = 2+Math.floor(Math.random()*size-2)
					cy = 2+Math.floor(Math.random()*size-2)
					//See if builder is ontop of root
					if (Math.abs(rootX - cx)<=0 && Math.abs(rootY-cy)<=0){
						//builder was spawned too close to root, clear that floor and respawn
						if (map[cx][cy]!=1){
							map[cx][cy]=1;
							allocatedBlocks++;
						} //end if
					} else {
						builderSpawned = 1;
						builderMoveDirection = Math.floor(Math.random()*8);
						stepped=0;
					} //end if
				} else { //builder already spawned and knows it's direction, move builder
					/* North     */        if (builderMoveDirection==0 && cy>0              ){cy--;stepped++;
					/* East      */ } else if (builderMoveDirection==1 && cx<size           ){cx++;stepped++;
					/* South     */ } else if (builderMoveDirection==2 && cy<size           ){cy++;stepped++;
					/* West      */ } else if (builderMoveDirection==3 && cx>0              ){cx++;stepped++;
					/* Northeast */ } else if (builderMoveDirection==4 && cx<size && cy>0   ){cy--;cx++;stepped++;
					/* Southeast */ } else if (builderMoveDirection==5 && cx<size && cy<size){cy++;cx++;stepped++;
					/* Southwest */ } else if (builderMoveDirection==6 && cx>0 && cy<size   ){cy++;cx--;stepped++;
					/* Northwest */ } else if (builderMoveDirection==7 && cx>0 && cy>0      ){cy--;cx--;stepped++;}
					/* ensure that the builder is touching an existing spot */
					if (cx<size && cy<size && cx>1 && cy>1 && stepped<=5){
					/* East      */        if (map[cx+1][cy]==1  ){if (map[cx][cy]!=1){map[cx][cy]=1;allocatedBlocks++;}
					/* West      */ } else if (map[cx-1][cy]==1  ){if (map[cx][cy]!=1){map[cx][cy]=1;allocatedBlocks++;} 
					/* South     */ } else if (map[cx][cy+1]==1  ){if (map[cx][cy]!=1){map[cx][cy]=1;allocatedBlocks++;}
					/* North     */ } else if (map[cx][cy-1]==1  ){if (map[cx][cy]!=1){map[cx][cy]=1;allocatedBlocks++;}
					/* Northeast */ } else if (map[cx+1][cy-1]==1){if (map[cx][cy]!=1){map[cx][cy]=1;allocatedBlocks++;
										 if (!orthogonalAllowed){map[cx+1][cy]=1;allocatedBlocks++;}}
					/* Southeast */ } else if (map[cx+1][cy+1]==1){if (map[cx][cy]!=1){map[cx][cy]=1;allocatedBlocks++;
										 if (!orthogonalAllowed){map[cx+1][cy]=1;allocatedBlocks++;}}
					/* Southwest */ } else if (map[cx-1][cy+1]==1){if (map[cx][cy]!=1){map[cx][cy]=1;allocatedBlocks++; 
										 if (!orthogonalAllowed){map[cx-1][cy]=1;allocatedBlocks++;}}
					/* Northwest */ } else if (map[cx-1][cy-1]==1){if (map[cx][cy]!=1){map[cx][cy]=1;allocatedBlocks++;
										 if (!orthogonalAllowed){map[cx-1][cy]=1;allocatedBlocks++;}}}
					} else { builderSpawned=0; }
				} //end if
			} //end while
			// Draw the map
			document.writeln("<canvas id = 'map' width='800' height='800'><font color='FFFFFF'>Your browser does not support canvas.</font></canvas>");
			var canvas = document.getElementById("map");
			var context = canvas.getContext("2d");
			document.writeln("<table><tr>");
			// Generate random color for the floor so it looks pretty every time
			var c1=Math.floor(Math.random()*255);
			var c2=Math.floor(Math.random()*255);
			var c3=Math.floor(Math.random()*255);
			var roomsize=25;
			for (x=1;x<=size;++x){
				for (y=1;y<=size;++y){
					if (map[x][y]==0){
						context.fillStyle="rgb(22,22,22)";
						context.fillRect(x*roomsize,y*roomsize,roomsize,roomsize);
					} else if (map[x][y]==1){
						context.fillStyle="rgb("+c1+","+c2+","+c3+")";
						context.fillRect(x*roomsize,y*roomsize,roomsize,roomsize);
					} //end if
				} //end for
			} //end for
			context.strokeStyle='#444';
			context.lineWidth=3;
			context.strokeRect(roomsize,roomsize,x*roomsize-roomsize,y*roomsize-roomsize);
			context.font="bold 18px sans-serif";context.textAlign="center";
			context.fillStyle='rgb(200,200,200)';
			context.fillText('Diffusion Limited Aggregation',x*roomsize/2,18);
		</script>
	</head>
	<body></body>
</html>

Related articles

See also

Retrieved from "http://roguebasin.com/index.php?title=Diffusion-limited_aggregation&oldid=50106"