RPG: How to handle key story elements with randomly generated levels?

Okay, my overly long discussion of random numbers got blocked. I'll message it to quest to see what tripped up the filters.

Dungeon Keeper II was better than the original :)

The reason I asked about the main through-path is to ensure that a Locked Door is actually something the player can't simply walk around. Having a "vault" take up one of the map squares should work just fine... the same key can simply open all of its connections to neighboring map squares.

I also second quest's idea on pseudorandom seeds, especially if you can have more than one random number generator active. One is used to generate levels and a completely different one is used for combat and other ephemeral bits. Using a random seed for the combat RNG keeps things unpredictable without messing up level generation.

A statistical analysis tool I used for work, Stata, has two different ways to fake multiple RNGs with a single Mersenne Twister RNG. First, Stata lets you "save" and "load" the RNG's state, so you can really have as many independent pseudorandom sequences as you like. Clunky, but it works. The second method is to use distinct "streams" based on the single seed. Each stream skips ahead 2^128 places in the pseudorandom sequence, wrapping around to the beginning if necessary. Each stream keeps track of its own position, so pulling 1000 draws from stream 1 doesn't affect what happens to stream 2, and you can get consistent repeatable pseudorandom behavior across multiple processors or even multiple machines.

Anyways, having (in effect) different RNGs for levels and combat prevents players from knowing exactly what will happen returning to a saved game. The level will be the same, but the swings and misses will be different.

In the specific case of the Mersenne Twister, the pseudorandom sequence is an eye-watteringly long series of numbers of length (2^19937)-1, or roughly a one followed by six thousand zeroes. That sequence is the same for every user of the Mersenne Twister algorithm anywhere in the Universe, regardless of operating system. The "seed" pre-positions at one of about two billion possible starting points in that list.

Drawing a number from the RNG moves you one step down the sequence. There's a way to specify the exact state of the RNG that would let you come back right where you left off. In Stata, that state string is about five thousand characters long.

Juggling multiple pseudorandom sequences using saved states is cumbersome, and really only useful in high-stakes situations like randomized clinical trials. In a real language like C++, you should be able to simply instantiate two identical RNG functions with different names.

foo() draws pseudorandom numbers from the first "deck" while bar() draws pseudorandom numbers from the second "deck". Each has its own seed and position.

Suppose one master seed is used for foo(), saved as part of the game's save file, that is then used to generate all of the mazes, terrain, etc. in some deterministic order. Another machine using the same seed would build the same world so long as it used the same version of your game. Think Minecraft or Dwarf Fortress.

If you don't want to build the entire world down to the atoms before play starts, use the foo() sequence to generate seeds for each major chunk of terrain, again in some deterministic order. Use those seeds in foo() when building the details at each chunk. The disadvantage is that you won't know who all of the big baddies are ahead of time to offer up appropriate cryptic clues and tavern conversations.

The bar() sequence is used for in-game "dice rolls" like combat and social reactions. By seeding bar() every time a game is loaded (say, number of days since 1JAN1900 times number of minutes since computer was last booted), new runs will be tactically unpredictable.

I think you misunderstood what both @FrankM and me were saying about the MAZE:

Much like @FrankM suggested, games like Minecraft use a SEED to generate the SAME identical looking terrain or landscape (in your case Maze)... So if it is a MAZE that you want players to WALKTHRU ... All you need to put in your SAVE GAME FILE is the "SEED" and a POSITION (X, Y) in the maze when you SAVE your game.

That's really it. There should be no other DATA.

Again furthermore as @FrankM explained it ... You should have a 2nd Random Number Generator which allows you to generate all kind of other things in the MAZE like items and monsters. That could be really random and based on the PCs Clock (getting a seed based on the time since 1970).

That's why the monsters would be different than say the MAZE and it's various paths, corridors and/or rooms.

I don't know if you understood because it's all really quite intuitive and not at all complicated for the MAZE. For the Adventure game which is Wizardry... That is something completely different. I'm just talking about the MAZE ATM. Since you seem to be "misunderstanding" how the save file is only 3 values...

Best!

I suspect this is why a lot of games have loading screens with factoids and quotes :)

You do need to ensure that things get generated in a deterministic way, and that ANY deviation from pristine is recorded in the save file. This is the bane of Dwarf Fortress, which can turn a single seed and settings file into a deep world... but then the save file explodes as the player moves around in Adventure Mode.

The game's author calls it The Pocket Lint Problem.

One suggestion would be to use foo() seeded with something "random" (days since 1/1/1960, plus the age of your dog in hours at the time the game was installed, plus the number of days since install times the number of hours since the game was last run) to generate seeds for each maze and store those in the game's database. That way you only need to generate dungeons as they're entered.

Seed foo() with the dungeon seed to create the maze and puzzles/bosses, branching out to make sure the keys, henchmen, lookouts, etc. are placed. Remember to generate names for these things, too.

At the start of a game, you may want to generate every dungeon, at least to the detail of bosses and puzzles, in order to have a pile of tales and rumors that the player can come across. This would require your dungeon generator to be breadth-first (making all the major obstacles first, then looping back to fill in the details of each) so that you can break off the generation early without losing replicability. Once the rumors and tales are jotted down in the database, you can discard the partially-spawned dungeons.

The only location that needs to be instantiated at the start of play is wherever the player starts. Other stuff can be filled in as the player approaches.

I think a single seed and everything being deterministic from that point on is the way to go and what probably almost all games with random generation do. Brogue by defaults saves full recordings of every game you play and each file is very small because they only need to store the seed and all player commands (key-presses basically).

If the world is big enough (like Minecraft, Dwarf Fortress, Cataclysm: Dark Days Ahead...) I do not think there is any other realistic way than to store the diff between the random world and what it looks like. I guess Brogue and other small games do something similar (technically they could save it as just a recording and play it back from the beginning, but that could be slow?).

