Grid Based Procedural Level Generator bsc compsci gamedev
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 weird occurrences. 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 which it would randomly pick a starting point in 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.
- A two-dimensional, doubly-linked, jagged, 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.
This project evolved into what I am now using for the dungeon generation in the game I am currently working on.