[Solved]Open world saving/seeds

[Catastrophe]

Got a bit of an open question regarding saving and random seeds.

So I've got a large grid based open world map and a seed defining said map. For terrain and small decorations I'm using perlin noise and a faster trig-based noise generator respectively, and simply making choices based on the float number I get from them at a grid point. This works great.

However, I also want unique random encounters and shops/towns based on a grid point, and doing these with just returned floats would be ultra-time consuming and complicated, since there are a lot of variables and they need to be deterministic based on the map seed and grid point. The two ideas I have here are:

A) just determine them on the fly after a randomize(), and save every detail of them into save files, though the player could visit dozens of towns/enemies,shops/etc over the course of the game. Edit: actually, this would mean the player could reroll these before a visit, so this is not so great.

B) use the map seed and the grid point to generate a new seed, and random_set_seed to it to use just for the encounter/shop/etc

--

B) sounds much more attractive, but I don't really know enough of what goes on under the hood of random() calls to know if it's truly random this way. It also sounds like I'd have to figure out my on noise generator to generate the new seed since the ones I'm using so far only give 2 decimals of accuracy.

Anyways, just thought I'd get some opinions before building the entire game around this concept.

 

[CloseRange]

to know if it's truly random this way

technically nothing in programming is random, this is why a seed is required. But it's more random than any human so it doesn't matter

if you wanna learn how random works I can explain it

Spoiler: Random

random takes a seed and performs some function that does 2 things. changes the seed and returns a number.
I'm not 100% sure of the exact formula that game maker uses but most languages use this:

X₂ = (aX₁+b) mod m
Y = X₂ / m

X₁ is the old seed
X₂ is the new seed
a, b, and m are big integeres determined by the developer (some combinations work better than others)
and Y is the return value from 0 to 1

functions like random range will just take this normalized return and do a scale and translate on it:

Y*(b-a) + a

where a is the min and b is the max

the way programs get a random seed to start with is variant.
You could get the tempature of the cpu down to a 1000th of a degree
You could get the current time
You could click a key 2 times and see the time beteen the presses down to the millisecond

As for saving lots of things like you want you could just take chunks of the game and save them as the player discovers them.
Don't generate a town or whatever until they are within maybe a 100 cell radius of it, then generate the encounters / shops, then save it in a file. When they reload the save check to see if they already discovered the chunk they are in and if so load it, if not make it

You'll need to do some form of chunking system anyway depending on how big your game is, otherwise your game could run the risk of bogging down.

Another option is to just save the seed and generate all shops and encounters and whatnot right at the start. As long as everything gets generated in the same order each time nothing will change.

 

[Catastrophe]

Well, the plan is a 500x500 map or therabouts, so initializing at start is probably not the way to go, though that does solve that if I need to go that route. Currently, the "chunking" system is there's a small viewable map (~30x30) and I just completely refill it using the noise system every time the player moves. Which is pretty slow but I nobody's going to notice a slow frame in that context since it's a warp move.

Regarding seeding, that's pretty interesting, I wonder if I can use that formula type using the grid spot. like...

X₂ = (aX₁+b) mod m
Y = X₂ / m

->

shopSeed = (xMap*worldSeed + yMap) mod 1000000.

And for different types I can just use offsets like

encounterOffset = 93921
encounterSeed = ((xMap + encounterOffset)*worldSeed + yMap + encounterOffset) mod 1000000

It doesn't have to be perfect or good really, I mostly just need to make sure I end up with a variety of seeds and nearby seeds do not end up the same, and I don't really need to worry about the "Y =" part.

I think when I start the game, I'll just reject worldSeeds that are small, so I don't have to worry about odd cases like when xMap,worldSeed, and yMap are all small

As long as all successive random() is fully deterministic based on the seed, this should work

 

[Yal]

If you want more control over your random number generator, you could always implement your own in pure GML. The simplest ones are just x(next) = (x(current) + prime1) mod prime2, but there's more complicated ones that use several independent seeds and have an array of internal states. If you want something that takes a coordinate and spits out a number you can use to access a random table of encounters, it sounds like you want something that takes 3 seeds (x and y coordinates, plus a world's random seed) and spits out an random integer on a pre-defined range.

Of course, since you're only going to do this once per grid cell, a random generator is overkill (no need to keep track of internal state). Just bake together the three values somehow and then hash them (or get a single number using built-in irandom using the baked combined value as a seed), then use modulo to force it into the desired range.



