A long time ago i also wrote a maze generator. It's helpfull to understand the algebra of (fully accessible) mazes:
1. Every wall may intersect with some other wall at most once. (this includes the outer wall)
With the above rule in mind, you can create mazes with any type of random proccess (without the need for backtracking or bookkeeping). You don't have to check wether places are still accessible -- they just always are and will be. Back in those days (qbasic on a 268) just drawing randomly from some point in random directions was about ten times faster than the common path walking (backtracking) style algorithms. Taking two seconds instead of a full minute.
Don't take my word for it. Grab a pencil. Start drawing random lines. They may only cross some other line at most once. You'll end up with a fully accessible maze.
The maze may be complicated -- the walls in a proper maze are not. Its a great example of how understanding the invariants and rules that govern your problem domain will help you write faster and simpler code.
Two walls interact in only 3 ways - first, they don't touch. you get hallways: ||, second one intersects ends at the other like a T (which is a kind of degenerate version of 3). Third, they cross over, like a +. if you don't let walls touch multiple times, say like a D you'll never have a closed off space like the center of that D.
I got that by drawing an exterior square with a single entrance in the bottom right hand corner. I then drew a line from the top wall to the bottom wall parallel to the left and right walls. I then drew a diagonal line from about a quarter of the way down the right wall left and downwards towards the bottom wall. I then drew a diagonal line from about three quarters of the way down the right wall, up and to left towards the top wall. This blocks off most of the maze. So I'm not sure the algorithm works as has been described.
This additional twist makes the original statement of:
without the need for backtracking or bookkeeping
appear to be misleading. You have to do some bookkeeping in order to know if the wall that your line just hit is connected to the start point, or any midpoint of the line you are drawing. The complexity is just hidden behind simpler words (They may only cross some other line at most once.).
Also, I'm not sure how the backtracking is missing. Once you've hit a new wall with your line, and check connectivity, if it's actually connected, then you have to backtrack that line until it's back to a place where it's no longer connected. Connectivity could be checked right before hitting a wall, but then it's just backtracking by another name. So I'm really not understanding how this would be implemented in an simpler and/or faster way.
If you have a way to draw a wall (twisty line) that doesn't intersect with any other wall, then it's trivial. Just draw a new wall optionally anchored on a wall. The line crossing bookkeeping seems annoying. If i had to do something right now, i'd use a bitmap of cells to indicate the presence or absence of a wall. Can't set a bit with more than 1 adjacent (north/south/east/west) bit set.
Can't set a bit with more than 1 adjacent (north/south/east/west) bit set.
Then you couldn't make a T (or + intersection) because as the newly incoming line was about to attach to the existing wall (regardless of any other connectivity), the final "bit" that would attach to the line and existing wall would have 2 adjacent bits set. ex: assuming a wall that travels east/west, and a line coming from the south northwards, when drawing the last pixel of the line before it attaches to the wall, the test would fail. The "south" bit would be set because that bit was set just one step prior, and the "north" bit would be set because that's where the wall is.
---------
x
|
|
Can't set "x" because there is more than one "adjacent" bit set (north and south).
Another cheap and very effective technique for procedural level and maze generation is to create a "walker" or series of walkers that start at some point, walk in a direction and then turn at random intervals, leaving a path of corridors and occasionally rooms in their wake. This is how Vlambeer's Nuclear Throne generates its levels, and there's a good article from Jan Willem Nijman, it's developer, here: http://www.vlambeer.com/2013/04/02/random-level-generation-i...
If you'd like a more academic look into procedural 2d game generation, there's a nice research paper here, that describes a method and talks about Spelunky a lot (the king of procedural 2d level generation, in my book): http://games.soe.ucsc.edu/sites/default/files/cig10_043CP2_1...
Additionally, Derek Yu open sourced the code to the original Spelunky, and Darius Kazemi created a great breakdown of its level generation techniques here, also with interactive examples: http://tinysubversions.com/spelunkyGen/index.html
The action roguelike genre, particularly the roguelike FPS, is a vital new area being explored by indie game developers. It reminds me of the way 2D platformers were mined, explored, and iterated upon starting around 7 or 8 years ago.
Right now, it doesn't take much to stand out from the herd, as many of the most popular games in the genre don't do much beyond generating a bunch of square rooms and connecting them with doors and short, straight corridors. In my opinion, developers in the genre should take more cues from Doom, and less from original Zelda dungeons moving forward.
And, from a more holistic perspective, nobody really cares about mazes, room placement on a grid, and connective corridors when playing a game, beyond a brute mechanical level. A more useful framework for thinking of generating levels might be to go one level of abstraction higher. Think about a level as a story for your player, and generate setpieces or 'acts' that you want the player to experience as they play. Keep in mind the basics of a good story: an escalation in tension and difficulty, spaced with breathers for rhythm and flow. Place those sets on a path in a map, then figure out a way to connect them together at the lower level with rooms, objects, enemies, and corridors.
These links are awesome. I've considered an "incremental digger" model like Nuclear Throne's before. I like that they're "realistic" in that they sort of simulate how creatures would have created the dungeon. I haven't played with them enough to see if I can get fun results out of them, but now I find myself wanting to try.
> Keep in mind the basics of a good story: an escalation in tension and difficulty, spaced with breathers for rhythm and flow.
It's out of scope for this article, but my little game tries to do some of that. Once the dungeon is generated, it chooses a random starting place for the player. Then it calculates the distance to that tile for every other tile.
When monsters, treasure, and quest goals are placed, those distances are taken into account. Harder monsters and better stuff are placed (roughly) farther from the player, so it feels like there's a general progression in difficulty and reward as you go farther through the dungeon.
There's definitely a lot more I could there.
Now that I think about it, one simple refinement would be:
1. Place all of the monsters first.
2. Recalculate distances and treat tiles near monsters as being "high distance" based on the monster's strength so that paths that go through monsters become "longer".
3. Now place treasure according to that.
That would give you dungeons where monsters "guard" better treasure, and stronger monsters protect better loot.
You could enhance that second point by adding some noise to the function so the difficulty isn't a smooth ramp — you get some tough monsters earlier and then maybe the next group isn't as difficult.
Right. I fuzz that on the other end in my game: the distances are calculated accurately, but the monsters are distributed semi-randomly by distance.
The basic process is:
1. Pick a random difficulty for the monster.
2. Pick n random locations for the monster and place it at the farthest one.
n is based on the monster's difficulty so stronger monsters get more chances to end up farther away. This means you can still run into really hard stuff early, it's just less common.
Can I take a moment to be critical here? I hate sounding negative, but I'll try to be constructive.
I was really excited when I first stumbled onto this book. As you can imagine, it's perfectly in line with my interests. But, when I tried to read it, the prose just killed me. I think there's good ideas in there, but I can't bear to wade through the heavy-handed academic style get there.
I understand writing for a certain venue requires certain stylistic choices, but I really hope you guys can tone it down a bit. Here's a sentence plucked randomly from the linked chapter:
> "Generative grammars were originally devised as a method to formally describe sets of linguistic phrases."
"as a method" -> This adds nothing to the sentence.
"formally" -> I suppose this matters in some cases but given that the chapter isn't a precise introduction to generative grammars, whether or not it's a formal system doesn't seem very critical to me.
"sets of" -> This adds nothing.
"linquistic" -> What other kinds of phrases are there?
I would edit this sentence down to:
> Generative grammars were invented to describe written text.
I understand academic writing isn't designed to be read for pleasure, but we're all human. If you make the prose more approachable, you'll reach a much wider audience. You have some fantastic material in here, great algorithms, diagrams, and structure. I just feel that the writing style gets in the way of it.
If I could suggest anything, it's that the authors go through the prose and for every phrase ask themselves: "Does this add information? Is there a way to convey the same concept in plainer language?"
This is not "academic writing", it is writing trying to sound academic. At my University you would get higher regard for your version and consequently better marks.
If it is a subject you are interested in, then George Orwell's essay on writing style [1] is worth a read.
The word original in the original text is used in the sense of "from or in the beginning; at first", while you seem to be taking it in the sense of "in a novel and inventive way".
The phrase "originally devised" implies the usage of the devised thing has since changed or expanded beyond the purpose of its invention. This is important, because it is in a passage talking about one of those new usages - dungeon generation.
Yes, your sentence has the same meaning, and in a weak sense has the same implication, but "originally devised/invented" has a history that boosts that implication to make the purpose clearer.
A reasonable point. I've been doing a bit of editing for style recently, and will make another pass before sending off the manuscript. At the moment the style is very uneven from chapter to chapter, partly because the authors come from different backgrounds. If you include chapter authors, we live in 6 countries and have 9 native languages between us, and different views on how a textbook should read. To generalize really broadly, the text from Americans and Scandinavians seems to use shorter sentences and a more conversational tone than that from others. (Of course, country/language isn't the only reason people vary on style and level of formality.)
But yes, I'm aiming to bring it in a more conversational direction. It still needs editing too, but Ch. 8 is closer to the style I'm personally aiming for.
Adom is a roguelike that does your "holistic perspective" very well - it mixes an overall story arc and set piece locations with a lot of randomised elements. It's going through a bit of a renaissance after raising 90k on IndieGoGo.
Have you seen Brogue? It's level design is pretty incredible. I do love Spelunky but I think Brogue, from a design and technical perspective, is better.
One area I've been experimenting in is constraint-based solvers in my generators. It requires keeping track of rooms or regions but allows the algorithm to express ideas like: this room has a health potion but the boss cannot be within 2 rooms of it. You can of course get more creative with your constraints. I'd like to build up the ability to have sophisticated (for some value of sophistication) puzzles built into the dungeons I generate.
I think this article is a fantastic example of how you can blend prose with working interactive examples. The examples make you really trance out watching dungeons being carved out of nothing.
I think an often-discounted aspect of JavaScript's appeal is its ability to breathe life into a bunch of fascinating but otherwise dry concepts. Another terrific example is this page by the prolific Mike Bostock: http://bost.ocks.org/mike/algorithms/
I agree totally. I love the ability to write blog posts with interactive animated content. We take for granted that the web platform can do all this, but it's rare to find content that takes advantage of it. Mike Bostock and Amit Patel's sites are notable counter-examples.
I'd like to do more posts like this, but I can see why they aren't common. This one took me forever to finish. Easily eight times as much effort as a regular text + code samples blog post.
I think I'd get faster as I did more in this style, but it's really hard to for me to stay energized on a single concept long enough to finish posts like this.
That was a very pleasant article and fills me with inspiration .. which is what I came here for, mostly, in the first place. I don't have many applications for twisty mazes in my space at the moment, but one thing that I always thought would be interesting is to use the dependency graphs/use-counts of various system libraries as inputs to a maze generator. Sort of like Fsn (http://en.wikipedia.org/wiki/Fsn) but with a lot more twisty, bendy mazes between the ldd details .. huh, yet another bit of bait for the bucket ..
Amusingly, I think this demonstrates one of the problems with classic roguelike dungeon generation: single-tile corridors are rarely very interesting, and usually much less interesting than the rooms they connect.
To cop a quote from the OP itself:
"Fundamentally, games are about making decisions from a set of alternatives."
In a hallway, your alternatives are reduced to moving forward and moving backward. When confronted with enemies, you can choose from at most two to attack (ignoring AOE for a moment, since it's usually also strictly less interesting in narrow corridors, as the article mentions as well).
Instead of passageways, I prefer a technique I've seen in Dungeon Crawl Stone Soup: start with an enormous open level (often in a more interesting shape than a square, such as a randomly-generated blob), and generate enclosed rooms within that level. At the limit, you can recursively partition the entire level until it's a series of small interconnected rooms, doing away with passageways altogether.
It is an amazing article. The "fluff" prose is well written and the visualizations are awesome. Kudos.
An honest question, though, is maze generation generally useful? Other than for generating mazes and dungeons, obviously, not that isn't a worthy goal in and of it self.
In case people didn't recognize, the author of the articel is also the author of this book which is for free (kudos!) on the interwebs and can be bought as a eBook.
http://gameprogrammingpatterns.com/
But what about something completely different? I get that generation of "content" is (going to be) a big thing, but I'm curious if there's something about it that was applicable in a completely different setting (medicine, finance, whatever).
Last time I needed a maze I implemented Kruskal's algorithm, which is generally useful for finding the minimum spanning tree of a graph. You just run it on a lattice graph where all edge weights are the same and you have yourself a perfect maze.
Maze generators are a lot of fun to play with, but don't always come up with the most compelling gameplay environments.
One of the techniques I've heard works well is to step up the abstraction level one click, and create interesting environments and set pieces, then combine those to create a compelling environment for your players. One approach to do this uses herringbone Wang tiles to place various precreated environment tiles in a random, pathable way.
Yes, that would work fine. You just have to track when that happens so that you know those two rooms are already merged.
Another option is to generate non-overlapping bounding boxes for rooms, but then don't fill in that entire box. Instead, you can draw whatever shape you want in there.
The maze generator will then fill in the cracks you leave.
1. Every wall may intersect with some other wall at most once. (this includes the outer wall)
With the above rule in mind, you can create mazes with any type of random proccess (without the need for backtracking or bookkeeping). You don't have to check wether places are still accessible -- they just always are and will be. Back in those days (qbasic on a 268) just drawing randomly from some point in random directions was about ten times faster than the common path walking (backtracking) style algorithms. Taking two seconds instead of a full minute.
Don't take my word for it. Grab a pencil. Start drawing random lines. They may only cross some other line at most once. You'll end up with a fully accessible maze.
The maze may be complicated -- the walls in a proper maze are not. Its a great example of how understanding the invariants and rules that govern your problem domain will help you write faster and simpler code.