Making a Minecraft Adventure World

As they often do, my thoughts have tuned to Minecraft. Specificlly, what it would take to make a Minecraft Adventure world. For those of you who've never used the dangerous "/gamemode 2" command, Adventure mode is a version of Minecraft where your ability to gather blocks and otherwise manipulate your environment is severely limited, at least in comparison to other Minecraft modes where your only real limits to block manipulation are knowledge and time.

Adventure mode, as the name suggests, is a mode based more around conventional video game interaction rather than the self-motivated, directionless motif of Minecraft. Unlike the remainder of Minecraft, it requires a conscious architect. So what kind of challenges can you pose with a Minecraft Adventure World? 

Gameplay
Puzzles come immediately to mind. Redstone wiring and switches can create paths, mazes can require players to create maps at home, and a given set of items can be used to bypass obstacles (like using a TNT block and flint and steel to destroy a series of obstructing blocks).

Combat is a layup. Throwing the occasional ghast, blaze, zombie or skeleton at a player goes a long way toward setting a difficulty curve for an area. You can even spit out enchanted weapons for them to carry and use. Given a way to draw a player into provoking them, passive mobs like wolves, iron golems, and zombie pigmen make even better opponents. Even the Wither can be an opponent, provided that you have a good reason to make a player assemble one, probably by requiring that a specific area of floor be destroyed. 

Platforming on Minecraft isn't the strongest gameplay element, but it is a legitimate one. Jumping, running, and even sneaking are all movement features that a player can manipulate to further their goals.

Structure
A hub structure could be useful. A central village with villagers could be a base of operations and source of supplies to ready players for their next adventures. Maps could lead players to dungeons or Nether portals, both of which would have inns allowing players to sleep the night away before they plunge into largely self-contained dungeons. Giving out emeralds at the end of each dungeon is a way to ensure that players can get the supplies they need from villagers. Alternatively, you could give out pieces of equipment that help defeat or explore other dungeons. 

Story
I'm not sure what the story would be. "Beat the dungeons. Save the world" is an obvious choice, but you could actually set up dispensers that spit zombies into the villages until you flip a switch in the final room of the dungeon. It's a lot of redstone to run, but it's a way to link dungeon completion to the village and its larger effects on the world. Alternatively, collecting enough Ender Eyes to open the End Portal and kill the End Dragon is a natural progression.

You can support a more complex story thanks to writable books. By having a narration book in each dungeon, you can advance a larger story as players proceed. While you're not going to get anything truly epic, enough story points and effects can come close. Imagine accessing an important dungeon via Nether portal in a distant temple. The actual dungeon is in the Nether, but it's "skinned" as a normal dungeon, but with ghasts and zombie pigmen as natural mobs. When the player beats the dungeon and emerges leaves through a nether portal, they're brought to a temple identical to the first one. The world they emerge back into is identical to the old one, but with a few tweaks. This is accomplished by copy/pasting a region file to a distant part of the same world and using the Nether dungeon to bridge from one into another. Obviously, this is a one-way trip and you have to be careful about changes a player makes to the original environment to address how they're reflected in the future/copy, but it's a way to cheat your way into large scale changes in the world.