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.
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???
Yeah, you could really code up a great physics engine using the 3D GPU in the Vic-20...
Got them moderator blues I blieve I walk out the do', With these mod-points I been gettin', I 'most never post no mo'
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...)
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.
Rogue was the most popular and cloned by many others. Moria on the Vax (780?) pushed the limits of the machine at the time and aparently the limit of the game features was based on what could be tested using the test program that would check that new changes could be won. The odd thing is that it was written on a one off VAX (ouvax?) that had been an odd upgrade research project when DEC had a crazy idea that they could do field updagrades from PDPs to VAXen.
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.
Got them moderator blues I blieve I walk out the do', With these mod-points I been gettin', I 'most never post no mo'
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.
Casual phone games have come up with an interesting variation on procedural generation -- I suppose you could call it "shuffling". One of my favourite examples is called "Platform Panic", and it looks like a very retro flick-screen platformer on first play. On second play, however, you notice that the screens are in a different order. As you play and get further, you get more screen types, and more variations on them, and they generally get more difficult as you progress. I've seen this same approach taken with games using one-touch flying interfaces (flying snakes, rocket ships etc) where you run a continuous track made of predefined blocks that have been shuffled, and rolling-ball balance games moving from one predefined problem block to another (again shuffled).
What makes this approach interesting is that your game now gets more challenging without necessarily taking any longer to play, but as most people will still want to see their high score increase over time, you have to balance the increasing difficulty carefully to ensure that games do still get longer.
Got them moderator blues I blieve I walk out the do', With these mod-points I been gettin', I 'most never post no mo'
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.
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.
File under 'M' for 'Manic ranting'
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.
Well said, sir.
Wow, what are you Coward? 12 years old?
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.
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
Oh, I definitely agree with that. Just saying it's not quite like Sword of Fargoal...
Got them moderator blues I blieve I walk out the do', With these mod-points I been gettin', I 'most never post no mo'
This is a more advanced algorithm than what would have been used back then! Placement was an integral part of the algorithm (rather than being done by a physics engine to 2D areas within a 2D space).
One example is the "mining" algorithm. Start off with a room, then from one of its walls, dig a corridor or another room. Repeat n times. Dungeon generated.
Obviously you could then do things for object placement. The article's algorithm can make use of the minimum spanning tree endpoints to place items at the end of long paths in the dungeon, for maximum playability. You could alternatively use some form of graph colouring. Back on the VIC-20, placement would probably have been random.
There's loads of dungeon generating algorithms on RogueBasin if you're interested.
Actually it's a different mechanism to generating non-overlapping rooms than other algorithms that either place rooms, or divide up areas. Overkill - probably. Does it matter? No, not on today's hardware. Also this algorithm isn't portable to very old computers, not that most people care.
There is always a desire to create 'realistic' dungeons. The truth is, most real dungeons are small and compact, so the entire concept of 'realistic dungeon' is rather silly.