Thursday, 12 July 2012

(Game Dev) Simple dungeon generator algorithm

I was thinking about creating a simple level generating algorithm, similar to what is made for The Binding of Isaac. If you are not familiar to The Binding of Isaac, the levels consists from rooms placed on a grid. There are different paths and special rooms. The level design is non-linear, so the main character can choose different paths to find the boss room, which is the end of the level.

My algorithm is not very efficient but it works. (so many loops, but it still generates larger maps in some milliseconds)

  1. Fill a 2D array with zeros (type: integer, 0 means nothing to place there)
  2. Set the place of the starting room (for example at [5,5])
  3. Select a random array element in this 2 dimensional array.
  4. If the selected element has a room next to it, make a room there! (fill the array element with not zero, I think different rooms will have different numbers, 0 will be the starter room where the player will spawn, 1 will be one room type, 2 will be an other,...)
  5. If there is no room next to the selected element, do step 3 again. We shouldn't make room if the selected empty place has 2 or more neighbours! This will make the level a little bit different (figure 1, 2nd image)
  6. Do it until we want: if we want 15 room we need to do step 3 until we have 15 rooms (don't forget, we already have a starter room!)

Dungeon Generation algorithm - two different setups:
2 different arrangements possible generated by the generator. Note that, the map on the right  is different, that algorithm doesn't make room if the selected element has more than 1 neighbor at generating.
What about marking rooms as a special room? Special rooms will be last rooms of a corridor. It means they have only one neighbour. It is easy to check if a room has one or more neighbors. I'll implement it soon, basically it will generate the level, then it will mark some rooms as "special".