Difference between revisions of "Diffusion-limited aggregation"
| Line 3: | Line 3: | ||
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. | 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. | ||
[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] until they hit the seed or a "frozen" particle, at which point they "freeze" in place and become a floor grid: | [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: | ||
##### ##### ##### ##&## ##### ##&## ##### ##### | ##### ##### ##### ##&## ##### ##&## ##### ##### | ||
&#### #&### ##### ##### ##&## ##### ##&## ##.## | &#### #&### ##### ##### ##&## ##### ##&## ##.## | ||
| Line 11: | Line 11: | ||
etc. | etc. | ||
Varying parameters can produce different-looking maps; for instance, here's one generated by random walkers who move both diagonally and orthogonally: | 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: | ||
########################################## | ########################################## | ||
| Line 99: | Line 99: | ||
############################################# | ############################################# | ||
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. | 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. | ||
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. | ||
| Line 136: | Line 136: | ||
[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 | [http://quendus.liero.be/aggregation.txt Examples of block aggregation with smallish blocks] (the disconnected one at the end is due to a bug) | ||
[[Category:Articles]] [[Category:WorldGeneration]] | [[Category:Articles]] [[Category:WorldGeneration]] | ||
Revision as of 01:31, 25 September 2010
(This page is under construction! More examples may be added soon)
Many roguelikes 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, an excellent article), so here's another radically different method.
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 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:
##### ##### ##### ##&## ##### ##&## ##### ##### &#### #&### ##### ##### ##&## ##### ##&## ##.## ##.## ##.## #&.## #..## #..## #..## #..## #..## ##### ##### ##### ##### ##### ##### ##### ####& ##### ##### ##### ##### ##### ##### ##### #####
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:
########################################## #######.#########.######################## #####.#.########.#############.#.######### ###.##.#.########.#############..######### ####.#....######.################.####.### #####.##....##...##############.#..#.....# ######..##..##..################..##....## #######.###...###############.#........### ######.#####....########..##....#..##...## ############.#.########...##.#...###..##.# ##########......#######..##.#..##..##.#### ##########....#.#####.#.####...#..####.### ########...##..##.###....#.......######### #######...#........###....#...#.########## ########..#.##.....####...#..##.########## ########...#######.#.....#....############ ########..######.##.....##...############# #######...#.####...#..#####..####.######## #######....###.#..#..#.#.##...##.#.####### ########.######.#####.#..#...#.......##### #################.##...#.............##### #################.....##...###.#..#.###### ################....#..##.....#.#....##### ############.###...#...####...#.....###### #########.#.##.##..##...###...##.######### #########.#.....#.###...###..############# ##.#####..#...#..#.#......#.############## ##..#.##......##.#..#.#.......############ ####....#..###..#.####..#.....############ ###..###.###..#.#####....#...############# #######.####...#.####..##...############## ####..#......#....####.#..#....###..###### ####.#.#..#..#.########...##....##..###### #######........#########.#.#.#....######## ########.#...#.########.#.#..#.#.######### ######..#.###.##########.###.#..########## ##.#...#.####..########################### #........###..############################ #.######.################################# ##########################################
And here's one produced by walkers who can only move orthogonally:
############################################# ############################.################ #########################.##.################ ########################..#..################ ##############.#########.....################ ##############..#######.......############### #############....#######.......############## ###############..####........################ ##############.#..##.....#.################## #############........##..#################### ###################..#...#################### ###############......##..###.################ ################......##..#..#...############ ######.#.########.#...##.##..#...############ ###..#....###.##.....##..##.###..##########.# #...........#..##..#.#..........###.#.#.##..# ####...###.....###.........#.#....#.#......## ####.##........#.#...........#.#.........#### ####.####..............##.##.....####...##### ########....#......##...#........############ ######......#.#..##...#.##..##.############## #######.....######.......#..#.############### ########...#####.#.............############## #########.#####..#...#..##......##..######### ################........#..#######.########## ###############....##........#.##....#.###### ##############...####.....#............###### ##########......####...##.#.#....#...######## ###########....####...#####.#..#.#....####### ###########...#######...##.....##..##.####### ##################....#.####...##...######### ##################..###..##.....#..########## ###################.###..###.#...#.########## ##################..###..###......########### #######################.########.############ ##################......##################### #################....#..##################### ######################...#################### #####################...##################### ####################..####################### #####################.####################### #############################################
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. 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.
- 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,
- 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.
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.
Other ideas for block aggregation:
- Circles and arcs
- Corridors only
- Diagonal corridors only (if you want to be evil - probably best used with Permissive Field of View)
- Outlines of rectangles
Code
(pseudocode or python may appear here sooner or later)
Related articles
Cellular Automata Method for Generating Random Cave-Like Levels Irregular Shaped Rooms
See also
Diffusion-limited aggregation on wikipedia
Examples of block aggregation with smallish blocks (the disconnected one at the end is due to a bug)