Skip to Content
 

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

56 replies [Last post]
FrankM
Offline
Joined: 01/27/2017
Randomness

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

larienna
larienna's picture
Offline
Joined: 07/28/2008
Quote:I think a lot of the

Quote:
I think a lot of the suggestions were because we thought it was for a Board Game and not a video game.

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.

FrankM
Offline
Joined: 01/27/2017
Randomness

larienna wrote:

Quote:
That looks like it might be Dungeonkeeper as a board game.

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.

Quote:
Given the choice, I think you should grab a maze generator that makes "rational" layouts like central corridors.

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.

Quote:
Do the maze generators you have available mark the main through-path for you? You'll want to make sure that your character doesn't fight long and hard to get a key that opens a door to a dead-end.

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.

larienna
larienna's picture
Offline
Joined: 07/28/2008
I think it's possible to

I think it's possible to change the seed during the game. In my case, the maze/adventure generator would be ran once before the game start. Using a seed for the maze would be possible. For the adventure, that is another problem. Since I am using SQL data base to store the quest possible and the generated quest, I will be using the RNG of the SQL engine. Still, if there is a bug of some sort, I could as the player to send his save game and it's maze generation seed. But I am not sure I could allow 2 players to play exactly the same game by sharing the same seed.

Quote:
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.

One idea I had before thinking about maze generator is the possibility to have optional locked doors placed on non-mandatory path that forces you to find an alternate path if you do not have a thief to pick the lock. This would prevent players from always using the same path all the time and force them to explore other portions of the maze. To do this, I would need an imperfect maze.

Like in souls-like game, in one of my game idea, I had that notion of game reset. During a reset, I would change the configuration of locked doors on optional paths.

FrankM
Offline
Joined: 01/27/2017
Seedy

larienna wrote:
I think it's possible to change the seed during the game. In my case, the maze/adventure generator would be ran once before the game start. Using a seed for the maze would be possible. For the adventure, that is another problem. Since I am using SQL data base to store the quest possible and the generated quest, I will be using the RNG of the SQL engine. Still, if there is a bug of some sort, I could as the player to send his save game and it's maze generation seed. But I am not sure I could allow 2 players to play exactly the same game by sharing the same seed.

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.

questccg
questccg's picture
Online
Joined: 04/16/2011
I hope this is all FILE-BASED and NOT full DB...?

larienna wrote:
...For the adventure, that is another problem. Since I am using SQL data base to store the quest possible and the generated quest, I will be using the RNG of the SQL engine...

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.

larienna
larienna's picture
Offline
Joined: 07/28/2008
Yes, it's SQLite. Best C

Yes, it's SQLite. Best C library of the 21st century so far for me. No server required.

Wizardry has tons of data, and all my game ideas, inspired from board games, also have tons of data (ex: NES Koei style war games). SQL database is the way to go. It's super easy and powerful. And once I'll finish reprogramming the user interface, I will be capable of buildings a dialog with only a SELECT query and a format string (like printf). Like I said, super easy.

The maze data is saved into a separate file. Originally, I wanted the "save game" only to be a copy of the adventure's SQL database. The maze would remain in the adventure. Now if I want to generate unique mazes, the save game will be composed of the database + the maze (in separate files), which could create pretty big save games if the maze is huge. I decided to add zlib compression to the maze to handle huge mazes. Having multiple save games using the same maze is also an option, if there is an interest for it (maybe for starting over your game). Manually edited adventures would also be possible.

For now, I am trying to finish my computer science studies. I should be finishing this year (And there will be much rejoicing). I'll see how things goes afterwards. Lot of plans ahead.

Just finished 2 homework, My next homework is to code a MinMax AI for Othello ... at least it will be fun. Maybe I should raise another thread about the subject.

questccg
questccg's picture
Online
Joined: 04/16/2011
I'm exploring CodeIgniter 4

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!

questccg
questccg's picture
Online
Joined: 04/16/2011
Hmm... Not sure about that!?

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

