Populating the Dungeon

(A lot of the work in this post is based off ideas introduced in this excellent blog post. I highly recommend reading it.)

Using the algorithm outlined in my previous post I have a dungeon generating, ensuring the chosen rooms are included and filling in the blanks with random rooms. The random rooms can be given an irregular shape by running one of multiple algorithms on them (At the moment the supported ones are Overlapping Rectangles, Starburst, Cellular Automata, Chambers. Credit to Unangband/Andrew Doull.)

So the output of this algorithm will look something like so:

As you can see it contains 2 vaults (one with a downward stair), and the rooms themselves are made more interesting by running them through the Cellular Automata algorithm. I feel that this map is now interesting enough in structure to begin to place enemies and etc.


To give the map a coherent feel I decided to not go for the 'random' approach to enemy placement, instead opting for a faction system. The idea is that each level should have a Major faction that dominates it, with a big boss sitting in one of the rooms. Every other room will then be influenced by this faction, based on its distance from the boss room. Some other minor factions can be sprinkled throughout the map to give some variety to the encounters.
Furthermore to give the rooms the feel of being owned by a faction (other than just the monsters you encounter in that room), a set of 'Features' can be placed in the room, based on the faction that owns it (for example the 'Fungi' faction will have glowing mushrooms, and the 'Toad' faction will have pools of water).

How the algorithm works is thus:

1. In the level definition a set of 'Major' factions and a set of 'Minor' factions are specified.
2.  Once the level has been generated a single 'Major' faction is selected. The largest room in the dungeon is then assigned this faction.
3. The furthest quarter of the rooms from this selected room are then assigned a random faction from the 'Minor' list.
4. All the remaining rooms are assigned an 'Influence' value based on their distance from the central room (minor faction rooms are assigned a random influence value).

Then for each room

First we look to place the features. Features can be assigned an influence range to appear within, a placement location that determines where they are placed (either FurthestFromEntrance, Wall, Centre or Any) and a Coverage percent (this determines what percentage of the valid tiles to cover with this feature).

1.  Seperate all floor tiles into 4 lists.
• A list of tiles sorted by average distance from the entrances (for FurthestFromEntrance).
• A list of the floor tiles that are adjacent to a wall (for Wall).
• A list of all the floor tiles that are not adjacent to a wall (for Centre).
• A list of all the floor tiles (for Any).
2. For each feature defined in the feature list.
• Check the feature is valid for this influence.
• Get the percentage through this features range ( (influence-min) / (max-min) )
• Multiply the coverage by this factor to get the coverage for this feature in this room.
• Calculate the number of features to place. (NumValidTiles * CurrentCoverage)
• Randomly pick tiles from the valid list and place the feature on this tile (remember to remove the tile from all the lists after using it).

This will leave a room filled with features for the faction. However there is no guarantee the new features havent blocked off the entrances, so to prevent this I try to path (using A*) between each pair of entrances, clearing features that block the route.

Now it is time to place the enemies. The faction definition contains a list of encounters (groups of monsters to spawn together), and the min/max influence they appear at. I then randomly pick a valid encounter for the rooms influence, and place the enemies on randomly selected floor tiles. (This part of the algorithm needs work, possibly by basing the number of spawned enemies off of the room size).

So at the end of all this you should be left with something like so:

This is the same level as before, but with the features added and enemies spawned. The major faction is the 'Fungi' faction and the 4 minor factions placed are all 'Toad' factions.

A quick picture of a dungeon being explored:

Another Before/After: