Messing with dungeon generation

[Robson]

I've been working on a dungeon generator, so I thought I'd share what I've done so far.

Here's a load of examples.
Here's a screenshot of the application.

Most of the examples are intentionally far bigger than I would use in a real game, because it's easier for me to test with larger maps and more stuff can be seen.

It's written in Visual Basic 6 in about 1,500 lines of code. The steps go like this:

1. Generate a perfect maze, which is a maze where every square can reach every other, with no loops. (image)
2. Depending on the size of the area, we may allocate some large spaces for mazes, caves or prisons. The bigger the area, the higher than chance of more being created. (image)
3. Overlay lots of rooms. 10% are circular. 90% are rectangular. Rectangular rooms may have additional bits carved out of the corners of them to make them less boring. (image)
4. All dead ends are removed. (image)
5. Doors are added everywhere that a corridor meets a room. (image)
6. Any corridors that loop back to the room they exited from are removed. (image)
7. If two rooms have multiple non-intersecting corridors between them, all but one is removed. (image)
8. The contents of the special rooms is created. (image)
9. Corridors are shortened. (image)

The basic code is almost complete, except for two things. The first is that only some corridors get shortened. Intersection-to-intersection and intersection-to-cave corridors aren't shortened yet, because the shortening code uses doors to find the corridors. The second is that the flood fill code needs to be rewritten from the first method here to one of the others.

Once the dungeon generator is done and optimised, I can work out the purpose of each room (wizards lab, barracks, food store, shop, creature lair, etc). Then I just need to make the creatures, magic, items, combat, high scores, inventory, gods, interface, minimap, quickbar, skills, conducts, ai, difficulty levels, harvesting, story...

[edexter]

that could be realy intresting as a command like tool to make it program independent...  I am writing something to take a maze from disk and load it into a 2d array...  checking for varous items like # exc... when I place monsters exc..

[Slash]

That dungeon generator looks pretty cool! results are neither completely organic nor blocky... how are you generating cave rooms? are they templates, CA or L jumps? also, I didnt see the circular rooms in the example image?

My current approach to dungeon generation is completely different, classic room carving, which has many problems including tree-like levels without loops, no branches in corridors for now... a start is a start though.. Up to now I have done mostly cave-like levels and overworlds, which generation follows very different principles than dungeon carving

Is this for Paprika? English gentlemen seem to be pretty profficient on dungeon generation

[Robson]

That dungeon generator looks pretty cool!

Thanks Slash!

results are neither completely organic nor blocky... how are you generating cave rooms? are they templates, CA or L jumps?

I used this excellent cellular automata tutorial: http://www.pixelenvy.ca/wa/ca_cave.html I haven't tried L jumps, I'll have to give that a try to see what it looks like.

also, I didnt see the circular rooms in the example image?

Ha! "Circular" is a bit of an exaggeration! They are sort of circles made of squares. Like this:

    #####
    #...#
  ###...###
  #.......#
###.......###
+...........#
#...........#
#...........#
###.......###
  #.......#
  ###...#+#
    #...#
    #####    

I'll make them a bit rounder at some point

My current approach to dungeon generation is completely different, classic room carving, which has many problems including tree-like levels without loops, no branches in corridors for now... a start is a start though.. Up to now I have done mostly cave-like levels and overworlds, which generation follows very different principles than dungeon carving

I really like your map/overworld generator. Very cool.

Is this for Paprika?

I've been planning a new roguelike to replace Paprika. I learnt a lot from writing Paprika, so I feel with that knowledge I can create a better roguelike. I really want to change a lot of fundamental things, so a new project seems to be the best way to go. I'm not calling it a rewrite, because I want to change a lot of ways that the game would work, rather than the code. In fact, I can use a lot of the code from Paprika in the new project.

One of my ideas is to build everything completely seperately, because I feel that the connections between all the different systems is where things quickly get complicated. So building things seperately allows me to avoid that and really focus on each one. It doesn't matter too much if I change my mind about something, because it's a lot easier to rewrite one system than one system connected to a lot of other ones. This dungeon generator is one of those systems.

But I won't go on too much, because I don't want to sound like another vapourware creator!

English gentlemen seem to be pretty profficient on dungeon generation

Aye, it's going to replace received-pronunciation as the number one English stereotype

[corremn]

One of my ideas is to build everything completely seperately, because I feel that the connections between all the different systems is where things quickly get complicated. So building things seperately allows me to avoid that and really focus on each one. It doesn't matter too much if I change my mind about something, because it's a lot easier to rewrite one system than one system connected to a lot of other ones. This dungeon generator is one of those systems.

Eeek, this way madness lies, just joking . This is one of the first things any programmer says to himself, it is much easier said that done.  Time to get the sketch pad out and start drawing how your modules will interact, try to think about every way needed.  Good luck with this, I hope it goes well.

[Ex]

How are you deciding on the initial locations to place your rooms? Are you dividing the map initially into sections based on some algorithm, or are your rooms placed by other means? If you don't mind my curiosity.

[Robson]

One of my ideas is to build everything completely seperately

Eeek, this way madness lies, just joking . This is one of the first things any programmer says to himself, it is much easier said that done.  Time to get the sketch pad out and start drawing how your modules will interact, try to think about every way needed.  Good luck with this, I hope it goes well.

Thanks for the advice corremn. I've written a load of stuff about how I want the game to work, but haven't put too much thought into the code yet. I'm still in the designing stage really and just testing code out for now. I'll do your sketch pad idea when the designing is finished

