Procedural Worlds, Handmade Details

Ultima Ratio Regum is probably the most radically experimental roguelike games that I haven’t talked about here yet. Dr. Mark Johnson gave a talk at GDC Europe 2015 about the balance between using handmade content and procedural content. 

Both ways to create content have benefits and drawbacks, and different kinds of games are better with different ratios between them. For example, Dungeon Crawl Stone Soup uses hand-made vaults to supplement its procgen dungeon layouts, and Spelunky has a progression chain of handmade secrets that must be accessed via mastery of the procedurally generated challenges along the way.

Ultima Ratio Regum is attempting the procedural generation of more abstract, qualitative concepts: not just map generation, but the generation of cultures, societies, religions, and behavior. Since these generators are difficult to build, Mark Johnson supplements them with hand-made unique content. For example, a religious altar generator can create either a totally procedurally generated, or draw from a few hand-made templates.

Mark Johnson posits two types of ways to integrate procgen and handmade content: overlaying, where a handmade thread runs throughout the game, such as in Spelunky or FTL; and integrating, where the two are intertwined, as in Dungeon Crawl Stone Soup and Ultima Ratio Regum.

He also asks the question: do we want to hide the differences between the two parts of the game? He points out that there are good arguments for both approaches, and I’m not sure that all of the potential tradeoffs have been explored at this point. 

“Romanesco 2.0” by Elias Schütt & HellMood

In just 1023 bytes of JavaScript, this fractal visualizer (apparently inspired by an article on Distance Estimated 3D Fractals) distills a lot of complex mathematics into a tiny representation, using less than a thousandth of the space of an average web page.

http://js1k.com/2016-elemental/details/2552

http://js1k.com/2016-elemental/demo/2552

(discovered via Jacob Garbe)

Neural Doodle and Pixel Art

A little while ago, @santiontanon suggested trying to use neural-doodle to upscale pixel art. Alex J. Champandard added some tweaks to improve the support for the process, and now we’re off to the races.

I’ve been running my own experiments, as you can see above. It doesn’t work for every texture, and there’s still a few occasional issues, but the combinations that do work are pretty astonishing.

NeuralDoodle generally takes a content image, and a style image, and translates the content into the style. You can also give it just the style image and seed data and have it synthesize a new image based on what it sees in the original style image.

Here’s a blue rock texture I made with Tilemancer getting interpreted as vines:

And here’s some more textures that used that same blue rock image as a seed. These were done with just a style image (the photographs, in this case) and a seed image (the pixel art blue rock), but no content image. 

Also using a content image results in a final output that more strongly resembles the content image, though with more discontinuities if there’s too great a mismatch between the content and style. You can see how this one doesn’t quite work:

These, on the other hand, came out much better:

As you can see, if there’s a huge mismatch between the content and the style, you may have trouble seeing the content in the result (though playing with the settings can sometimes find a better blend). But they still make for some pretty good images anyway.

Now, there’s a virtuoso pointillism to the practice of pixel art, so this isn’t going to replace all pixel art. Pixel art has already found its evolutionary art niche; new technology replaced all of the pixel art that had technologic reasons a long time ago. (Though we’re likely to get some Minecraft texture packs out of this.) 

But as part of a larger workflow–sketch out a rough idea of the texture you want, let the neural network dream up the details–this is going to be an interesting tool in the toolbox.

algopop:

Evolved Virtual Creatures by Karl Sims, 1994

Karl Sims Evolving Virtual Creatures uses genetic algorithms to evolve 3D animated creatures in a virtual simulation of a 3D physical world. Different goals such as swimming, walking and jumping result in different morphologies. I blogged about this before but hadn’t discovered the amazing video for it.

Rounding out the week, have a video that @algopop found of this procedural animation research. Here’s Karl Sim’s page with some more background information.

These days, Karl Sims is co-founder of a software company called GenArts and is making art installations, like this reaction diffusion simulation.

Map Generation in Lenna’s Inception

It’s worth taking a deeper look inside the procedural generation of Lenna’s Inception, because Tom Coxon has written a lot about it and given talks.

The generator actually starts with a smooth perlin noise map, which gets posterized into discrete height strata–perfect for the top-down 2D RPG style.  

(That’s a useful technique to remember: even if you’re making a map with discrete binary barriers, like an oldschool NES game, you can still use more complex source data for your inputs. Under the hood it’s all math, and harnessing unusual inputs that have a hidden order can help give the map structure.) 

The generator is specifically designed to keep the player in a flow state of not-too-hard-not-too-easy challenges. It uses a lock-and-key system to guide players through the game, encountering challenges appropriate to their level. The key’s don’t have to be literal keys; any tool or ability that gives the player access to new areas can be a key, and any terrain or enemy that blocks a player’s progress if they don’t have the right ability can be a lock.

