You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
405 lines
13 KiB
405 lines
13 KiB
/** |
|
* @file random.hpp |
|
* |
|
* Contains convenience functions for random number generation |
|
* |
|
* This includes specific engine/distribution functions for logic that needs to be compatible with the base game. |
|
*/ |
|
#pragma once |
|
|
|
#include <algorithm> |
|
#include <cstdint> |
|
#include <initializer_list> |
|
#include <random> |
|
|
|
namespace devilution { |
|
|
|
class DiabloGenerator { |
|
private: |
|
/** Borland C/C++ psuedo-random number generator needed for vanilla compatibility */ |
|
std::linear_congruential_engine<uint32_t, 0x015A4E35, 1, 0> lcg; |
|
|
|
public: |
|
/** |
|
* @brief Set the state of the RandomNumberEngine used by the base game to the specific seed |
|
* @param seed New engine state |
|
*/ |
|
DiabloGenerator(uint32_t seed) |
|
{ |
|
lcg.seed(seed); |
|
} |
|
|
|
/** |
|
* @brief Advance the global RandomNumberEngine state by the specified number of rounds |
|
* |
|
* Only used to maintain vanilla compatibility until logic requiring reproducible random number generation is isolated. |
|
* @param count How many values to discard |
|
*/ |
|
void discardRandomValues(unsigned count) |
|
{ |
|
lcg.discard(count); |
|
} |
|
|
|
/** |
|
* @brief Generates a random non-negative integer (most of the time) using the vanilla RNG |
|
* |
|
* This advances the engine state then interprets the new engine state as a signed value and calls std::abs to try |
|
* discard the high bit of the result. This usually returns a positive number but may very rarely return -2^31. |
|
* |
|
* This function is only used when the base game wants to store the seed used to generate an item or level, however |
|
* as the returned value is transformed about 50% of values do not reflect the actual engine state. It would be more |
|
* appropriate to use GetLCGEngineState() in these cases but that may break compatibility with the base game. |
|
* |
|
* @return A random number in the range [0,2^31) or -2^31 |
|
*/ |
|
int32_t advanceRndSeed() |
|
{ |
|
const int32_t seed = static_cast<int32_t>(lcg()); |
|
// since abs(INT_MIN) is undefined behavior, handle this value specially |
|
return seed == std::numeric_limits<int32_t>::min() ? std::numeric_limits<int32_t>::min() : std::abs(seed); |
|
} |
|
|
|
/** |
|
* @brief Generates a random integer less than the given limit using the vanilla RNG |
|
* |
|
* If v is not a positive number this function returns 0 without calling the RNG. |
|
* |
|
* Limits between 32768 and 65534 should be avoided as a bug in vanilla means this function always returns a value |
|
* less than 32768 for limits in that range. |
|
* |
|
* This can very rarely return a negative value in the range (-v, -1] due to the bug in AdvanceRndSeed() |
|
* |
|
* @see AdvanceRndSeed() |
|
* @param v The upper limit for the return value |
|
* @return A random number in the range [0, v) or rarely a negative value in (-v, -1] |
|
*/ |
|
int32_t generateRnd(int32_t v) |
|
{ |
|
if (v <= 0) |
|
return 0; |
|
if (v <= 0x7FFF) // use the high bits to correct for LCG bias |
|
return (advanceRndSeed() >> 16) % v; |
|
return advanceRndSeed() % v; |
|
} |
|
|
|
/** |
|
* @brief Generates a random boolean value using the vanilla RNG |
|
* |
|
* This function returns true 1 in `frequency` of the time, otherwise false. For example the default frequency of 2 |
|
* represents a 50/50 chance. |
|
* |
|
* @param frequency odds of returning a true value |
|
* @return A random boolean value |
|
*/ |
|
bool flipCoin(unsigned frequency) |
|
{ |
|
// Casting here because GenerateRnd takes a signed argument when it should take and yield unsigned. |
|
return generateRnd(static_cast<int32_t>(frequency)) == 0; |
|
} |
|
|
|
/** |
|
* @brief Picks one of the elements in the list randomly. |
|
* |
|
* @param values The values to pick from |
|
* @return A random value from the 'values' list. |
|
*/ |
|
template <typename T> |
|
const T pickRandomlyAmong(const std::initializer_list<T> &values) |
|
{ |
|
const auto index { std::max<int32_t>(generateRnd(static_cast<int32_t>(values.size())), 0) }; |
|
|
|
return *(values.begin() + index); |
|
} |
|
|
|
/** |
|
* @brief Generates a random non-negative integer |
|
* |
|
* Effectively the same as GenerateRnd but will never return a negative value |
|
* @param v upper limit for the return value |
|
* @return a value between 0 and v-1 inclusive, i.e. the range [0, v) |
|
*/ |
|
inline int32_t randomIntLessThan(int32_t v) |
|
{ |
|
return std::max<int32_t>(generateRnd(v), 0); |
|
} |
|
|
|
/** |
|
* @brief Randomly chooses a value somewhere within the given range |
|
* @param min lower limit, minimum possible value |
|
* @param max upper limit, either the maximum possible value for a closed range (the default behaviour) or one greater than the maximum value for a half-open range |
|
* @param halfOpen whether to use the limits as a half-open range or not |
|
* @return a randomly selected integer |
|
*/ |
|
inline int32_t randomIntBetween(int32_t min, int32_t max, bool halfOpen = false) |
|
{ |
|
return randomIntLessThan(max - min + (halfOpen ? 0 : 1)) + min; |
|
} |
|
}; |
|
|
|
// Based on fmix32 implementation from MurmurHash3 created by Austin Appleby in 2008 |
|
// https://github.com/aappleby/smhasher/blob/61a0530f28277f2e850bfc39600ce61d02b518de/src/MurmurHash3.cpp#L68 |
|
// and adapted from https://prng.di.unimi.it/splitmix64.c written in 2015 by Sebastiano Vigna |
|
// |
|
// See also: |
|
// Guy L. Steele, Doug Lea, and Christine H. Flood. 2014. |
|
// Fast splittable pseudorandom number generators. SIGPLAN Not. 49, 10 (October 2014), 453–472. |
|
// https://doi.org/10.1145/2714064.2660195 |
|
class SplitMix32 { |
|
uint32_t state; |
|
|
|
public: |
|
SplitMix32(uint32_t state) |
|
: state(state) |
|
{ |
|
} |
|
|
|
uint32_t next() |
|
{ |
|
uint32_t z = (state += 0x9e3779b9); |
|
z = (z ^ (z >> 16)) * 0x85ebca6b; |
|
z = (z ^ (z >> 13)) * 0xc2b2ae35; |
|
return z ^ (z >> 16); |
|
} |
|
|
|
void generate(uint32_t *begin, const uint32_t *end) |
|
{ |
|
while (begin != end) { |
|
*begin = next(); |
|
++begin; |
|
} |
|
} |
|
}; |
|
|
|
// Adapted from https://prng.di.unimi.it/splitmix64.c written in 2015 by Sebastiano Vigna |
|
// |
|
// See also: |
|
// Guy L. Steele, Doug Lea, and Christine H. Flood. 2014. |
|
// Fast splittable pseudorandom number generators. SIGPLAN Not. 49, 10 (October 2014), 453–472. |
|
// https://doi.org/10.1145/2714064.2660195 |
|
class SplitMix64 { |
|
uint64_t state; |
|
|
|
public: |
|
SplitMix64(uint64_t state) |
|
: state(state) |
|
{ |
|
} |
|
|
|
uint64_t next() |
|
{ |
|
uint64_t z = (state += 0x9e3779b97f4a7c15); |
|
z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9; |
|
z = (z ^ (z >> 27)) * 0x94d049bb133111eb; |
|
return z ^ (z >> 31); |
|
} |
|
|
|
void generate(uint64_t *begin, const uint64_t *end) |
|
{ |
|
while (begin != end) { |
|
*begin = next(); |
|
++begin; |
|
} |
|
} |
|
}; |
|
|
|
/** Adapted from https://prng.di.unimi.it/xoshiro128plusplus.c written in 2019 by David Blackman and Sebastiano Vigna */ |
|
class xoshiro128plusplus { |
|
public: |
|
typedef uint32_t state[4]; |
|
|
|
xoshiro128plusplus() { seed(); } |
|
xoshiro128plusplus(const state &s) { copy(this->s, s); } |
|
xoshiro128plusplus(uint64_t initialSeed) { seed(initialSeed); } |
|
xoshiro128plusplus(uint32_t initialSeed) { seed(initialSeed); } |
|
|
|
uint32_t next(); |
|
|
|
/* This is the jump function for the generator. It is equivalent |
|
to 2^64 calls to next(); it can be used to generate 2^64 |
|
non-overlapping subsequences for parallel computations. */ |
|
void jump() |
|
{ |
|
static constexpr uint32_t JUMP[] = { 0x8764000b, 0xf542d2d3, 0x6fa035c3, 0x77f2db5b }; |
|
|
|
uint32_t s0 = 0; |
|
uint32_t s1 = 0; |
|
uint32_t s2 = 0; |
|
uint32_t s3 = 0; |
|
for (const uint32_t entry : JUMP) |
|
for (int b = 0; b < 32; b++) { |
|
if (entry & UINT32_C(1) << b) { |
|
s0 ^= s[0]; |
|
s1 ^= s[1]; |
|
s2 ^= s[2]; |
|
s3 ^= s[3]; |
|
} |
|
next(); |
|
} |
|
|
|
s[0] = s0; |
|
s[1] = s1; |
|
s[2] = s2; |
|
s[3] = s3; |
|
} |
|
|
|
void save(state &s) const |
|
{ |
|
copy(s, this->s); |
|
} |
|
|
|
private: |
|
state s; |
|
|
|
void seed(uint64_t value) |
|
{ |
|
uint64_t seeds[2]; |
|
SplitMix64 seedSequence { value }; |
|
seedSequence.generate(seeds, seeds + 2); |
|
|
|
s[0] = static_cast<uint32_t>(seeds[0] >> 32); |
|
s[1] = static_cast<uint32_t>(seeds[0]); |
|
s[2] = static_cast<uint32_t>(seeds[1] >> 32); |
|
s[3] = static_cast<uint32_t>(seeds[1]); |
|
} |
|
|
|
void seed(uint32_t value) |
|
{ |
|
SplitMix32 seedSequence { value }; |
|
seedSequence.generate(s, s + 4); |
|
} |
|
|
|
void seed() |
|
{ |
|
seed(timeSeed()); |
|
|
|
#if !(defined(WINVER) && WINVER <= 0x0500 && (!defined(_WIN32_WINNT) || _WIN32_WINNT == 0)) |
|
static std::random_device rd; |
|
std::uniform_int_distribution<uint32_t> dist; |
|
for (uint32_t &cell : s) |
|
cell ^= dist(rd); |
|
#endif |
|
} |
|
|
|
static uint64_t timeSeed(); |
|
static void copy(state &dst, const state &src); |
|
}; |
|
|
|
/** |
|
* @brief Returns a copy of the global seed generator and fast-forwards the global seed generator to avoid collisions |
|
*/ |
|
xoshiro128plusplus ReserveSeedSequence(); |
|
|
|
/** |
|
* @brief Advances the global seed generator state and returns the new value |
|
*/ |
|
uint32_t GenerateSeed(); |
|
|
|
/** |
|
* @brief Set the state of the RandomNumberEngine used by the base game to the specific seed |
|
* @param seed New engine state |
|
*/ |
|
void SetRndSeed(uint32_t seed); |
|
|
|
/** |
|
* @brief Returns the current state of the RandomNumberEngine used by the base game |
|
* |
|
* This is only exposed to allow for debugging vanilla code and testing. Using this engine for new code is discouraged |
|
* due to the poor randomness and bugs in the implementation that need to be retained for compatibility. |
|
* |
|
* @return The current engine state |
|
*/ |
|
uint32_t GetLCGEngineState(); |
|
|
|
/** |
|
* @brief Advance the global RandomNumberEngine state by the specified number of rounds |
|
* |
|
* Only used to maintain vanilla compatibility until logic requiring reproducible random number generation is isolated. |
|
* @param count How many values to discard |
|
*/ |
|
void DiscardRandomValues(unsigned count); |
|
|
|
/** |
|
* @brief Advances the global RandomNumberEngine state and returns the new value |
|
*/ |
|
uint32_t GenerateRandomNumber(); |
|
|
|
/** |
|
* @brief Generates a random non-negative integer (most of the time) using the vanilla RNG |
|
* |
|
* This advances the engine state then interprets the new engine state as a signed value and calls std::abs to try |
|
* discard the high bit of the result. This usually returns a positive number but may very rarely return -2^31. |
|
* |
|
* This function is only used when the base game wants to store the seed used to generate an item or level, however |
|
* as the returned value is transformed about 50% of values do not reflect the actual engine state. It would be more |
|
* appropriate to use GetLCGEngineState() in these cases but that may break compatibility with the base game. |
|
* |
|
* @return A random number in the range [0,2^31) or -2^31 |
|
*/ |
|
[[nodiscard]] int32_t AdvanceRndSeed(); |
|
|
|
/** |
|
* @brief Generates a random integer less than the given limit using the vanilla RNG |
|
* |
|
* If v is not a positive number this function returns 0 without calling the RNG. |
|
* |
|
* Limits between 32768 and 65534 should be avoided as a bug in vanilla means this function always returns a value |
|
* less than 32768 for limits in that range. |
|
* |
|
* This can very rarely return a negative value in the range (-v, -1] due to the bug in AdvanceRndSeed() |
|
* |
|
* @see AdvanceRndSeed() |
|
* @param v The upper limit for the return value |
|
* @return A random number in the range [0, v) or rarely a negative value in (-v, -1] |
|
*/ |
|
int32_t GenerateRnd(int32_t v); |
|
|
|
/** |
|
* @brief Generates a random boolean value using the vanilla RNG |
|
* |
|
* This function returns true 1 in `frequency` of the time, otherwise false. For example the default frequency of 2 |
|
* represents a 50/50 chance. |
|
* |
|
* @param frequency odds of returning a true value |
|
* @return A random boolean value |
|
*/ |
|
bool FlipCoin(unsigned frequency = 2); |
|
|
|
/** |
|
* @brief Picks one of the elements in the list randomly. |
|
* |
|
* @param values The values to pick from |
|
* @return A random value from the 'values' list. |
|
*/ |
|
template <typename T> |
|
const T PickRandomlyAmong(const std::initializer_list<T> &values) |
|
{ |
|
const auto index { std::max<int32_t>(GenerateRnd(static_cast<int32_t>(values.size())), 0) }; |
|
|
|
return *(values.begin() + index); |
|
} |
|
|
|
/** |
|
* @brief Generates a random non-negative integer |
|
* |
|
* Effectively the same as GenerateRnd but will never return a negative value |
|
* @param v upper limit for the return value |
|
* @return a value between 0 and v-1 inclusive, i.e. the range [0, v) |
|
*/ |
|
inline int32_t RandomIntLessThan(int32_t v) |
|
{ |
|
return std::max<int32_t>(GenerateRnd(v), 0); |
|
} |
|
|
|
/** |
|
* @brief Randomly chooses a value somewhere within the given range |
|
* @param min lower limit, minimum possible value |
|
* @param max upper limit, either the maximum possible value for a closed range (the default behaviour) or one greater than the maximum value for a half-open range |
|
* @param halfOpen whether to use the limits as a half-open range or not |
|
* @return a randomly selected integer |
|
*/ |
|
inline int32_t RandomIntBetween(int32_t min, int32_t max, bool halfOpen = false) |
|
{ |
|
return RandomIntLessThan(max - min + (halfOpen ? 0 : 1)) + min; |
|
} |
|
|
|
} // namespace devilution
|
|
|