Since the projects sounds quite similar to a traditional roguelike, I can recommend taking some time to explore Rogue Basin if you have not already done that. There are many good articles there on how to develop roguelikes (e.g. http://www.roguebasin.com/index.php/Category:Maps for articles about generating maps).

SQLite is amazing. I played around with it a bit and I would not hesitate to use it as a fileformat to store game data. Did you read this article? https://www.sqlite.org/appfileformat.html

I really like the way the SQLite developers think. They make really simple super-portable (and super-free) tools that are very far from the bloat that we see so much of in software today. For my hobby projects for the last two years or so I have started using their Fossil version-control system that is infinitely simpler and less bloated than git (despite including its own web server, user forum, bug tracker, wiki, and some other things...). It is used for version control of SQLite (can be seen here: https://sqlite.org/src/doc/trunk/README.md) among other things. I use git as well for my other projects and at work, but I think fossil fits better for small projects (one or a few developers) that do not need all the weird things you can do with git.

Both Wolfenstein 3D and Doom used two-dimensional maps; they just used fantastically clever tricks to make them appear 3D.

Prior to Wolfenstein 3D, plenty of games rendered first-person views of dungeon maps... they just constrained the player to looking exactly North, South, East, or West at every step with 90-degree turns. Floors and ceilings could have textures just as easily as the walls. (There were also truly 3D games like Mercenary, but everything was wireframe graphics with no occlusion, so they were a very different experience. To give you an idea of just how long ago that was, one reviewer cautioned potential players that Mercenary requires a color TV.)

Wold3D gave the illusion of smoothly turning in the dungeon maze because the top half of the background was "ceiling color" and the bottom half "floor color" and the maze was designed that you could never see to the "horizon" where those halves meet. Every "tile" was either wall or open space, and there could be one object in each tile. That object would always be facing the player (which looked odd when that object was supposed to be a table).

In the case of Doom, the tiles became arbitrary polygons, floors and ceilings could had textures again, and each tile had a height attribute. It was called 2.5D. The game rendered all of this to appear fully 3D, though if you look carefully you'll note that every surface is either horizontal or vertical. Since the map is really 2D, you could shoot at enemies standing above or below your level without having to tilt your gun up or down. One bizarre artifact was that a melee attack could hit someone at a very different elevation.

Duke Nukem was, to my knowledge, the first FPS with an actual 3D map.

Duke Nukem 3D was still 2.5D, but with even more tricks going on to make it seem like 3D. You could never have one sector above another sector in the same spot IF both were visible to the player at the same time. Doing so resulted in bad glitches on the screen. However you could fake small amounts of real 3D because you could position sprites horizontally and flag them as solid (player could not fall through them) so you could build extra floors and walls using sprites (and any texture used to paint floors and walls could also be placed as a sprite if you wanted to). It had some strange effects (I do not remember the details) and it could look weird because light levels did not affect them the same as the real ground/walls/ceilings. The game almost never used that.

Since two sectors could be above each other as long as the player could never see both, you could also do some tricks with making sure ramps/stairs between levels were created in such a way that there was no location the player could stand that would allow them to see both levels. With careful planning the illusion worked (especially if you used some of the sprite tricks).

Most of the time the levels are just carefully made so that for instance when there are several windows in the same building you can never look into rooms that are directly above each other. And there is never a roof you can walk on on top of a building if there is a room below that you can see. Most of the time everything is just 2D like in Doom. The editor also becomes a bit messy when you do sectors on top of other sectors.

I am credited in one of the popular unofficial FAQs for making Duke Nukem 3D maps that circulated shortly after the game was released. I was on a the 3D Realms forum when the game came out (I had it pre-ordered!) in 1996 where a bunch of people got together to help uncover all the hidden tricks and stuff you could do with the partially documented editor that came with the game. Unfortunately the forum no longer exists, but at least some of the content was saved into various documents like that FAQ.

I think Quake was the first shooter with real 3D levels, unless some more obscure game beat it.

That is to be expected, so you probably save the version together with the seed, and the game always has to be able to generate terrain using old versions. Some games get away with saving everything that has been generated instead (only the parts of the world that the player has actually visited), but that can also have some strange effects if you move save-games between different versions. Another option of course is to simply refuse to load too old saved games (previous major version or whatever) to avoid that problem.

Yes, having a fixed schema or at least only make simple additions once you hit version 1.0.0 is probably a sensible goal.

I have some open source Doom engine installed that I used to play Doom bought from gog.com on my Linux desktop, but I do not remember what version I ended up using. There are quite many different ones, especially since the original Doom source code (same as for Wolfenstein 3D and Quake) were released as open source many years ago.

I also noticed that article and skimmed it a few days ago (good clickbaity title!). I think it had an interesting method for placing stuff in the maze (measuring distances from the closest path through the maze) even if that did not have so much to do with the title.

It too was 3D and FPS ... But the genre had not evolved much past that until games like Wolfenstein, DOOM and Quake came around. That's probably when they first coined the acronym "FPS" (First Person Shooter). They were more categorized as "Simulators" and things like the "Wing Commander" series also pushed the boundaries of 3D too... And then you have "X-Wing" and "Tie-Fighter" and those games that also pushed "Simulators" to their limits even further.

The bottom line is that those games were all CATEGORIZED as "Simulators" ... And not FPS even thought the game do share similarities with 3D (or 2.5D as @pelle stated).

So I agree with everyone assessment that the "Simulators" were 3D a lot before the FPS "genre" was even coined...

There's a whole convention about them, Roguelike Celebration (@roguelike_con).

Here's the URL/Link: https://www.roguelike.club