How are you deciding on the initial locations to place your rooms? Are you dividing the map initially into sections based on some algorithm, or are your rooms placed by other means? If you don't mind my curiosity.

I welcome the curiousity, that's why I posted about this

The locations are decided quite simply really. I select a random height and width, which must be an odd number from 3 to 7. Then a random tile is selected from the whole area. A check is made to see if it would overlap with another room. If not, the rectangular room is created. After that a random number of corners are also removed to create more interestingly shaped rooms. When enough rooms have been created, the generating moves along to the next bit.

This part of the code is very fast, the biggest layouts on the examples page take less than 0.02 seconds to select all the locations and create the rooms.

[Slash]

I used this excellent cellular automata tutorial: http://www.pixelenvy.ca/wa/ca_cave.html I haven't tried L jumps, I'll have to give that a try to see what it looks like.

Ah! I remember the Wa project... a shame it seems to be dead now... IIRC it was one of the few to be developed by a female roguedev

I'll make them a bit rounder at some point

They look cool like this

I've been planning a new roguelike to replace Paprika. I learnt a lot from writing Paprika, so I feel with that knowledge I can create a better roguelike. I really want to change a lot of fundamental things, so a new project seems to be the best way to go. I'm not calling it a rewrite, because I want to change a lot of ways that the game would work, rather than the code. In fact, I can use a lot of the code from Paprika in the new project.

Yeah, I know how that feels... I hope being able to restart Guardian Angel soon with all I have learned with the rest of projects! (But I won't go on too much, because I don't want to sound like another vapourware creator!)

One of my ideas is to build everything completely seperately, because I feel that the connections between all the different systems is where things quickly get complicated. So building things seperately allows me to avoid that and really focus on each one. It doesn't matter too much if I change my mind about something, because it's a lot easier to rewrite one system than one system connected to a lot of other ones. This dungeon generator is one of those systems.

Ah, thats true... as long as you keep your heading into your GAME direction, and not a generic engine

[Robson]

I used this excellent cellular automata tutorial: http://www.pixelenvy.ca/wa/ca_cave.html I haven't tried L jumps, I'll have to give that a try to see what it looks like.

Ah! I remember the Wa project... a shame it seems to be dead now... IIRC it was one of the few to be developed by a female roguedev

Aye, that's a shame. A little bit more diversity would have been cool.

I had a go with the L jumps though:
http://iceyboard.no-ip.org/stuff/dungeons_l_caves.html

The results are interesting and look different to the CA method. I think I'll include both the cellular-automata generator and the l-jump generator, with a 50/50 chance of each being used.

I'll make them a bit rounder at some point

They look cool like this

Cool. Maybe I'll include both... oh the possibilities!

I hope being able to restart Guardian Angel soon with all I have learned with the rest of projects! (But I won't go on too much, because I don't want to sound like another vapourware creator!)

Heh that sounds like something I'd say! Oh, wait a minute...

I think that's a great idea though. I'm always seeing people talk about your roguelikes, so adding another one will ensure they never shut up

Ah, thats true... as long as you keep your heading into your GAME direction, and not a generic engine

Oh yes. Most definitely. I'm not interesting in making an engine.

[Slash]

I had a go with the L jumps though:
http://iceyboard.no-ip.org/stuff/dungeons_l_caves.html

The results are interesting and look different to the CA method. I think I'll include both the cellular-automata generator and the l-jump generator, with a 50/50 chance of each being used.

Yeah, they look much less organic while still being irregular... perhaps would be nice for some kind of "crystal" caves or erosion-less environment.

I think that's a great idea though. I'm always seeing people talk about your roguelikes, so adding another one will ensure they never shut up

Hehe

[Krice]

My approach to dungeon generation is quite similar to what Icey has. At the moment I'm re-factoring corridor routine so that it can handle connections to what I call "strict" rooms (that don't overlap with other rooms or structures) and cave style overlapping rooms. Previously I had problems how to accurately find walls from irregular rooms, but then I made a mask map and marked rooms with different directions and also corners.

I have an example pic to show (a mask map of level). It has three types of rooms: irregular rooms which some of them overlap with each other creating bigger areas, and "strict" rectangular rooms plus small rooms which attach themselves directly to other rooms and corridors. There are no corridors yet, because the old routine can't handle connections between different types of rooms...

http://koti.mbnet.fi/paulkp/temp/rooms.gif

[Ex]

I have an example pic to show (a mask map of level). It has three types of rooms: irregular rooms which some of them overlap with each other creating bigger areas, and "strict" rectangular rooms plus small rooms which attach themselves directly to other rooms and corridors. There are no corridors yet, because the old routine can't handle connections between different types of rooms...

http://koti.mbnet.fi/paulkp/temp/rooms.gif

That looks really good.

[beam]

Icey, image #9 looks really good. I hope I'll get to play in something like it at some point

[valianjuan]

These are nice!  I like the variety!
So far I have a simple but effective algorithm.

Make the grid entirely unwalkable.
Check the grid area's size, and choose how many rooms you want to put in.
For each room:
  make a room at a valid random point (save the point)
  Connect point 1 to 2, 2 to 3, etc..., n to 1

Now you have rooms all over that are all connected.  You can change what your rooms look like or the connection algorithm that makes the tunnel.  And everything is filled. (in case you want tunneling or something...

I suppose if I wanted tunnels to split, I could change the algorithm to do that too.

[Slash]

Icey, image #9 looks really good. I hope I'll get to play in something like it at some point

Just wear a bowler hat while programming long enough, you will eventually catch it