Sunday 15 August 2010

Because procedural developers are lazy

The meme of a procedural Zelda is a compelling concept when thinking about procedural generation. The classic Zelda design could be reduced to a the lock and key maze, of which EaS is an excellent example. A lock and key maze requires that every key is placed somewhere in the maze before the lock that opens it, which ensures that the maze is solvable. The puzzle is exploration based, rather than requiring particular problem solving skills, but I would qualify it as a puzzle nonetheless.

The question I have is what other puzzle designs are suited to procedural generation techniques? (With a particular focus on those that produce interesting level design).

Is it possible to procedurally generate Sokoban levels? Explorable match 3 puzzles?

Rather than answer the question myself, I'd like to throw the floor open to suggestions from the readers...

12 comments:

kikito said...

I'd say that one example is a "enemies-with-different-characteristics and terrain advantage vs limited set of capabilities on the player" level.

For example, a Starcraft 2 single player game were some tanks are blocking several choke points and the player needs to deal with that. A frontal attack would be a suicide. Maybe make the invisible unit take the tank on the left, and he flying unit take the one on the right. Or a stealth-based level, where the player has to avoid lots of traps/enemies.

Brian Jeffears said...

http://sites.google.com/site/gentrieve/home

In a way, I suppose Gentrieve approaches this---I surely have run into people that consider the Metroid sensibilities to be something of a puzzly nature.

Otherwise, maybe if the Macro-Maths was amazingly strong you could wrangle something like a procedural DROD RPG: Tendry's Tale?

Matt said...

Sokoban seems like it'd be easy to generate if you just worked backwards from a solution.

Anonymous said...

Procedural generation is generation of content algorithmically.
SokEvo generates Sokoban puzzles by (un)natural selection, which can be considered an algorithm.

wlievens said...

Atually some guy did a thesis on a grammar-based system for generating puzzles of this type. In that case, key-lock is just one possible grmmar rule. You add more rules (boss, alternative path, one-way-route, etc) and then randomly compose the rules to grow a dungeon of your desired size.

Nik Coughlin said...

There are a lot of Sokoban generators, I looked into it not so long ago.

x said...

You could generate various types of switch puzzles randomly. For instance, a puzzle where you have to flip the switches in a certain order, or where a certain combination of switches must be flipped to proceed.

You could also generate various puzzles based on switches that you step on to activate. Like, find your way through the room without stepping on the switches that close the door. Or where you have to step on the switches in a certain order, or move things onto certain switches but not others.

I bet that a lot of types of puzzles could be randomly generated, if not all of them.

The Mad Tinkerer said...

I've been considering doing a text adventure with procedural puzzles (in Inform 7). In addition to the obvious room randomization, it would focus mainly on NPC interaction as well as puzzles (i.e. this iteration, Mandy won't let you in her house until you bring her doll from next door... which is being guarded by a vicious dog, so you first need a hamburger and that night-time cough syrup... etc.).

Also I'd like to see/make a procedural point & click style adventure game.

Also: I noticed when I was playing KOTOR that if you take out the combat sequences and optional dialogue it's basically a set of gates and keys in the first area, and then you get a hub where you can choose between different areas, but each of them still operate under the same principle. The most interesting difference between KOTOR and my procedural Zelda idea, however, is periodical plot development as you open up new areas.

Hmmm... procedural plot development?

Pikalek said...

As for other techniques, Squidi.net theorizes a bit about procedural platform jumping challenges under Mechanic #084 - PCG Platformer.

I think there's a lot of subtext to Andrew's last questions. I.E. Can we determine how many different N move sokobans can be generated in an X by Y sized room without generating them all? If we want to move from pure random generation to constrained generation (I.E. level 15 needs to be a 10 move sokoban in two 5x5 rooms connected w/ 2 narrow hallways), then it seems like we sort of need to know if our constraints are feasible to begin with.

Pender said...

Depends which Zelda we're talking about. Recent Zelda dungeons are a lot more than lock-and-key mazes. It's going to be a long time before a program can spit out random dungeons as engaging and elegant as Ocarina of Time's Water Temple.

The Mad Tinkerer said...

When I say "Procedural Zelda" I of course mean the first one. At least, the first one as the first iteration of the idea. It's the one with the simplest geography, so LoZ and other NES-era games are what I'm looking to for inspiration.

I've been recently playing through Okami again and while the basic gameplay and logic of much of it is similar to the Zelda games(though the monster encounters are more like a traditional JRPG), the actual layout of the levels would be kind-of ridiculous to try and recreate procedurally simply because every area is completely different and very hand-crafted to look and feel like natural landscapes. Not impossible(Spore, as just one example, has very detailed natural-looking proc. gen. environments), but not something you want to tackle as a first project.

Bioshock would be easier. It's an enclosed environment with various corridors and branches and simple fetch quests. Plus there's hardly any friendly character interaction but plenty of variety of random, scripted and emergent encounters. The environments are all indoors with mostly perpendicular walls. Bioshock 2 has a few "outdoor" areas, but they're relatively small and most of the levels follow the same aesthetic as the first game.

Pikalek said...

So, back to the OP, here's a few borrowed puzzles that could be procedurally generated:

Evading as per: yellow vs. red

Platform navigation: Brogue gives you the option of jumping off ledges - a puzzle version could require a series of careful jumps (where exactly was the lava on the map below...)

As a variation of Elig's switch puzzle, Q*bert, esp the later levels.

Warping Maze: original NES Metal Gear (& maybe Zelda?) had a 'maze' where you had to move from one screen to the next in a predetermined order - any deviation would place you back at the beginning screen of the maze.

crack the code: probably has a more 'proper' name, but I can't seem to find it.