You’re probably familiar with this kind of pattern: it’s been used by games going back to Doom, Metroid, and, yes, Legend of Zelda.

Since it knows what keys are required to reach certain areas, Lenna’s Inception can use this information to guide the placement of enemies, treasure, and other challenges, making them gradually harder and more complex as the player gains new abilities to deal with them.

The lock-and-key principles could theoretically be used to generate a metroidvania, or any other form of action-adventure where open-world content is gradually unlocked. Tom has released the lock-and-key algorithm as the open-source metazelda library, which you can use in your own games.

Lenna’s Inception also uses the lock-and-key information to place the walls and other barriers in the game. Since it knows what order the rooms (or parts of rooms) can be visited, it can place them dynamically in interesting patterns, and plan out the entire overworld.

The action-adventure structure of quests, puzzles, and lock-and-key progression that was pioneered by Legend of Zelda and games like it is the inspiration for entire genres of games, including those that look quite different. It’s be interesting to see what someone could do by taking these techniques and using them to procedurally generate a Metroidvania. Or Doom campaigns. Or a city for Mirror’s Edge.

http://bytten-studio.com/devlog//2014/09/08/overworld-overview-part-1/

http://bytten-studio.com/devlog//2014/09/15/overworld-overview-part-2/

https://github.com/tcoxon/metazelda

https://github.com/julsam/haxe-metazelda

https://www.youtube.com/watch?v=z6lweIGJYS8

Race the Sun: Behind the scenes

Something I want to do more of on this blog is to hear from the developers who are working with procedural generation and get their perspective on how they dealt with it. There’s a lot of experience out there to learn from, and it’s my hope that by sharing the information I’ll see more people succeed in using generative techniques in their projects.

I met Aaron San Filippo at GDC, and he was gracious enough afterwards to answer some of my questions about how procedural generation fits into Race the Sun:

How does the procedural generation in Race the Sun work?

1. We created an editor that allowed us to hand-design square patterns. The patterns are made up out of objects, which are hierarchies of other objects. So, a flock of birds is 4 birds, and a bird is a torso and two animated wings. These objects are all created in the editor down to the primitive level.

2. The patterns can be sequenced to create things like tunnels and roads etc. but beyond that,the system is a pretty dumb randomized picker. Each region will use up to 10 regions, from a pool of around 100.

3. The game is divided into regions, each region lasting about 45 seconds, punctuated by a brief breather section in between. Each pattern specifies a minimum/maximum region, so we can increase the difficulty of the patterns as you progress through the regions.

Were the regions always part of the plan, or did you add them later?

As I recall, we added the concept of regions after realizing that the pacing of the game wasn’t quite right. It just felt better to have a short break, and then have a distinctly more difficult section - rather than just slowly ramping up the difficulty. Also, the region separation allowed up to queue up pools of objects for each section separately, and so during the downtime in between, objects from the previous region are cleaned up and then objects for the new region are created.

What was your process for deciding the min/max settings for the patterns?

Mostly trial and error I think! Players on average spend most of their time in the earlier regions, so those regions have the most variety. So we designed the patterns for each region for difficulty and variety, and then occasionally adjusted the min/max depending on playtesting, if we felt a pattern was too hard or too easy.

How did the editor and modding work out for you?
The editor was pretty central to our success, since it allowed us to combine procedural generation with hand-authored patterns, and this gives the game a pretty unique flavor. The editor was easy enough to work with and fully featured enough that it allowed Forest (a non programmer) to implement everything without me (the programmer) needing to be involved on a day-to-day basis.

As for user modding - we had a burst at the beginning when we launched Workshop support on Steam - but the modding community never really took off in a big way. Ultimately we’re OK with this, but I’m not sure if we’d release the level editor if we could go back and do it again.

Dwarf Fortress Interview on PC Gamer

This post is mostly an excuse to link to the recent interview PC Gamer did with the elusive Tarn Adams, but it’s not like I ever have a shortage of stuff to talk about when it comes to Dwarf Fortress.

I’ve talked about the history embedded in the simulation, and the new mythology generation, so let’s focus on something else in the interview: the popular bugs.

While procedural generation doesn’t strictly require emergence, designing modular content that combines in emergent ways is a powerful way to get more out of procedural generation, so it does come up a lot.

Bugs are where the emergence escapes the intentions of the designer. Sometimes this breaks the game and makes it less interesting; a dominant choice that unbalances the system. But many bugs reveal unexpected connections. The drunk cats in Dwarf Fortress and the way the ball-and-chain enables the solo eggplant run in Spelunky both reveal something about the system that the designers were unaware of. 

I think emergent bugs are related to what the Oulipo group referred to as the clinamen. The Oulipoians did a lot with the automatic generation of text, but in writing to a strict set of constraints they had a philosophical problem: because they were using a deterministic, mechanical process, how do you reconcile that with the creative act of the artist? 