Another approach you could consider is to do what roguelike Eldritch did, and place the important encounters first and then have the world around them adapt to them. For instance, some buildings and other landmarks needed walls on certain sides, so the generator was informed than there needed to be walls there in a list of conditions for the generation. Rather than finding the best conditions in a pre-generated level (which could be impossible if the random generation generated 0 cases where it was met this time), it forced randomness to comply with what landmarks was placed in the level so that their necessary conditions WERE met 100% of the time. The approach that game took wouldn't quite work in your case since it was based 100% on using vaults (pre-fabricated room chunks) but it's a good idea to keep in mind.

 

[CloseRange]

Well, the plan is a 500x500 map

that's really not as big as you'd think.
A chunking system like you have is common in something like minecraft, but there it makes sense because the maps are something like 1,000,000,000 x 1,000,000,000 x 50
but if you've ever played minecraft you'd know that when coming into a chunk there is no lag, in fact if you're lagging you can reach the end of the chunk before it even renders, no delay.
This is because their generation system runs on a separate thread however I have no idea how to make a separate thread in game maker, most likely would need the use of extensions
If you're curious a thread just allows you to do multiple tasks at once without having to stop the other. So in this case letting you run the game while generating the chunk in the background.

In a 500x500 map you could easily just pre-warm all the data at start or when you press 'new game' or whatever the case is.
If the freeze time at start is too long for your liking you could implement a loading screen and it should still be a short one. Most users are willing to sacrifice a 10-15 second load screen for smoother gameplay (plus you could add some fun text to make it more enjoyable)
a lot of loading screens do take advantage of multi-threading as well but you can just as easily get away with using coroutines.

Spoiler: About Coroutines

In case you wanna know more about Coroutines:
Coroutines are a close brother of Multi-threading except they are made strictly by developers instead of off hardware.
Imagine 2 people have to do some task (one must update a loading screen and one must generate the game)
Multi-threading will give each of them a pencil and tell them to start working.
Coroutines will give one of them a a pencil and tell them to take turns.
When some of the game has been generated he will hand the pencile off and tell the other guy to update the load screen and maybe add new text
then the pencil goes back to the generator to do a little more work.

The problem with this vs Multi-threading is that in order for a load screen and text to be rendered (at least in most engines) you must iterate one tick cycle (the end of the draw event is when the screen gets updated.
If you made your own game engine you could get around this by updating the screen right away, but Game Maker doesn't allow you to choose.
This means that if you pass the pencile back and forth 100 times, you must go through 100 ticks of the step event. leaving an extra 3.3 seconds (on 30fps) of overhead time.
That's why it's best to minimize the amount of times the pencil gets passed, but doing it too few times will make the loading screen look a little more jumpy and less smooth.

Anyway, what were we talking about? The seeding thing?

Yes having your own personal PRNG (psudo random number generator) available is fine if you're very sensitive about what control you give to Game Maker and want to minimize what's under the hood.
Just remember that the values a, b, and m should always be the same, never change.
If they change then the seed becomes pointless, you are free to add the 'encounterOffset' to them just make sure that throughout game play and throughout loads that the value doesn't change.
Though there really is little to no point in having it change ever. They are just constants that don't really mean much, they are just used to produce a differant set of random numbers.

x(next) = (x(current) + prime1) mod prime2,

Was I wrong? I thought x(current) needed to be scaled by a value as well? It's been a while since a learned about this so maybe not, even forgot that the numbers had to be prime.

 

[Yal]

Was I wrong? I thought x(current) needed to be scaled by a value as well? It's been a while since a learned about this so maybe not, even forgot that the numbers had to be prime.

*gets out Beta Matemathics Handbook*
*nearly suffocates from all the dust it exudes*
xn+1 = (axn + b) mod m (mixed congruential)
Okay, you're right. Derp.


And yeah, I agree that 500x500 tiles is pretty small. 250,000 values x 8 byte (GM uses doubles for floating-point values) = 2,000,000 byte = 2MB. As in, smaller than an average piece of OGG background music. Just store it all pre-generated in an array instead of re-generating it constantly. (You could have an object generate new values for hitherto unvisited cells each step as a sort of "kinda background thread" if the generation time is too noticeably slow)

 

[Catastrophe]

Alright, thanks all, learned a lot about psuedo-RNG I think I've got a solid plan from here Yeah I wasn't really thinking it through when I said 500x500 was too big. I forgot I just needed to generate a seed, not generate everything about the encounter/shop. So generating a seed for every grid spot on game after loading/creating the worldSeed actually might work just fine.

Edit: yeah this took 1/10 of a second haha. whoops. talk about overthinking it

worldSeed = 13089435;
random_set_seed(worldSeed);
show_message("gen seeds")
gridSeeds = ds_grid_create(500,500);

for (i = 0; i < 500; i++) {
for (i2 = 0; i2 < 500; i2++) {
ds_grid_set(gridSeeds,i,i2,irandom(5000000))
}
}
show_message("done")