Author Topic: Messing with dungeon generation  (Read 74540 times)

Robson

  • Newcomer
  • Posts: 34
  • Karma: +0/-0
    • View Profile
Messing with dungeon generation
« on: September 17, 2007, 12:16:30 AM »
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

  • Newcomer
  • Posts: 3
  • Karma: +0/-0
    • View Profile
    • Email
Re: Messing with dungeon generation
« Reply #1 on: September 17, 2007, 04:42:05 AM »
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

  • Creator of Roguetemple
  • Administrator
  • Rogueliker
  • *****
  • Posts: 1203
  • Karma: +4/-1
    • View Profile
    • Slashie.net
    • Email
Re: Messing with dungeon generation
« Reply #2 on: September 20, 2007, 02:30:57 PM »
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 :D

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

Robson

  • Newcomer
  • Posts: 34
  • Karma: +0/-0
    • View Profile
Re: Messing with dungeon generation
« Reply #3 on: September 20, 2007, 07:30:52 PM »
That dungeon generator looks pretty cool!
Thanks Slash!

Quote from: 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.

Quote from: Slash
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 :)

Quote from: Slash
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 :D

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

Quote from: Slash
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!

Quote from: Slash
English gentlemen seem to be pretty profficient on dungeon generation ;)
Aye, it's going to replace received-pronunciation as the number one English stereotype :P
« Last Edit: September 24, 2007, 09:24:20 PM by Slash »

corremn

  • Rogueliker
  • ***
  • Posts: 700
  • Karma: +0/-0
  • SewerJack Extraordinaire
    • View Profile
    • Demise RogueLike Games
Re: Messing with dungeon generation
« Reply #4 on: September 21, 2007, 02:39:15 AM »
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 ;D. 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.
corremn's Roguelikes. To admit defeat is to blaspheme against the Emperor.  Warhammer 40000 the Roguelike

Ex

  • IRC Communications Delegate
  • Rogueliker
  • ***
  • Posts: 313
  • Karma: +0/-0
    • View Profile
Re: Messing with dungeon generation
« Reply #5 on: September 21, 2007, 05:12:04 PM »
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

  • Newcomer
  • Posts: 34
  • Karma: +0/-0
    • View Profile
Re: Messing with dungeon generation
« Reply #6 on: September 21, 2007, 07:17:01 PM »
One of my ideas is to build everything completely seperately
Eeek, this way madness lies, just joking ;D. 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

  • Creator of Roguetemple
  • Administrator
  • Rogueliker
  • *****
  • Posts: 1203
  • Karma: +4/-1
    • View Profile
    • Slashie.net
    • Email
Re: Messing with dungeon generation
« Reply #7 on: September 24, 2007, 09:23:26 PM »
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

  • Newcomer
  • Posts: 34
  • Karma: +0/-0
    • View Profile
Re: Messing with dungeon generation
« Reply #8 on: September 25, 2007, 05:59:38 PM »
Quote from: Slash
Quote from: Icey
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.

Quote from: Slash
Quote from: Icey
I'll make them a bit rounder at some point :)
They look cool like this :)
Cool. Maybe I'll include both... oh the possibilities!

Quote from: Slash
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 :P

Quote from: Slash
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

  • Creator of Roguetemple
  • Administrator
  • Rogueliker
  • *****
  • Posts: 1203
  • Karma: +4/-1
    • View Profile
    • Slashie.net
    • Email
Re: Messing with dungeon generation
« Reply #9 on: September 26, 2007, 06:30:23 PM »
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 :P
Hehe

Krice

  • (Banned)
  • Rogueliker
  • ***
  • Posts: 2316
  • Karma: +0/-2
    • View Profile
    • Email
Re: Messing with dungeon generation
« Reply #10 on: October 21, 2007, 08:28:04 PM »
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

  • IRC Communications Delegate
  • Rogueliker
  • ***
  • Posts: 313
  • Karma: +0/-0
    • View Profile
Re: Messing with dungeon generation
« Reply #11 on: October 22, 2007, 11:18:22 AM »
Quote
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

  • Newcomer
  • Posts: 17
  • Karma: +0/-0
  • haw
    • MSN Messenger - winkerbeam@hotmail.com
    • AOL Instant Messenger - robotscomputers
    • View Profile
    • justinpoliey.com
Re: Messing with dungeon generation
« Reply #12 on: October 23, 2007, 04:32:10 PM »
Icey, image #9 looks really good. I hope I'll get to play in something like it at some point

valianjuan

  • Newcomer
  • Posts: 27
  • Karma: +0/-0
    • View Profile
    • Beggar
Re: Messing with dungeon generation
« Reply #13 on: October 23, 2007, 05:46:42 PM »
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.
« Last Edit: October 23, 2007, 05:49:14 PM by valianjuan »

Slash

  • Creator of Roguetemple
  • Administrator
  • Rogueliker
  • *****
  • Posts: 1203
  • Karma: +4/-1
    • View Profile
    • Slashie.net
    • Email
Re: Messing with dungeon generation
« Reply #14 on: October 23, 2007, 06:57:40 PM »
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