Design Level creation, trust the random or save the levels

Joh

Member
Hi, this is more of a design question.

I am making a game with randomly generated levels (logic puzzles) the algorithm generating them makes sure everything works out and so far so good.
A problem I am facing is I can know the level before it is generated: it uses a seed, so it is always the same. but before generating it I have no "meta-data" of the level.

A solution would be to just generate all levels once at the start and record/save the data externally (or internally).
But if I do that I might as well, do it myself, distribute the game with the levels stored externally.

Each levels uses multiple grids of varying sizes, and the idea is to have unlimited levels,(so far hundreds).
As I've mentioned generating on the spot works fine. but there is some disparity between platforms ("random" execution differences I guess). Maybe there will be differences between OS? GM version (if i ever need to update)? or something. relying on random seems a bit risky for the Defined set of levels.

On the other hand, saving say 200+ group of (4-5)grids of up to 100x100 seems like overkill. especially since I only ever need one at a time. Upon writing this I realize I could just turn the grids into strings with ds_write and store everything in an array... seems like the best approach, but I just thought of this, maybe I'm missing something.

How do/would you handle large number of disposable yet persistent/defined levels?
 

Psycho_666

Member
When you do procedural generation you don't want to use any random functions. You use the seed to create the level. That will kill any issues you may have from different CPUs and different platforms executing randomness.
You make an equation, that will give you the results, you cover the edge cases and you have your algorithm. You don't really want to use any random functions.
Other than that - save a few levels, you know the ones you need for the story mode and use the algorithm to generate the others on the fly or even give your players a level editor and let them.make their own levels.

That's what I'm going to be doing in my project - have the story maps and give the players a level editor, so they can create their own maps.
 

Yal

šŸ§ *penguin noises*
GMC Elder
When you do procedural generation you don't want to use any random functions. You use the seed to create the level. That will kill any issues you may have from different CPUs and different platforms executing randomness.
This is complete nonsense. The seed is the input to the random number generator; every time it generates a number it also updates the seed so that the next number will be different. The seed can't be used on its own.


As for platform differences, GM uses different libraries on different platforms. You will get different random number sequences on different platforms (because you use completely different random number generators in some cases), so levels would be different. If you absolutely need them to be the same for every player, you need to implement your own random number generator so that you have full control over it - there's several relatively simple versions ("next = seed + prime mod another_prime" is the simplest) although doing it in GML will probably have a performance impact.

On the plus side, between-version differences shouldn't be a thing as long as the library GM uses for randomness isn't updated. You can't 100% trust that won't happen, but it shouldn't happen very often.
 

Joe Ellis

Member
The best code for a random number generator I found was gold noise:

Code:
// Gold Noise Ā©2015 [email protected]
//  - based on the Golden Ratio, PI and Square Root of Two
//  - superior distribution
//  - fastest noise generator function
//  - works with all chipsets (including low precision)

float PHI = 1.61803398874989484820459 * 00000.1; // Golden Ratio
float PI  = 3.14159265358979323846264 * 00000.1; // PI
float SQ2 = 1.41421356237309504880169 * 10000.0; // Square Root of Two

float gold_noise(in vec2 coordinate, in float seed){
    return fract(tan(distance(coordinate*(seed+PHI), vec2(PHI, PI)))*SQ2);
}
It's very lightweight compared to most other ones I've seen and the distribution is very even, so if you filled a screen with this, the average of all of them would be 0.5.

I think converted to gml it's like this:
GML:
///gold_noise(x, y, seed)

var
seed = argument2,
phi = 0.161803398874989484820459,
pi  = 0.314159265358979323846264,
sq2 = 141421356.237309504880169,
sp = seed + phi,
d = point_distance(argument0 * sp, argument1 * sp, phi, pi);

return frac(tan(d) * sq2)
The x & y inputs are a problem cus this function was made to work with shaders, so it works well with the varying values per pixel.
But cus we're relying on this function alone to create completely random results, I think a way around this is to just keep them at a constant value, like 0.5, then change the seed every time the function is called, either by adding 1 to it each time, or any other amount, and this way, the value it starts at becomes the seed which will make the levels always generate the same every time.
You could possibly change it to this:

GML:
///gold_noise()

var sp = 0.5 * (++global.seed + 0.161803398874989484820459);
return frac(tan(point_distance(sp, sp, 0.161803398874989484820459, 0.314159265358979323846264)) * 141421356.237309504880169)
I'm not sure if the tan function works the same in gml as it does in glsl so you might need to change it to arctan, and I don't know if it will work that well if both x & y coords are 0.5, it might work better if they're 0.48742787 and 0.584269642 or something.
But hopefully this will give you a good starting point if you want to use gold noise
 
Last edited:
  • Like
Reactions: Yal

chamaeleon

Member
The best code for a random number generator I found was gold noise:
GMS has a precision value problem with the trigonometric functions. Just something to be aware of which may skew the behavior of a random number generator.

 

Joe Ellis

Member
GMS has a precision value problem with the trigonometric functions. Just something to be aware of which may skew the behavior of a random number generator.

I think it'll still produce good results and even distribution cus shaders work with 32 bit precision by default and it's designed to work with that. But I don't know if results will be different per platform after reading that thread, and in the case of making levels using certain seeds, that'd be ruined if you're releasing it for several.
I guess a way around it would be to make your own tan script and calculate the point distance manually, that should have no problem then cus all maths with code is done in 64 bit.
Also the precision error might not be a problem in the case of procedural level generation if all the random numbers are integers, cus the gold noise function returns a value between 0-1, so you'd multiply this by the chosen range and round it, so from the results on the thread it should be fine if the range of the random integers doesn't exceed 1000
 
Last edited:
Top