Quote:
You should only require one SEED Value and the maze is generated from all of that.

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!

questccg
questccg's picture
Online
Joined: 04/16/2011
I almost forgot...

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.

larienna
larienna's picture
Offline
Joined: 07/28/2008
Quote:That's really it. There

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

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 also have to make sure that the maze remains read only thought the game, else any modifications to the maze would be discarded when closing the game. Else I need to save the modifications in the database, then when I generate the maze I apply the modification lists in the DB.

As for using the RNG of the SQL DB, I could work around it, preload certain records in memory, then randomly select them myself. So I could do an 100% adventure generation from a seed allowing 2 players to have the same adventure.

By the way, I am not saving a maze in a text file. Each bit of data is valuable. Thinks about it, a maze that can go up to 256x256x256 = takes 16 megs time the size of the structure, the previous maze structure for a single space was 8 bytes. The new one is still a work in progress, but I am aiming for something between 8-16 bytes. That means something between 128-256 megs for a full size map.

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.

questccg
questccg's picture
Online
Joined: 04/16/2011
Let me clarify a bit...

larienna wrote:
Think about it, a maze that can go up to 256x256x256 = takes 16 megs time the size of the structure, the previous maze structure for a single space was 8 bytes. The new one is still a work in progress, but I am aiming for something between 8-16 bytes. That means something between 128-256 megs for a full size map.

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!

FrankM
Offline
Joined: 01/27/2017
Seeds

larienna wrote:
Quote:
That's really it. There should be no other DATA.

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.

larienna
larienna's picture
Offline
Joined: 07/28/2008
I could generate maze

I could generate maze partially, as long as I have the top navigation maze to plan the adventure. But the order by which I explore the various areas would change the resulting layout unless I assign a seed to every maze area/tile.

But again, that depends on the speed of the algorithm. Considering multiple algo are involved, I cannot predict the time it would take to generate the entire adventure, I can only predict the size. If speed is not an issue, then it open up more possibilities.

Yes, I am using multi-level maze, still it's not really a 3D maze since there will be few connections between levels. From 1-4 stairs between two levels, else it would be madness.

As an example: "Wizardry Labyrinth of lost souls" has 20x20 maps, with 6-10 levels, and there is 3 dungeons if I remember correctly.

Handling multiple non-generated map would have been more complicated as it requires multiple files.So my idea was to make a huge map, put all dungeons on the same map and connect them "a la metroidvania". The drawback is that there can be wasted space and I have little chance to use the warp around feature.

But if each dungeon is stored as seed + a difficulty level and using the same list of KEY-REWARD, then having multiple dungeons does not require multiple files. It could even allow another of my game idea to be possible. The concept was to make various missions in different small maps. Generated maps + seed makes it possible.

So very interesting possibilities I did not think about just for the maze generation. For the adventure, using a tree graph, I think it could be possible to implement, as long as I have a varied pool of KEY-REWARDS.

pelle
pelle's picture
Offline
Joined: 08/11/2008
I think a single seed and

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.

questccg
questccg's picture
Online
Joined: 04/16/2011
Bloat-ware and young devs

pelle wrote:
...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...

...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.

FrankM
Offline
Joined: 01/27/2017
Three D!

questccg wrote:
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.

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.

larienna
larienna's picture
Offline
Joined: 07/28/2008
There is a single flaw to

There is a single flaw to saving the map as a seed: Updates. If I update how the maze is generated, like adding new features, I change how RNG will be read therefore how the adventure will look. Maybe I could give the option, for my engine to support this, while not being mandatory.

I used SQLite in my old code and it worked well. Now I am going to extract the code into my user interface engine. Still on my todo list. SQLite almost replace the need for binary files, and stuff like CSV, XML, etc. Even if I code in plain C, and I don't have access to complex data structures like vectors, trees, stacks, queues, etc, SQL does all the complex record management for me. Which allows me to implement almost any strategy game with it. SQL does has some limitation for graph and tree structure querying, but in worst case scenario, you could copy the SQL data into an internal structure and apply your algorithm (ex: A* path finding).

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.

