Puzzles in a randomly generated dungeon

[Etinarg]

I'd like to start a brainstorming session about puzzles in randomly generated dungeons. What kinds of puzzles could there be? And how would the engine make sure they can be solved?

A classic seems to the the locked chest/door puzzle, that requires a key. It seems trivial first, the dungeon generator only needs to place the key in a part of the dungeon that is reachable for the player from the location where the door is (e.g. not behind the door). But this already looks very tricky on a second sight ... how to procedurally check "not behind the door", and what if a pack of nasty monsters makes the key inaccessible although the dungeon layout would allow the player to reach it?

What other kinds of puzzles can you imagine for a dungeon based game?

[NON]

how to procedurally check "not behind the door"

Why not just this?

Pseudo code:

while (ok==false)
   {
   <place key in random cell>

   <use pathfinder from room entrance to key, with locked door as forbidden cell>

   if (path exists)
      ok = true
   else
      <delete key>
   }

I use this and it works well - if I have counter for how many times it tried to replace the key.
If more than x amount of tries - screw it, no puzzle, unlock the door.

Edit: Or you could do some sort of flood fill from the room entrance, that does not move past the locked door. Then mark those grid cells as true in a Boolean array and make random x & y-coordinates for the key until in an okay grid cell. Probably much faster.

[purestrain]

Actually it is trivial if you have some sort of hierarchie in your dungeon generation process. My dungeons are usually generated as simple graphs in which i place a key in a branch and search for another branch which does not include rooms of the first one (just example).

Currently i can imagine only variations of the key/door puzzle.

- get a key and unlock door/chest (maybe recursive)

- kill a monster and unlock door/chest (could be fun if the monster tries to avoid you and you have to trap it.... placing a trap and hunting it into it)

- follow a given path (e.g. 2 pillars and move in a eight around them)

- two platforms which must be "pushed" (you either move a rock on one, and step on the other... or move rocks/bodies on both of them; throw a object on a platform far away)

- entering rooms in the right direction (example1: treasure will be unlocked if you move in each door counter clockwise, and each door has a sign Example2: "Follow the moon" and each door has a half moon, new moon, full moon whatever)

- put on some items.. ("only a king may pass", so you have to wear a crown)

- turn off / on all torches in a room to see a hidden entrance ("only the darkness tells the truth")

- give a skelleton king on his throne his equipment back and the throne moves away

- reorder some objects in a room (e.g. you see a pattern and a single piece is missing)

- digging at a certain area marked by a pattern (a shiny light at certain times, a cross....)

- you could only pass a bridge with a certain maximum weight (after the first bridgecell the games says: "you feel like any further movement will break the bridge"

- making no noise... would require that your armour/equipment makes noise and the player knows it

..... well, roguelikes are fairly limited; you can't use mirrors to "guide" the light and so on.

Edit:
am i the only one who really hates "try randomly and discard after x tries" - approaches?

Edit2:
minor enhancements and explanations

[NON]

am i the only one who really hates "try randomly and discard after x tries" - approaches?

Well it's a bit dumb, but it works... 
Especially if a couple of thousand tries takes 0.1 seconds.

[Rya.Reisender]

Can random generated puzzles really be interesting and challenging?

I'd rather have a list of 100+ possible puzzle rooms that are randomly placed.

[Etinarg]

Can random generated puzzles really be interesting and challenging?

I'd rather have a list of 100+ possible puzzle rooms that are randomly placed.

That's sure an options and included in the idea of puzzles in a randomly generated dungeon. At least I used this approach in two of my projects - but the player learns the rooms quickly and from that point it's boring again. I must admit though, I didn't make 100 rooms, but rather like 20.

To answer the question: I think they can. Roguelikes randomize a lot of things already, like scroll texts or potion colors for each new game. Some have random artifacts in each new game. I'd say randomly generated puzzles work about as well.

What kind of puzzles would you put in those 100 rooms?

@NON: The floodfill idea works. It's just tricky sometimes to decide weather a door should block the fill ... but if one plays safe, it will always work, just place the key sometimes too close to the origin of the fill. It's not a problem, though.

@Purestrain: Thats a nice list of puzzles already maybe we can find a few non trivial puzzles that are actually fun when randomized.

[Fenrir]

..... well, roguelikes are fairly limited; you can't use mirrors to "guide" the light and so on.

Why not? Use ray-casting.

[Rabiat]

I'm no NetHack fan, but I played it a few times long ago, and came across a puzzle which I liked a lot.

In a branch off the main dungeon, there are some small levels that consist of floor tiles, pits, and boulders. Effectively it's an ASCII version of Sokoban. The only way to reach the down stairs is to push every boulder into a pit. If you solve four levels, there's some reward.

I believe these levels were hardcoded, and one out of several variations would be randomly picked for each level. Generating random solvable Sokoban levels with controlled difficulty could be interesting, in a 'head explodes' kind of way.


Edit: another one is ChessRogue. I've never played it, but restricting (N)PC movement (like chess pieces) looks like a brilliant idea for emergent difficulty. And as far as I can imagine it can be done on freely generated levels, without a need for pathfinding or your memory regurgitating all kinds of NP-completeness.

[Etinarg]

It's a challenge for sure. A nice idea also. Now I must search the web for algorithms of procedurally generation solvable sokoban puzzles

Google points to a few documents that but I had no time yet to read through them all. Sokoban seems to be one of the harder problems for automated solving, but still many of the "hard" problems are easy to generate in a way that makes sure that the results are solvable.

[Z]

See this mini-roguelike: Get Out!!

It is a nice puzzle, and as I mentioned in the thread, there is actually a very easy way to check whether it can be solved (although it has not been implemented, so you can lose because the level was impossible).

[purestrain]

It's a challenge for sure. A nice idea also. Now I must search the web for algorithms of procedurally generation solvable sokoban puzzles

Google points to a few documents that but I had no time yet to read through them all. Sokoban seems to be one of the harder problems for automated solving, but still many of the "hard" problems are easy to generate in a way that makes sure that the results are solvable.

I would just reverse the puzzle; start with the finished situation and pull the blocks; would be enough.

[Vanguard]

I don't think randomly generated puzzles will ever be on the same level of quality as hand-made ones.

I bet that a lot of them would end up being ridiculously easy, and serve as more of a waste of time than an actual challenge challenge, and that occasionally you'd end up with one that makes no sense to anyone except for the computer.

[Fenrir]

What about Rube-Goldberg-style puzzles? The components would trigger each other in a certain way. Some components might only trigger specific components. The machine would be made of randomly arranged components, but it would have some missing that the player would find in the dungeons. Putting the right components in the right places would open new areas in the dungeon, possibly revealing yet more components.

[Numeron]

This might help you out with the colored keys for colored locks thing:

http://www.squidi.net/three/entry.php?id=4

There are a few other gems in there too...

[Vanguard]

What about Rube-Goldberg-style puzzles? The components would trigger each other in a certain way. Some components might only trigger specific components. The machine would be made of randomly arranged components, but it would have some missing that the player would find in the dungeons. Putting the right components in the right places would open new areas in the dungeon, possibly revealing yet more components.

It would either end up being too static to be interesting for replaying it multiple times, or it would end up being so random as to be more or less a guessing game.