From 255f85c12d104f7f7b12bd69892a1c993885451d Mon Sep 17 00:00:00 2001 From: zaaarf Date: Tue, 2 Jan 2024 13:56:42 +0100 Subject: feat: integer and fixed point square root functions --- .../types/fixed_point/FixedPoint.hpp | 6 +++++ src/openvic-simulation/utility/NumberUtils.hpp | 29 ++++++++++++++++++++-- 2 files changed, 33 insertions(+), 2 deletions(-) (limited to 'src/openvic-simulation') diff --git a/src/openvic-simulation/types/fixed_point/FixedPoint.hpp b/src/openvic-simulation/types/fixed_point/FixedPoint.hpp index 75abefb..8d3a74b 100644 --- a/src/openvic-simulation/types/fixed_point/FixedPoint.hpp +++ b/src/openvic-simulation/types/fixed_point/FixedPoint.hpp @@ -209,6 +209,12 @@ namespace OpenVic { return !is_negative() ? value : -value; } + constexpr fixed_point_t sqrt() const { + return !is_negative() + ? static_cast(NumberUtils::sqrt(static_cast(value) << PRECISION)) + : 0; + } + // Doesn't account for sign, so -n.abc -> 1 - 0.abc constexpr fixed_point_t get_frac() const { return value & (ONE - 1); diff --git a/src/openvic-simulation/utility/NumberUtils.hpp b/src/openvic-simulation/utility/NumberUtils.hpp index 6211772..d814019 100644 --- a/src/openvic-simulation/utility/NumberUtils.hpp +++ b/src/openvic-simulation/utility/NumberUtils.hpp @@ -9,7 +9,7 @@ namespace OpenVic::NumberUtils { return (num > 0.0) ? (num + 0.5) : (num - 0.5); } - constexpr uint64_t pow(uint64_t base, size_t exponent) { + constexpr uint64_t pow(uint64_t base, std::size_t exponent) { uint64_t ret = 1; while (exponent-- > 0) { ret *= base; @@ -17,11 +17,36 @@ namespace OpenVic::NumberUtils { return ret; } - constexpr int64_t pow(int64_t base, size_t exponent) { + constexpr int64_t pow(int64_t base, std::size_t exponent) { int64_t ret = 1; while (exponent-- > 0) { ret *= base; } return ret; } + + constexpr uint64_t sqrt(uint64_t n) { + uint64_t x = n; + uint64_t c = 0; + uint64_t d = 1ull << 62; + + while (d > n) + d >>= 2; + + for (; d != 0; d >>= 2) { + if (x >= c + d) { + x -= c + d; + c = (c >> 1) + d; + } else { + c >>= 1; + } + } + + //round up + if (x > 0) { + c += 1; + } + + return c; + } } -- cgit v1.2.3-56-ga3b1 From 2f5706fd5ef6bbdee54c82860e03f00a96751693 Mon Sep 17 00:00:00 2001 From: zaaarf Date: Tue, 2 Jan 2024 15:24:06 +0100 Subject: feat: calculate province distance using new sqrt functions --- src/openvic-simulation/map/Map.cpp | 171 +++++++++++++++++++++++++++++++- src/openvic-simulation/map/Map.hpp | 8 ++ src/openvic-simulation/map/Province.cpp | 156 ----------------------------- src/openvic-simulation/map/Province.hpp | 6 -- 4 files changed, 177 insertions(+), 164 deletions(-) (limited to 'src/openvic-simulation') diff --git a/src/openvic-simulation/map/Map.cpp b/src/openvic-simulation/map/Map.cpp index cce120e..95f4991 100644 --- a/src/openvic-simulation/map/Map.cpp +++ b/src/openvic-simulation/map/Map.cpp @@ -69,6 +69,173 @@ bool Map::add_province(std::string_view identifier, colour_t colour) { return provinces.add_item(std::move(new_province)); } +Province::distance_t Map::calculate_distance_between(Province const& from, Province const& to) const { + const fvec2_t to_pos = to.get_unit_position(); + const fvec2_t from_pos = from.get_unit_position(); + + const fixed_point_t min_x = std::min( + (to_pos.x - from_pos.x).abs(), + std::min( + (to_pos.x - from_pos.x + width).abs(), + (to_pos.x - from_pos.x - width).abs() + ) + ); + + return fvec2_t { min_x, to_pos.y - from_pos.y}.length_squared().sqrt(); +} + +/* This is called for all adjacent pixel pairs and returns whether or not a new adjacency was add, + * hence the lack of error messages in the false return cases. */ +bool Map::add_standard_adjacency(Province& from, Province& to) const { + if (from == to) { + return false; + } + + const bool from_needs_adjacency = !from.is_adjacent_to(&to); + const bool to_needs_adjacency = !to.is_adjacent_to(&from); + + if (!from_needs_adjacency && !to_needs_adjacency) { + return false; + } + + const Province::distance_t distance = calculate_distance_between(from, to); + + using enum Province::adjacency_t::type_t; + + /* Default land-to-land adjacency */ + Province::adjacency_t::type_t type = LAND; + if (from.is_water() != to.is_water()) { + /* Land-to-water adjacency */ + type = COASTAL; + + /* Mark the land province as coastal */ + from.coastal = !from.is_water(); + to.coastal = !to.is_water(); + } else if (from.is_water()) { + /* Water-to-water adjacency */ + type = WATER; + } + + if (from_needs_adjacency) { + from.adjacencies.emplace_back(&to, distance, type, nullptr, 0); + } + if (to_needs_adjacency) { + to.adjacencies.emplace_back(&from, distance, type, nullptr, 0); + } + return true; +} + +bool Map::add_special_adjacency( + Province& from, Province& to, Province::adjacency_t::type_t type, Province const* through, + Province::adjacency_t::data_t data +) const { + if (from == to) { + Logger::error("Trying to add ", Province::adjacency_t::get_type_name(type), " adjacency from province ", from, " to itself!"); + return false; + } + + using enum Province::adjacency_t::type_t; + + /* Check end points */ + switch (type) { + case LAND: + case IMPASSABLE: + case STRAIT: + if (from.is_water() || to.is_water()) { + Logger::error(Province::adjacency_t::get_type_name(type), " adjacency from ", from, " to ", to, " has water endpoint(s)!"); + return false; + } + break; + case WATER: + case CANAL: + if (!from.is_water() || !to.is_water()) { + Logger::error(Province::adjacency_t::get_type_name(type), " adjacency from ", from, " to ", to, " has land endpoint(s)!"); + return false; + } + break; + case COASTAL: + if (from.is_water() == to.is_water()) { + Logger::error("Coastal adjacency from ", from, " to ", to, " has both land or water endpoints!"); + return false; + } + break; + default: + Logger::error("Invalid adjacency type ", static_cast(type)); + return false; + } + + /* Check through province */ + if (type == STRAIT || type == CANAL) { + const bool water_expected = type == STRAIT; + if (through == nullptr || through->is_water() != water_expected) { + Logger::error( + Province::adjacency_t::get_type_name(type), " adjacency from ", from, " to ", to, " has a ", + (through == nullptr ? "null" : water_expected ? "land" : "water"), " through province ", through + ); + return false; + } + } else if (through != nullptr) { + Logger::warning( + Province::adjacency_t::get_type_name(type), " adjacency from ", from, " to ", to, " has a non-null through province ", + through + ); + through = nullptr; + } + + /* Check canal data */ + if (data != Province::adjacency_t::NO_CANAL && type != CANAL) { + Logger::warning( + Province::adjacency_t::get_type_name(type), " adjacency from ", from, " to ", to, " has invalid data ", + static_cast(data) + ); + data = Province::adjacency_t::NO_CANAL; + } + + const Province::distance_t distance = calculate_distance_between(from, to); + + const auto add_adjacency = [distance, type, through, data](Province& from, Province const& to) -> bool { + Province::adjacency_t* existing_adjacency = from.get_adjacency_to(&to); + if (existing_adjacency != nullptr) { + if (type == existing_adjacency->get_type()) { + Logger::warning( + "Adjacency from ", from, " to ", to, " already has type ", Province::adjacency_t::get_type_name(type), "!" + ); + if (type != STRAIT && type != CANAL) { + /* Straits and canals might change through or data, otherwise we can exit early */ + return true; + } + } + if (type != IMPASSABLE && type != STRAIT && type != CANAL) { + Logger::error( + "Provinces ", from, " and ", to, " already have an existing ", + Province::adjacency_t::get_type_name(existing_adjacency->get_type()), " adjacency, cannot create a ", + Province::adjacency_t::get_type_name(type), " adjacency!" + ); + return false; + } + if (type != existing_adjacency->get_type() && existing_adjacency->get_type() != (type == CANAL ? WATER : LAND)) { + Logger::error( + "Cannot convert ", Province::adjacency_t::get_type_name(existing_adjacency->get_type()), " adjacency from ", from, + " to ", to, " to type ", Province::adjacency_t::get_type_name(type), "!" + ); + return false; + } + *existing_adjacency = { &to, distance, type, through, data }; + return true; + } else if (type == IMPASSABLE) { + Logger::warning( + "Provinces ", from, " and ", to, " do not have an existing adjacency to make impassable!" + ); + return true; + } else { + from.adjacencies.emplace_back(&to, distance, type, through, data); + return true; + } + }; + + return add_adjacency(from, to) & add_adjacency(to, from); +} + bool Map::set_water_province(std::string_view identifier) { if (water_provinces.is_locked()) { Logger::error("The map's water provinces have already been locked!"); @@ -564,7 +731,7 @@ bool Map::_generate_standard_province_adjacencies() { const auto generate_adjacency = [this, &changed](Province* current, size_t x, size_t y) -> bool { Province* neighbour = get_province_by_index(province_shape_image[x + y * width].index); if (neighbour != nullptr) { - return Province::add_standard_adjacency(*current, *neighbour); + return add_standard_adjacency(*current, *neighbour); } return false; }; @@ -641,7 +808,7 @@ bool Map::generate_and_load_province_adjacencies(std::vector const& } const Province::adjacency_t::data_t data = data_uint; - ret &= Province::add_special_adjacency(*from, *to, type, through, data); + ret &= add_special_adjacency(*from, *to, type, through, data); } ); return ret; diff --git a/src/openvic-simulation/map/Map.hpp b/src/openvic-simulation/map/Map.hpp index 3e7ff35..393f8d3 100644 --- a/src/openvic-simulation/map/Map.hpp +++ b/src/openvic-simulation/map/Map.hpp @@ -5,6 +5,7 @@ #include +#include "openvic-simulation/map/Province.hpp" #include "openvic-simulation/map/Region.hpp" #include "openvic-simulation/map/State.hpp" #include "openvic-simulation/map/TerrainType.hpp" @@ -89,6 +90,13 @@ namespace OpenVic { bool add_province(std::string_view identifier, colour_t colour); IDENTIFIER_REGISTRY_NON_CONST_ACCESSORS_CUSTOM_INDEX_OFFSET(province, 1); + Province::distance_t calculate_distance_between(Province const& from, Province const& to) const; + bool add_standard_adjacency(Province& from, Province& to) const; + bool add_special_adjacency( + Province& from, Province& to, Province::adjacency_t::type_t type, Province const* through, + Province::adjacency_t::data_t data + ) const; + /* This provides a safe way to remove the const qualifier of a Province const*, via a non-const Map. * It uses a const_cast (the fastest/simplest solution), but this could also be done without it by looking up the * Province* using the Province const*'s index. Requiring a non-const Map ensures that this function can only be diff --git a/src/openvic-simulation/map/Province.cpp b/src/openvic-simulation/map/Province.cpp index 1285b0d..a9bf329 100644 --- a/src/openvic-simulation/map/Province.cpp +++ b/src/openvic-simulation/map/Province.cpp @@ -185,166 +185,10 @@ bool Province::has_adjacency_going_through(Province const* province) const { ); } -/* This is called for all adjacent pixel pairs and returns whether or not a new adjacency was add, - * hence the lack of error messages in the false return cases. */ -bool Province::add_standard_adjacency(Province& from, Province& to) { - if (from == to) { - return false; - } - - const bool from_needs_adjacency = !from.is_adjacent_to(&to); - const bool to_needs_adjacency = !to.is_adjacent_to(&from); - - if (!from_needs_adjacency && !to_needs_adjacency) { - return false; - } - - const distance_t distance = calculate_distance_between(from, to); - - using enum adjacency_t::type_t; - - /* Default land-to-land adjacency */ - adjacency_t::type_t type = LAND; - if (from.is_water() != to.is_water()) { - /* Land-to-water adjacency */ - type = COASTAL; - - /* Mark the land province as coastal */ - from.coastal = !from.is_water(); - to.coastal = !to.is_water(); - } else if (from.is_water()) { - /* Water-to-water adjacency */ - type = WATER; - } - - if (from_needs_adjacency) { - from.adjacencies.emplace_back(&to, distance, type, nullptr, 0); - } - if (to_needs_adjacency) { - to.adjacencies.emplace_back(&from, distance, type, nullptr, 0); - } - return true; -} - -bool Province::add_special_adjacency( - Province& from, Province& to, adjacency_t::type_t type, Province const* through, adjacency_t::data_t data -) { - if (from == to) { - Logger::error("Trying to add ", adjacency_t::get_type_name(type), " adjacency from province ", from, " to itself!"); - return false; - } - - using enum adjacency_t::type_t; - - /* Check end points */ - switch (type) { - case LAND: - case IMPASSABLE: - case STRAIT: - if (from.is_water() || to.is_water()) { - Logger::error(adjacency_t::get_type_name(type), " adjacency from ", from, " to ", to, " has water endpoint(s)!"); - return false; - } - break; - case WATER: - case CANAL: - if (!from.is_water() || !to.is_water()) { - Logger::error(adjacency_t::get_type_name(type), " adjacency from ", from, " to ", to, " has land endpoint(s)!"); - return false; - } - break; - case COASTAL: - if (from.is_water() == to.is_water()) { - Logger::error("Coastal adjacency from ", from, " to ", to, " has both land or water endpoints!"); - return false; - } - break; - default: - Logger::error("Invalid adjacency type ", static_cast(type)); - return false; - } - - /* Check through province */ - if (type == STRAIT || type == CANAL) { - const bool water_expected = type == STRAIT; - if (through == nullptr || through->is_water() != water_expected) { - Logger::error( - adjacency_t::get_type_name(type), " adjacency from ", from, " to ", to, " has a ", - (through == nullptr ? "null" : water_expected ? "land" : "water"), " through province ", through - ); - return false; - } - } else if (through != nullptr) { - Logger::warning( - adjacency_t::get_type_name(type), " adjacency from ", from, " to ", to, " has a non-null through province ", - through - ); - through = nullptr; - } - - /* Check canal data */ - if (data != adjacency_t::NO_CANAL && type != CANAL) { - Logger::warning( - adjacency_t::get_type_name(type), " adjacency from ", from, " to ", to, " has invalid data ", - static_cast(data) - ); - data = adjacency_t::NO_CANAL; - } - - const distance_t distance = calculate_distance_between(from, to); - - const auto add_adjacency = [distance, type, through, data](Province& from, Province const& to) -> bool { - adjacency_t* existing_adjacency = from.get_adjacency_to(&to); - if (existing_adjacency != nullptr) { - if (type == existing_adjacency->get_type()) { - Logger::warning( - "Adjacency from ", from, " to ", to, " already has type ", adjacency_t::get_type_name(type), "!" - ); - if (type != STRAIT && type != CANAL) { - /* Straits and canals might change through or data, otherwise we can exit early */ - return true; - } - } - if (type != IMPASSABLE && type != STRAIT && type != CANAL) { - Logger::error( - "Provinces ", from, " and ", to, " already have an existing ", - adjacency_t::get_type_name(existing_adjacency->get_type()), " adjacency, cannot create a ", - adjacency_t::get_type_name(type), " adjacency!" - ); - return false; - } - if (type != existing_adjacency->get_type() && existing_adjacency->get_type() != (type == CANAL ? WATER : LAND)) { - Logger::error( - "Cannot convert ", adjacency_t::get_type_name(existing_adjacency->get_type()), " adjacency from ", from, - " to ", to, " to type ", adjacency_t::get_type_name(type), "!" - ); - return false; - } - *existing_adjacency = { &to, distance, type, through, data }; - return true; - } else if (type == IMPASSABLE) { - Logger::warning( - "Provinces ", from, " and ", to, " do not have an existing adjacency to make impassable!" - ); - return true; - } else { - from.adjacencies.emplace_back(&to, distance, type, through, data); - return true; - } - }; - - return add_adjacency(from, to) & add_adjacency(to, from); -} - fvec2_t Province::get_unit_position() const { return positions.unit.value_or(positions.centre); } -Province::distance_t Province::calculate_distance_between(Province const& from, Province const& to) { - const fvec2_t distance_vector = to.get_unit_position() - from.get_unit_position(); - return distance_vector.length_squared(); // TODO - replace with length using deterministic fixed point square root -} - bool Province::reset(BuildingTypeManager const& building_type_manager) { terrain_type = default_terrain_type; life_rating = 0; diff --git a/src/openvic-simulation/map/Province.hpp b/src/openvic-simulation/map/Province.hpp index bb10b29..b77ec06 100644 --- a/src/openvic-simulation/map/Province.hpp +++ b/src/openvic-simulation/map/Province.hpp @@ -155,13 +155,7 @@ namespace OpenVic { std::vector get_adjacencies_going_through(Province const* province) const; bool has_adjacency_going_through(Province const* province) const; - static bool add_standard_adjacency(Province& from, Province& to); - static bool add_special_adjacency( - Province& from, Province& to, adjacency_t::type_t type, Province const* through, adjacency_t::data_t data - ); - fvec2_t get_unit_position() const; - static distance_t calculate_distance_between(Province const& from, Province const& to); bool reset(BuildingTypeManager const& building_type_manager); bool apply_history_to_province(ProvinceHistoryEntry const* entry); -- cgit v1.2.3-56-ga3b1