11#include "../map_func.h"
13#include "../tilearea_type.h"
14#include "../track_func.h"
15#include "../transport_type.h"
16#include "../landscape.h"
17#include "../tunnelbridge_map.h"
21#include "../3rdparty/fmt/ranges.h"
22#include "../core/convertible_through_base.hpp"
23#include "../safeguards.h"
25using WaterRegionTraversabilityBits = uint16_t;
28static_assert(
sizeof(WaterRegionTraversabilityBits) * 8 == WATER_REGION_EDGE_LENGTH);
34static inline int GetWaterRegionX(
TileIndex tile) {
return TileX(tile) / WATER_REGION_EDGE_LENGTH; }
35static inline int GetWaterRegionY(
TileIndex tile) {
return TileY(tile) / WATER_REGION_EDGE_LENGTH; }
37static inline int GetWaterRegionMapSizeX() {
return Map::SizeX() / WATER_REGION_EDGE_LENGTH; }
38static inline int GetWaterRegionMapSizeY() {
return Map::SizeY() / WATER_REGION_EDGE_LENGTH; }
41static inline WaterRegionIndex GetWaterRegionIndex(
TileIndex tile) {
return GetWaterRegionIndex(GetWaterRegionX(tile), GetWaterRegionY(tile)); }
43using WaterRegionPatchLabelArray = std::array<WaterRegionPatchLabel, WATER_REGION_NUMBER_OF_TILES>;
51 std::array<WaterRegionTraversabilityBits, DIAGDIR_END> edge_traversability_bits{};
52 std::unique_ptr<WaterRegionPatchLabelArray> tile_patch_labels;
53 bool has_cross_region_aqueducts =
false;
54 WaterRegionPatchLabel::BaseType number_of_patches{0};
77 assert(this->tile_area.
Contains(tile));
83 : data(water_region_data)
84 , tile_area(
TileXY(region_x * WATER_REGION_EDGE_LENGTH, region_y * WATER_REGION_EDGE_LENGTH), WATER_REGION_EDGE_LENGTH, WATER_REGION_EDGE_LENGTH)
103 int NumberOfPatches()
const {
return static_cast<int>(this->data.number_of_patches); }
117 assert(this->tile_area.
Contains(tile));
118 if (this->data.tile_patch_labels ==
nullptr) {
119 return this->
NumberOfPatches() == 0 ? INVALID_WATER_REGION_PATCH : FIRST_REGION_LABEL;
121 return (*this->data.tile_patch_labels)[this->
GetLocalIndex(tile)];
130 Debug(map, 3,
"Updating water region ({},{})", GetWaterRegionX(this->tile_area.
tile), GetWaterRegionY(this->tile_area.
tile));
131 this->data.has_cross_region_aqueducts =
false;
134 if (this->data.tile_patch_labels ==
nullptr) {
135 this->data.tile_patch_labels = std::make_unique<WaterRegionPatchLabelArray>();
138 this->data.tile_patch_labels->fill(INVALID_WATER_REGION_PATCH);
139 this->data.edge_traversability_bits.fill(0);
146 for (
const TileIndex start_tile : this->tile_area) {
147 static std::vector<TileIndex> tiles_to_check;
148 tiles_to_check.clear();
149 tiles_to_check.push_back(start_tile);
151 bool increase_label =
false;
152 while (!tiles_to_check.empty()) {
153 const TileIndex tile = tiles_to_check.back();
154 tiles_to_check.pop_back();
160 if (tile_patch != INVALID_WATER_REGION_PATCH)
continue;
162 tile_patch = current_label;
163 highest_assigned_label = current_label;
164 increase_label =
true;
169 if (ft.
Follow(tile, dir)) {
171 tiles_to_check.push_back(ft.
new_tile);
176 SetBit(this->data.edge_traversability_bits[side], local_x_or_y);
178 this->data.has_cross_region_aqueducts =
true;
184 if (increase_label) current_label++;
187 this->data.number_of_patches = highest_assigned_label.base();
190 std::all_of(this->data.tile_patch_labels->begin(), this->data.tile_patch_labels->end(), [](
WaterRegionPatchLabel label) { return label == FIRST_REGION_LABEL; }))) {
192 this->data.tile_patch_labels.reset();
196 void PrintDebugInfo()
198 Debug(map, 9,
"Water region {},{} labels and edge traversability = ...", GetWaterRegionX(this->tile_area.
tile), GetWaterRegionY(this->tile_area.
tile));
200 const size_t max_element_width = fmt::format(
"{}", this->
NumberOfPatches()).size();
203 Debug(map, 9,
" {:{}}", fmt::join(traversability,
" "), max_element_width);
204 Debug(map, 9,
" +{:->{}}+",
"", WATER_REGION_EDGE_LENGTH * (max_element_width + 1) + 1);
206 for (
int y = 0; y < WATER_REGION_EDGE_LENGTH; ++y) {
208 for (
int x = 0; x < WATER_REGION_EDGE_LENGTH; ++x) {
210 if (label == INVALID_WATER_REGION_PATCH) {
211 line = fmt::format(
"{:{}} {}",
".", max_element_width, line);
213 line = fmt::format(
"{:{}} {}", label, max_element_width, line);
219 Debug(map, 9,
" +{:->{}}+",
"", WATER_REGION_EDGE_LENGTH * (max_element_width + 1) + 1);
221 Debug(map, 9,
" {:{}}", fmt::join(traversability,
" "), max_element_width);
228static TileIndex GetTileIndexFromLocalCoordinate(
int region_x,
int region_y,
int local_x,
int local_y)
230 assert(local_x >= 0 && local_x < WATER_REGION_EDGE_LENGTH);
231 assert(local_y >= 0 && local_y < WATER_REGION_EDGE_LENGTH);
232 return TileXY(WATER_REGION_EDGE_LENGTH * region_x + local_x, WATER_REGION_EDGE_LENGTH * region_y + local_y);
237 assert(x_or_y >= 0 && x_or_y < WATER_REGION_EDGE_LENGTH);
239 case DIAGDIR_NE:
return GetTileIndexFromLocalCoordinate(region_x, region_y, 0, x_or_y);
240 case DIAGDIR_SW:
return GetTileIndexFromLocalCoordinate(region_x, region_y, WATER_REGION_EDGE_LENGTH - 1, x_or_y);
241 case DIAGDIR_NW:
return GetTileIndexFromLocalCoordinate(region_x, region_y, x_or_y, 0);
242 case DIAGDIR_SE:
return GetTileIndexFromLocalCoordinate(region_x, region_y, x_or_y, WATER_REGION_EDGE_LENGTH - 1);
243 default: NOT_REACHED();
247static WaterRegion GetUpdatedWaterRegion(uint16_t region_x, uint16_t region_y)
250 WaterRegion water_region(region_x, region_y, _water_region_data[index]);
251 if (!_is_water_region_valid[index]) {
252 water_region.ForceUpdate();
253 _is_water_region_valid[index] =
true;
260 return GetUpdatedWaterRegion(GetWaterRegionX(tile), GetWaterRegionY(tile));
269 return GetWaterRegionIndex(water_region.
x, water_region.
y);
278 return water_region_patch.
label.base() | GetWaterRegionIndex(water_region_patch).base() << 8;
288 return TileXY(water_region.
x * WATER_REGION_EDGE_LENGTH + (WATER_REGION_EDGE_LENGTH / 2), water_region.
y * WATER_REGION_EDGE_LENGTH + (WATER_REGION_EDGE_LENGTH / 2));
297 return WaterRegionDesc{ GetWaterRegionX(tile), GetWaterRegionY(tile) };
306 const WaterRegion region = GetUpdatedWaterRegion(tile);
318 auto invalidate_region = [](
TileIndex tile) {
320 if (!_is_water_region_valid[water_region_index])
Debug(map, 3,
"Invalidated water region ({},{})", GetWaterRegionX(tile), GetWaterRegionY(tile));
321 _is_water_region_valid[water_region_index] =
false;
324 invalidate_region(tile);
332 if (GetWaterRegionIndex(adjacent_tile) != GetWaterRegionIndex(tile)) invalidate_region(adjacent_tile);
345 if (water_region_patch.
label == INVALID_WATER_REGION_PATCH)
return;
347 const WaterRegion current_region = GetUpdatedWaterRegion(water_region_patch.
x, water_region_patch.
y);
350 const int nx = water_region_patch.
x + offset.
x;
351 const int ny = water_region_patch.
y + offset.
y;
353 if (nx < 0 || ny < 0 || nx >= GetWaterRegionMapSizeX() || ny >= GetWaterRegionMapSizeY())
return;
355 const WaterRegion neighbouring_region = GetUpdatedWaterRegion(nx, ny);
361 if (traversability_bits == 0)
return;
369 static std::vector<WaterRegionPatchLabel> unique_labels;
370 unique_labels.clear();
371 for (
int x_or_y = 0; x_or_y < WATER_REGION_EDGE_LENGTH; ++x_or_y) {
372 if (!
HasBit(traversability_bits, x_or_y))
continue;
374 const TileIndex current_edge_tile = GetEdgeTileCoordinate(water_region_patch.
x, water_region_patch.
y, side, x_or_y);
376 if (current_label != water_region_patch.
label)
continue;
378 const TileIndex neighbour_edge_tile = GetEdgeTileCoordinate(nx, ny, opposite_side, x_or_y);
380 assert(neighbour_label != INVALID_WATER_REGION_PATCH);
381 if (std::ranges::find(unique_labels, neighbour_label) == unique_labels.end()) unique_labels.push_back(neighbour_label);
394 if (water_region_patch.
label == INVALID_WATER_REGION_PATCH)
return;
396 const WaterRegion current_region = GetUpdatedWaterRegion(water_region_patch.
x, water_region_patch.
y);
403 for (
const TileIndex tile : current_region) {
406 if (GetWaterRegionIndex(tile) != GetWaterRegionIndex(other_end_tile)) callback(
GetWaterRegionPatchInfo(other_end_tile));
417 const int number_of_regions = GetWaterRegionMapSizeX() * GetWaterRegionMapSizeY();
419 _water_region_data.clear();
420 _water_region_data.resize(number_of_regions);
422 _is_water_region_valid.clear();
423 _is_water_region_valid.resize(number_of_regions,
false);
425 Debug(map, 2,
"Allocating {} x {} water regions", GetWaterRegionMapSizeX(), GetWaterRegionMapSizeY());
426 assert(_is_water_region_valid.size() == _water_region_data.size());
429void PrintWaterRegionDebugInfo(
TileIndex tile)
431 GetUpdatedWaterRegion(tile).PrintDebugInfo();
debug_inline constexpr bool HasBit(const T x, const uint8_t y)
Checks if a bit in a value is set.
constexpr T SetBit(T &x, const uint8_t y)
Set a bit in a variable.
debug_inline static constexpr uint GB(const T x, const uint8_t s, const uint8_t n)
Fetch n bits from x, started at bit s.
TileIndex GetOtherBridgeEnd(TileIndex tile)
Starting at one bridge end finds the other bridge end.
bool IsBridgeTile(Tile t)
checks if there is a bridge on this tile
Iterator to iterate over a tile area (rectangle) of the map.
A sort-of mixin that adds 'at(pos)' and 'operator[](pos)' implementations for 'ConvertibleThroughBase...
The data stored for each water region.
Represents a square section of the map of a fixed size.
WaterRegionPatchLabel GetLabel(TileIndex tile) const
Returns the patch label that was assigned to the tile.
int NumberOfPatches() const
bool HasCrossRegionAqueducts() const
int GetLocalIndex(TileIndex tile) const
Returns the local index of the tile within the region.
void ForceUpdate()
Performs the connected component labeling and other data gathering.
WaterRegionTraversabilityBits GetEdgeTraversabilityBits(DiagDirection side) const
Returns a set of bits indicating whether an edge tile on a particular side is traversable or not.
#define Debug(category, level, format_string,...)
Output a line of debugging information.
DiagDirection ReverseDiagDir(DiagDirection d)
Returns the reverse direction of the given DiagDirection.
Axis DiagDirToAxis(DiagDirection d)
Convert a DiagDirection to the axis.
DiagDirection
Enumeration for diagonal directions.
@ DIAGDIR_NE
Northeast, upper right on your monitor.
@ DIAGDIR_END
Used for iterations.
@ DIAGDIR_BEGIN
Used for iterations.
Template function for track followers.
TrackStatus GetTileTrackStatus(TileIndex tile, TransportType mode, uint sub_mode, DiagDirection side)
Returns information about trackdirs and signal states.
uint DistanceManhattan(TileIndex t0, TileIndex t1)
Gets the Manhattan distance between the two given tiles.
DiagDirection DiagdirBetweenTiles(TileIndex tile_from, TileIndex tile_to)
Determines the DiagDirection to get from one tile to another.
TileIndex TileAddXY(TileIndex tile, int x, int y)
Adds a given offset to a tile.
TileIndex AddTileIndexDiffCWrap(TileIndex tile, TileIndexDiffC diff)
Add a TileIndexDiffC to a TileIndex and returns the new one.
static debug_inline TileIndex TileXY(uint x, uint y)
Returns the TileIndex of a coordinate.
TileIndexDiffC TileIndexDiffCByDiagDir(DiagDirection dir)
Returns the TileIndexDiffC offset from a DiagDirection.
static debug_inline uint TileY(TileIndex tile)
Get the Y component of a tile.
static debug_inline uint TileX(TileIndex tile)
Get the X component of a tile.
Track follower helper template class (can serve pathfinders and vehicle controllers).
bool Follow(TileIndex old_tile, Trackdir old_td)
main follower routine.
bool is_bridge
last turn passed bridge ramp
TileIndex new_tile
the new tile (the vehicle has entered)
static uint SizeY()
Get the size of the map along the Y.
static debug_inline uint SizeX()
Get the size of the map along the X.
Represents the covered area of e.g.
OrthogonalTileIterator end() const
Returns an iterator to the end of the tile area.
bool Contains(TileIndex tile) const
Does this tile area contain a tile?
TileIndex tile
The base tile of the area.
OrthogonalTileIterator begin() const
Returns an iterator to the beginning of the tile area.
Iterable ensemble of each set bit in a value.
A pair-construct of a TileIndexDiff.
int16_t x
The x value of the coordinate.
int16_t y
The y value of the coordinate.
Describes a single square water region.
int x
The X coordinate of the water region, i.e. X=2 is the 3rd water region along the X-axis.
int y
The Y coordinate of the water region, i.e. Y=2 is the 3rd water region along the Y-axis.
Describes a single interconnected patch of water within a particular water region.
int y
The Y coordinate of the water region, i.e. Y=2 is the 3rd water region along the Y-axis.
int x
The X coordinate of the water region, i.e. X=2 is the 3rd water region along the X-axis.
WaterRegionPatchLabel label
Unique label identifying the patch within the region.
bool IsValidTile(Tile tile)
Checks if a tile is valid.
constexpr TileIndex INVALID_TILE
The very nice invalid tile marker.
TrackdirBits TrackBitsToTrackdirBits(TrackBits bits)
Converts TrackBits to TrackdirBits while allowing both directions.
TrackBits TrackStatusToTrackBits(TrackStatus ts)
Returns the present-track-information of a TrackStatus.
TrackBits
Allow incrementing of Track variables.
Trackdir
Enumeration for tracks and directions.
TrackdirBits
Allow incrementing of Trackdir variables.
@ TRACKDIR_BIT_NONE
No track build.
@ TRANSPORT_WATER
Transport over water.
TransportType GetTunnelBridgeTransportType(Tile t)
Tunnel: Get the transport type of the tunnel (road or rail) Bridge: Get the transport type of the bri...
void AllocateWaterRegions()
Allocates the appropriate amount of water regions for the current map size.
WaterRegionDesc GetWaterRegionInfo(TileIndex tile)
Returns basic water region information for the provided tile.
WaterRegionPatchDesc GetWaterRegionPatchInfo(TileIndex tile)
Returns basic water region patch information for the provided tile.
static void VisitAdjacentWaterRegionPatchNeighbours(const WaterRegionPatchDesc &water_region_patch, DiagDirection side, VisitWaterRegionPatchCallback &func)
Calls the provided callback function for all water region patches accessible from one particular side...
TileIndex GetWaterRegionCenterTile(const WaterRegionDesc &water_region)
Returns the center tile of a particular water region.
void InvalidateWaterRegion(TileIndex tile)
Marks the water region that tile is part of as invalid.
int CalculateWaterRegionPatchHash(const WaterRegionPatchDesc &water_region_patch)
Calculates a number that uniquely identifies the provided water region patch.
void VisitWaterRegionPatchNeighbours(const WaterRegionPatchDesc &water_region_patch, VisitWaterRegionPatchCallback &callback)
Calls the provided callback function on all accessible water region patches in each cardinal directio...
Handles dividing the water in the map into regions to assist pathfinding.