Basically this approach is what I'm going to do. Except the allotment will go bottom up, so largest (and rarest) features get placed first. Continuing on to smaller features. The final bit will be bog standard rectangular rooms. I'm going to start with these first and then start adding the special rooms.
I haven't decided whether to make an allocation table like this or go with my original idea of power/rarity ratings. The nice thing about the allocation tables is that you can set features that are more common at shallower depths like garrisons (places filled with kobolds, orcs, ogres or trolls).
Pyrel dungeon generation
Collapse
X
-
O has an approach 2 algorithm, with the added feature that there is a desired room type distribution for given depths (table indicates relative numbers), and a minimum depth certain types can occur:
IMHO it leads to really good dungeon levels.Code:Depth: 0 10 20 30 40 50 60 70 80 90 100 min Simple {{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 0}, Overlap {{ 60, 80, 100, 120, 140, 165, 180, 200, 220, 240, 260}, 1}, Cross {{ 0 25, 50, 70, 85, 100, 110, 120, 130, 140, 150}, 3}, Large {{ 0, 25, 50, 70, 85, 100, 110, 120, 130, 140, 150}, 3}, Pit {{ 0, 5, 12, 25, 30, 35, 38, 40, 40, 40, 40}, 5}, Chambers {{ 0, 2, 6, 12, 15, 18, 19, 20, 20, 20, 20}, 5}, I.Room {{ 50, 60, 70, 80, 80, 80, 80, 80, 80, 80, 80}, 0}, L.Vault {{ 0, 1, 4, 9, 16, 27, 40, 55, 70, 80, 90}, 5}, G.Vault {{ 0, 0, 1, 2, 3, 4, 6, 7, 8, 10, 12}, 20}, Huge {{ 0, 0, 0, 0, 4, 4, 4, 4, 4, 4, 4}, 41}Leave a comment:
-
In my experience generating rooms is simple. Connecting them with tunnels is the tricky part. Choosing #3 might save you lots of work later on...
Angband doesn't have checks to make sure that all the rooms are connected. It relies on generating lots and lots of random tunnels between the rooms. It succeeds almost always, but the resulting dungeons always have that distinct "Angband feel". If you want to have levels with different styles, you need to come up with another method.
I changed the dungeon style in Halls of Mist and had big problems with unconnected rooms. I got some ideas from Un that helped me hack together a working system. It's very ugly because I wasn't able to understand everything about the Un system.
Basically, Unangband rooms have "sections". If two rooms get connected by a tunnel, their sections are joined. Connecting the rooms can stop when they all have the same section number. (IIRC.)
If you want to play around with the Angband dungeon generation to create levels with a different look, you may want to tweak the lottery where all rooms are randomly paired with each other for tunnel building purposes. You can keep rerolling the room pairs until some predefined conditions are satisfied. For instance, you can degree that the paired rooms cannot be too far from each other. Tweaking the numbers here enabled me to create dungeon levels that satisfied me aesthetically.
(Written before reading the last two posts!)Leave a comment:
-
I'm not too worried about connectedness. The connectedness algorithm for Vanilla works fairly well and is not overly complicated. Plus it makes for an interesting tunnel pattern. (tunnels are not handled explicitly in option 3!)Extra advantage for #3
Ensures the dungeon will be connected
Extra disadvantage for #3
If you end up with a tree structure, you may be blocked off by breeders / very strong monsters with no way to go around them short of digging or teleporting.
This was a problem in halls of mist sometimes.
If I understand the connection algorithm, you randomize all rooms and then connect each room to the next random one by starting a corridor from the room and heading in the general direction of the room you want to get to (with random twistinesses added in). You stop if you intersect another room or another corridor.
I think there's also a check to ensure you don't create a bipartite map, but I need to look at it. I know d_m worked on this.
I have no plans on making major alterations to this procedure (or the streamer placing routines for that matter).Leave a comment:
-
Extra advantage for #3
Ensures the dungeon will be connected
Extra disadvantage for #3
If you end up with a tree structure, you may be blocked off by breeders / very strong monsters with no way to go around them short of digging or teleporting.
This was a problem in halls of mist sometimes.Leave a comment:
-
I am not overly worried about performance for that exact reason. Nevertheless, it's probably a good idea to keep it to a reasonable speed (say under 5s for a normal computer) anymore than that and it becomes very annoying to wait.
The main performance kick to number 2 is determining whether you've intersected something (and possibly adjusting values so that you don't)
The methodology would be when creating a room, check every other (every third?) square one beyond the perimeter, making sure to check all convex corners. If nothing is on those squares, then you're good to go. Then check every third grid in a matrix inside the room to make sure you haven't completely covered up a room. (assume 3 blocks is the minimum size for a room feature.)
If checking is a major pain, some improvement can be made by first sorting by size and then you only need to check the center point and the perimeter.
An alternative would be to figure out how big a space any randomly chosen location can handle, but I think I'd rather start out picking the room first and then trying to place it.Last edited by fizzix; October 10, 2012, 20:52.Leave a comment:
-
I wouldn't worry too much about performance in dungeon generation. Even in the original comments in generate.c it is mentioned that clarity is much more important here than efficiency. Save the worries for things that happen multiple times every game turn!Leave a comment:
-
I think #2 is probably the best compromise, though I worry about the performance given recent IRC debate. (But I worry about that whichever method we choose, so it doesn't influence the choice.)
I am not really sure that #3 will provide sufficient gain to make it worth the significant additional coding effort (though I like the straightforward relationship between config variables and dungeon level sparseness/denseness). By contrast, I think #2 provides a great deal that #1 doesn't, in terms of the handling of different room shapes and generally improved randomness of dungeon level layout.
So my recommendation is to code up #2 and see how dog slow it turns out to be. If we can't optimise it to a good enough level of performance, we can always try something else.Leave a comment:
-
Just a little idea I tried in Mist: after all the rooms have been generated and connected with tunnels, and all the stairs are in place, create some extra rooms (teleport-proof) and tunnels. Then you can have truly challenging locks, stuck doors, and other puzzles that not every character can pass. The locks in Angband are absolutely boring.Leave a comment:
-
Basic room allotment algorithm
The algorithm for deciding where rooms are and whether they fit is probably the first area to focus. I've come up with several ways to do this. It's good to figure this out first because it will have some considerable impact on how the dungeon looks. The goal is to place rooms assuming the existence of off-limits areas (vaults and already placed rooms)
For all possible approaches it may be best to pre-select room sizes and try to place larger or more awkward rooms first and then fill the rest with the easier smaller and rectangular rooms.
Approach 1 - dungeon block approach
------------------------------------------------------
This is the method currently use in Angband and the several variants I looked at. (Thanks Nick for the github variant repository, it has been helpful here!) The basic idea is to split up the dungeon into smaller blocks, 11x11 is the size used in Angband but the value is arbitrary.
You cycle through all the blocks picking a random one each time. After selecting a dungeon block you try to place a room and check if it fits by seeing if the room only uses unused blocks. If the room fits, you mark off all the blocks that it touches as "used" blocks.
There's some logic to try to move rooms around to fit them in as few blocks as possible, but I haven't really looked into it too much.
Positives for this approach:
It is simple and essentially already coded. I would just need to port it over.
It does a decent job of keeping the levels mostly filled up.
It can be used to prevent rooms from spanning window boundaries (part of the original reason)
Negatives for this approach:
It handles non-rectangular rooms (crosses, double rooms, etc.) inefficiently.
It can lead to blocky looking dungeons with stacked rooms vertically.
Approach 2: Random room location approach
--------------------------------------------------------------
This is probably the easiest conceptual approach. You pick a random location, place a room (if it fits) then pick another and repeat until you've placed enough rooms or failed enough times. This is kind of the standard angband way of doing things like this, pick a bunch of random points and throw away the ones that don't fit your criteria.
Positives:
Extremely simple to code.
Dungeon room layout is randomized (no blocky effects)
Has the potential to densely pack odd shaped rooms.
Negatives:
Room intersection finding is much more difficult, instead of checking if blocks are occupied, you have to check if most of the squares are already used.
Dungeon has a chance to be very sparsely populated (unlucky RNG location selection) or over-dense.
Probably more inefficient than the blocky approach
Approach 3: Network
------------------------------
The idea here is to start with a random point and place a room. Then select another room size and travel some random amount in a direction so that the room fits and place it (room 2) Repeat n times for room 1 (probably 3 or so) and then do the same thing for room 2 etc. Eventually you get a network of rooms that grows somewhat organically from the starting location.
This probably needs a reasonably sophisticated graph-theory routine, and I'm not sure I'm up for it, nevertheless it's worth thinking about.
Positives:
Capable of creating highly dense or highly sparse grids very easily.
Can be the most efficient method (but with significantly more code).
Negatives:
I'm not sure I can actually do this one.
Room intersection checking is just as hard as in version 2 (you probably still want to place the vaults/caverns/labyrinths first)
------------------------------------------------------
I'm leaning towards 1 for ease of writing, but there are good arguments for 2 if someone wants to convince me. 3 could be cool but it's a tough algorithm and may not be transparent.
There are possibly other approaches that are used in different roguelikes, so if anyone knows one with interesting dungeon characteristics, I'll check it out.Leave a comment:
-
I would just say the Angband is at a most interesting stage in its development. As usual.Leave a comment:
-
ha! surely you jest sir. the more people were involved, the less likely it would be to be a faithful port.No, it'll be a 100% faithful port of Vanilla Angband, because YOU, along with Timo and and everybody else who likes to carp from the sidelines, will step up and contribute to make sure it is.
And if you don't, you'll stop bitching about the difference between a faithful port and a variant rewrite, won't you?
let me be the first to welcome this fine new variant!
a.Leave a comment:
-
No, it'll be a 100% faithful port of Vanilla Angband, because YOU, along with Timo and and everybody else who likes to carp from the sidelines, will step up and contribute to make sure it is.
And if you don't, you'll stop bitching about the difference between a faithful port and a variant rewrite, won't you?Leave a comment:
-
-
Here are what I envision to be the changes to the "final product" of dungeon generation.
1) Labyrinths and Caverns will become features on a level instead of their own level. This was actually a design goal for a while, so it's well in the intended spirit.
2) Angband splits up the dungeon into smaller sub-blocks and then creates rooms contained entirely in those blocks. Vaults can span multiple blocks. I think the original idea was to prevent rooms from spanning across a window boundary (this is prior to window resizing and center on player). I'm not sure there's another good reason to split the dungeon this way anymore, so I have a feeling rooms will be placed more or less randomly in the pyrel generation script.
3) Frequencies of various features may change. This is probably for the better, since the current allotment is far from ideal (every level in the 90s is almost guaranteed a demon, ainu, undead or if you're lucky dragon pit).
I have lots of other ideas for improvement including making pits variably sized, making sections immune to item/feature detection and mapping, and creating sections where certain monster types are prevalent. But I'm not even sure I'll be able to get generation working given the poor state of my python abilities. So these extra things may not happen.Leave a comment:
Leave a comment: