Angband.oook.cz
Angband.oook.cz
AboutDownloadVariantsLadderForumCompetitionSpoilersComicScreenshotsFunniesLinks

Go Back   Angband Forums > Angband > Variants

Reply
 
Thread Tools Display Modes
Old August 28, 2008, 17:44   #1
RogerN
Swordsman
 
RogerN's Avatar
 
Join Date: Jul 2008
Posts: 305
RogerN is on a distinguished road
Over-engineering dungeon generation

I've been working on a new variant (yeah, I'll probably never finish it) and I decided to overhaul the dungeon generation code a bit. I'm sure my techniques are overly-complicated, inefficient, and generally involve more programming work than necessary... but I rather like the results so far.

A few quick notes:
- I'm using the SAngband character set at the moment, mostly because I liked the doors
- I'm writing everything in C# because I'm a lazy bum who doesn't like to deal with memory allocation issues
- I've only implemented a handful of basic room types. It's very easy to add other types of rooms later, though.

Here's a quick preview of the dungeon generation output.

So why did I even bother writing a new dungeon generator?
1. IMO it's actually a very fun and interesting programming exercise
2. I wanted to be able to cram more rooms into a smaller space
3. I didn't like the Angband-style corridors; they meander a little too much for my taste

From here I'll just describe the techniques I'm using. Feel free to tell me that I'm going about this all wrong

Step 1: Make a random list of rooms

At this point I don't worry about drawing rooms on the map or even deciding where they go. I just randomly create a list of 30-40 rooms with defined sizes.

Step 2: Room placement

I start placing the rooms by putting the 1st room in the center of the dungeon. The remaining rooms are distributed by essentially playing Tetris

At each step, the algorithm considers the dungeon from a different direction: from above, left, right, or below. It really does play a form of Tetris at this point. It looks for the deepest hole into which it can slide one of the remaining rooms. The room is then placed into the hole, leaving 1-4 tiles as a buffer.

We keep going until we run out of rooms or the Tetris algorithm has failed to work from every direction.

Step 3: Which rooms should be connected?

Now Angband just connects rooms randomly. It might (and frequently does) try to connect rooms on opposite sides of the map, and it doesn't care if the rooms between get turned into swiss cheese.

Instead of random connections, I decided to use delaunay triangulation of the room coordinates. The resulting triangle edges form a pool of room connections that I construct the tunnels from. Not all of the triangle edges are used to make tunnels (that would make too many tunnels), but the triangulation ensures that tunnels are frequently drawn between neighboring rooms.

From the edges that were obtained during the triangulation I construct a minimum spanning tree; this ensures that there are no disconnected regions of the dungeon. I use approximately 30% of the remaining edges to make additional tunnels, so that there are multiple paths between rooms.

Step 4: Drawing tunnels

Sometimes I like Angband tunnels, and sometimes they're totally crazy. They can move in and out of the same room multiple times, bend back on themselves, and generally behave in a very illogical fashion.

I wanted my tunnels to be a little less erratic: more straight (on average), but with a few bends to add flavor and tactical complexity to the dungeon. I settled on using the A* pathfinding algorithm, with the following additional considerations:

- Similar to Angband, tunnels into and out of rooms are only allowed in certain areas. We don't allow the pathfinder to move through certain types of rock.

- The pathfinder incurs a cost penalty whenever the tunnel makes a turn. This forces it to prefer straight sections

- I'm using Perlin noise in order to define invisible regions of "hard" rock. The pathfinder incurs a penalty for trying to move through hard areas. This prevents our tunnels from being completely straight.

- It's cheaper to move through existing tunnels. Therefore the pathfinder will prefer to meet up with an existing tunnel whenever possible, creating intersections

- Some of the tunnel intersections are artificial. One of the random "room" types is actually just a solid block of granite, but it still gets considered as a room when everything is connected. So when adjacent rooms gets connected to it it appears to be a natural tunnel intersection. This also causes occasional dead-end tunnels which are great for staircase placement.
RogerN is offline   Reply With Quote
Old August 28, 2008, 21:22   #2
Antoine
Ironband/Quickband Maintainer
 
