Function FindClosestShipDepot

src/ship_cmd.cpp:150–201

}

static const Depot *FindClosestShipDepot(const Vehicle *v, uint max_distance)
{
	const int max_region_distance = (max_distance / WATER_REGION_EDGE_LENGTH) + 1;

	static std::unordered_set<int> visited_patch_hashes;
	static std::deque<WaterRegionPatchDesc> patches_to_search;
	visited_patch_hashes.clear();
	patches_to_search.clear();

	/* Step 1: find a set of reachable Water Region Patches using BFS. */
	const WaterRegionPatchDesc start_patch = GetWaterRegionPatchInfo(v->tile);
	patches_to_search.push_back(start_patch);
	visited_patch_hashes.insert(CalculateWaterRegionPatchHash(start_patch));

	while (!patches_to_search.empty()) {
		/* Remove first patch from the queue and make it the current patch. */
		const WaterRegionPatchDesc current_node = patches_to_search.front();
		patches_to_search.pop_front();

		/* Add neighbours of the current patch to the search queue. */
		VisitWaterRegionPatchCallback visit_func = [&](const WaterRegionPatchDesc &water_region_patch) {
			/* Note that we check the max distance per axis, not the total distance. */
			if (std::abs(water_region_patch.x - start_patch.x) > max_region_distance ||
					std::abs(water_region_patch.y - start_patch.y) > max_region_distance) return;

			const int hash = CalculateWaterRegionPatchHash(water_region_patch);
			if (visited_patch_hashes.count(hash) == 0) {
				visited_patch_hashes.insert(hash);
				patches_to_search.push_back(water_region_patch);
			}
		};

		VisitWaterRegionPatchNeighbours(current_node, visit_func);
	}

	/* Step 2: Find the closest depot within the reachable Water Region Patches. */
	const Depot *best_depot = nullptr;
	uint best_dist_sq = std::numeric_limits<uint>::max();
	for (const Depot *depot : Depot::Iterate()) {
		const TileIndex tile = depot->xy;
		if (IsShipDepotTile(tile) && IsTileOwner(tile, v->owner)) {
			const uint dist_sq = DistanceSquare(tile, v->tile);
			if (dist_sq < best_dist_sq && dist_sq <= max_distance * max_distance &&
					visited_patch_hashes.count(CalculateWaterRegionPatchHash(GetWaterRegionPatchInfo(tile))) > 0) {
				best_dist_sq = dist_sq;
				best_depot = depot;
			}
		}
	}

	return best_depot;
}

static void CheckIfShipNeedsService(Vehicle *v)
{