I was thinking about exploration as a core part of games.
A big part of open worlds is exploration, yes. Awkwardly, they are also incredibly bad at it: most open worlds have very little worth discovering, and most are vast empty areas with just vague variations in layout. This is especially true in generative open-world games like Minecraft.
Minecraft and other generative world games such as Dwarf Fortress, Terraria, and so on do have interesting things to discover, and exploring is rather fun. In the long run, however, these games boil down less to exploring interesting new areas and more to figuring out which preset terrains are nearby and which you have to go search for. What I mean is that, while the world is endless, the secrets are not. Experienced players are not exploring so much as exploiting known terrains.
Of course, non-generative worlds have the same problem, but in those games you play through the game and stop. In a constructive open-world game, you can keep playing pretty much forever. So it makes sense for a constructive open-world game to allow for exploration forever.
Sounds nice, but there's a lot of barriers to this.
The first barrier is the easy one: pacing. In a constructive game, you tend to construct things. This typically means establishing a home. You need to be careful how you define the concept of "home" and "travel" so that even after the player has built a home, they can continue to explore. As far as I know, that means one of three things.
1) The home is portable (a space ship, for example).
2) Travel is often via teleportation or some similar method.
3) The home is temporary, or some other means of making the player create new homes in new places all the time.
The second barrier is much more difficult: you need to have an infinite number of interesting secrets to explore.
Normally, secrets are custom content by the developer. For example, pre-existing mines in Minecraft, randomized super-monsters in Dwarf Fortress, jet packs in Terraria... it's entertaining, but obviously limited. Even if you try to make it never-ending (for example, by randomizing the nature of each super-monster) it still remains a known thing... just a random variation on that known thing.
This brings up the question of what "new" content really is. If I build a fortress and find a demon on Monday and again on Friday, the demons might be different enough that they provide radically different kinds of challenges. The rareness of the content and the high variability means that I'm always taking a gamble.
On the other hand, if I dig down into corruption in Terraria, it becomes pretty rote after a while. It's a common part of each adventure, and even though the layout varies, you quickly figure out various optimal approaches and go into it with the proper equipment.
To be honest, I think that last bit is important. "Proper equipment".
I think "new" doesn't necessarily have to be completely new. It just has to be a new kind of challenge to make you think on your feet. If you know the parameters of what will happen and you're prepared for them, it's not exploration. It's just mining, just a skill challenge.
To that end, I think this question of "how do you give infinite new secrets" is actually two questions: "how do you give infinite new content" and "how do you continually reframe it to keep the player off-balance".
Reframing is a game design decision of the most basic sort. You have to create a game where the player cannot always be "ready", but you still need to allow them to create - since that's the point of the game. There are a lot of options.
One is that the things the player creates are orthogonal to the content in exploration. That is, the player can create their character's appearance, but not equipment. They can create a castle, but when they go to explore they can't bring anything in it with them. The problem with this approach is that reducing the player to a specific baseline power level is just as static a frame as allowing them to perfectly prepare.
So the other option is to somehow come up with ways to allow them to have erratic power-ups based on their creations. For example, they bring two random items from their stack. Or they keep jumping into the body of a random new colonist, who is equipped with whatever the colony provided her to do her job.
You can also offer unique and varying debuffs, such as metal being forbidden in a given cave, or turning the player into a frog. Granting random upgrades has the same effect - allowing the player to fly will shake up the frame just as much as disabling their jump.
In all cases, balance is tough to maintain. It becomes more and more difficult to guarantee that a given piece of content can actually BE explored. Rather than trying to fix that, it's probably best to embrace it. Let the player come back and make steady progress later, but always with a shaky frame, always with shaky prep. Failing is fine, whether you die or go home.
Anyway, with the frame-shaking in place, we can talk about the big nasty: content.
Exploration requires content. And not just any content: meaningful content. Content that the player will notice.
There are a few subtypes of this.
1) Skill challenge content. This is the sort of content offered by something like Spelunky, where randomly generated segments challenge your mastery of the gameplay. May also be puzzles that challenge your mind - it's the same basic idea. A skill challenge. These can be largely randomized.
2) Color content. This is content that sets a mood and helps pace the play. This is difficult to create randomly just because it needs to vary, but it includes things like grottos, overlooks, tunnels decorated with appropriate objects, shattered columns, polished mirror-walls... things that the player notices when they are in any given area, but don't really have any gameplay purpose. Color content is best when it has context - that is, when the content meshes well with the upcoming/ongoing challenges.
3) Narrative content. Sometimes overlapping with color content, narrative content strongly implies that something is/did/will happen/ning/ed, and typically creates implicit sidequests or, at least, side-narratives. For example, a locked door, the key somewhere else, and the clue to help you find the key. Messages about a monster, scrawled in blood on the wall. A fairy prince who helpfully takes you on a tour of the castle. An alien spaceship hanging in orbit, apparently dead. A ring with a name etched into it.
4) Mechanical content. This is content that has strongly idiosyncratic mechanical functions. This can be mechanical as in actual gears and such, but it usually refers to the game mechanics. For example, if you're generating new monsters, you'll want to be able to generate new abilities for them to use in combat. Just adding a die of damage or a bit of health won't make the monster feel mechanically special. But allowing monsters to have extremely unique and far-ranging abilities will make them a challenge, especially since those abilities will frequently interact with the other three types of content.
All four of these kinds of content can be generated algorithmically, usually by defining prescripted segments. You grab the pieces, alter some details, and glue them together with other randomly-grabbed pieces.
But that only lasts so long, and it's pretty expensive to add in more fundamental content.
So the other option, of course, is to use player-generated content. Since we're talking about a constructive game, that's obviously a good idea. They're already building things, after all.
The problem is mechanical content.
The other three can be created by players. In fact, you can shape your game such that they make those things incidentally as they play, so there's no barrier to resharing it. But mechanical content is both the most difficult and the most important.
I'm not sure how to accomplish it, aside from letting players make mods for your game.
Hm. Just to make things complicated, in a constructive game nearly all mechanical content will relate to objects which can be incorporated into player constructions.
I feel like there's actually an easy way to do this. I just can't quite see it.