Join Date: Nov 2007
Posts: 843
Antoine is on a distinguished road
Quote:
Originally Posted by RogerN View Post
I've been working on a new variant (yeah, I'll probably never finish it) and I decided to overhaul the dungeon generation code a bit. I'm sure my techniques are overly-complicated, inefficient, and generally involve more programming work than necessary... but I rather like the results so far.
It's looking good already!

Remember a dungeon does not consist only of rooms and corridors. If you can think of innovative ways of placing monsters, objects and other features, it will be a good thing.

A.
__________________
Ironband - http://angband.oook.cz/ironband/
Antoine is offline   Reply With Quote
Old August 28, 2008, 22:55   #3
andrewdoull
Unangband maintainer
 
andrewdoull's Avatar
 
Join Date: Apr 2007
Location: Sydney, Australia
Age: 39
Posts: 871
andrewdoull is on a distinguished road
Quote:
Originally Posted by RogerN View Post
Some of the tunnel intersections are artificial. One of the random "room" types is actually just a solid block of granite, but it still gets considered as a room when everything is connected. So when adjacent rooms gets connected to it it appears to be a natural tunnel intersection. This also causes occasional dead-end tunnels which are great for staircase placement.
Nice hack rendered problematic by the original Angband tunnelling code as it doesn't tunnel the first grid. Obviously you've avoided that particular issue here.

That's quite a few rooms you've managed to pack into the level. What's the average room count per level (including or excluding 'room junctions')?

Also, what's the line count for the implementation?

Andrew
__________________
The Roflwtfzomgbbq Quylthulg summons L33t Paladins -more-
In UnAngband, the level dives you.
ASCII Dreams: http://roguelikedeveloper.blogspot.com
Unangband: http://unangband.blogspot.com
andrewdoull is offline   Reply With Quote
Old August 29, 2008, 01:53   #4
Nick
FAangband maintainer
 
Nick's Avatar
 
Join Date: Apr 2007
Location: Canberra, Australia
Age: 49
Posts: 4,322
Donated: $60
Nick is on a distinguished road
This is very cool. I'm looking at revamping level generation for FAangband in the next version, so thanks for giving me some stuff to think about.
__________________
One Ring to rule them all, One Ring to find them,
One Ring to bring them all and in the darkness bind them.
Nick is offline   Reply With Quote
Old August 29, 2008, 02:53   #5
RogerN
Swordsman
 
RogerN's Avatar
 
Join Date: Jul 2008
Posts: 305
RogerN is on a distinguished road
Quote:
That's quite a few rooms you've managed to pack into the level. What's the average room count per level
Right now I'm only trying to create 40 rooms max. Since they're packed pretty tight I'm using a smaller overall dungeon size than Angband. However, if I expand the dungeon to full Angband size (198 x 66) then I can usually cram 90 rooms inside, including intersections.

Of course it varies a bit depending on the sizes of the rooms. The number might shrink as I add larger room types.

Quote:
Also, what's the line count for the implementation?
That's also difficult to say since I'm reusing a lot of code. The triangulation code came from here , while the A* code and the perlin noise generator were borrowed from another one of my (failed) projects.

Excluding the reused bits, the amount of new code (not ported directly from Angband) is probably about 300 lines. That count also excludes the code for picking room types, etc... That's C# code, though, so if the implementation were ported back into C then it would probably grow.
RogerN is offline   Reply With Quote
Old August 29, 2008, 15:55   #6
takkaria
Veteran
 
takkaria's Avatar
 
Join Date: Apr 2007
Posts: 1,596
Donated: $40
takkaria is on a distinguished road
Nice dungeon, though I'd suggest that smaller levels than Angband uses at present are pretty much a good thing. (It used to be that dungeons would be much more size-variable than they are now.)

Quote:
Originally Posted by RogerN View Post
- I'm using Perlin noise in order to define invisible regions of "hard" rock. The pathfinder incurs a penalty for trying to move through hard areas. This prevents our tunnels from being completely straight.
Hmm. Try placing streamers of quartz/magma/hard rock/whatever through the dungeon before generating any rooms, and then tweak the pathfinder to avoid those rather than using a noise function, maybe? I dunno what the results would be like, but it would reduce work if you're planning to have streamers anyway and results in some nice internal consistency.
takkaria is offline   Reply With Quote
Old August 29, 2008, 18:01   #7
darkdrone
Apprentice
 