Enter the clinamen: a swerve that creates free will within the otherwise entirely deterministic system.

In the case of Georges Perec, it was an imperfect knights-tour of the 10x10 building in Life, a User’s Manual that skipped one square. In Dwarf Fortress it’s death-by-carp, cats getting drunk, and all of the other emergent effects that Tarn Adams regularly reports in his development log.

http://www.pcgamer.com/dwarf-fortress-creator-on-how-hes-42-towards-simulating-existence/

Lenna’s Inception

There was quite a bit of interest in Becky Lavender’s research into procedurally generating Legend of Zelda dungeons, but did you know that there’s a procedurally-generated game in the style of Legend of Zelda that you can play right now?

Lenna’s Inception is in early access, but it’s already got a completely procedurally generated map, generated dungeons, procedurally-hidden treasures, side quests, an unidentified potion system, and more.

The game currently has a Gameboy-ish graphics style, though a more colorful updated graphics mode is also in the works.

Despite its not-yet-finished state, there’s a lot of solid use of procedural generation already implemented, and Tom Coxon, the main developer, has talked extensively about the map generation and lock-and-key system the game uses to make the entire overworld and all the dungeons procedurally generated.

An interview with the NetHack DevTeam

Legendarily, the NetHack DevTeam seldom makes public announcements but always Thinks of Everything. In a rare look behind the scenes, John Bridgman interviewed them, using the context of the recent, unexpected update to take a look at what they think about the game.

Whenever I talk to developers, they each have a unique story to tell about how they got into making games, and the NetHack team is evidently no exception. Though their maintenance task is unusual even by major software standards: NetHack 3.6.0 has ports to the VMS and OS/2, among other operating systems (they’d like help updating the Atari, Amiga, NeXT, and Solaris ports).

Counting its Hack precursor, NetHack’s codebase has been around for over thirty years. What keeps people playing that long?

The procedural generation is certainly part of it: each new level is a new, never-before-seen challenge. But it’s not just the procedural generation. Indeed, unlike some other roguelikes, winning NetHack involves a relatively proscribed set of goals you need to complete. (Though it’ll take a while for new players to get good enough to encounter even the first.) As you go deeper into the dungeon, you’ll encounter the fixed landmarks: the Gnomish mines, the Sokoban branch, the Oracle, etc. 

This fits in with the content-heavy approach of the DevTeam that Thinks of Everything: there’s a ton of special cases, unique items, and obscure content in the game, all of which can interact with each other. And many of those interactions have unique messages, because the DevTeam really did anticipate it. As in Spelunky, the emergent effects are what makes the game, but NetHack has orders of magnitude more content then Spelunky. It would take you years to see every combination.

And that’s where the procedural generation comes back in: by only giving you access to a specific subset of its content, NetHack keeps the game fresh. You may never have had an occasion to read a scroll of remove curse confused and hallucinating before, but there’s something unique that happens when you finally encounter that circumstance.

How and why Spelunky makes its own levels (Game Maker’s Toolkit)

If you’re the kind of person that closely follows procedural generation you might have seen this video (or read Derek Yu’s Spelunky book). But my philosophy for this blog has always been to be comprehensive, not timely. No one can keep track of everything in the constant flood of new information that is the internet, and in a few month or years it’ll be new to people who just started to get interested.

The video is a good look at the principles that go into making Spelunky what it is (including the details of the generator’s inner workings). But it also touches on something I’ve talked about a lot here: that the procedural generation moves the player’s process of understanding from figuring out the individual levels to a process of directly figuring out the implications of the individual components.

This is, you’ll note, the exact opposite of what I was talking about yesterday with Race the Sun. There’s no one best way to use procedural generation, and what’s ideal for one game might not work in another game. In Spelunky’s case, I think the major thing that lets this work is that each chunk of content already comes with a dense network of emergent associations. Where Race the Sun’s building blocks are letters in a hyperspeed sentence, Spelunky’s are ideograms or cartouches. 

The way the levels combine the modular content also speaks to the pacing of the game. Just like Crypt of the Necrodancer’s shovel takes advantage of how its level generator works, the deliberate pacing and the way the different elements of a Spelunky level are far enough apart to encounter separately but close enough to emergently combine as you make your way past them is an intimate part of the game.

While you are unlikely to foster an intimate relationship with that one snake on level 2, you will have a relationship with the snakes as a whole. The game’s use of unique signpost content to anchor the generation also lets you develop relationships with the shopkeepers as a group, or the snake pit, or the jetpack. And the emergent results mean that you will remember that one snake that tipped that perfect run into a series of disastrous decisions.

https://www.youtube.com/watch?v=Uqk5Zf0tw3o