widelands-dev team mailing list archive

[Arty <diego.scheide@xxxxxx>]

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.