I'm having difficult deciding on how to procedurally generate a dungeon floor. The way I've been doing it so far is like so:

  • Populate list of Rooms with random height and width.
  • Place first room in list at (0, 0).
  • Add room to a temporary list of rooms that have been successfully placed.
  • Place next room adjacent to a room randomly chosen from the aforementioned temporary list
  • Keep repeating previous step until room is successfully placed then move onto the next room.
  • Repeat the two previous steps until all rooms have been placed.

After that the doorways between the rooms are created and various steps are taken to assure collision is working properly but my question is this: Why does it appear to be common practice to first create a large area of cells that all are 'filled in' and to then 'carve out' rooms and corridors rather than to generate dungeons my way? I'm not saying my way is better, I would be happy for someone to tell me what I'm doing wrong and why I should be doing it differently. I just find my way easier for managing the various rooms and cells within my dungeon. It also means I don't have a bunch of 'useless' cells on the other side of the dungeon walls doing nothing but hogging processing power - that's something I never understood.

I just want to a way of generating a dungeon which balances efficiency and design.

  • there is no "best way" to do this. What you use is entirely dependent on the details of your game. – Almo Oct 21 '15 at 17:21
  • define "details"? I am trying to create a dungeon in which a hero crawls through killing monsters finding loot and delving deeper into said dungeon. It is my first dungeon crawler game I'm trying to create so the details are sort of being made as I go along. I want a dungeon floor that has individual rooms that only show up on the map when discovered so they will have to be individual entities. Some rooms may have locked doors. – ImperialCoder Oct 21 '15 at 17:25
  • 1
    Here's an example of game that procedurally generates its dungeons, but you can see they have a LOT of different types. Maybe some or others of these are suitible for your game. That depends on a lot of factors of your design. crawl.develz.org/wiki/… – Almo Oct 21 '15 at 17:32
  • Wow, some of those are amazing. My dungeons typically end up being a collaboration of square rooms next to each other, and my algorithm can't even create a dungeon with multiple paths (i.e.: there is only one way to get from room A to room B) – ImperialCoder Oct 21 '15 at 17:38
  • 1
    @Roflo - Thanks for that, although I'm not having too much trouble connecting my rooms (although that was the hardest part of developing my algorithm). It's more just deciding how to go about it that II was having a hard time doing. However the trouble now lies with making a better generator. – ImperialCoder Oct 21 '15 at 22:57
up vote 3 down vote accepted

If it's easy for you, keep to it. No one says you have to do it a certain way, or that yours is wrong.

The reason it's typically done this way - subtractively or as you aptly put it, "carved" - is most likely due to the influence of roguelikes, which were arguably some of the first games to generate dungeons. In roguelikes the player can tunnel anywhere within the level's rectangular space, so every cell, even if not initially walkable, is recorded as a tile in the map, in case it becomes walkable later. Thus, tiles may as well all start out as closed spaces with the potential to be opened.

Another genre very often associated with tilemaps is the RTS, where most ground is open by default, and in which it thus makes sense to simply generate the map as all open tiles. Overland RPGs are similar in this regard. So this is certainly another influence on the typical approach.

Your approach better suits a game in an indoor space where no dynamic tunnelling will occur, i.e. once the level's rooms have been created, they will always remain the same. Obviously then we can have various very small 2D arrays each representing a room's tiles, and these can be connected in graph-fashion. This is far more memory-efficient, but again, tunnelling in the large spaces between room bounds is, if not impossible, then harder to achieve (at least, you would need to create new nodes in your graph of rooms, and allocation may not be intuitive since you don't know how wide/high the room in question will ultimately be). Memory is hardly an issue for most game levels, given the low cost per tile and the memory we have available these days (gigabytes).

This is informative in terms of the sheer number of different approaches to maze generation.

  • Thanks that pretty much cleared up all of my doubts! I kn ow memory will never really be an issue, I just like to have nice efficient code that uses as little memory as possible. I personally have never played a classic rogue-like (with the perma-death and tunnelling feature and stuff) so this explains a lot for me. Thank you :) – ImperialCoder Oct 21 '15 at 19:28
  • @CompleteNoob You're welcome, good luck :) – Arcane Engineer Oct 21 '15 at 19:30

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.