2009-08-21 22:21:05 +02:00
|
|
|
/*
|
|
|
|
* This file is part of OpenTTD.
|
|
|
|
* OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
|
|
|
|
* OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
|
|
|
|
* See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
|
|
|
|
*/
|
|
|
|
|
2008-05-06 17:11:33 +02:00
|
|
|
/** @file random_func.hpp Pseudo random number generator. */
|
2007-11-21 20:13:38 +01:00
|
|
|
|
|
|
|
#ifndef RANDOM_FUNC_HPP
|
|
|
|
#define RANDOM_FUNC_HPP
|
|
|
|
|
2024-01-17 03:45:47 +01:00
|
|
|
/**
|
|
|
|
* Scale a uint32_t number to be within the range [0,\a limit).
|
|
|
|
* @param value The value to scale.
|
|
|
|
* @param limit The limit to scale to.
|
|
|
|
* @return The scaled value.
|
|
|
|
*/
|
|
|
|
static constexpr uint32_t ScaleToLimit(uint32_t value, uint32_t limit)
|
|
|
|
{
|
|
|
|
return ((uint64_t)value * (uint64_t)limit) >> 32;
|
|
|
|
}
|
2007-12-23 15:06:03 +01:00
|
|
|
|
2008-01-29 01:27:25 +01:00
|
|
|
/**
|
|
|
|
* Structure to encapsulate the pseudo random number generators.
|
|
|
|
*/
|
|
|
|
struct Randomizer {
|
|
|
|
/** The state of the randomizer */
|
2023-05-08 19:01:06 +02:00
|
|
|
uint32_t state[2];
|
2008-01-29 01:27:25 +01:00
|
|
|
|
2023-05-08 19:01:06 +02:00
|
|
|
uint32_t Next();
|
|
|
|
void SetSeed(uint32_t seed);
|
2024-01-17 03:45:47 +01:00
|
|
|
|
|
|
|
/**
|
|
|
|
* Generate the next pseudo random number scaled to \a limit, excluding \a limit
|
|
|
|
* itself.
|
|
|
|
* @param limit Limit of the range to be generated from.
|
|
|
|
* @return Random number in [0,\a limit)
|
|
|
|
*/
|
|
|
|
inline uint32_t Next(uint32_t limit) { return ScaleToLimit(this->Next(), limit); }
|
2008-01-29 01:27:25 +01:00
|
|
|
};
|
|
|
|
extern Randomizer _random; ///< Random used in the game state calculations
|
2019-01-13 08:38:48 +01:00
|
|
|
extern Randomizer _interactive_random; ///< Random used everywhere else, where it does not (directly) influence the game state
|
2008-01-29 01:27:25 +01:00
|
|
|
|
2008-08-16 16:02:20 +02:00
|
|
|
/** Stores the state of all random number generators */
|
|
|
|
struct SavedRandomSeeds {
|
|
|
|
Randomizer random;
|
|
|
|
Randomizer interactive_random;
|
|
|
|
};
|
|
|
|
|
2010-08-01 21:22:34 +02:00
|
|
|
/**
|
|
|
|
* Saves the current seeds
|
2008-08-16 16:02:20 +02:00
|
|
|
* @param storage Storage for saving
|
|
|
|
*/
|
2024-01-06 12:19:27 +01:00
|
|
|
inline void SaveRandomSeeds(SavedRandomSeeds *storage)
|
2008-08-16 16:02:20 +02:00
|
|
|
{
|
|
|
|
storage->random = _random;
|
|
|
|
storage->interactive_random = _interactive_random;
|
|
|
|
}
|
|
|
|
|
2010-08-01 21:22:34 +02:00
|
|
|
/**
|
|
|
|
* Restores previously saved seeds
|
2008-08-16 16:02:20 +02:00
|
|
|
* @param storage Storage where SaveRandomSeeds() stored th seeds
|
|
|
|
*/
|
2024-01-06 12:19:27 +01:00
|
|
|
inline void RestoreRandomSeeds(const SavedRandomSeeds &storage)
|
2008-08-16 16:02:20 +02:00
|
|
|
{
|
|
|
|
_random = storage.random;
|
|
|
|
_interactive_random = storage.interactive_random;
|
|
|
|
}
|
|
|
|
|
2023-05-08 19:01:06 +02:00
|
|
|
void SetRandomSeed(uint32_t seed);
|
2007-11-21 20:13:38 +01:00
|
|
|
#ifdef RANDOM_DEBUG
|
2024-01-17 03:45:47 +01:00
|
|
|
uint32_t Random(const std::source_location location = std::source_location::current());
|
2007-11-21 20:13:38 +01:00
|
|
|
#else
|
2024-01-17 03:45:47 +01:00
|
|
|
inline uint32_t Random([[maybe_unused]] const std::source_location location = std::source_location::current())
|
2008-06-22 17:41:38 +02:00
|
|
|
{
|
|
|
|
return _random.Next();
|
|
|
|
}
|
2007-11-21 20:13:38 +01:00
|
|
|
#endif
|
|
|
|
|
2024-01-17 03:45:47 +01:00
|
|
|
/**
|
|
|
|
* Pick a random number between 0 and \a limit - 1, inclusive. That means 0
|
|
|
|
* can be returned and \a limit - 1 can be returned, but \a limit can not be
|
|
|
|
* returned.
|
|
|
|
* @param limit Limit for the range to be picked from.
|
|
|
|
* @return A random number in [0,\a limit).
|
|
|
|
*/
|
|
|
|
inline uint32_t RandomRange(uint32_t limit, const std::source_location location = std::source_location::current())
|
|
|
|
{
|
|
|
|
return ScaleToLimit(Random(location), limit);
|
|
|
|
}
|
|
|
|
|
2024-01-06 12:19:27 +01:00
|
|
|
inline uint32_t InteractiveRandom()
|
2008-06-22 17:41:38 +02:00
|
|
|
{
|
|
|
|
return _interactive_random.Next();
|
|
|
|
}
|
|
|
|
|
2024-01-06 12:19:27 +01:00
|
|
|
inline uint32_t InteractiveRandomRange(uint32_t limit)
|
2008-06-22 17:41:38 +02:00
|
|
|
{
|
2013-10-20 16:48:08 +02:00
|
|
|
return _interactive_random.Next(limit);
|
2008-06-22 17:41:38 +02:00
|
|
|
}
|
2007-11-21 20:13:38 +01:00
|
|
|
|
2007-11-25 16:35:25 +01:00
|
|
|
/**
|
|
|
|
* Checks if a given randomize-number is below a given probability.
|
|
|
|
*
|
|
|
|
* This function is used to check if the given probability by the fraction of (a/b)
|
2009-04-10 00:37:59 +02:00
|
|
|
* is greater than low 16 bits of the given randomize-number r.
|
2007-11-25 16:35:25 +01:00
|
|
|
*
|
|
|
|
* Do not use this function twice on the same random 16 bits as it will yield
|
|
|
|
* the same result. One can use a random number for two calls to Chance16I,
|
|
|
|
* where one call sends the low 16 bits and the other the high 16 bits.
|
|
|
|
*
|
|
|
|
* @param a The numerator of the fraction
|
|
|
|
* @param b The denominator of the fraction, must of course not be null
|
|
|
|
* @param r The given randomize-number
|
2009-04-10 00:37:59 +02:00
|
|
|
* @return True if the probability given by r is less or equal to (a/b)
|
2007-11-25 16:35:25 +01:00
|
|
|
*/
|
2024-01-17 03:45:47 +01:00
|
|
|
inline bool Chance16I(const uint32_t a, const uint32_t b, const uint32_t r)
|
2007-11-25 16:35:25 +01:00
|
|
|
{
|
|
|
|
assert(b != 0);
|
2023-05-08 19:01:06 +02:00
|
|
|
return (((uint16_t)r * b + b / 2) >> 16) < a;
|
2007-11-25 16:35:25 +01:00
|
|
|
}
|
|
|
|
|
|
|
|
/**
|
2009-04-26 00:22:27 +02:00
|
|
|
* Flips a coin with given probability.
|
2007-11-25 16:35:25 +01:00
|
|
|
*
|
2009-04-26 00:22:27 +02:00
|
|
|
* This function returns true with (a/b) probability.
|
2007-11-25 16:35:25 +01:00
|
|
|
*
|
|
|
|
* @see Chance16I()
|
2009-04-26 00:22:27 +02:00
|
|
|
* @param a The nominator of the fraction
|
2007-11-25 16:35:25 +01:00
|
|
|
* @param b The denominator of the fraction
|
2009-04-26 00:22:27 +02:00
|
|
|
* @return True with (a/b) probability
|
2007-11-25 16:35:25 +01:00
|
|
|
*/
|
2024-01-17 03:45:47 +01:00
|
|
|
inline bool Chance16(const uint32_t a, const uint32_t b, const std::source_location location = std::source_location::current())
|
2007-11-25 16:35:25 +01:00
|
|
|
{
|
2024-01-17 03:45:47 +01:00
|
|
|
return Chance16I(a, b, Random(location));
|
2007-11-25 16:35:25 +01:00
|
|
|
}
|
|
|
|
|
|
|
|
/**
|
|
|
|
* Flips a coin with a given probability and saves the randomize-number in a variable.
|
|
|
|
*
|
|
|
|
* This function uses the same parameters as Chance16. The third parameter
|
|
|
|
* must be a variable the randomize-number from Random() is saved in.
|
|
|
|
*
|
2012-12-01 14:12:39 +01:00
|
|
|
* The low 16 bits of r will already be used and can therefore not be passed to
|
2007-11-25 16:35:25 +01:00
|
|
|
* Chance16I. One can only send the high 16 bits to Chance16I.
|
|
|
|
*
|
|
|
|
* @see Chance16I()
|
|
|
|
* @param a The numerator of the fraction
|
|
|
|
* @param b The denominator of the fraction
|
|
|
|
* @param r The variable to save the randomize-number from Random()
|
|
|
|
* @return True in (a/b) percent
|
|
|
|
*/
|
2024-01-17 03:45:47 +01:00
|
|
|
inline bool Chance16R(const uint32_t a, const uint32_t b, uint32_t &r, const std::source_location location = std::source_location::current())
|
2007-11-25 16:35:25 +01:00
|
|
|
{
|
2024-01-17 03:45:47 +01:00
|
|
|
r = Random(location);
|
2007-11-25 16:35:25 +01:00
|
|
|
return Chance16I(a, b, r);
|
|
|
|
}
|
|
|
|
|
2024-01-18 23:52:53 +01:00
|
|
|
void RandomBytesWithFallback(std::span<uint8_t> buf);
|
|
|
|
|
2007-11-21 20:13:38 +01:00
|
|
|
#endif /* RANDOM_FUNC_HPP */
|