6 files changed, 210 insertions, 166 deletions

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<uint32_t>(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<uint32_t>(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<LineObject> 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 33ca4b2..a472a6c 100644
--- a/src/openvic-simulation/map/Map.hpp
+++ b/src/openvic-simulation/map/Map.hpp
@@ -5,6 +5,7 @@
 
 #include <openvic-dataloader/csv/LineObject.hpp>
 
+#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<uint32_t>(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<uint32_t>(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<adjacency_t const*> 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);
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<int64_t>(NumberUtils::sqrt(static_cast<uint64_t>(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;
+	}
 }