widelands-dev team mailing list archive

[Arty <diego.scheide@xxxxxx>]

Review: Needs Fixing

I reviewed the code and also tested somewhat. Still has a few issues, most of them minor though. See diff comments.

The file data\world\immovables\bush1\init.lua still has a few comments (lines 86-94) referring to the floating point values, this should also be changed in this branch.

Overall it should be much less likely now to get different results based on platform/compiler dependent precision choices, but they might still happen. There are still things based on floating point calculations (like the main probability calculation in calculate_probability_to_grow) but they might be difficult to replace with pure integer based stuff.
That said, considering that the ratios of the final probabilities of the six best immovables already change significantly with this branch, we could possibly also change the basic probability calculation to somewhat that uses only integer operations but is not too far off from the current approach (which seems to have been based roughly on multivariate normal distributions).

Btw, where did those three weight constants in calculate_probability_to_grow originally come from? Their precision is too high to be from a simple "try and error until it feels right" approach. They still feel quite arbitrary though.

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) {

Can you please rename that to "sqr" or some such? ("pow2" usually stands for computing powers of two. It's really irritating here.) The function is only used three times in the function below, so a renaming is also quick to apply.

>  	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) +

One pair of brackets is obsolete: The opening bracket before "pow2" in the line above, and the corresponding closing bracket in the line below. (The just group the humidity and temperature part together in the sum, but the swapped summation order won't give any benefit here.)

> +                                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,

With the streamlined calculation below, the function name "average" is misleading now. Should better be called "sum" or "add" or some such.

>  	                      &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());
> @@ -136,10 +143,10 @@
>  	}
>  
>  	return calculate_probability_to_grow(
> -	   affinity, terrain_humidity, terrain_fertility, terrain_temperature);
> +	   affinity, terrain_humidity / 6, terrain_fertility / 6, terrain_temperature / 6);

That's an integer division now. To get proper rounding for those averages, it would have to be "(terrain_humidity + 3) / 6" etc. Or instead of changing it here, just initialize the three variables with 3 instead of 0 (with a small comment why).

>  }
>  
> -double probability_to_grow(const TerrainAffinity& affinity, const TerrainDescription& terrain) {
> +unsigned int probability_to_grow(const TerrainAffinity& affinity, const TerrainDescription& terrain) {
>  
>  	return calculate_probability_to_grow(
>  	   affinity, terrain.humidity(), terrain.fertility(), terrain.temperature());
> 
> === modified file 'src/logic/map_objects/terrain_affinity.h'
> --- src/logic/map_objects/terrain_affinity.h	2018-04-07 16:59:00 +0000
> +++ src/logic/map_objects/terrain_affinity.h	2018-11-16 06:27:07 +0000
> @@ -39,39 +38,41 @@
>  // define this.
>  class TerrainAffinity {
>  public:
> +    static constexpr int kPrecisionFactor = 100000000;

I wonder if it might be beneficial to use a power of 2 here, e.g. 1<<26 or 1<<27.
Could be safer when using in floating point division, i.e. not produce rounding discrepancies when platforms/compilers use different precisions internally. Might even allow to skip some casting in favour of shift operations.

> +
>  	explicit TerrainAffinity(const LuaTable& table, const std::string& immovable_name);
>  
>  	// Preferred temperature is in arbitrary units.
> -	double preferred_temperature() const;
> -
> -	// Preferred fertility in percent [0, 1].
> -	double preferred_fertility() const;
> -
> -	// Preferred humidity in percent [0, 1].
> -	double preferred_humidity() const;
> -
> -	// A value in [0, 1] that defines how well this can deal with non-ideal
> +	int preferred_temperature() const;
> +
> +	// Preferred fertility, ranging from 0 to 1000.
> +	int preferred_fertility() const;
> +
> +	// Preferred humidity, ranging from 0 to 1000.
> +	int preferred_humidity() const;
> +
> +	// A value in [0, 99] that defines how well this can deal with non-ideal
>  	// situations. Lower means it is less picky, i.e. it can deal better.
> -	double pickiness() const;
> +	int pickiness() const;
>  
>  private:
> -	double preferred_fertility_;
> -	double preferred_humidity_;
> -	double preferred_temperature_;
> -	double pickiness_;
> +	const int preferred_fertility_;
> +	const int preferred_humidity_;
> +	const int preferred_temperature_;
> +	const int pickiness_;
>  
>  	DISALLOW_COPY_AND_ASSIGN(TerrainAffinity);
>  };
>  
>  // Returns a value in [0., 1.] that describes the suitability for the

That's not true anymore. It now returns a value in [0, TerrainAffinity::kPrecisionFactor].

>  // 'immovable_affinity' for 'field'. Higher is better suited.
> -double probability_to_grow(const TerrainAffinity& immovable_affinity,
> +unsigned int probability_to_grow(const TerrainAffinity& immovable_affinity,
>                             const FCoords& fcoords,
>                             const Map& map,
>                             const DescriptionMaintainer<TerrainDescription>& terrains);
>  
>  // Probability to grow for a single terrain

Also here it might be worth mentioning that values are in [0, TerrainAffinity::kPrecisionFactor] with TerrainAffinity::kPrecisionFactor representing probability 1.

> -double probability_to_grow(const TerrainAffinity& immovable_affinity,
> +unsigned int probability_to_grow(const TerrainAffinity& immovable_affinity,
>                             const TerrainDescription& terrain);
>  
>  }  // namespace Widelands
> 
> === 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
> @@ -464,7 +464,7 @@
>  		}
>  	}
>  	// normalize value to int16 range
> -	const int16_t correct_val = (std::numeric_limits<int16_t>::max() - 1) * best;
> +	const int16_t correct_val = (std::numeric_limits<int16_t>::max() - 1) * (best / TerrainAffinity::kPrecisionFactor);

This doesn't work. We should cast "best" to double here, otherwise it's an integer division yielding either 0 or 1. (So correct_val would only be either 0 or INT_MAX-1.)

>  
>  	if (x_check && (correct_val != cache_entry)) {
>  		forester_cache.clear();
> @@ -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)));

Switching from square before to square root now? Why such a drastic change?

Of course using the squares isn't feasible anymore because that would result in overflows. And generally we can choose whatever we want to weigh our probabilities, but why not just stay linear? Considering that the values already resemble probabilities, this seems to be the mst natural choice anyway. And there wouldn't be any need to cast between floats and ints (which is pretty safe here though), and TerrainAffinity::kPrecisionFactor is small enough that even six times as much still fits into an int. (To be somewhat robust against future changes, we could add a "static_assert" after the definition of TerrainAffinity::kPrecisionFactor to ensure that it stays small enough.)

Or did you choose the square roots to add a lot more variability in immovables shoing up?

>  	}
>  
> -	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)));

In case you are changing the square roots, also here.

>  		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.