diff options
Diffstat (limited to 'thirdparty/misc')
| -rw-r--r-- | thirdparty/misc/open-simplex-noise.c | 11 | ||||
| -rw-r--r-- | thirdparty/misc/pcg.cpp | 23 | ||||
| -rw-r--r-- | thirdparty/misc/triangulator.h | 4 |
3 files changed, 31 insertions, 7 deletions
diff --git a/thirdparty/misc/open-simplex-noise.c b/thirdparty/misc/open-simplex-noise.c index 42f2fbb5be..88fbd3e51d 100644 --- a/thirdparty/misc/open-simplex-noise.c +++ b/thirdparty/misc/open-simplex-noise.c @@ -189,14 +189,15 @@ int open_simplex_noise(int64_t seed, struct osn_context *ctx) permGradIndex3D = ctx->permGradIndex3D; // -- GODOT end -- + uint64_t seedU = seed; for (i = 0; i < 256; i++) source[i] = (int16_t) i; - seed = seed * 6364136223846793005LL + 1442695040888963407LL; - seed = seed * 6364136223846793005LL + 1442695040888963407LL; - seed = seed * 6364136223846793005LL + 1442695040888963407LL; + seedU = seedU * 6364136223846793005ULL + 1442695040888963407ULL; + seedU = seedU * 6364136223846793005ULL + 1442695040888963407ULL; + seedU = seedU * 6364136223846793005ULL + 1442695040888963407ULL; for (i = 255; i >= 0; i--) { - seed = seed * 6364136223846793005LL + 1442695040888963407LL; - r = (int)((seed + 31) % (i + 1)); + seedU = seedU * 6364136223846793005ULL + 1442695040888963407ULL; + r = (int)((seedU + 31) % (i + 1)); if (r < 0) r += (i + 1); perm[i] = source[r]; diff --git a/thirdparty/misc/pcg.cpp b/thirdparty/misc/pcg.cpp index 5f4bf40460..914a353874 100644 --- a/thirdparty/misc/pcg.cpp +++ b/thirdparty/misc/pcg.cpp @@ -25,8 +25,31 @@ void pcg32_srandom_r(pcg32_random_t* rng, uint64_t initstate, uint64_t initseq) } // Source from https://github.com/imneme/pcg-c-basic/blob/master/pcg_basic.c +// pcg32_boundedrand_r(rng, bound): +// Generate a uniformly distributed number, r, where 0 <= r < bound uint32_t pcg32_boundedrand_r(pcg32_random_t *rng, uint32_t bound) { + // To avoid bias, we need to make the range of the RNG a multiple of + // bound, which we do by dropping output less than a threshold. + // A naive scheme to calculate the threshold would be to do + // + // uint32_t threshold = 0x100000000ull % bound; + // + // but 64-bit div/mod is slower than 32-bit div/mod (especially on + // 32-bit platforms). In essence, we do + // + // uint32_t threshold = (0x100000000ull-bound) % bound; + // + // because this version will calculate the same modulus, but the LHS + // value is less than 2^32. uint32_t threshold = -bound % bound; + + // Uniformity guarantees that this loop will terminate. In practice, it + // should usually terminate quickly; on average (assuming all bounds are + // equally likely), 82.25% of the time, we can expect it to require just + // one iteration. In the worst case, someone passes a bound of 2^31 + 1 + // (i.e., 2147483649), which invalidates almost 50% of the range. In + // practice, bounds are typically small and only a tiny amount of the range + // is eliminated. for (;;) { uint32_t r = pcg32_random_r(rng); if (r >= threshold) diff --git a/thirdparty/misc/triangulator.h b/thirdparty/misc/triangulator.h index c85792fd50..24b79e7d34 100644 --- a/thirdparty/misc/triangulator.h +++ b/thirdparty/misc/triangulator.h @@ -21,9 +21,9 @@ #ifndef TRIANGULATOR_H #define TRIANGULATOR_H -#include "core/list.h" +#include "core/templates/list.h" #include "core/math/vector2.h" -#include "core/set.h" +#include "core/templates/set.h" //2D point structure |