darkdrone's Avatar
 
Join Date: Apr 2007
Posts: 68
darkdrone is on a distinguished road
good work !

i've been always meaning to do a Dungeon Generator in C# , but somehow my line of work doesnt offer too many opportunities...

or the time to!

would like to look at that code there sometime !
__________________
"When you look into an abyss, the abyss also looks into you." - Friedrich Nietzsche.
(does this mean the RNG learns my worst fears, mummy?)
darkdrone is offline   Reply With Quote
Old August 29, 2008, 19:47   #8
RogerN
Swordsman
 
RogerN's Avatar
 
Join Date: Jul 2008
Posts: 305
RogerN is on a distinguished road
Quote:
Originally Posted by takkaria View Post
Try placing streamers of quartz/magma/hard rock/whatever through the dungeon before generating any rooms, and then tweak the pathfinder to avoid those rather than using a noise function, maybe?
Using the streamers was my actually my first idea for improving the tunnels. Unfortunately the effects weren't all that great. I think there are a couple of reasons why:

- There's only a couple of streamers per level, so most of the tunnels are unaffected by them

- Streamers are usually very long. The pathfinder just ignores them most of the time because crossing the streamer is inevitable. There's no benefit in trying to avoid it.

But using perlin noise isn't much of a hassle. Since I already had the perlin noise function lying around, it was only 4 or 5 lines of code to tweak the pathfinder.

Quote:
would like to look at that code there sometime !
I'll post it when I get a chance. There's very little functionality, though, other than dungeon generation. You can walk around, open doors, etc... but there are no monsters yet.
RogerN is offline   Reply With Quote
Old August 29, 2008, 20:54   #9
Mangojuice
Z+Angband Maintainer
 
Join Date: Jun 2008
Posts: 318
Mangojuice is on a distinguished road
Quote:
Originally Posted by RogerN View Post
I'll post it when I get a chance. There's very little functionality, though, other than dungeon generation. You can walk around, open doors, etc... but there are no monsters yet.
I'll look forward to that, too. In my variant, Z+Angband, certain quests take place in "castles" that are meant to be densely packed with rooms. I'm really not so happy with the way they look right now... but the kind of well-packed dungeon your code creates would be great! I'm filling up a square region by recursively dividing a rectangle in two.. and it gets a little dull.

Of course, I maybe don't need the code. If I have to port it back to C anyway, I might as well just implement the algorithm myself.
__________________
-----------------------------------------
Z+Angband: A Zangband evolution
http://tinyurl.com/5pq2bd
Mangojuice is offline   Reply With Quote
Old August 30, 2008, 01:32   #10
RogerN
Swordsman
 
RogerN's Avatar
 
Join Date: Jul 2008
Posts: 305
RogerN is on a distinguished road
I've posted the source code for anyone who's interested in playing with it. It's well-documented (for me at least). Just a couple of notes:

- I'm using Visual C# Express 2005. But the code should also compile in VS 2008.

- If you want to explore the dungeon properly then you might consider modifying the CreateRandomDoor function so that it only creates open doors. I haven't implemented lock-picking or searching for secret doors, so you might get stuck otherwise.
RogerN is offline   Reply With Quote
Reply


Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump

Similar Threads
Thread Thread Starter Forum Replies Last Post
getting past dungeon level 14 Blackleaf Vanilla 6 August 8, 2008 09:14
[FA] Found a dungeon chris28 Variants 6 June 4, 2008 22:00
Dungeon window size Bodkin Vanilla 2 March 30, 2008 04:48
Edit File For Dungeon Generation? Zero Vanilla 3 January 9, 2008 18:17
Dungeon Size ? lugonn Vanilla 5 September 2, 2007 12:11


All times are GMT +1. The time now is 03:30.


Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2014, vBulletin Solutions, Inc.