widelands-dev team mailing list archive

[GunChleoc <fios@xxxxxxxxxxxxxxxxxxx>]

Thanks for the excellent review :)

I have addressed most of your comments and left replies to the rest.

One of our math wizards spent a long time tweaking the system and the function, so I'm hesitant to change any semantics here. There is an e function involved, so there is no way to avoid floating point completely unless we radically change the system.

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

Unlike real numbers, floating point multiplication/division is neither associative nor commutative, so I am forcing the same order of calculation here for all compilers and optimization settings. I am adding a comment to the code to make sure that nobody will "clean it up."

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

In addition to avoiding overflows, I didn't want to change the semantics. The original calculation was using power2 with values < 0, with is the same as using sqrt with values > 0.

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