Rooms & Maze Pruning

Time to update what I've been up to for the last few weeks. Last time I posted, I showed my dungeon generation algorithm where it was. Since then, I've made a bunch of improvements. First, I added room support. Currently, it only uses square rooms, but it supports irregularly shaped rooms.
I also made some small fixes to problems that I'd seen. In the old model, the hallways started big, and then always got smaller. This had the effect that hallways would just get very small very fast. Now, the hallway starts at a medium width, and each child can get bigger or smaller. This has the effect of making sure that there is a better distribution of large and small corridors.
I also changed the order in which children are drawn to create a more regular look. Now, child hallways are processed depth-first, starting with children nearest to the starting point of the parent hallway. Midway through last week, this had me creating dungeons that looked like this:

Corridors vary in length. Rooms are spawned off of corridors. The size of a room is proportional to the size of the corridor that spawned it. "C" represents a corridor. "R" represents a room. "D" represents a door.

This brought me to the beginning of this week. As you can see, the "spawn hallways and doors randomly" algorithm creates something pretty good, but there are a lot of unnecessary corridors that lead to nowhere. Nobody who was building a dungeon would go to the trouble of building these long corridors to nowhere. So before I moved to rendering these hallways in 3D, I wanted to work out some way to trim the maze.

My first attempt involved backtracking along each corridor after building it and its children. Essentially, after a corridor finished building, it would begin to erase itself until it reached a room or a corridor that led to a room. I was unable to get this method to work. It mostly just erased all or almost all of the corridors. No good.

Take two was much more successful. First, the maze algorithm above is applied, including unnecessary hallways. Then a second draft is drawn, which gets rid of the unnecessary pathways. While the rough draft is being drawn, each corridor keeps track of whether or not it leads to a room or to a corridor that leads to a room. When a corridor draws a room, it remembers the position of that room as a potential end-point. It then updates its parent and tells the parent to end at the start of the child corridor. After the rough draft is done, each corridor knows whether or not it leads to a room. Corridors that lead off to nowhere are not drawn. The corridors that are drawn know the position of their most distal room or corridor that leads to a room. When these corridors are being redrawn, they use this information to prevent corridors from being too long.

The same map, after being filtered. Notice that each corridor ends at a door or at the start of a new corridor that leads to a door. The rooms are in the same positions as in the rough version. Some of the corridors led off to nothing, and were removed completely.

As you can see, the trimmed map looks much more tame and is much easier to navigate. All of the rooms are in the same place, and every room is still accessible from every other room. Every now and again, a corridor goes one square too far (you can see one such instance in the upper right quadrant of the map), but I'm not particularly concerned by this occasional off-by-one error.

Now that I've got a nice, sane dungeon map generator, I can set about rendering it in 3D in Unity. This will be my task for next week. I do not anticipate it being too difficult, as it is fairly similar to what I did last semester.

EDIT: Also, just in case anyone was curious about run times, I did a test where I generated 1000 trimmed mazes, and measured the average time it took to make a maze. Here are the results:

