Okay, my overly long discussion of random numbers got blocked. I'll message it to quest to see what tripped up the filters.
RPG: How to handle key story elements with randomly generated levels?
I barely played the first game. I like the concept of that game, I could take a look at it as a source of inspiration.
I am not sure I want to go 100% that way. I can live with a portion of irrational layout. The game which is based on (Wizardry) had almost only irrational layout. There might be a few consideration here and there, but the entire maze will not be logical. At least not the generated one.
So far what I have in mind is to have 2 layer of maze. Think like Dungeon Quest tiles, Legend of zelda rooms, or Carcassone roads tiles where each tile side has entry points. Those connections determine the navigation between the tiles, therefore the logic of the maze resolution. The quest and key planning will be made with this high level maze/graph. Also that graph is 3D, as it would include dungeon depth.
Then each tile is a unique 2D generated maze in itself that the user must navigate in. For now, I would assume that all tile entry point can be accessed by any other entry point. But like Dungeon quest and legend of Zelda, there could be tiles where not all connections are possible. For example diagonal split tiles. If I want to go this route, I'll have to change how the high level maze organized to make sure navigation is possible.
Finally, all the objectives of the game could be drawn as a tree of objectives and requirements. Only 1 leaf is the end of the game, other leaf are just extra rewards, side quest or keys to the main path. Still it is possible to make sure that the deepest leaf is the end game, to make sure it's worth the effort.
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.
That worries me a bit. You require a DATABASE to run a Maze/Adventure Game?!?!
Don't you think that is OVERKILL??? If you've played DOOM 1, they use a WAD file which is sort of like a ZIP file with all the textures and such. And then .SAV files to save games and such.
I hope you are using something like SQLite (which is a file-based database)?!
At least tell me you are using a FILE-BASE database not requiring you to INSTALL a separate DB like MariaDB or MySQL... right???
Just ease my worries that you are not required to create and install a DB with the game... That would be such a big turn-off... You don't want to have to INSTALL a separate Database just to play a game.
Also you could use something SIMPLE like JSON... But need to ZIP it to compress the Text File... And name it SAVEGAME.001, etc. 8 characters like in the OLD DOS games... Like DOOM 1 and such.
If a PHP Framework for coding websites. It uses an SQL Database (MariaDB or MySQL) and abstracts all the tables from the developer. Not sure how, I am also learning Bootstrap v5.2 and learning how to BUILD a theme for a websites. When I learned how to code, there weren't much in terms of "Frameworks"... Yes multiple languages like C/C++, Turbo Pascal, Assembler, Visual Basic... But "Frameworks" were not yet popular.
If you look at it from a pragmatic perspective, basically you have: a language and then on top you can have multiple Frameworks...
So in my case, I have PHP > CodeIgniter 4, HTML5 > Bootstrap v5.2 ... So CodeIgniter is a bunch of "Apps" or building blocks you can use for all kinds of purposes without the need to go back to pure PHP to code everything by hand. It handles a lot of stuff related to websites.
Bootstrap is a optimize CSS Framework which takes out all the guess-work to handling the APPEARANCE of the website (Buttons, Check-boxes, Radio-Buttons, Textfields, Tabbed Panes, etc.) Whatever you need in designing forms for websites and how to control the flow of information is all driven by Bootstrap.
So I'm coming in to the 21st Century with a bunch of Frameworks and getting them to work together to build websites. Obviously I like learning too... It's not as if my own "personal" website requires all of this. But it's nice to take time to learn about newer practices and how to work with them.
Obviously jQuery is another Front-Back-End communication layer which relies of Event Handling... I've got to piece together Bootstrap and jQuery... But I believe CodeIgniter 4 will also handle some of the communication... Not sure... Still in progress on learning all this "newer" tech.
Cheers!
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!
You may need the STARTING (X, Y) position when you restart the MAZE. So we have:
1> "SEED" value from which the MAZE is constructed.
2> Starting (X, Y) position.
3> Current (X, Y) position after exploring some of the maze.
4> Ending (X, Y) position to complete the MAZE.
That's about it... For the MAZE, not Wizardry. That you can save in a JSON file for sure or a CSV File or a simple .TXT file.
Cheers.
If you add control characters when using a JSON like format, with text encoding that will explode in gigs. Of course, 256x256x256 is an super huge map, only a crazy person would play a map of this size. Wizardry 1 had a map of size 20x20x10= 4000 bytes * 8-16 = approximately 32-64K. More recent games have bigger maps, including multiple dungeons.
Hmm... From what I know of a MAZE, there are only 2 Dimensions: X and Y. So 256 x 256 = 64kbytes. Then there are LEVELS ... But usually a MAZE is only one (1) level. I know you're not programming for MS-DOS ... And Floppy Disk Drives... But still you don't want such a HUGE file for saving purposes. Even Starcraft Maps are MAX 256x256.
But generating a MAP from a single "SEED" is pretty quick IMHO. Remember it's a mathematical process. The CPU was designed to handle RNG and mathematics. You would need a process though:
1> RNG (0, 1) is this a ROOM? Yes or No.
2> RNG (Max Size) how large is the room (X, Y)
3> RNG (1 to 8) how many exits are there.
4> RNG (Length of corridor) "for each exit".
...
You could use RECURSION instead of procedurally. But both are possible... You just need to understand that it's much SIMPLE to store a few DATA points and RE-GENERATE the MAZE each time you LOAD the game.
Obviously you need to watch for BOUNDARIES (256 or other). But that's pretty much what sums up a MAZE. Sure there are more steps... I haven't explained ALL of them (Corridors split into several "directions" just like exits do...) but you probably (hopefully) get the idea.
Remember if they did it in MS-DOS era on a 360k floppy disk... You should also be able to do that SAME with better HARDWARE (CPU, Memory Speed, CACHE). Don't try to do like some Games that require Gigabytes of Data to RUN. You're ONLY making a MAZE (doesn't require a Degree in Rocket Science).
Hahahaha!
Note #1: I THINK(?) Rogue generates the rooms FIRST and the interconnects the with a series of corridors. That's what I believe that they do... Obviously it depends what kind of MAZE you are generating. My above sample LOGIC was for something like Rogue and could be different than something like a Wolfenstein Level/Maze (which are pre-generated but you can have connecting ROOMS) where you can have one room connect via a door to another room. My example is more like Rogue where you have rooms and corridors connecting to them.
Obviously this is NOTHING like a REAL MAZE (the kind that are all interconnected and winding and that there is only one path to the exit). Again in my Mind, you were thinking more along the lines of "Rogue".
Cheers!
Oh!, that's is an interesting idea I have not considered, to regenerate the maze every time. The outcome is that I am trading space for time. I need to make sure that the maze generation algorithm takes little time, because that will become the save game's loading time.
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.
...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.
I agree that many of today's software contain much "bloat" as you put it. It's mainly because the teams are usually younger devs working with each other and they don't have the OLD "MS-DOS mentality". Like I said you need the GAME and it's SAVE GAMES to fit on a 360k Floppy Disk (back in the day)!
Nowadays it's quite easy to get huge data from things like textures and such, but DOOM's WAD file which was a compressed archive of Textures and such was pretty revolutionary in it's day. Also being one of the first FPS (not THE first... Wolfenstein came before) it also used an interesting map generation tool to design levels where you could not have one player below the other but that there were LEVELS (or heights) like Elevators (platforms that go up and down)... etc.
I remember getting Rogue from my Uncle... It was so cool, he gave me the Floppy with the game. I had two (2) Floppy drives, one for MS-DOS (A:) and one for running games and programs (B:). Even if MS-DOS was a TSR (in-memory) some commands relied upon programs on the MS-DOS disk (like Format for example).
Anyhow... You should always aim to make your code as TIGHT as possible and limit the amount of BLOAT (as @pelle says it). That's why I am really digging CodeIgniter 4 ... Because it has a bunch of "Apps" (like an e-mail app) which can be used by the PHP website and doesn't require you to go down to the LOWEST level (strict PHP commands and code). I think it has like 10 categories of apps... TBH.
It's super lean too with high performance from PHP 7.0+...
You eschew complexity, favoring simple solutions. You want a framework with a small footprint. You want a framework that requires nearly zero configuration. etc...
I'm still learning... Just watched one video and are going to watch some vids from professional training online. He's got an HOUR video about how to create a BLOG from "scratch"... Going to check that one next... Maybe on Friday.
Bottom line: it's seems cool and high performing.
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.
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.
Yes, you need to use the same seed and the same version of the generator to get the same dungeon. Include the version in the save data somewhere.
For maximum future-proofing, retain the old generators from earlier released versions of the game. A new world obviously uses the newest generator, but loading a game file from two or three releases ago would still work. Note that the old generator doesn't need to be precisely the same code... it just needs to make the same decisions. In other words, re-use modules as much as possible between different versions of the generator.
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.
Updates are still a bane for SQL file, but they seems manageable. If an update forces a schema to change, I could keep track of the version in the DB and list all the necessary modification to port a DB from one version to another then apply the modification. Else certain queries could fail. Still, once the game mechanics are solid, there should be little modifications to the DB schema.
Yes, having a fixed schema or at least only make simple additions once you hit version 1.0.0 is probably a sensible goal.
Now that you mention Doom, I made so many maps for Hexen, a Doom engine game. It had the possibility to have scripts to make those unique traps and puzzle. Lot of fun back then. I think there is an open source engine called Zdoom that allows playing those games again on modern computer if you have the wad files. It worked pretty well with Hexen, the high resolution screen now made the texture more beautiful.
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.
There is an interesting topic on that like you given me that ask the question: "How to measure that a level is fun?" His conclusion is to visit every portion of the maze, but there could be a better way to evaluate this. I have see that issue of unfun generated level in a few games. That as the case of 20XX.
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.
...
I think Quake was the first shooter with real 3D levels, unless some more obscure game beat it.
Thanks for the info :)
Mercenary was true 3D, but like I said it was a completely different experience than what we think of as FPS games.
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
![Comments for "RPG: How to handle key story elements with randomly generated levels?" Syndicate content](/misc/feed.png)
It does not matter, ideas and mechanics can be transposed from a medium to another.
Brogue use a seed system to debug the generator. I found it to be a good idea, I would probably do the same. All random number generator use seed (Even in C). Normally you take the time/date, but you could use any value.
With little I have done so far with the new 3D engine, I could easily generate a maze as a demo where you need to reach the other end of the maze. It will not be an adventure, just a classic maze.