Game seed


Questions, Explanations, Howtos

bel

Cocytus Succeeder

Posts: 2184

Joined: Tuesday, 3rd February 2015, 22:05

Post Monday, 26th December 2016, 07:24

Game seed

I sometimes play brogue, and there is a "game seed" there which determines all item/level generation, so the same game seed will lead to the same game. This allows a pseudo-multiplayer option for contests etc.

I recall some old post which said that crawl has some rudimentary support for this, but it doesn't work very well. Can someone tell me how it is implemented in crawl, what are the limitations etc. and tentatively, how much work it would be to implement this fully?
User avatar

Zot Zealot

Posts: 982

Joined: Monday, 29th September 2014, 09:04

Post Monday, 26th December 2016, 08:42

Re: Game seed

Crawl uses the same RNG for every RNG roll, so things like taking a different path through D:1 will change what monsters roll to detect the player through stealth, if you detect traps, etc etc. This means the dungeon layout of further floors is not constant. Therefore, Crawl's "seed" support doesn't really result in the same game for different people, even if you replay the same seed several times they will feel like completely different games.

For this message the author chequers has received thanks:
bel

Ziggurat Zagger

Posts: 8786

Joined: Sunday, 5th May 2013, 08:25

Post Monday, 26th December 2016, 20:09

Re: Game seed

chequers wrote:Crawl uses the same RNG for every RNG roll, so things like taking a different path through D:1 will change what monsters roll to detect the player through stealth, if you detect traps, etc etc. This means the dungeon layout of further floors is not constant. Therefore, Crawl's "seed" support doesn't really result in the same game for different people, even if you replay the same seed several times they will feel like completely different games.
You can even change the state of the RNG on the character selection screen, so two games with the same seed and the same character don't even necessarily generate the same D:1.

bel

Cocytus Succeeder

Posts: 2184

Joined: Tuesday, 3rd February 2015, 22:05

Post Monday, 26th December 2016, 20:48

Re: Game seed

chequers wrote:Crawl uses the same RNG for every RNG roll, so things like taking a different path through D:1 will change what monsters roll to detect the player through stealth, if you detect traps, etc etc. This means the dungeon layout of further floors is not constant. Therefore, Crawl's "seed" support doesn't really result in the same game for different people, even if you replay the same seed several times they will feel like completely different games.

Yes, I know the way it's done right now doesn't work. I am asking, what needs to be changed in the code for it to work, and how hard it would be. Is there something existing, which one could build upon?

Dungeon Master

Posts: 1613

Joined: Thursday, 16th December 2010, 21:54

Post Monday, 26th December 2016, 20:58

Re: Game seed

To implement it fully would probably be relatively feasible, but a lot of work - everything related to dungeon generation would need to use its own RNG with a separate seed (as is currently done for randomised elements of the UI such as elemental colours - see ui_random() and the things that call it, and the rng_type enum). The other option that's been mentioned in the past would be to pre-generate the entire dungeon but there's a pretty substantial list of things of issues that would need to be solved for that to work at all.

For this message the author Kate has received thanks:
bel

Ziggurat Zagger

Posts: 6454

Joined: Tuesday, 30th October 2012, 19:06

Post Monday, 26th December 2016, 21:43

Re: Game seed

MarvinPA wrote:To implement it fully would probably be relatively feasible, but a lot of work - everything related to dungeon generation would need to use its own RNG with a separate seed (as is currently done for randomised elements of the UI such as elemental colours - see ui_random() and the things that call it, and the rng_type enum). The other option that's been mentioned in the past would be to pre-generate the entire dungeon but there's a pretty substantial list of things of issues that would need to be solved for that to work at all.

Also once you got the rng for dungeon/monster/item generation on a separate seed from everything else, you would need to ensure that the same seed was used for each level, if the levels were generated in a different order, they would be generated differently.

