*by structures I mean premade locations/cells added on random positions inside a dungeon
This is the most important thing. As game creators, it is important that we retain the ability to create interesting and thought provoking content.
When we just soley rely on randomization, it takes away from the ability to make content that has ''logic''.
The player should be on his toes most of the time playing, and questioning his surroundings, wondering what could be here, what could he learn from what he sees.
Here is a small crude example of a ''quest''/puzzle i'd like to have in a randomized dungeon.
There is a keep, locked in the dungeon, that has a puzzle required to open the front gate for 30 minutes, and has ''hints'' laid out in the dungeon to help figure out the puzzle.
The puzzle itself is to set the color of stones in a sequenced order.
The hint itself might be something like a red statue, or a fire to signify red. The object would be chosen from an array of items to represent its specific color.
Imagine the dungeon as a 10x10 square (with each square being say, a 30x30 tile area)
Key:
0 - Open Area
K - Keep
E - Entrance to the keep
H - Hint
P - Puzzle
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
Now, we would have to place the keep, which has a pre-made shape. (the keep is placed randomly, but must keep all of it's respected shape)
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 K K K K K
0 0 0 0 0 0 K K K 0
0 0 0 0 0 0 K E K 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
Now that we have placed the keep, we have to place the hints and the puzzle to open the keep. (again, the hints and puzzle are random spots)
0 H 0 0 0 0 0 0 0 0
0 0 0 0 0 K K K K K
0 0 0 0 0 0 K K K 0
0 0 0 0 0 0 K E K 0
0 0 0 0 0 0 0 0 0 0
H 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 P H 0 0 0 0
Now, here comes the hard part. The hints themselves have to give information on where the other hints and the puzzle is located, and must reflect the randomized spots.
An example for this would be a simple riddle like "Three brothers who used to live in the south, all moved out. One brother loved the cold winds, one brother wanted to explore the west, and one brother hardly moved at all"
This riddle might be found at the E, P and H locations on the map.
Now, that riddle has to be generated after the puzzle location is placed, and it chooses how many hints there are for the puzzle.
Lets say the puzzle is a puzzle that you have to do some actions in a sequence.
The ''three brothers'' part is just listing how many hints there are, which reflects how long the sequence is.
The 'live in the south'' part is a reflection of where the actual puzzle location is. There would be an array of phrases dependent on location of the puzzle, with obvious alternatives such as"in the north'', ''due west'', ''due east''.
Then the riddle lists off the brothers, in order of their use for the sequence.
The hints themselves can either roll a direction relative to the map/dungeon it is in, relative to the location of the puzzle, or if it is a red herring or not.
The first part is ''one brother loved the cold winds'', which is a hint at his location. In reality, (and most fiction), the higher north you go, the colder it gets. So the ''cold winds'' is a reference in that the hint might be found in the north.
Now again, there would an array for options when a hint rolls a north location, with other options such as ''one brother wanted to open a snow cone shop'' ''one brother went north'' and so on.
However, this is different than if it would of rolled ''located north of the puzzle''.
The second part is ''one brother wanted to explore the west'' which means that the location must be west of the puzzle itself, rather than just being a pure western location. Wording is important here, as this hint rolled the ''relative to the puzzles location'' part.
The last part ''hardly moved at all'' is again a ''relative to the puzzles location'' roll, which means that this hint can be found relatively close to the puzzle itself.
-------------------------------
The above puzzle has to be generated along with the map itself, and the text itself could be found at the E, H and P locations, but if the sign is there would be a random roll in itself, but must be found at least one of the locations.
The puzzle, when solved, has to open the keep at the E location, which can be as simple enough as removing a gate item, and replacing it after X time has passed. I guess instead of using a location remove an the gate item, we would use UIDs, and remove whatever has the UID.
It must be noted, that the above locations can be placed anywhere on the map.
The above map could even look like this:
H 0 0 0 0 0 0 0 P 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 H 0 0 0 0
K 0 0 0 0 0 0 0 0 0
K K K 0 0 0 0 0 0 0
K K E 0 0 0 0 0 0 0
K K K 0 0 0 0 0 0 H
K 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 H 0 0 0 0 0 0
And the puzzle/hint should be generated to work still.
--------------------
Very long post, but it's always been my dream to have an MMO that plays like Rogue or Nethack, and retains a high level of puzzle solving/critical thinking.
I'm just throwing ideas out there to remind everyone that randomization can be good, but it is more than just the randomized layout or encounters that matter. Puzzle solving itself matters as well, and can be randomized to go along with the dungeons as well. Even scripted events can be incorporated into a randomized way.
PS
On your randomized chest, it's a good idea, it being a different reward every time that chest is found. I just prefer the ''first come, first server' rule, meaning only one person can get the chest, and it doesn't have to have a set location, or be unmovable. After the chest is used, and 10 minutes passed, it should pick a new location to spawn, and even if it spawns at all.