An Algorithm To Randomly Generate Game Dungeons

An anonymous reader writes: Game developers frequently turn to procedural algorithms to generate some of their game's content. Sometimes it's to give the game more diverse environments, or to keep things fresh upon subsequent playthroughs, or simply just to save precious development time. If you've played a game that had an unpredictable layout of connected rooms, you may have wondered how it was built. No longer; a post at Gamasutra walks through a procedural generation algorithm, showing how random and unique layouts can be created with some clever code. The article is filled with animated pictures demonstrating how rooms pop into existence, spread themselves out to prevent overlap, finds a sensible series of connections, and then fill in the gaps with doors and hallways.

Comments

Yesteryears Algorithms

[Anonymous Coward]

While I agree that the animations are nice to look at fore a minute, such concepts have been around for 30 years, since the early days of Rogue and Hack. Why is this on Slashdot in 2015???

Re:Yesteryears Algorithms

[ledow]

Exactly my thoughts.

Sorry, but a lot of it is obvious (don't stomp over other rooms, etc.). A lot of it has been around for decades. And I was writing things to do this over 20 years ago for HOBBY projects, so I'm damn sure anyone who needs to write these sorts of things can find the material online, come up with it themselves, and/or already knows it.

Honestly, "geek site" does not equate to "let's just regurgitate 20 year old articles on the basis of programming that people were doing back in the 1980's". The EXACT opposite.

Fuck, I'm pretty sure the Marshal Cavendish INPUT magazine I read back in the 80's - aimed at kids - describes this sort of shit, and more, and is at least 50% assembly language of various kinds (6502, Z80, etc.). This would barely rate a full page article from thousands, with some BASIC example code, in a weekly series, aimed at teaching kids programming, 20 years ago.

Re:Yesteryears Algorithms

[Half-pint HAL]

The interesting point to draw from this is surely how the internet has really, really, dumbed us down. I'm constantly infuriated by the amount of repetitive superficial crap that pops up in computer tutorials, and lament the fact that even expensive programming textbooks are seemingly less sophisticated than the magazines of the 80s.

While I agree that it's wrong that our current environment makes this sort of stuff into front-page news, surely we should at least be thankful that there are materials on interesting problems, and we should look at how we can expand on that to try to improve the quality of programming education...?

I see this as an interesting programming problem for learners. In the past, room placement would have been the sticking point for most beginners, so while physics engines are overkill, they get the job done. Let's call that the "blunt instrument" solution, and once it's in place, we can start using modular programming techniques to come up with alternative strategies, which can then lead to discussions over execution time and efficiency, and even the trade-off between programming time efficiency vs execution efficiency.

Re:Yesteryears Algorithms

[hsa]

Yeah, old algorithms and I wouldn't use this guy's work for my projects. You read about this stuff on a magazine. Kids these days read about this stuff on the net. I am hoping, that other media outlets have covered this as well. This article gives great ideas and hopefully inspires some future game developers, who are now in their teens.

Too bad it has some fairly advanced concepts, like Delaunay triangulation, which has been taken from a library and quite frankly - useless. Carmack himself speculated some years ago, that just pushing every wall in Doom to a modern GPU without any visibility checking would result in faster performance than raycasting or portals or any other 90s technique. And why do you need triangles, when the graphics pipeline supports quads? And why do they have to be roughly the same size? Have some faith in the GPU.

Good article. Would have been great, if it would have stuck with the trivial algorithms that do not require advanced CS courses. Spanning tree, anyone? I have have worked as a TA in university for a course teaching those subjects, but I didn't have a faintest idea about those in my teens.

Re:Yesteryears Algorithms

[Sloppy]

Damn, what a sad attitude to see.

Say there's some 11 year old newbie programmer. She hasn't done any of this yet, and hears, "a lot of people who are into the stuff you're into, are on a place called Slashdot." Yeah, let's agree that our position is: fuck off, newbie, go get your learning and inspiration somewhere else.

I remember reading articles kind of like this, a few decades ago in "COMPUTE!" magazine and similar things. The topics were even old then, and some graybeard from the 1960s might have scoffed with "oh, I was doing that 10-20 years ago." Well, guess what, 1960s graybeard: maybe you didn't leave enough accessible notes, much less, code. And yes, someone can look at (or imagine) results, and make up how they'll do it, without needing to know how you did it. But maybe some kid wants to learn from your mistakes and successes.

Anybody who writes up decent problems and solutions is welcome, IMHO. I don't give a fuck if it's stuff we were doing decades ago. And honestly, most of that source code isn't around anyway. And when I think of my 1980s code, even if I had my old source, you sure-as-fuck wouldn't want to try to read it.

Re:Yesteryears Algorithms

[rochrist]

That's great and all, but whatever happened to, you know....just skipping the articles that don't interest you? You on a 300 baud modem or something?

Re:Oh just like Sword of Fargoal?

[UPi]

That, and many others. Procedural generation is not new.

I did enjoy the article, though. It was well written, well illustrated and fun to read. I have recently written some 2D game code that was generating a different kind of dungeon (not rectangular rooms, more organic / cave like environment. That was a fun project.

An article doesn't have to be about the cutting edge latest smart phone to be interesting. (I admit to have very little interest in smart phone news. I might read some articles when the time comes to buy a new handset...)

Re:Oh just like Sword of Fargoal?

[Half-pint HAL]

The physics engine in Exile was pretty basic, but used to good effect. The procedural generation of the map was heavily specialised and optimised, otherwise it wouldn't have fitted in 32K. The sort of physics engine that the article seems to be referring to is pretty heavy stuff, and is computationally overkill for the task at hand. However, it's "efficient" in programming terms because it already exists, so is "free" to the programmer. Sword of Fargoal had a minimal and highly efficient solution custom-coded to do the job.

Carmack said...

[Fragnet]

All procedural generation is is a really, really, really tight form of compression. It's also lossy compression, so what you recover from it is almost always lots of different things that are all basically the same. Artist created content may be expensive, but it's superior to procedural generation in almost every way.

Re:Carmack said...

[jbeaupre]

Physicists might counter that artists are procedural generated.

Re:Carmack said...

[ultranova]

What I mean is that this variation is all different in the same way. If you've ever spent time flying around the Elite Dangerous universe, you'll find that once you've seen one system, you're more or less seen them all.

But this has more to do with current state of procedural generators rather than the concept of general. Try Dwarf Fortress, and you do get extremely varied environments to get your dwarfs killed in.

Only artists and animators are able to genuinely surprise you.

That is untrue. Any game with sufficiently complex mechanics will create surprising situations, through glitching if nothing else.

What humans can currently do that computers can't is recognize and combine tropes, or generic thematic elements, and adapt them to current situation. However, there is no known reason why an algorithm couldn't do so too.

An intermediate step might be to move the gameworld over from curent scripted and otherwise static model to a strategic simulation. Imagine, for example, an open-world game where the computer was playing a game of Civilization in the background and a procedural generator was responsible for rendering the results - city growth, roads, marching armies, etc - in the player-explorable environment, along with quests to affect the game either way (for example, the player could sneak into a besieged city to open the gates, or assassinate the army's general). Space Rangers does something like this: the missions you do affect how the game world develops, the war goes on in the background, and as you get stronger you become more and more important player in it.

The whole reason everyone and their dog is investing in physics engines is precisely that they can procedurally generate behaviour as it's needed, thus freeing the artist from having to guess everything the player might do (which is impossible). Procedurally generating animation is currently under development - beyond current ragdoll physics, that is - and then, of course, there's games like Victoria which are about generating alternate world histories. Then there's the ancient Neverwinter Nights Aurora toolset where the designer laid down rooms and procedural generator filled them with semi-random details.

The future of gaming is procedural generation, both because automation is the only way to keep costs under control and because the end result is superior. That doesn't mean those games won't require artists, it simply means those artists will be doing high-level design of thematic elements and interacting systems rather than hand-painting every pixel and modeling every room.

Re:yawn.

[mark-t]

The algorithm is new... or at least it's one I've never seen before, and I've been a fairly avid follower of game programming algorithms since the early 1990's, and reading rec.games.programmer every single day.

Using steering behaviors or a physics engine to separate randomly generated rooms is a different approach from anything I've ever seen for dungeon generation.

I'm not convinced that the approach is necessarily superior to anything else that has been done so far, however. It is innovative, yes... interesting, even. Useful? I'm not so sure about that.

Re:1980 called and wants their story back

[redlemming]

This story is about approximately 35 years old stuff. (I think Rogue came out in 1980)

The ADND Dungeon Master's Guide (a book first published in 1979) had a pretty complex random dungeon (and wilderness) generation system, so the idea is certainly nothing new. There may have been even earlier variants on this theme, I haven't read all the earlier books.

The ADND system was intended for use by a human, but I'm sure lots of people ended up writing computer variants (most of which probably never got published).

It's always nice to have people publish their versions of this kind on thing. There's still lots of room for innovation in this area.