You could either pregenerate the whole dungeon (with the associated overhead), or track a different seed for each level (pregenerating each potential level's rng seed from the root seed and storing them for later might be a plausible way to do that)
Spoiler: show
This high quality signature has been hidden for your protection. To unlock it's secret, send 3 easy payments of $9.99 to me, by way of your nearest theta band or ley line. Complete your transmission by midnight tonight for a special free gift!

For this message the author Siegurt has received thanks:
bel

bel

Cocytus Succeeder

Posts: 2184

Joined: Tuesday, 3rd February 2015, 22:05

Post Monday, 26th December 2016, 22:26

Re: Game seed

Siegurt wrote:Also once you got the rng for dungeon/monster/item generation on a separate seed from everything else, you would need to ensure that the same seed was used for each level, if the levels were generated in a different order, they would be generated differently.

You could either pregenerate the whole dungeon (with the associated overhead), or track a different seed for each level (pregenerating each potential level's rng seed from the root seed and storing them for later might be a plausible way to do that)

I can think of only one case where levels in a branch may be generated out of order, namely shafts. If I get shafted from D:10 to D:12 without seeing D:11 and then go upstairs to D:11 from D:12, does D:11 generate after D:12?
User avatar

Zot Zealot

Posts: 982

Joined: Monday, 29th September 2014, 09:04

Post Monday, 26th December 2016, 23:43

Re: Game seed

Currently yes

Ziggurat Zagger

Posts: 6454

Joined: Tuesday, 30th October 2012, 19:06

Post Tuesday, 27th December 2016, 01:03

Re: Game seed

bel wrote:
Siegurt wrote:Also once you got the rng for dungeon/monster/item generation on a separate seed from everything else, you would need to ensure that the same seed was used for each level, if the levels were generated in a different order, they would be generated differently.

You could either pregenerate the whole dungeon (with the associated overhead), or track a different seed for each level (pregenerating each potential level's rng seed from the root seed and storing them for later might be a plausible way to do that)

I can think of only one case where levels in a branch may be generated out of order, namely shafts. If I get shafted from D:10 to D:12 without seeing D:11 and then go upstairs to D:11 from D:12, does D:11 generate after D:12?

Thats the only way i can think of for a level within a branch to get generated out of order, but you could go back and forth between branches any number of times to generate individual levels in weird orders.

It might be possible to maintain a separate rng state for each branch, but it would be much simpler to just maintain a pregenerated random list of seeds for each level, then generate the level from that seed whenever you got there.
Spoiler: show
This high quality signature has been hidden for your protection. To unlock it's secret, send 3 easy payments of $9.99 to me, by way of your nearest theta band or ley line. Complete your transmission by midnight tonight for a special free gift!

Tartarus Sorceror

Posts: 1739

Joined: Tuesday, 13th March 2012, 02:48

Post Tuesday, 27th December 2016, 19:53

Re: Game seed

Siegurt wrote:it would be much simpler to just maintain a pregenerated random list of seeds for each level, then generate the level from that seed whenever you got there.


Even simpler to maintain just a master dungeon seed, then when generating a level, concat the level number to the branch id and xor that with the master seed to get your level seed.

Ziggurat Zagger

Posts: 6454

Joined: Tuesday, 30th October 2012, 19:06

Post Wednesday, 28th December 2016, 00:32

Re: Game seed

Rast wrote:
Siegurt wrote:it would be much simpler to just maintain a pregenerated random list of seeds for each level, then generate the level from that seed whenever you got there.


Even simpler to maintain just a master dungeon seed, then when generating a level, concat the level number to the branch id and xor that with the master seed to get your level seed.

I am not sure that using a psudohash algorithm is any simpler than using a psudo random number generating algorithm. I mean you would have to write some super simple code either way (to either store a few numbers or generate them in a deterministic way)

I guess i had in mind the 4 or so lines of code to loop through and populate an array at game start, and you are suggesting the 4 lines of code to implement that trivial hashing function (you store one number, i am storing a couple dozen)

I think either implementation is so trivial that claiming one is simpler that the other is silly.
Spoiler: show
This high quality signature has been hidden for your protection. To unlock it's secret, send 3 easy payments of $9.99 to me, by way of your nearest theta band or ley line. Complete your transmission by midnight tonight for a special free gift!

Tartarus Sorceror

Posts: 1739

Joined: Tuesday, 13th March 2012, 02:48

Post Wednesday, 28th December 2016, 04:47

Re: Game seed

I'm at a disadvantage here since I'm not as familiar with the crawl codebase... but wouldn't my way be less likely to break savefile compatibility when branch lengths change or whatever?

bel

Cocytus Succeeder

Posts: 2184

Joined: Tuesday, 3rd February 2015, 22:05

Post Wednesday, 28th December 2016, 08:47

Re: Game seed

I tinkered around with the code a bit. What Siegurt said is accurate and rather easy, at least in principle. You just increase the number of random number generators pre-generated (currently it is 2, for gameplay and UI; can just make it 100000), assuming it doesn't affect performance.

We just need number of RNGs at most number of branches times the maximum number of levels in a branch. The easiest way is to assume that the latter is at most 100 (or 1000 or whatever), then the index of the rng would be simply (100 * you.where_are_you + you.depth). Since levels are generated only when the player visits them, these things would always be available to you. Then, it is just a matter of replacing some random2 functions with, say, dungeon_random2 (similarly for other functions). Combat, god powers etc. would still be separate, so the vast majority of function calls do not need to be touched. Maybe one in 10 files would need to be modified to call the new function.

As MarvinPA said above, it would not be hard to implement this, it would just take some time.
User avatar

Zot Zealot

Posts: 982

Joined: Monday, 29th September 2014, 09:04

Post Wednesday, 28th December 2016, 11:23

Re: Game seed

There is a thread from about a year ago where someone else said the same thing, then found a few corner cases and disappeared. It would be nice if anyone attempting this does their development in the open, so others can help out.

For this message the author chequers has received thanks:
bel

bel

Cocytus Succeeder

Posts: 2184

Joined: Tuesday, 3rd February 2015, 22:05

Post Wednesday, 28th December 2016, 12:40

Re: Game seed

Are you talking about this post?

For this message the author bel has received thanks:
chequers

Snake Sneak

Posts: 91

Joined: Saturday, 6th August 2016, 18:03

Post Saturday, 31st December 2016, 02:11

Re: Game seed

There may be one alternative without messing with the rng: think about a descriptor. Once a level (as in shape, items, creeps) is generated then write a binary string like in hashes or bitmaps images. It would just require an importing method to bypass the generator.
My 2 cents

Ziggurat Zagger

Posts: 6454

Joined: Tuesday, 30th October 2012, 19:06

Post Sunday, 1st January 2017, 18:04

Re: Game seed

neverEnough wrote:There may be one alternative without messing with the rng: think about a descriptor. Once a level (as in shape, items, creeps) is generated then write a binary string like in hashes or bitmaps images. It would just require an importing method to bypass the generator.
My 2 cents

Isn't that just saving and loading?

Part of the appeal of the "seeded" game is for things like having multiple people play through the same dungeon separately, so you can have two people play through the exact same, completely unseen dungeon.

You could accomplish that, as was already said, by pregenerating all levels and saving/loading them, however pregenrating has it's own technical problems, at least as complex as what was being discussed with the rng. And if you aren't inplying pregenerating then what, from an already-played game? Aside from missing out on the "unseen" factor, what do you do with levels that were never created?
Spoiler: show
This high quality signature has been hidden for your protection. To unlock it's secret, send 3 easy payments of $9.99 to me, by way of your nearest theta band or ley line. Complete your transmission by midnight tonight for a special free gift!

Snake Sneak

Posts: 91

Joined: Saturday, 6th August 2016, 18:03

Post Thursday, 5th January 2017, 02:01

Re: Game seed

Siegurt wrote:
neverEnough wrote:There may be one alternative without messing with the rng: think about a descriptor. Once a level (as in shape, items, creeps) is generated then write a binary string like in hashes or bitmaps images. It would just require an importing method to bypass the generator.
My 2 cents

Isn't that just saving and loading?

i'm not sure, i didn't check the code. If floors are saved as game maps then yes. If saves are a complete dump of the current progress then not. Obviously is a good place to start with if u can save some from reinventing the wheel.

Siegurt wrote:
Part of the appeal of the "seeded" game is for things like having multiple people play through the same dungeon separately, so you can have two people play through the exact same, completely unseen dungeon.

You could accomplish that, as was already said, by pregenerating all levels and saving/loading them, however pregenrating has it's own technical problems, at least as complex as what was being discussed with the rng. And if you aren't inplying pregenerating then what, from an already-played game? Aside from missing out on the "unseen" factor, what do you do with levels that were never created?

U can create them by triggering a bot.

As outsider i can't really give factual advices, but i tried to give a different view of it since the proposal sounds like a not mainline feature and timesaving solutions (hacks) are often the key to have such good ideas working.

Sorry i'll join coding discussions only when i'll be involved into the code, sounds fair to prevent dummy spams.

neverEnough wrote:My 2 cents

bel

Cocytus Succeeder

Posts: 2184

Joined: Tuesday, 3rd February 2015, 22:05

Post Friday, 6th January 2017, 19:45

Re: Game seed

Can someone familiar with the code tell me the following:

Are branch placements determined at the start of the game? I see in ng-init.cc a function called "initialise_branch_depths()". Also, in wizmode, "&:" lists all the branch placements and altars, so I'm guessing they are all determined at the start.

Shoals Surfer

Posts: 270

Joined: Sunday, 23rd March 2014, 23:51

Post Saturday, 7th January 2017, 14:22

Re: Game seed

bel wrote:Can someone familiar with the code tell me the following:

Are branch placements determined at the start of the game? I see in ng-init.cc a function called "initialise_branch_depths()". Also, in wizmode, "&:" lists all the branch placements and altars, so I'm guessing they are all determined at the start.

I believe they must, or the Ash overflow altar that shows you which Lair branches you have that game wouldn't work.

Ziggurat Zagger

Posts: 6454

Joined: Tuesday, 30th October 2012, 19:06

Post Saturday, 7th January 2017, 21:56

Re: Game seed

Floodkiller wrote:
bel wrote:Can someone familiar with the code tell me the following:

Are branch placements determined at the start of the game? I see in ng-init.cc a function called "initialise_branch_depths()". Also, in wizmode, "&:" lists all the branch placements and altars, so I'm guessing they are all determined at the start.

I believe they must, or the Ash overflow altar that shows you which Lair branches you have that game wouldn't work.

I know the branch depths (and s branch selection) are pre determined, i don't know off the top of my head for things like timed portals, and vault-placed portals (like the hell portal in lair)
Spoiler: show
This high quality signature has been hidden for your protection. To unlock it's secret, send 3 easy payments of $9.99 to me, by way of your nearest theta band or ley line. Complete your transmission by midnight tonight for a special free gift!

For this message the author Siegurt has received thanks:
bel

bel

Cocytus Succeeder

Posts: 2184

Joined: Tuesday, 3rd February 2015, 22:05

Post Monday, 16th January 2017, 14:01

Re: Game seed

I have set up a fork on github, branch "seeded_crawl".

I tried to implement seeding using path of least resistance. Also, I have done minimal testing. Here's what I've done so far.
(a) Increase number of RNGs to 100000.
(b) Each floor uses a separate RNG. Index is you.where_are_you * 100 + you.depth. I added a flag generating_level and modified get_uint32 and get_uint64 to return numbers from the indexed RNG if the flag is true.
(c) Pregenerated floors at the start of the game (only partially done). I did this by using the wizmode function _wizard_go_to_level and running it for D:2, D:3 and so on. If it broke some things, I simply special cased them. It kind of works.

Here's what seems to work (again, I have done minimal testing):
Items, shops, uniques, portal vaults are fixed at the start of the game. Boris is a special case which I'm ignoring.

Issues:
(a) Since portal vaults depend on the order in which you visit the floors, there should be a "canonical ordering" of visits. I plan to use the following (only partially implemented):
D -> Lair -> D -> Orc -> D15 -> 2 lair branches one after another -> vaults 1-4 -> Depths 1-5 -> Elf -> vaults 5 -> slime -> crypt -> tomb -> Zot.
(b) Portal timers (like ice cave) probably start when one generates the level, which means the start of the game. This means they will probably be unreachable in time. If someone can tell me which files I should be looking at to fix this issue, it will be great.
(c) Dungeon overview/travel shows empty floors which have been already pre-generated, but not visited yet. I'll probably add a flag "visited" to each floor to make it clear that the player hasn't actually seen the level yet. Again, someone who knows the code can probably tell me which files I should be looking at.
(d) Haven't decided how to handle Pan, Abyss and Hell, but probably shouldn't be too different.

bel

Cocytus Succeeder

Posts: 2184

Joined: Tuesday, 3rd February 2015, 22:05

Post Friday, 20th January 2017, 17:01

Re: Game seed

Need coding help:

How are portal vaults like Ice Cave and Labyrinth placed, and how is their timer determined? I am unable to find this in the code. Pointers to files or functions which do it are enough.

Dungeon Master

Posts: 1613

Joined: Thursday, 16th December 2010, 21:54

Post Friday, 20th January 2017, 19:21

Re: Game seed

I sent some quick !tells after you asked in -dev the other day, but to go into a little more detail:
Placement happens by the chance lines in the entry vault definitions which is usually handled in a Lua function (for example, the e.chance(500) line in ice_cave_portal() translates to a 5% chance per level in the depth range). That function also sets up a timed_marker for the timer, see dat/dlua/lm_timed.lua - you can see that it gets started when the dgnevent "entered_level" triggers, so you presumably want some new kind of dgnevent for creating a level but not entering it. Another separate thing that might need its own separation of "creating a level" vs "entering a level for the first time" if you haven't already is the various other effects that trigger only when entering a level for the first time - see just_created_level in files.cc.

Mostly I have very little knowledge of vault and Lua stuff so somebody else might be able to give better information on the portal vault handling in particular.

For this message the author Kate has received thanks:
bel

bel

Cocytus Succeeder

Posts: 2184

Joined: Tuesday, 3rd February 2015, 22:05

Post Saturday, 21st January 2017, 10:50

Re: Game seed

Ok, that explains it: I was ignoring all the Lua stuff because I, uh, don't know Lua. This is probably a good excuse for me to learn it, or at least the basics of it.

Anyway, I looked at the .des files for sewer, ice cave etc. and some of the Lua code in lm_timed.lua. As for the C++ files, I looked at mapmark.cc and l-dgnevt.cc. The latter file is the only one where I found the "entered_level" trigger (using grep). I am not much the wiser though.

It would be nice if someone could tell me how exactly the "entered_level" event is triggered in the C++ code / lua code. I'm guessing somewhere in dungeon.cc, but not sure where. Knowing the answer to this question would probably tell me how to add a trigger called "created_level" which is separate from "entered_level".

For this message the author bel has received thanks:
shping

Dungeon Master

Posts: 1613

Joined: Thursday, 16th December 2010, 21:54

Post Saturday, 21st January 2017, 13:06

Re: Game seed

Look for DET_ENTERED_LEVEL (and the other DET_ enums for a general sense of how it's used on the C++ side) - l-dgnevt.cc is translating from the dgn_event_type enums to the Lua calls, it looks like.

For this message the author Kate has received thanks:
bel

bel

Cocytus Succeeder

Posts: 2184

Joined: Tuesday, 3rd February 2015, 22:05

Post Monday, 23rd January 2017, 18:46

Re: Game seed

I have mostly finished coding a playable, mostly-working seeded game. It is available at the git repository mentioned above. Again, it needs more playtesting; I have only done a minimal amount. I have only tested with console so far, but I believe there shouldn't be any major problem with tiles.

What to do:

Start up the game by typing "crawl -seed <integer>" to seed the game. The game will prompt you for a keypress and take a little bit of time (takes about 15 secs on my machine) to pre-generate the dungeon. Then it's a normal game.

How it works and what works:

  • Each floor has a separate RNG seed, chosen in a deterministic fashion. This means that for a given game seed and given floor, the RNG seed is fixed. For Pan, if you have seen 3 Pan levels, the next one is assumed to be Pan:4. Same thing with Bazaars.
  • All finite branches of the game are pre-generated. This means D, Lair, Orc, Lair branches, Vaults, Elf, Depths, Crypt, Tomb, Zot, Vestibule and all Hell branches. This means that all the initial monsters, items, shops, portal vault locations (like Ice Cave) and uniques are fixed. Of course, more can be generated randomly during the game.
  • Pandemonium and the portal vaults themselves are not pre-generated. However, because I have given them each a separate seed index in a deterministic manner, they should have the same layout (and runes etc.) for a fixed seed. I tested it a little bit (for instance, going into Pan through separate gateways in two separate games with the same seed, and they both had the same layout). One cannot of course guarantee the fixedness of uniques, also perhaps artifacts etc. in Pan. Monsters like Ignacio and Cerebov (if you didn't kill it) can appear in a non-fixed manner (I think, not sure).
  • Abyss is probably totally random, though the initial map is probably fixed. I haven't really tested this.
  • Combat is totally random and not bound by the RNG of the level.

Issues:
  • There are some interface issues, which don't affect gameplay. The most noticeable one is showing empty screens for levels which have been generated but not visited yet, for intstance if you go downstairs from the "X" dungeon overview. There are also some minor weird things in the dungeon overview screen ("Ctrl-O"). I hope to fix them at some time in the future.
  • I haven't handled Ziggurats yet.

For this message the author bel has received thanks: 3
chequers, n1000, Speleothing

bel

Cocytus Succeeder

Posts: 2184

Joined: Tuesday, 3rd February 2015, 22:05

Post Tuesday, 31st January 2017, 17:43

Re: Game seed

I have fixed the interface issues listed above and pushed them to the branch.

For Zigs, I'm not sure that any solution really makes sense, so I think it's best to leave it totally random like the Abyss.

Next up:
I thought that it might make sense to make this a separate "game type" like Dungeon Sprint. I made a weak effort, but apparently I messed up the menu somehow so it crashes the game. I will get to it when I have some time. I haven't pushed my partial work to the github branch - so that version remains playable without any bugs. Or at least without any intended bugs; I'm sure there are some lurking somewhere.

Dungeon Master

Posts: 388

Joined: Monday, 18th August 2014, 20:04

Post Monday, 28th January 2019, 17:47

Re: Game seed

Just some thread necromancy: I implemented a bunch of seeding improvements including pregeneration, and merged them into trunk. Pregeneration is still somewhat experimental and is enabled mainly for offline games, but we are working on some experimental online modes that will be outside of sequell/scoring. The branch that got merged can be seen here: https://github.com/crawl/crawl/pull/968.

Thanks to bel for putting together the branch linked here, which was my starting point for many of these changes; it would have taken me a lot longer without this branch already existing!

For this message the author advil has received thanks: 5
Airwolf, bel, chequers, duvessa, pedritolo

Return to Coding

Who is online

Users browsing this forum: No registered users and 4 guests

Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group.
Designed by ST Software for PTF.