After playing Tunic, I realized that Wizardry had more similarity to Dark Souls than Rogue. So I intend to import more features from Dark Souls, especially the idea of resetting the monsters and other stuff in the dungeon. In one of my project, even if you party dies, it does not matter, some stuff remains, and you can power up your "city" over time which should make the game easier.

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.

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 found, on your link, the maze generator using a binary tree. I could be interesting for the high level graph. Similar to what I had in mind by fusing cells, but the Binary Tree technique makes sure everything is always connected.

pelle
pelle's picture
Offline
Joined: 08/11/2008
FrankM wrote: In the case of

FrankM wrote:

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.

FrankM
Offline
Joined: 01/27/2017
Generational change

larienna wrote:
There is a single flaw to saving the map as a seed: Updates. If I update how the maze is generated, like adding new features, I change how RNG will be read therefore how the adventure will look. Maybe I could give the option, for my engine to support this, while not being mandatory.

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.

pelle
pelle's picture
Offline
Joined: 08/11/2008
larienna wrote:There is a

larienna wrote:
There is a single flaw to saving the map as a seed: Updates. If I update how the maze is generated, like adding new features, I change how RNG will be read therefore how the adventure will look. Maybe I could give the option, for my engine to support this, while not being mandatory.

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.

larienna wrote:

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.

larienna wrote:

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.

larienna wrote:

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.

FrankM
Offline
Joined: 01/27/2017
What's 0.5D between friends?

pelle wrote:
Duke Nukem 3D was still 2.5D, but with even more tricks going on to make it seem like 3D.

...

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.

questccg
questccg's picture
Online
Joined: 04/16/2011
Same with Mechwarrior and FASA Corporation

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...

larienna
larienna's picture
Offline
Joined: 07/28/2008
Descent was 2.99D. Levels

Descent was 2.99D. Levels consisted in a series of cubes that only knew their adjacent cubes, but not their over all position in the space. So you could have 2 corridors that overlap each other and 2 players in each of those corridors would not see each other, they are like be in 2 different dimensions.

There is probably a few articles on the net talking about how to make fun generated level. It's probably more than making the whole level useful.

FrankM
Offline
Joined: 01/27/2017
@roguelike_con

larienna wrote:
There is probably a few articles on the net talking about how to make fun generated level. It's probably more than making the whole level useful.

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

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

larienna
larienna's picture
Offline
Joined: 07/28/2008
I made further R&D. For the

I made further R&D. For the high level navigation graph, I managed to design an algorithm similar to binary tree exploration. You start in 1 tile, connect adjacent tiles if you can, then explore new adjacent tiles and grow again. When using warp around maze, there is no chances of getting stuck in a corner, all tiles are getting explored this way.

Each node is given a random number which determines the priority order to initiate those explorations. Which generate a different navigation graph for each number sequence. Up to N! possibilities where N is the width of the maze in tiles. Even better, I can partition the layout in multiple different connected graph by using multiple starting position and make each graph explore 1 node one after the other.

This navigation graph is like a maze of tiles in dungeon quest or carcassone (roads). By default I could create a maze using any of the algorithm available for each of those tiles. Then I though of Brogue's machines and Dungeon quest tiles where each area can have feature instead of beign just random corridors. It adds more flavor to the dungeon. So I though maybe I could have many tile generation algorithm which not only draw mazes, but could create boss rooms, make the tile layout a puzzle with switches, make it irregular like a cave, make livable areas with lot of rooms,etc.

The main constraint is that the algorithm must accommodate multiple tile size and it must be independent of the theme of the game. So a if I have a boss room design algorithm, it could work for any game theme.

This is the progress so far, I might try to test a few techniques this summer.

Syndicate content


forum | by Dr. Radut