Grid Based Procedural Level Generator
A room-oriented, tile-based, procedural level generator that creates rooms and hallways according to a set of parameters to avoid unnatural looking occurrences while allowing, but not mandating, interesting and unusual scenarios.
For my 3rd year project I wrote a tile based, procedural level generator. The overall concept was that it would create hallways between six and twelve tiles long which would terminate in a small room. This room would then have up to three more hallways leading out of it. The hallways could intersect but there must be three tiles on either side of the intersection before a room was reached, this rule was designed to prevent unnatural halls just outside of a room. Hallways are also not allowed to run alongside each other which would create double-width hallways, they may touch rooms, however, but this will immediately terminate the hallway so that it looks like it should be there rather than running through the room.
Conceptually, the algorithm had a two dimensional grid of tiles in which it would randomly pick a starting point and create a room. It would then decide what direction to start and would generate a hall of six to twelve tiles long, terminating in another room (this means that the player always starts in a dead end with one initial direction to move in). Now the algorithm decides for the remaining cardinal directions whether or not to make a hallway and if so create one six to twelve tiles long. The algorithm follows a depth first approach to generation so that there will not be an exponential increase in remaining work as it got further through the generation.
Two of the techniques I used in the creation of the algorithm were:
- Using a 2D array of thirty two bytes in 256 rows to represent the 256x256 grid that would be the level, each 32 bytes was a row and each bit in a byte was a Boolean value representing whether that tile was open or closed.
- An undirected, possibly cyclical, graph data-structure that kept track of the rooms and hallways being generated by the algorithm. This allowed for traversal of the graph in any direction and kept track of which nodes had been visited when deleting the data-structure which also uses a depth first approach but must not get caught in a loop.