Like with other aspects of AI, there are some procgen techniques that have faded into the background: it can sometimes be hard for me to tell if a game has a random map generator because that’s no longer the unique selling point it once was.
On the other end of the spectrum there are things like Panoramical, which couldn’t exist without procgen techniques to give it a complete generative space to explore. In each world the player has eighteen different dimensions to travel in, each reacting with its own link to the music and effects.
Just some more BotRoss paintings to admire. I kind of want to hook these up to a procedurally-generated C64 adventure game.
If you want to generate some yourself, you can download the source code. It works just fine in the current version of Processing, though you’ll probably want to set deleteOnceDone to false if you want to save the images it outputs without hooking it up to Twitter.
Because so many roguelikes are open source, their map generators are available for examination. While many clearly borrow from each other, they also show a number of different approaches to procedural generation. Examining the source code can tell us a lot about what works.
NetHack is one of the major roguelikes, rivaling Angband at the most significant roguelike of the Usenet era. Unlike Angband, but like Rogue, it generates levels that are the same size as the screen and consist of rooms and connecting corridors. (It’s close enough to Rogue that there’s actually an optional Rogue-emulation bonus level!)
Nethack is mostly written in the 1989 version of ANSI C with some translation macro hacks to account for different compilers and versions of C. This makes for a fairly gnarly codebase, though it means that it is portable enough that the current version still runs natively on an Atari ST. The syntax isn’t too hard to follow if you’re familiar with the syntax of C++, C#, Java, or the like, but there’s some weirdness even for C programs. (Many function declarations are actually preprocessor macros so the code can work on compilers with different ways of defining functions with a variable number of arguments.)
Because of this, I don’t actually recommend copying NetHack’s level generation line by line. It is undercommented and nearly three decades of development have left tons of hidden assumptions buried in the code. Or more than three decades: some of this code seems to date to Hack. Still, I think there’s a few things we can learn by looking at its approach.
Helpfully, the NetHackWiki has the source code of NetHack in a relatively easy to access format. A few of the files have been annotated in great detail, though unfortunately that doesn’t include much about the map generator (yet).
Note that when I’m basing this on the code in 3.4.3. This was because it had been the latest version for the past ten years, so I figured it was pretty stable. Right up until 3.6.0 came out and shocked everyone. There’s been a few changes to the code (and it’s formatted slightly differently) so I’ll continue to link to 3.4.3′s version. The essence of the code is pretty much the same.
When Nethack starts a new game, it does some setup of the player and the objects in the game, and then creates the first level by calling mklev(). The name has some historical reasons behind it, but the modern version is pretty straightforward.
In makelevel(), we start by declaring some variables that will be used later:
room_threshold is the minimum number of rooms before a special room can be added. There’s always two reserved rooms (for the up and down stairs) and possibly a third (if there’s a stair to a dungeon branch) so room_threshold will eventually be set to either 3 or 4, after the stairs are added.
The keyword “register” is a somewhat obsolete way to tell the C compiler to keep the variable in memory because we’re going to be using it a lot. Modern compilers do this automatically, but NetHack doesn’t rely on modern compilers.
The game then checks if wiz1_level.dlevel is equal to zero. There’s nothing particularly relevant about this variable itself, it just uses this as a flag to check if things are uninitialized. If this variable is set to 0 (such as by the code that loads a saved game), it assumes that a bunch of other stuff isn’t set either. A quick call to init_dungeons() takes care of that.
There’s a couple of other setup things to do: set level dependent object probabilities (which appears to be only used for for gems?) and clear out the saved information about the current level, such as the number of rooms it has, the list of monsters, and so on.
Once the setup is done, it does a check to see if this is a special level. There’s a entire system for creating these special levels from templates, using the makemaz() function. So-called because if you don’t specify a level, it will create a maze instead (again, this function dates back to Hack). There’s also a separate check here to see if this is the Rogue emulation level, in which case it does the Rogue room generation instead, complete with a ghost of the Rogue player character.
Once we pass all those checks and setup, it’s time to start making the actual rooms, which we’ll discuss in Part 2.
Rolling on a random table is an effective way to abstract a complex system into something that can be quickly resolved. This was borrowed from wargames, which used similar methods to abstract combat results. Early roleplaying games extended
Random results also act as prompts, similar to improv exercises: a constraint to spark creativity.
Adventuresmith is an open-source Android app by
Steve Christensen
with a ton of random generators from many sources, including Stars without Number, Hack & Slash, and the Dungeon World supplement The Perilous Wilds.
Rather than dressing up the results, it just gives you the direct output as you would from rolling on the tables in the source material, and leaves it to you to figure out what to do with the asthmatic orc bandit or the tattooed Templar addict.
Here’s another practical use for procgen: as a more accessible interface to complex data.
KONE, a Finnish elevator company, monitors their elevator data across the globe. To advertise this service, they’ve also created an interface that translates these messages into human-readable conversations, which you can watch and listen to live on their website.
The life of an elevator turns out to involve a lot of waiting around, with occasional bursts of excitement.
Translating a complex data stream into something more comprehensible to humans is useful, particularly if it can also highlight important information and thus avoid the over-exposure that is a common cause of human error.
What’s particularly interesting about this one is that it builds on several different techniques–flocking, genetic algorithms–to create a complete system. None of the underlying algorithms are new: they don’t need to be.
I’d love to see a ton more projects like this, that take procgen techniques and use them as building blocks. There are, of course, quite a few out there already, but there’s no shortage of opportunity.
Take an algorithm, make it yours, and then tell me about what you made!
Today marks the 2nd anniversary of this blog. Now that we’re 584 posts and 1233 followers later, I can definitely say that I’m glad my friend goaded me into starting it.
While there were a lot of new things this year, I felt like it was also a year of building on the past, and I anticipate that this next year will continue that. Some of the upcoming projects I’ve had my eye on are explicitly building on stuff we’ve talked about here. And technologies like using neural networks for generation are rapidly building on past discoveries. I look forward to seeing what comes next.
Speaking of machine learning and mapping multidimensional space into something more comprehensible, this research by James Owen Ryan and Eric Kaltman uses machine learning to place games into 3D space, clustered near other, similar games.
The project uses GameNet, a database of the links between 12,000 games, with the links learned from feeding the Wikipedia pages into a machine learning algorithm called latent semantic analysis. GameSpace maps that data into 3D space, forming a galaxy of games where nearness corresponds to similarity.
Here, for example, is the cluster of Zelda games. Note Elliot Quest down in the corner: I’d never heard of it before, but the algorithm puts it closer to Zelda II than Majora’s Mask 3D (which is further down, outside of this image and closer to the Mario games).
Not too far away, you can find the cluster of Mario games, which are a bit looser. Presumably because the Zelda games are more similar than, say, Super Mario Brothers 2 and Dance Dance Revolution: Mario Mix.
Zooming even further out, thousands of games are visible. The Infocom text adventure cluster is a little ways away, while that bright spot I highlighted on the far side of the galaxy is a tight cluster that contains Far Cry, Borderlands (including Tales of the Borderlands), the Dead to Rights games, and Peter Jackson’s King Kong, among other games.
Of note is that this constellation isn’t directly based on the games themselves, but instead is constructed from how we talk about them. (I’d like to see some game review archives mapped like this. Or some indie game review sites, plus TIGDB. Or the Ludum Dare archives.)
I’d suggest a couple of aesthetic changes to make it a little easier to navigate if they want people to use it as a tool (the ability to orbit, to show labels at a distance, etc.), but even in its current state it’s quite informative.
The best thing I found so far is the Jack Cluster. All the Samurai Jack games, Nightmare Before Christmas games (Jack Skellington), MadWorld (main character: Jack), some Jack the Ripper games, Jack Bros, Puss in Boots (the wiki mentions Jack and Jill), Quantum Break, the whole Dead to Rights series…. a big ol cluster of games with nothing in common but the name “Jack” which the network fixated on
If you want to see it yourself it’s pretty easy to find, since it’s between two very visually distinct clusters. On the left is what appear to mostly be Japanese games - the line running bottom left to top right seems to be all visual novels, except also Akuji the Heartless is in there which I don’t understand at all, and the bottom right thing seems to be manga adaptations. The long line on the right that thins out in the middle is a weird spectrum of music games, with RockBand and Guitar Hero near the bottom, DDR and similar dance games near the otp, and karaoke in the middle i guess. Then right in the middle of all of these is the cluster of games that have someone named Jack in them
Cool example of both the depth of the data set and the limitations of the approach.
One challenge with training neural nets is figuring what, exactly, is going on in them. A company called Graphcore has one solution, which you can see above. They used machine learning to learn about their machine learning. It’s a bit like GameSpace, in that it’s a mapping of complex graph structures into visually-perceivable dimensions.
Speaking of machine learning and mapping multidimensional space into something more comprehensible, this research by James Owen Ryan and Eric Kaltman uses machine learning to place games into 3D space, clustered near other, similar games.
The project uses GameNet, a database of the links between 12,000 games, with the links learned from feeding the Wikipedia pages into a machine learning algorithm called latent semantic analysis. GameSpace maps that data into 3D space, forming a galaxy of games where nearness corresponds to similarity.
Here, for example, is the cluster of Zelda games. Note Elliot Quest down in the corner: I’d never heard of it before, but the algorithm puts it closer to Zelda II than Majora’s Mask 3D (which is further down, outside of this image and closer to the Mario games).
Not too far away, you can find the cluster of Mario games, which are a bit looser. Presumably because the Zelda games are more similar than, say, Super Mario Brothers 2 and Dance Dance Revolution: Mario Mix.
Zooming even further out, thousands of games are visible. The Infocom text adventure cluster is a little ways away, while that bright spot I highlighted on the far side of the galaxy is a tight cluster that contains Far Cry, Borderlands (including Tales of the Borderlands), the Dead to Rights games, and Peter Jackson’s King Kong, among other games.
Of note is that this constellation isn’t directly based on the games themselves, but instead is constructed from how we talk about them. (I’d like to see some game review archives mapped like this. Or some indie game review sites, plus TIGDB. Or the Ludum Dare archives.)
I’d suggest a couple of aesthetic changes to make it a little easier to navigate if they want people to use it as a tool (the ability to orbit, to show labels at a distance, etc.), but even in its current state it’s quite informative.
