In Mystic Empyrean the players create the world as they explore it with a mix of individual authority, shared authority, and random card draws. It's non-traditional in a lot of ways though, so not everyone's cup of tea. It is definitely a worthwhile example of how such a system could be built. Studying the interplay between the system mechanics, character mechanics, world-generation mechanics, and setting conceits to determine how it ticks could be enlightening.
Key to the on-the-fly world generation are the game's authority structure and the nature of the setting and characters.
Authority is shared by all players:
- Everyone has a character and GM duties rotate each encounter round.
- Everyone has opportunities to declare or randomly generate what the group encounters next.
- Important facets of the world and game are divided up and "owned" by different players so that players can appeal to an authority and so players can contribute in ways they enjoy. Different groups will divide things differently, so some might share creating all new realms and NPCs, or one player might enjoy making NPCs and "own" NPC creation, or one player may own a story arc, or each new realm will be created and owned by a different player, or some other division of ownership.
The nature of the setting is specific but also not particular:
- The characters are mutable immortals whose personality determines their nature, appearance, and powers. Personality is challenged and changed by play, influencing nature/appearance/power.
- The world is multi-faceted, with many different realms with vastly different physics and realities all in one shared "multiverse" that the PCs can cross between.
- All realms but the starting realm are lost within all-consuming mists where there is no existence or time, due to an ancient catastrophe. Gameplay is about restoring lost realms into the fabric of reality and exploring/exploiting/helping/ruling/whatever those realms.
- The setting defines seven elements that every thing and every action is composed of and aligned with, and can use these in a card-draw random generator to determine everything from a realm's inhabitants' government style to the fantastic geography to the realm's possible technologies.
- The player characters are rebuilding the world in their own image as they rediscover lost realms and influence how they re-integrate with reality.
The world-generation system, then, relies on the fact that authority is shared and on the nature of the setting to harness the group's creativity to build out from the starting realm. The shared authority means that small contributions build up in unexpected ways into interesting, engaging places and events that nobody needed to construct (or even could have predicted) beforehand. The nature of the setting means that there is lots of room to build anything the players can imagine (really, anything is compatible, the way the world is defined in the book) and individual players can lean on their creative strengths.
The setting also means that there are natural bounds to play, so the mode of play switches to a creative building mode only when one of those limits is deliberately crossed by the group in order to discover what's over there. It handles during-play world creation as well as between-play solo creation, depending on how ownership is apportioned for the to-be-discovered piece of the world. The conceit that the PCs are shaping the rebuilt world in their own image makes the creative play mode parallel what is happening within the game: the player creating a realm represents their PC rediscovering a lost realm and influencing it's unfolding back into reality with their own personality.
The default way of playing is very non-traditional, but it also supports a more traditional GM/players division of labour simply by giving one player ownership of more kinds of things in the world – if all new realms are owned by the "world player", then one player can craft the world to their vision while the "character players" manipulate and explore it. It also spends a few paragraphs on using the system for different genres.
It's not a generic on-the-fly world-building system by far, but it's an interesting game technology and the only one that I know of that actually works seamlessly during play to give both structured results while being flexible and who and how it's used.