Slashdot Mirror
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.
that came out in 1983 on the VIC-20? I always wondered how that worked.
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???
Worked pretty good, better than what most people made themselves.
Thats a really overly complex way to do it.
Not only a very lame implementation of an old idea.
The author is using a physics engine to separate the rooms. Bloody pathetic.
It is the evening of the day
I sit and watch the children play
Doing things I used to do
They think are new
I sit and watch
As tears go by
I haven't met a game that employed a procedurally generated environment that I found enjoyable. Environments always feel repetitive and boring. A huge drive for a game to me is level design, and procedurally generated levels mean they give up any pretense of that. For some genres, the levels are nothing more than a backdrop and employ level design like looping background music, but it's just not my cup of tea.
http://journal.stuffwithstuff.com/2014/12/21/rooms-and-mazes/
I personally used this one, although I'm curious what the differences are.
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 architecture, but that isn't actually boring if you're properly doing your job of filling those rooms with interesting stuff.
Mass Effect had very noticeably lazy level design for its exploration/filler material. Hey, it's that one grey box again, sitting next to its grey box friend. Oh boy, I'm going down this hole for the tenth time, I wonder if the door will open left or right. I did it all anyway, because I found the contents of these little adventure capsules at least somewhat engaging, and I was interested in the mechanical rewards from them which I could apply to the prettier parts of the game.
what the fuck is new or news here? random content (i.e. dungeons) is not an innovation.
make completely random zones (and complete, including npcs quests and monsters, and balanced for the levels intended) in worlds for games like wow or tera.. then you might have something.
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)
(-1: Post disagrees with my already-settled worldview) is not a valid mod option.
> gamasutra
stopped reading there
fuck off SJW's
This story is about approximately 35 years old stuff. (I think Rogue came out in 1980)
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.
... sure some of us old-timers know this stuff dates back to Rogue, but there is a whole new generation of programmers who might find this a great introduction to such things.
Keeping the knowledge fresh by re-teaching it is a good thing.
Big fan of Brogue and I find that the author did a great interview explaining how it works in his game here:
http://www.rockpapershotgun.com/2015/07/28/how-do-roguelikes-generate-levels/
He gets more into how the terrain is generated as well.
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.
deleting the extra space after periods so i can stay relevant, yeah.
offload the work to the physics engine you don't fully understand.
Snowden and Manning are heroes.
They are doing a walkthrough of a 2 year old reddit post:
https://www.reddit.com/r/gamedev/comments/1dlwc4/procedural_dungeon_generation_algorithm_explained/
The animated pictures are screencaps of an interactive demo you can play with yourself here:
http://tinykeep.com/dungen/
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.
Seastead this.
As soon as someone employs a physics engine to randomize rectangles on a plane, then it's already gone wrong.
Sounds like the endless Benghazi investigations.
Big fan of Brogue and I find that the author did a great interview explaining how it works in his game here:
http://www.rockpapershotgun.com/2015/07/28/how-do-roguelikes-generate-levels/
He gets more into how the terrain is generated as well.
That is a MUCH better article. Brian Walker has a good overview of dungeon pathfinding too.
http://www.roguebasin.com/inde...
+0 Meh
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 front of your nose.
And all you fellow graybeards kvetching about this kid's solution... get stuffed. He's doing something and sharing his solutions. /rant
NOT