2D Map Generation with Cellular Automata
This project uses cellular automata to create a 2D grid map made up of grass (green), gravel (light grey), stone (dark grey), and water (blue) tiles. Every grass/gravel area (room) can be accessed from the other areas in the map. The map has no isolated rooms. Isolated rooms means any section of passable terrain on the map (grass/gravel) that cannot be reached from all other locations on the map.
I was never that great at creating maps so the purpose of this project was to create a program that did it for me. I also wanted to make the algorithm as data driven as possible. How open or enclosed the map along with the ratio of tile types is completely driven by XML documents.
I was never that great at creating maps so the purpose of this project was to create a program that did it for me. I also wanted to make the algorithm as data driven as possible. How open or enclosed the map along with the ratio of tile types is completely driven by XML documents.
Random Noise of Gravel, Grass, Stone, and Water
Each tile type has a ratio which decides how much of it is in the random noise. (20% stone, 10% gravel, 63% grass, 7% water)
The XML data below sets everything about a tile type. The ratios decides how much of it is included in the random noise at the start of the algorithm as well as what tile it finally produces during a cellular automata step. Weight effects how much influence a tile type has on the cellular automata algorithm. IsSolid tells the program if the tile is considered a wall or not and waterThreshold effects how well river tiles flow through it.
The XML data below sets everything about a tile type. The ratios decides how much of it is included in the random noise at the start of the algorithm as well as what tile it finally produces during a cellular automata step. Weight effects how much influence a tile type has on the cellular automata algorithm. IsSolid tells the program if the tile is considered a wall or not and waterThreshold effects how well river tiles flow through it.
|
|
Cellular Automata Steps
|
|
Cellular automata (CA) changes the current tile based on the meta data of its surrounding tiles. In this case, CA takes the weights of all surrounding tiles and averages them together. If the average is within the ratio of a tiletype, that tile becomes that new tiletype.
Find Bodies of Water and Start Water Automata
|
|
|
|
Bodies of water are any sections where three or more water tiles are connected. These water tile then become river tiles which are each given a random flow direction. Each river tile has a starting strength (equal to its weight) that adds to other river tiles it collides into. A river's strength is reduced when it collides with a stone, gravel, or grass tile. Each tile reduces the strength by its waterThreshold. If the river has strength remaining, it will replace that tile with a water tile and continue flowing in that direction.
Add Border and Perform Final Cellular Automata Step
|
|
The water steps leave behind rather stringy bodies of water. Performing one last CA step will fill things out while solidifying the rest of the map. A stone border can be added to the edges.
Check for Isolated Rooms, Seal Small Rooms, and Connect Remaining Rooms
|
|
|
Isolated rooms are areas of non-solid (or non-water) tiles that are not connected with other areas of non-solid tiles. The reddish tint shows the different rooms. Tiny holes in stone and water are sealed with stone and water as they are too small to be considered rooms. Each room is then connected to a nearby room by the smallest gap between them.
Putting it All Together
The data in this XML document influences what the program does from start to finish when putting all the steps together. This influences the size of the world, how many cellular automata steps are done, and how many river automata steps are done. Other custom options include sealing the map with a border of stone walls, connecting isolated rooms, and filling in tiny enclosed rooms.
This will perform all but one of the listed cellular automata steps before performing the river automata steps. Then, the final cellular automata step fills out the rest of the map.
This will perform all but one of the listed cellular automata steps before performing the river automata steps. Then, the final cellular automata step fills out the rest of the map.
Code Behind Cellular Automata Steps
AlteredMaps contains all the updated tile data to refresh the world with. The averageTileTypeValues keeps track of the total amount of weight is within this 3x3 tile area and numberOfSurroundingTiles is used to turn averageTileTypeValues into the average weight for that area.
The borderingTiles is just a way to for loop through all the surrounding tiles without producing a bunch of repeated code. For these cellular automata passes, it includes the current tile as part of the average as well, totaling up to nine tiles being averaged for each tile position.
The borderingTiles is just a way to for loop through all the surrounding tiles without producing a bunch of repeated code. For these cellular automata passes, it includes the current tile as part of the average as well, totaling up to nine tiles being averaged for each tile position.
This is getting the average weight for the tiles around the current index.
Once an average is produced, the function cycles through all available TileBlueprints and finds what tile ratio matches the average weight. It then takes that TileBlueprint and pushes it onto alteredMaps to be pushed to the world map later.
The previous steps repeat for every tile in the map before pushing all the new TileBlueprints from alteredMaps onto the world map. This completes one cellular automata step.
Code Behind River Automata Steps
Much like with the CellularAutomataPass(), this water specific pass uses an alteredMap to keep track of changes. Rivers do not go diagonal so the borderingTiles consist only of the four primary directions (up, down, left, right). The function still cycles through every tile in the map but will only act on river tiles.
If the current tile is a river, it will immediately check the borderingTile that is in the same direction as the river tile's flowDirection. If the checked tile is another river, it adds its own m_tileTypeValue (listed as weight in the XML document) to the borderingTile and takes the borderingTile's new flow direction. If it is water, it turns that tile into a river, matching all the stats of the current tile.
The other tile types also turn into a river tile but will only take a portion of the current river tile's weight, weakening the river with every land/stone tile it forces its way through. This can only happen if the current river tile's weight is greater than or equal to the borderingTile's waterThreshold. Stone has the highest threshold while grass has the lowest.
The other tile types also turn into a river tile but will only take a portion of the current river tile's weight, weakening the river with every land/stone tile it forces its way through. This can only happen if the current river tile's weight is greater than or equal to the borderingTile's waterThreshold. Stone has the highest threshold while grass has the lowest.
If the river runs into a land/stone tile and cannot beat its waterThreshold, it will try to flow in a perpendicular direction. The direction is chosen randomly. If it cannot beat the new tile's waterThreshold, it will try the other direction. If still cannot flow anywhere, the river tile stops expanding.
New tile data is pushed onto alteredMap.
The world tiles are updated with either new water or river tiles. River tiles will have a flowDirection and a riverWeight that affects where they flow for future river automata steps.
