The demoscene is a computer art subculture that has its roots in the elaborate intros created by crackers in the early days of commercial software, and evolved into programs specifically created to show off the most awesome graphical effects that can be crammed into as small a filesize as possible. 

The demo above, “The Timeless” by Mercury, fits into 64K, roughly the size of the original Elite. It took 1st place in the 64K category at Revision 2014.

There’s a long history of procedural generation in the demoscene: when file size is so tightly constrained, the demos quickly became optimized for maximum output from minimum input.

The Wager (2011)

Remember of Seven Cities of Gold? The Wager is also a game about exploring a procedurally generated unknown. Though instead of SCoG’s disembarked expeditions, the islands in The Wager are little story snippets or choices, a bit closer to Strange Adventures in Infinite Space. The stories also procedurally distributed, so even if you know that having the parrot will solve this particular encounter, there’s no guarantee that you’ll have previously discovered a parrot this game.

Originally created in the Ludum Dare game jam by Surprised Man (a team of Peter Silk and Kieran Walsh) The Wager has since been expanded with a bit more polish and a few more features.

http://surprisedman.itch.io/thewager

In Ruins (2012)

An experimental game by Tom Betts, who would later go on to make the procedural generation systems in Sir, You Are Being Hunted. In Ruins was a part of Tom’s PhD research, originating in a roguelike geometry test.

Here’s a SIGGRAPH paper on Procedural Generation of Villages on Arbitrary Terrains. Lots of approaches to city generation assume that the ground is flat, but most real-world cities are constrained by the terrain they were constructed on. Especially for older European hamlets, like the villages pictured here.

https://hal.inria.fr/hal-00694525/
http://arches.liris.cnrs.fr/publications/CGI2012.html
https://hal.inria.fr/file/index/docid/694525/filename/template.pdf

Procjam and the future of procedural generation

An article from PC Gamer on PROCJAM 2014. Gives a good retrospective overview of the jam and some of the projects that came out of it.

A quote:

The brief is an unusually broad one for the often constrictive world of game jams—and that’s very much the point. “Often, jams have very tight time constraints or don’t let you use any existing code,” Cook explains. “But I wanted to use this more for the purposes of catalysing exciting work, so I’ve said yeah, use existing code if you want, work in teams, and if you need an extra day take an extra day.”

http://www.pcgamer.com/special-report-procjam-and-the-future-of-procedural-generation/

Procedural generation isn’t just for static things; there’s a related field of procedural animation that generates movement for animated characters and things. In this case, that thing is spiders. 

This video showcases the research of Llyr ap Cenydd and Bill Teahan, for their paper “The dynamic animation of ambulatory Arthropods”. Llyr has a blog where he discusses the VR projects he’s working on, which naturally include some discussions of procedural animation.

Red Blob Games has a ton of articles about game development, including several excellent ones on procedural generation. This one is a look at using polygons rather than tiles to generate a map. It uses Voronoi cells and Lloyd’s algorithm to generate the basic structure and then uses that to further refine the smaller-scale details.

What’s particularly helpful here is the breakdown of the reasoning behind the different sub-generators and how they fit together to create a cohesive map.

http://www-cs-students.stanford.edu/~amitp/game-programming/polygon-map-generation/

Strange Adventures in Infinite Space (2002)

One of the first roguelike-likes (or, as video-game-foliage calls them, rogueloves): Take the ideas of a roguelike, but instead of exploring a fantasy dungeon you’re exploring a procedurally generated star map. 

Unlike the grid-based map of Rogue, the map is primarily node-based (with black holes and nebulas complicating the routes). It has a lot of the elements that later games like FTL would build on. Each star is its own little island of modular content, with items to discover and enemies to fight. The contours of the invisible generation algorithm not only determine the layout of the stars, but also randomly shuffle the items that are the key to progression in Strange Adventures in Infinite Space’s emergent systems.

Digital Eel has made the game available for free, and released its source code, though it’s a bit tricky to get it to run on recent systems. They have also made two sequels which I’ll probably mention here in due time: Weird Worlds: Return to Infinite Space, and Infinite Space III: Sea of Stars, which is currently in Early Access.

Perlin noise is one of the more important noise basis functions. Ken Perlin got an Academy Award for inventing it, which hints at the impact it has had, both on computer graphics and the world in general.

Unlike the randomness of value noise, Perlin noise is coherent: the value of one point is similar to the value of nearby points. This makes it smoother and gives it larger patterns, which is key in generating interesting results in all kinds of procedural outputs.

Here’s a talk by Ken Perlin himself, all about the noise:
http://www.noisemachine.com/talk1/

Here’s a look under the hood, showing how Perlin noise works:
http://freespace.virgin.net/hugo.elias/models/m_perlin.htm

Beneath Apple Manor (1978)

If I’ve learned one thing today, it’s that I’m terrible at Beneath Apple Manor. Created by Don Worth in 1978, it is the earliest known commercially-released RPG. You’ll also note that 1978 puts it before the first version of Rogue, which means that Rogue is technically not the first roguelike.

The images above are of me playing the 1983 hi-res PC version. MobyGames has some screenshots of the 1978 Apple ][ version.

Beneath Apple Manor can be played at the Internet Archive here: https://archive.org/details/msdos_Beneath_Apple_Manor_1978

The CRPG Addict played BAM and exchanged a few words with Don Worth about it.

Don Worth has a website here: http://worth.bol.ucla.edu/ (I had trouble opening it in Chrome, but it was fine in Firefox.) There’s a PC version of BAM available for download from there.