40x40 maze w/ minimum 20 rooms: .0055 seconds per maze
40x40 maze w/ minimum 30 rooms: .0919 seconds per maze
NOTE: 30 rooms in a 40x40 maze is about as many as can fit.
100x100 maze w/ minimum 50 rooms: .0289 seconds per maze
100x100 maze w/ minimum 100 rooms:  4.375 seconds per maze (Averaged based on generating 50 mazes - didn't want to wait over an hour to generate 1000 mazes.)

The minimum number of rooms limit is enforced by checking the number of rooms after a maze has been generated, and restarting the maze if there are too few rooms. The running times get large if a maze has to start over a lot before a suitable maze is created. So running times can be said to be roughly proportional to minrooms/totalsquares.
Considering that the maze must only be generated once at the start of a level, these generation times are very reasonable. Even the 100x100 maze with minimum 100 rooms took an average of less than 5 seconds. An extra 5 second wait on top of the rest of the load time is not an unreasonable amount of time to expect the player to wait.

If you want to see one of the 100x100 with minimum 100 rooms mazes, you can see one here. (Download the .txt file and then open it in your text editor of choice.)

Quick Update on Corridors

Changed it to grow the corridors in a breadth first instead of depth first manner. It looks WAY better now. And now on to rooms!

Corridor Mapping is Go!

It's been a while since my last post, and I apologize. I've been busy with trying to get a job for last year, and a lot happened this week. That having been said, I've made some progress. I've switched over to prototyping in processing for the time being, because it is quick and easy. All I'm trying to do right now is get out a floor plan, and then I can turn that floor plan into something pretty in Unity.

Last week, I was trying to generate my maps rooms-first, by generating a bunch of rooms and then trying to connect them. This proved to be problematic, as finding paths between rooms, and for that matter, picking which rooms to connect was proving computationally expensive. So, now I am generating corridors-first, and the results are looking promising.

Basically, each corridor is given a starting location, a direction and a width. The corridors are drawn outwards from the starting position one row at a time. At each location, there is a certain probability that a new corridor will be drawn starting at that position perpendicular to the current corridor. There is also a set probability that the new corridor will be smaller than the current corridor. There is also a set probability that a given corridor will stop short. All of these probabilities are controllable by the user. For example, here is another maze with the probability of spawning a new corridor turned down:

As you can see, the maze is considerably sparser. The next step is to give corridors some probability of spawning rooms as well as corridors. This behavior is similar to spawning a new corridor, so I do not anticipate it causing problems. Because there will be rooms taking up space and obstructing corridors, this will have the effect of making the mazes much sparser. I suspect that the solution to this problem will be to fiddle with the weights of various behaviors.

Will post again once room placement is up and running.

Processing is my Favorite

Things are moving slower than I'd like in Unity, so I'm trying a new tactic - I'm making a 2D prototype in Processing. I should have an overhead map ready by the end of the week, and then I can translate that code into C# and start assembling that 2D overhead map into navigable Unity scenes.

(Note on post frequency: As a means of keeping me on track and of giving you - my peers and advisors - more opportunities to call me if I get off track, I'm trying to post way more frequently than I did last semester. Hopefully this'll help. I apologize if this clogs up your RSS feeds.)

Some Cool Stuff I Found

I am still working on getting random rooms up and running, so while you wait, here is something really cool that I found. It's an article in Game Developer Magazine by Adam Saltsman about procedurally generated content. Although most of this was old news to me, it offered some interesting avenues to pursue. One came from Saltsman's own procedural level generator. (It's in the references of the article, but you can find it here if you're lazy.) His basic idea was to set key locations that you want the player to visit first, and then dig a series of successively smaller tunnels towards these key locations. I like it because it allows a little bit more control on the part of the designer.
I've also been looking at the documentation of a program called DungeonMaker, which is a simple dungeon generator for 2D dungeons for Roguelike games. The strategy behind DungeonMaker is that the dungeon is "carved" by a series of agents. Big tunnelers crawl around digging large tunnels and spawning a series of smaller tunnelers who dig side passages. These tunnelers have the option of spawning a room digger, which will cut out a room if there is enough room. DungeonMaker takes the opposite approach of what I want to do. I intend to place the rooms first, and then use a variant on Kruskal's algorithm to connect them. Nonetheless, he provides a different interesting solution to the problem I'm trying to solve.

That's all for now. Once I get Unity to stop being so finicky, I'll show off some room generation.

Hi! This is post number 0 of my blog on my dungeon generator. My proposal is basically to make a procedural level generator for video games built in Unity. Where most games have a level generator built specifically for them, however, I will be making a general purpose level generator that allows artists to input their own assets and set preferences as to how they want the dungeon to look and feel. Additionally, the generator will allow for non-procedurally generated content to be seamlessly integrated with the dungeon. For example, if a designer wanted a procedural level, but then wanted to design the boss chamber by hand, he or she could do so and the chamber would be connect properly with the rest of the level.

 This is an offshoot of my project from last semester, so there is already some progress. However, much of this is being rewritten. This past week, I have been brainstorming redesigns of my old system. Last semester's generator used a tile based system to create a sprawling series of tunnels. I would like something that feels a little bit more like it was constructed by humans, so I will be rewriting it to take an approach more similar to the building process. Instead of sending corridors all over the place randomly, the generator will take the space and divide it up into bounding boxes that will eventually contain rooms. It will then design an outline for the room to be constructed. It will then connect the rooms via tunnels and doors to create a minimum spanning tree. By controlling access to the various branches of the MST through locked doors, the generator can know the order in which the player will have to explore the rooms (or at least, which groups of rooms will be accessible before others). This means that a game designer who is using this system can say "I want the player to see X before Y" and the generator will be able to make sure this happens.

This is the basic idea. I will go into more detail about specific features as I implement them. However, if you are interested, you can see my design doc here.

Looking forward to updating you as I go.

-Eliot J. Kaplan

Procedural Storytelling

My idea for creating a procedural story based around an archaeology dig has always been that the character travels around the ruins, gathering artifacts and learning about the ancient civilization. In order for the game to be successful, I need two things. First, I need to be able to dynamically generate a history about which the player can learn, and then the player needs some means for tracking their process in learning about that history.

The fact that the player is the only character in the game helps me a lot - it means that I just need to generate what happened without needing the character to have to interact with the stories as they occur. In the game, history will be made up of distinct events. Each event keeps track of which historical characters were involved in the event. Characters only need to keep track of their relations to other characters.

The player keeps track of his or her progress in learning the full history of Mu in a journal. As the player makes new discoveries, these discoveries are tracked in the journal, which acts as an encyclopedia of Mu. The journal will have two kinds of pages: character pages and event pages.

A quick mock-up of a character page.

The character pages will display information that the player has discovered about a particular Character. Most importantly, their dates of birth and death, their relationships to other players and a fact sheet, which will mainly serve to link to the event pages of events in which the character was involved. This page may also include some flavor text.

A quick mock-up of an event page.

The event pages display information that the player has discovered about a particular Event, most importantly the people that the player knows were involved so far, and the player's progress in learning the three big facts about the event. Whenever the player finds an artifact, journal entry, carving or painting, a new event-piece is revealed in the journal, and all relevant character pages are updated/created.

The journal serves as a scoring mechanism (you are a better and better archaeologist as you fill out more and more pages) and as an events-in-progress page (You still need to investigate X to fill in the blank on this page.)

So, with all of this in mind, generating new events actually becomes really easy:
1) Pick an event template to base your event on.
2) Cast characters to play the various roles in the event. A character can be cast in a role if nothing in the character's history conflicts with events that happen during the event. So, requirement for the role of the groom in the wedding example would be:
hasn't already played the role of groom at a wedding AND is male AND (spouse not yet assigned OR spouse was assigned as this character's bride as part of a different event) AND there is no temporal conflict. (That is, nobody should be marrying someone who lived 200 years before they were born.) AND isn't already assigned to some other role in this event.
New characters should only be created if no character already created fits the requirements.
3) Spawn an item in the world that is related to the first of the three plot points in the event. The second and third items should only be spawned after the first item to make sure that the player discovers the story in the correct order.

Done. That's the plan so far. I'll be discussing it with Dr. Lane when I meet with him on monday. I'll also be talking with Matt from the SIG Lab later that day.