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.
_______________________________________________
Mailing list: https://launchpad.net/~widelands-dev
Post to : widelands-dev@lists.launchpad.net
Unsubscribe : https://launchpad.net/~widelands-dev
More help : https://help.launchpad.net/ListHelp
