I might have to process that for a second. Definately sounds like it's getting into a more effecient method.
At this stage I've given up on the algorithm I specified at the start. I think you can generate far more interesting maps faster by using other means.
However using predefined features sparingly is a great way to add history/lore to your dungeon.
What an interesting experience it's been writing that though and I've learned so much.
Lummox: Thanks for the Rogue correction.
Other things: - You can do simple AABB rectangle collision for rooms (if you have their rectangle, anyway), and if that passes for every room it's a safe place to put a new room. If it fails, then you can check component turfs to see whether your complicated shape actually can fit. - There's probably something clever you can do here using a quadtree to represent where stuff's dense that'll get you a fast placement state - any nonroomed quadtree node large enough to contain the room you want to place and in the right location can just be used. If you split quadtree nodes on room edges and treat all rooms as rectangular you can guarantee rooms will always be adjacent to quadtree nodes, so that state will come up a lot. - There is stuff out there about generating zelda-style key-and-lock maps. Figuring out where on a graph you can place locks and keys to still have reachability, basically. The first thing that comes to mind is selecting some arcs to be locked doors, removing them from the graph, and now if there's one key somewhere in every sub-graph that generates, you can still reach every node (if there's a goal node, though, you don't have to reach every other node first before you get there). There are extensions to have multiple classes of key (boss keys, items that let you solve puzzles, etc.). I don't think that handles one-way rooms right, though. Maybe with some thought + care. EDIT: Here's the zelda thing. Blog post explaining the algorithm. Doesn't have directed arcs but I'm pretty sure it could be extended easily. | |
A simple way of ensuring reachability with keys and locks is running a DFS from the starting node of the dungeon, and then placing the key for a node of depth d (in the tree) at a depth smaller than d. I'm not sure if from a gameplay perspective this generates dungeons that are particularly 'fun' though. To make this work for one-way doors, after placing your keys generate a connected component graph, and for every connected component add a one-way path to a previous component that uses a key of the same type as the easiest one used to reach the current component.
A better idea is pre-generating areas (you could make them of different kinds to vary it a bit) and connecting them linearly with locked doors, so you have a locked door from area_1 to area_2, from area_2 to area_3, and so on. Then ensure area_i holds the key to area_(i+1). After you do that you can add a few random paths from area_j to area_k without worrying about whether the player could immediately take advantage of them. Of course any algorithm that talks about abstract 'graphs' runs into the more difficult problem of how to translate those graphs into an interesting-looking dungeon in an NxN map. You could just connect your vertices through "hallways", but this is ugly. So it's not as though the problem was necessarily solved just because we have a graph of the dungeon layout. Ultimately I don't think any of the Conway's Game of Life-esque algorithms for dungeon generation look or play as good as the hybrid ones that make a bunch of biomes (generated however) and worry about connecting them later. | |
From a graph theory perspective, I don't think you can look strictly at depth.
First, you want the graph to have adequate articulation points or bridges. (Most good approaches would, I think, be based on bridges.) An articulation point is any node that, if removed, will split the graph into more pieces. A bridge is any edge that would do the same. The edges between nodes would represent the means of travel from one room to another. So in a regular Roguelike that'd be something as simple as a door, with rooms and passages being nodes. In a game like Runt, the screen edges are graph edges, since they're how you move from one room to the next. In the classic Atari game Adventure, you have screen edges, castle gates, and any walls that you might need a bridge to cross. Typically, to ensure players explore everything you'd want most keys or special treasures to be at the very far nodes of the graph, from a DFS perspective. (Those would be "leaf" nodes, if you look at it like a tree.) In some kinds of games the level exit might be a goal item as well. Here's what I would do. Using a DFS approach and identifying bridges, I'd "color" each group of nodes that are interconnected by assigning a group ID. Any place that a bridge is encountered, the color would change. Thus your starting nodes might be group 1, the nodes behind bridges X and Y might be 2 and 3 respectively, and maybe there's bridge Z after the 3 group, and the nodes behind that are group 4. Eventually, you should have a list of group relationships that look like this: G1 > G2, G1 > G3, G3 > G4 Knowing that, you can place your puzzles by doing a topological sort. These are the ways the above groups can be sorted topologically: G1 G2 G3 G4 G1 G3 G2 G4 G1 G3 G4 G2 Let's pick one of these arbitrarily, and go with G1 G3 G2 G4. Say that the final goal of the game is to reach the princess. It is therefore logical that the princess should go in the final group, G4. If the puzzle to reach the princess is to be interesting, you don't want the player to go straight from G1 to G3 to G4. The most logical place to put the G3-G4 key, therefore, is in the next-to-last group in the sorted list: G2. The deepest node in G2 is the best place for it. Now for the G1-G2 key, you'd repeat this process: G1 isn't ideal if you can put the key in G3 instead, so it goes there. And then the G1-G3 key has to go in G1. Another approach here is that, again starting from the back, you can place the key in any available group following these rules: - A group that already holds a key will only be given another key to hold as a last resort. (This should never happen.) - The locked group should try not to place a key in one of its predecessor nodes, if possible. - The key should always prefer to be put in groups towards the end of the topological sort. Bridges alone needn't be your only guide, though, and you don't even have to use all of them. Articulation points are great places to add physical challenges. For instance, a node in G1 that happens to be an articulation point (let's say it's where the path forks to go towards G2 or G3) might be a terrific spot for a dragon. | |
Here's another interesting thought.
1) Build a graph as big as you want. Do something simple, like maybe starting with a single map cell and working outward from there. Consider all map cells interconnected with all their immediate neighbors (where added) at first. 2) Decide on puzzle complexity, e.g. the goal number of "colors". The graph should be big enough so that you have an adequate number of cells (nodes) for each group. E.g., in a 25-cell map, maybe there will be a target of 6+ groups. 3) Build the home group by starting at the home position and extending outwards, preferring breadth over depth. Stop when the number of nodes you've colored is the target size. 4) Do a BFS and assign a depth to each node. 5) Starting with one of the farthest uncolored nodes, build a group by traversing other uncolored nodes. Its immediate neighbors in depth should be the most attractive candidates, but try to avoid more than, say, 3 or 4 nodes at the same depth. (It depends on how many nodes are in an average group, and how great the depth is. If depth is shallow and the groups are large, more nodes at the outer depth are welcome.) Once a good target size has been reached, OR you run out of room to expand before bumping into another group, return to step 4. If this group is too small, you have the option of folding it into the group you bumped into. 6) Create a graph representing the relationships between the groups; each group is a node, and has edges extending to all its neighbors. Snip all non-bridge edges (and recalculate which edges are bridges) until there are none left to snip, which will remove all cycles. 7) Based on the group graph, now snip edges between nodes in the original graph. If two groups never meet, then two nodes in those groups that border each other should never meet either. Any bridge that may be used as a lock should have only one path between nodes of these two groups on the map, so snip all but one connection between the nodes in these two groups. 8) To add a little flair, you can now snip edges within each group, separating their nodes, as long as the edges you snip aren't bridges themselves. (Remember, with each snip the potential bridges will change!) All of this sounds complex, but the goal is to allow for an organic map shape to be rendered puzzlable, by creating artificial choke points and/or making use of natural ones. An example of what I mean might look like this, where the @ represents the home node:
## ### ###
##### ####
### ##########
# ###@ ######
## ## ######
#######
#### ####
The groups might be built like so:
## ### ###
##### ####
### #AAAA#####
# ##A@ ######
## ## AA####
##A####
#### ####
## ### DDD
##### #DDD
BBB #AAAA#####
B ##A@ ######
BB ## AA##CC
##A###C
#### CCCC
FF HHH DDD
FFFFF HDDD
BBB JAAAA#EEEE
B JJA@ #I#EEE
BB JJ AAIICC
GGAIIIC
GGGG CCCC
FF HHH DDD
FFFFF HDDD
BBB JAAAAAEEEE
B JJA@ AIIEEE
BB JJ AAIICC
GGAIIIC
GGGG CCCC
If you map out how the groups touch each other, you'll see there's far too much connection between them. So you'll want to snip those out. Additonally, the H group represents a problem I forgot to address in my last post: You want each group to be accessible to one and only one precursor, except for A which has no precursors. The group graph should have no cycles at all when you're done with it, which eliminates that problem. Step 7 is where you would look at the places where groups touch, and decide on the one place (if any!) where they can be allowed to touch. B and F touch in two places, so one of those edges would have to be snipped--such as by putting a wall between two cells, for instance. And finally in step 8, groups like E would be broken up a little bit by adding in more internal walls. | |
Yeah, I was mentioning (B/)DFS just as a very rudimentary way of ensuring your player would be able to unlock every door. If a key appears at a depth lower than the depth of your door that means any node blocked by that door would have larger depth, so you will always be able to unlock the door before exploring a node that goes beyond it.
But about the graph searching approach in general: As I said, I think you will get better results by first generating your puzzle areas, according to certain parameters and disconnected from each other, and then sorting them by difficulty and adding bridges accordingly. You could then add more arbitrary connections between the areas to spice it up. The issue with doing this the other way around (other than guaranteeing the existence of said bridges) is that the topological layout of the map is decided first, and only then are the features of the rooms determined. G4 might not really 'look the part' for the area that should hold the princess. For example it might have very few nodes and be very small. In the hierarchy of generation it seems better to first decide on the general features of your game areas/puzzles and the dependencies between them, and then zoom into each area and give it individual, organic features. Looking at articulation points and other isoperimetric features of a graph would most likely be more effective if that graph represents a single gameplay area. | |
If we want to make things more interesting: thinking about classics such as Zelda, Monkey Island and the such, there was usually an element of non-linear progression in that some areas required you to have more than one key or item to unlock. You might require the rope, found in the swamp, to climb a certain mountain, but then you need the golden key from the treasure chest in the castle to unlock the castle atop the mountain.
The nice thing about toposorts (that you've mentioned in your post) is that very often there are several possible sorts at a time. We can use this to add non-linearity. 1) Generate your areas, G1 ... G10, and assign to each of them a key item, ordered by difficulty perhaps. 2) Lock area G_i with a random combination of locks from areas G_1 ... G_(i-1), your choice being skewed towards the more difficult areas. 3) We generate our dependencies graph, K: for any area G_k, direct an edge from it to any areas that requires its key. 4) Note that G1 G2 ... G10 is a valid traversal of K, but there can be others. Find another toposort; it can be say G1 G3 G2 G5 G4 G6 G7 G8 G9 G10. Add an edge between immediate areas in this new toposort. 5) Now you have several possible ways to complete the game, and our locks are more interesting as well. | |
One thing you might consider is keeping a list of rectangles. Each rectangle in the list represents unused, or potentially unused, space. (This will work best with square rooms, but you can make some adjustments for round rooms and such.) It doesn't matter if these rectangles overlap, but hopefully you can find a way to merge rectangles that are within one another. Any time a room is placed, the rectangles it touches will be split into multiple rectangles. You could have a threshold where they're too skinny to be used anymore as well. The benefit of this is that by checking only the appropriate rectangles, you can tell more quickly if a room will fit or not.