Yes, the exponential function is the problem. Approximating it with highish
precision using only integer calculations would require a lot of computation,
which isn't really feasible. There are reasonable options though if we don't
mind straying a little. The function we use here is basically a
three-dimensional Gauß-curve, and I think we could find an alternative that
roughly preserves the shape and can be done with a small number of integer
operations.
It's probably not necessary though, but if we keep getting desyncs because of
such platform/compiler-dependent computation differences, this would provide an
option.
I also replied to your replies.
Diff comments:
>
> === modified file 'src/logic/map_objects/terrain_affinity.cc'
> --- src/logic/map_objects/terrain_affinity.cc 2018-04-07 16:59:00 +0000
> +++ src/logic/map_objects/terrain_affinity.cc 2018-11-16 06:27:07 +0000
> @@ -33,85 +33,92 @@
>
> namespace {
>
> +// Literature on cross-platform floating point precision-problems:
> +// https://arxiv.org/abs/cs/0701192
> +// Monniaux, David (2008): "The pitfalls of verifying floating-point
> computations",
> +// in: ACM Transactions on Programming Languages and Systems 30, 3 (2008) 12.
> +//
> +// Recommends using heximal float constants, but we'd need to switch to
> C++17 for that.
> +//
> +//
> https://randomascii.wordpress.com/2012/03/21/intermediate-floating-point-precision/
> +
> constexpr double pow2(const double& a) {
> return a * a;
> }
>
> // Helper function for probability_to_grow
> // Calculates the probability to grow for the given affinity and terrain
> values
> -double calculate_probability_to_grow(const TerrainAffinity& affinity,
> - double terrain_humidity,
> - double terrain_fertility,
> - double terrain_temperature) {
> -
> - constexpr double kHumidityWeight = 0.500086642549548;
> - constexpr double kFertilityWeight = 0.5292268046607387;
> - constexpr double kTemperatureWeight = 61.31300863608306;
> -
> - const double sigma_humidity = (1. - affinity.pickiness());
> - const double sigma_temperature = (1. - affinity.pickiness());
> - const double sigma_fertility = (1. - affinity.pickiness());
> -
> - return exp((-pow2((affinity.preferred_fertility() - terrain_fertility) /
> - (kFertilityWeight * sigma_fertility)) -
> - pow2((affinity.preferred_humidity() - terrain_humidity) /
> - (kHumidityWeight * sigma_humidity)) -
> - pow2((affinity.preferred_temperature() -
> terrain_temperature) /
> - (kTemperatureWeight * sigma_temperature))) /
> - 2);
> +inline unsigned int calculate_probability_to_grow(const TerrainAffinity&
> affinity,
> + int terrain_humidity,
> + int terrain_fertility,
> + int terrain_temperature) {
> + constexpr double kHumidityWeight = 5.00086642549548;
> + constexpr double kFertilityWeight = 5.292268046607387;
> + constexpr double kTemperatureWeight = 0.6131300863608306;
> +
> + // Avoid division by 0
> + assert(affinity.pickiness() < 100);
> + const double sigma = std::floor(100.0 - affinity.pickiness());
> +
> + const double result = exp(-
> + (pow2(((affinity.preferred_fertility() -
> terrain_fertility) / kFertilityWeight) / sigma) +
> + (pow2(((affinity.preferred_humidity() -
> terrain_humidity) / kHumidityWeight) / sigma) +
The operator "+" is left-to-right associative in C++
(https://en.cppreference.com/w/cpp/language/operator_precedence) so without
those extra brackets the evaluation (inside the "exp(-(...))") would always be
"(fertility_part + humidity_part) + temperature_part".
for every compiler. You are simply forcing it to always be
"fertility_part + (humidity_part + temperature_part)", which is different but
not inherently better.
Of course those two different evaluation orders could have slightly different
results, but the order is specified by the expression, so every compiler would
use the same order anyway.
Operator associativity is defined by the C++ standard, so compiler
optimizations should not be able to change the order, but if they were then the
extra brackets wouldn't stop them either.
Anyway, it doesn't really matter which way, I just think that with such a big
expression we don't need to make it even harder to read by more brackets,
especially not to separate those three semantically similar terms.
> + pow2(((affinity.preferred_temperature() -
> terrain_temperature) / kTemperatureWeight) / sigma))) / 2.0);
> +
> + return static_cast<unsigned int>(std::max(0.0, std::floor(result *
> static_cast<double>(TerrainAffinity::kPrecisionFactor))));
> }
>
> } // namespace
>
> TerrainAffinity::TerrainAffinity(const LuaTable& table, const std::string&
> immovable_name)
> - : preferred_fertility_(table.get_double("preferred_fertility")),
> - preferred_humidity_(table.get_double("preferred_humidity")),
> - preferred_temperature_(table.get_double("preferred_temperature")),
> - pickiness_(table.get_double("pickiness")) {
> - if (!(0 <= preferred_fertility_ && preferred_fertility_ <= 1.)) {
> - throw GameDataError("%s: preferred_fertility is not in [0,
> 1].", immovable_name.c_str());
> - }
> - if (!(0 <= preferred_humidity_ && preferred_humidity_ <= 1.)) {
> - throw GameDataError("%s: preferred_humidity is not in [0, 1].",
> immovable_name.c_str());
> - }
> - if (!(0 <= pickiness_ && pickiness_ <= 1.)) {
> - throw GameDataError("%s: pickiness is not in [0, 1].",
> immovable_name.c_str());
> + : preferred_fertility_(table.get_int("preferred_fertility")),
> + preferred_humidity_(table.get_int("preferred_humidity")),
> + preferred_temperature_(table.get_int("preferred_temperature")),
> + pickiness_(table.get_int("pickiness")) {
> + if (!(0 <= preferred_fertility_ && preferred_fertility_ <= 1000)) {
> + throw GameDataError("%s: preferred_fertility is not in [0,
> 1000].", immovable_name.c_str());
> + }
> + if (!(0 <= preferred_humidity_ && preferred_humidity_ <= 1000)) {
> + throw GameDataError("%s: preferred_humidity is not in [0,
> 1000].", immovable_name.c_str());
> + }
> + if (!(0 <= pickiness_ && pickiness_ < 100)) {
> + throw GameDataError("%s: pickiness is not in [0, 99].",
> immovable_name.c_str());
> }
> if (preferred_temperature_ < 0) {
> throw GameDataError("%s: preferred_temperature is not
> possible.", immovable_name.c_str());
> }
> }
>
> -double TerrainAffinity::preferred_temperature() const {
> +int TerrainAffinity::preferred_temperature() const {
> return preferred_temperature_;
> }
>
> -double TerrainAffinity::preferred_fertility() const {
> +int TerrainAffinity::preferred_fertility() const {
> return preferred_fertility_;
> }
>
> -double TerrainAffinity::preferred_humidity() const {
> +int TerrainAffinity::preferred_humidity() const {
> return preferred_humidity_;
> }
>
> -double TerrainAffinity::pickiness() const {
> +int TerrainAffinity::pickiness() const {
> return pickiness_;
> }
>
> -double probability_to_grow(const TerrainAffinity& affinity,
> +unsigned int probability_to_grow(const TerrainAffinity& affinity,
> const FCoords& fcoords,
> const Map& map,
> const DescriptionMaintainer<TerrainDescription>&
> terrains) {
> - double terrain_humidity = 0;
> - double terrain_fertility = 0;
> - double terrain_temperature = 0;
> + int terrain_humidity = 0;
> + int terrain_fertility = 0;
> + int terrain_temperature = 0;
>
> const auto average = [&terrain_humidity, &terrain_fertility,
> &terrain_temperature,
> &terrains](const int terrain_index) {
> const TerrainDescription& t = terrains.get(terrain_index);
> - terrain_humidity += t.humidity() / 6.;
> - terrain_temperature += t.temperature() / 6.;
> - terrain_fertility += t.fertility() / 6.;
> + terrain_humidity += t.humidity();
> + terrain_temperature += t.temperature();
> + terrain_fertility += t.fertility();
> };
>
> average(fcoords.field->terrain_d());
>
> === modified file 'src/logic/map_objects/tribes/worker.cc'
> --- src/logic/map_objects/tribes/worker.cc 2018-11-07 10:19:29 +0000
> +++ src/logic/map_objects/tribes/worker.cc 2018-11-16 06:27:07 +0000
> @@ -856,18 +856,18 @@
> // Randomly pick one of the immovables to be planted.
>
> // Each candidate is weighted by its probability to grow.
> - double total_weight = 0.0;
> + int total_weight = 0;
> for (const auto& bsii : best_suited_immovables_index) {
> - double weight = std::get<0>(bsii);
> - total_weight += weight * weight;
> + const int weight = std::get<0>(bsii);
> + total_weight += static_cast<int>(std::floor(std::sqrt(weight)));
That's not how math works. In this context, squares still behave like squares,
and square-roots like square-roots, no matter if you scale them up or not.
Changing this from squares to square-roots will result in a drastic change in
how often which immovables will be chosen.
Here's an example. Let's keep it simple and assume we only have two different
immovables to chose from for the given terrain.
Let's say that in the old version, one had a suitability of 0.2 and the other a
suitability of 0.8. (Now it's scaled up to 0.2*kPrecisionFactor and
0.8*kPrecisionFactor.)
To get the actual probability which one we choose, the old version would (for
whatever reason) weigh the squares 0.04 and 0.64, i.e. the better suited
immovable would be chosen 16 times as often as the other (on average)
In the new version, if we would still use squares (and assuming that our int
were big enough to not have overflows), then those square weights would be
0.04*kPrecisionFactor^2 and 0.64*kPrecisionFactor^2. Huge numbers but their
ratio is still 16:1, so the better suited one would still be chosen 16 times as
often as the other (on average).
BUT if we switch to weighing with square-roots in the new version, then those
weights are sqrt(0.2)*sqrt(kPrecisionFactor) and
sqrt(0.8)*sqrt(kPrecisionFactor). They have a ratio of exactly 2:1, so the
better suited immovable would be chosen only twice as often as the other (on
average). That's a huge difference to the 16:1 before.
Basically, when two of the suitabilities have a ratio of "x : y", then (no
matter whether working in [0..1] or scaled up to [0..kPrecisionFactor]) working
with squares results in a "x^2 : y^2" ratio for the actual probabilities (i.e.
different values are stretched further apart), while working with sqrt results
in a "sqrt(x) : sqrt(y)" ratio for the actual probabilities (i.e. different
values come closer together). That's a significant difference between these two
methods. When the best six values differ quite a bit, then it should be easily
noticable in the game.
The real question is whether we want to force exactly the same behaviour as
before or not.
If we want to preserve it, we could just do the calculation in 64-bit integers.
(I assume that no one is using ancient compilers who don't support this.)
Or, if we define kPrecisionFactor as a power of two, i.e. "kPrecisionFactor =
1<<kPrecisionBits" then we could still use 32-bit integers for a scaled down
(and truncated) version:
total_weight += (weight >> baseBits) * (weight >> baseBits) + ( 2 * (weight >>
baseBits) * (weight & ((1 << baseBits) - 1)) >> baseBits)
where
int32_t baseBits = kPrecisionBits / 2;
Looks a bit nasty though. Just using 64-bit integers is much more readable.
If we don't mind changing the method, we could just use the weights linearly.
(To be honest, I find the squares somewhat heavy anyway.)
> }
>
> - double choice = logic_rand_as_double(&game) * total_weight;
> + int choice = game.logic_rand() % total_weight;
> for (const auto& bsii : best_suited_immovables_index) {
> - double weight = std::get<0>(bsii);
> + const int weight = std::get<0>(bsii);
> state.ivar2 = std::get<1>(bsii);
> state.ivar3 = static_cast<int>(std::get<2>(bsii));
> - choice -= weight * weight;
> + choice -= static_cast<int>(std::floor(std::sqrt(weight)));
> if (0 > choice) {
> break;
> }
--
https://code.launchpad.net/~widelands-dev/widelands/terrain_affinity_as_int/+merge/358299
Your team Widelands Developers is subscribed to branch
lp:~widelands-dev/widelands/terrain_affinity_as_int.
_______________________________________________
Mailing list: https://launchpad.net/~widelands-dev
Post to : [email protected]
Unsubscribe : https://launchpad.net/~widelands-dev
More help : https://help.launchpad.net/ListHelp
