Slashdot is powered by your submissions, so send in your scoop

 


Forgot your password?
Close
typodupeerror
×
Programming Games

An Algorithm To Randomly Generate Game Dungeons 77

Posted by Soulskill from the but-how-do-they-always-manage-to-hide-the-exit dept.
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.
This discussion has been archived. No new comments can be posted.

An Algorithm To Randomly Generate Game Dungeons More

An Algorithm To Randomly Generate Game Dungeons

Comments Filter:

  • Yesteryears Algorithms (Score:2, Insightful)

    by 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: (Score:3)

      by ledow ( 319597 )

      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"

      • Indeed, on the surface this appears to be nothing more than an updated version of nethack

        • Indeed, on the surface this appears to be nothing more than an updated version of nethack

          Yeah, but this is webscale. Huge difference.

      • 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 inter

      • Re: (Score:3)

        by hsa ( 598343 )
        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 y

      • Obviously you have accumulated too much knowledge for anything to be still interesting to you.

        You're getting old. If you're lucky you will develop altzheimers and all of this old stuff will be exciting for you once again.

    • Re:Yesteryears Algorithms (Score:5, Insightful)

      by Sloppy ( 14984 ) on Saturday September 05, 2015 @11:07AM (#50462605) Homepage Journal

      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: (Score:1)

        by Anonymous Coward

        I'm the AC you replied to. You got my attitude totally wrong. I'm a high school lecturer and am quite used to regurgitating yesteryears concepts to undergraduate students. I like to do it, I take pride in being good at that, I thoroughly enjoy my job.

        But: This is not a 1980s (or 60s) textbook, neither a newbie programmer's ideas-for-a-summer-project collection. This is slashdot, and I expect slashdot to be different. Your expectation may vary.

        • 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?
    • In other breaking news, Alaska implements oil dividend fund for citizens.
  • A Complicated Algorithm to Build a Crappy Looking Dungeon

    Any "hallways" in any area but the periphery are going to be wonky and stupid agglomerations of whatever rooms happened to be shoved in there. Attempting to control for that factor would just make all the rooms too similarly square. And frankly, randomized connectivity is just silly to begin with. Other map generators tend to focus on sticking modules together, in part because the connectivity always makes sense that way. It makes for samey architec
    • NB: If a core gameplay element of your game is maze navigation or something similar to it, then this isn't so bad. Though I think it could still be improved.

  • Focusing Without Seeing
    A Play in One Act

    Beowulf17: "OH BOY! Another random dungeon. Cool! Ok, lads, here we go!"

    (send in the tank to start taunting)

    (everyone else enters)

    (sigh)

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

    • Hunt the wumpus in 1972.

    • 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'

  • 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.

    • Physicists might counter that artists are procedural generated.

    • 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.

      But they need not. Chaos theory means that a deterministic system is capable of generating endless variation. Fractals are a famous example, and in fact games could be seen as systems which procedurally generate a timeline of events based on user input along the way.

      Also, I'm not at all sure tha

      • 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. Only artists and animators are able to genuinely surprise you.

        • 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 [bay12games.com], 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 s

  • The third major rev of Avatar brought an extensible maze generated as needed. One team explored 800+ to the east. Coming from a game that was in a maze 30 by 30 and 15 floors deep (and everybody and their mother knew it), this was a revelation. And annoying.

  • offload the work to the physics engine you don't fully understand.

  • Probably the first massive multiplayer dungeon game to employ random algorithm "room" generation was the Mines of Moria on the PLATO system circa 1975-78 [wikipedia.org].

  • It is easy to argue that all of the ideas in the article are not new.

    What I found interesting is that rather than reinventing the wheel with custom built functions this author took advantage of
    library element that are already in the game engine. Using the physics engine is only a heavyweight solution if you don't have a
    preexisting API for handling physics. Since all modern game engines come with these tools it makes sense to adapt the crusty
    old process of generating mazes to the tools that are right in fr

Slashdot Top Deals

Think of it! With VLSI we can pack 100 ENIACs in 1 sq. cm.!

Close