23 using TWaterRegionTraversabilityBits = uint16_t;
24 constexpr TWaterRegionPatchLabel FIRST_REGION_LABEL = 1;
26 static_assert(
sizeof(TWaterRegionTraversabilityBits) * 8 == WATER_REGION_EDGE_LENGTH);
27 static_assert(
sizeof(TWaterRegionPatchLabel) ==
sizeof(uint8_t));
32 static inline int GetWaterRegionX(
TileIndex tile) {
return TileX(tile) / WATER_REGION_EDGE_LENGTH; }
33 static inline int GetWaterRegionY(
TileIndex tile) {
return TileY(tile) / WATER_REGION_EDGE_LENGTH; }
35 static inline int GetWaterRegionMapSizeX() {
return Map::SizeX() / WATER_REGION_EDGE_LENGTH; }
36 static inline int GetWaterRegionMapSizeY() {
return Map::SizeY() / WATER_REGION_EDGE_LENGTH; }
38 static inline TWaterRegionIndex
GetWaterRegionIndex(
int region_x,
int region_y) {
return GetWaterRegionMapSizeX() * region_y + region_x; }
41 using TWaterRegionPatchLabelArray = std::array<TWaterRegionPatchLabel, WATER_REGION_NUMBER_OF_TILES>;
49 std::array<TWaterRegionTraversabilityBits, DIAGDIR_END> edge_traversability_bits{};
50 std::unique_ptr<TWaterRegionPatchLabelArray> tile_patch_labels;
51 bool has_cross_region_aqueducts =
false;
52 TWaterRegionPatchLabel number_of_patches = 0;
75 assert(this->tile_area.
Contains(tile));
81 : data(water_region_data)
82 , tile_area(
TileXY(region_x * WATER_REGION_EDGE_LENGTH, region_y * WATER_REGION_EDGE_LENGTH), WATER_REGION_EDGE_LENGTH, WATER_REGION_EDGE_LENGTH)
101 int NumberOfPatches()
const {
return static_cast<int>(this->data.number_of_patches); }
115 assert(this->tile_area.
Contains(tile));
116 if (this->data.tile_patch_labels ==
nullptr) {
117 return this->
NumberOfPatches() == 0 ? INVALID_WATER_REGION_PATCH : FIRST_REGION_LABEL;
119 return (*this->data.tile_patch_labels)[this->
GetLocalIndex(tile)];
128 Debug(map, 3,
"Updating water region ({},{})", GetWaterRegionX(this->tile_area.
tile), GetWaterRegionY(this->tile_area.
tile));
129 this->data.has_cross_region_aqueducts =
false;
132 if (this->data.tile_patch_labels ==
nullptr) {
133 this->data.tile_patch_labels = std::make_unique<TWaterRegionPatchLabelArray>();
136 this->data.tile_patch_labels->fill(INVALID_WATER_REGION_PATCH);
137 this->data.edge_traversability_bits.fill(0);
139 TWaterRegionPatchLabel current_label = FIRST_REGION_LABEL;
140 TWaterRegionPatchLabel highest_assigned_label = INVALID_WATER_REGION_PATCH;
144 for (
const TileIndex start_tile : this->tile_area) {
145 static std::vector<TileIndex> tiles_to_check;
146 tiles_to_check.clear();
147 tiles_to_check.push_back(start_tile);
149 bool increase_label =
false;
150 while (!tiles_to_check.empty()) {
151 const TileIndex tile = tiles_to_check.back();
152 tiles_to_check.pop_back();
157 TWaterRegionPatchLabel &tile_patch = (*this->data.tile_patch_labels)[this->
GetLocalIndex(tile)];
158 if (tile_patch != INVALID_WATER_REGION_PATCH)
continue;
160 tile_patch = current_label;
161 highest_assigned_label = current_label;
162 increase_label =
true;
167 if (ft.
Follow(tile, dir)) {
168 if (this->tile_area.Contains(ft.
new_tile)) {
169 tiles_to_check.push_back(ft.
new_tile);
174 SetBit(this->data.edge_traversability_bits[side], local_x_or_y);
176 this->data.has_cross_region_aqueducts =
true;
182 if (increase_label) current_label++;
185 this->data.number_of_patches = highest_assigned_label;
188 std::all_of(this->data.tile_patch_labels->begin(), this->data.tile_patch_labels->end(), [](TWaterRegionPatchLabel label) { return label == FIRST_REGION_LABEL; }))) {
190 this->data.tile_patch_labels.reset();
194 void PrintDebugInfo()
196 Debug(map, 9,
"Water region {},{} labels and edge traversability = ...", GetWaterRegionX(this->tile_area.
tile), GetWaterRegionY(this->tile_area.
tile));
198 const size_t max_element_width = std::to_string(this->
NumberOfPatches()).size();
201 Debug(map, 9,
" {:{}}", fmt::join(traversability,
" "), max_element_width);
202 Debug(map, 9,
" +{:->{}}+",
"", WATER_REGION_EDGE_LENGTH * (max_element_width + 1) + 1);
204 for (
int y = 0; y < WATER_REGION_EDGE_LENGTH; ++y) {
206 for (
int x = 0; x < WATER_REGION_EDGE_LENGTH; ++x) {
208 const std::string label_str = label == INVALID_WATER_REGION_PATCH ?
"." : std::to_string(label);
209 line = fmt::format(
"{:{}}", label_str, max_element_width) +
" " + line;
214 Debug(map, 9,
" +{:->{}}+",
"", WATER_REGION_EDGE_LENGTH * (max_element_width + 1) + 1);
216 Debug(map, 9,
" {:{}}", fmt::join(traversability,
" "), max_element_width);
220 std::vector<WaterRegionData> _water_region_data;
221 std::vector<bool> _is_water_region_valid;
223 static TileIndex GetTileIndexFromLocalCoordinate(
int region_x,
int region_y,
int local_x,
int local_y)
225 assert(local_x >= 0 && local_x < WATER_REGION_EDGE_LENGTH);
226 assert(local_y >= 0 && local_y < WATER_REGION_EDGE_LENGTH);
227 return TileXY(WATER_REGION_EDGE_LENGTH * region_x + local_x, WATER_REGION_EDGE_LENGTH * region_y + local_y);
232 assert(x_or_y >= 0 && x_or_y < WATER_REGION_EDGE_LENGTH);
234 case DIAGDIR_NE:
return GetTileIndexFromLocalCoordinate(region_x, region_y, 0, x_or_y);
235 case DIAGDIR_SW:
return GetTileIndexFromLocalCoordinate(region_x, region_y, WATER_REGION_EDGE_LENGTH - 1, x_or_y);
236 case DIAGDIR_NW:
return GetTileIndexFromLocalCoordinate(region_x, region_y, x_or_y, 0);
237 case DIAGDIR_SE:
return GetTileIndexFromLocalCoordinate(region_x, region_y, x_or_y, WATER_REGION_EDGE_LENGTH - 1);
238 default: NOT_REACHED();
242 static WaterRegion GetUpdatedWaterRegion(uint16_t region_x, uint16_t region_y)
245 WaterRegion water_region(region_x, region_y, _water_region_data[index]);
246 if (!_is_water_region_valid[index]) {
247 water_region.ForceUpdate();
248 _is_water_region_valid[index] =
true;
255 return GetUpdatedWaterRegion(GetWaterRegionX(tile), GetWaterRegionY(tile));
283 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));
292 return WaterRegionDesc{ GetWaterRegionX(tile), GetWaterRegionY(tile) };
301 const WaterRegion region = GetUpdatedWaterRegion(tile);
313 auto invalidate_region = [](
TileIndex tile) {
315 if (!_is_water_region_valid[water_region_index])
Debug(map, 3,
"Invalidated water region ({},{})", GetWaterRegionX(tile), GetWaterRegionY(tile));
316 _is_water_region_valid[water_region_index] =
false;
319 invalidate_region(tile);
340 if (water_region_patch.
label == INVALID_WATER_REGION_PATCH)
return;
342 const WaterRegion current_region = GetUpdatedWaterRegion(water_region_patch.
x, water_region_patch.
y);
345 const int nx = water_region_patch.
x + offset.
x;
346 const int ny = water_region_patch.
y + offset.
y;
348 if (nx < 0 || ny < 0 || nx >= GetWaterRegionMapSizeX() || ny >= GetWaterRegionMapSizeY())
return;
350 const WaterRegion neighboring_region = GetUpdatedWaterRegion(nx, ny);
356 if (traversability_bits == 0)
return;
364 static std::vector<TWaterRegionPatchLabel> unique_labels;
365 unique_labels.clear();
366 for (
int x_or_y = 0; x_or_y < WATER_REGION_EDGE_LENGTH; ++x_or_y) {
367 if (!
HasBit(traversability_bits, x_or_y))
continue;
369 const TileIndex current_edge_tile = GetEdgeTileCoordinate(water_region_patch.
x, water_region_patch.
y, side, x_or_y);
370 const TWaterRegionPatchLabel current_label = current_region.
GetLabel(current_edge_tile);
371 if (current_label != water_region_patch.
label)
continue;
373 const TileIndex neighbor_edge_tile = GetEdgeTileCoordinate(nx, ny, opposite_side, x_or_y);
374 const TWaterRegionPatchLabel neighbor_label = neighboring_region.
GetLabel(neighbor_edge_tile);
375 assert(neighbor_label != INVALID_WATER_REGION_PATCH);
376 if (std::find(unique_labels.begin(), unique_labels.end(), neighbor_label) == unique_labels.end()) unique_labels.push_back(neighbor_label);
378 for (TWaterRegionPatchLabel unique_label : unique_labels) func(
WaterRegionPatchDesc{ nx, ny, unique_label });
389 if (water_region_patch.
label == INVALID_WATER_REGION_PATCH)
return;
391 const WaterRegion current_region = GetUpdatedWaterRegion(water_region_patch.
x, water_region_patch.
y);
398 for (
const TileIndex tile : current_region) {
412 const int number_of_regions = GetWaterRegionMapSizeX() * GetWaterRegionMapSizeY();
414 _water_region_data.clear();
415 _water_region_data.resize(number_of_regions);
417 _is_water_region_valid.clear();
418 _is_water_region_valid.resize(number_of_regions,
false);
420 Debug(map, 2,
"Allocating {} x {} water regions", GetWaterRegionMapSizeX(), GetWaterRegionMapSizeY());
421 assert(_is_water_region_valid.size() == _water_region_data.size());
424 void PrintWaterRegionDebugInfo(
TileIndex tile)
426 GetUpdatedWaterRegion(tile).PrintDebugInfo();
constexpr debug_inline 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.
constexpr static debug_inline 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.
The data stored for each water region.
Represents a square section of the map of a fixed size.
TWaterRegionPatchLabel 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.
TWaterRegionTraversabilityBits GetEdgeTraversabilityBits(DiagDirection side) const
Returns a set of bits indicating whether an edge tile on a particular side is traversable or not.
Functions related to debugging.
#define Debug(category, level, format_string,...)
Ouptut 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.
Functions related to OTTD's landscape.
uint DistanceManhattan(TileIndex t0, TileIndex t1)
Gets the Manhattan distance between the two given tiles.
Functions related to maps.
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.
Definition of base types and functions in a cross-platform compatible way.
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.
TWaterRegionPatchLabel label
Unique label identifying the patch within the 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.
bool IsValidTile(Tile tile)
Checks if a tile is valid.
constexpr TileIndex INVALID_TILE
The very nice invalid tile marker.
Type for storing the 'area' of something uses on the map.
Different conversion functions from one kind of track to another.
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.
Base types related to transport.
@ TRANSPORT_WATER
Transport over water.
Functions that have tunnels and bridges in common.
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.
static TWaterRegionIndex GetWaterRegionIndex(const WaterRegionDesc &water_region)
Returns the index of the water region.
static void VisitAdjacentWaterRegionPatchNeighbors(const WaterRegionPatchDesc &water_region_patch, DiagDirection side, TVisitWaterRegionPatchCallBack &func)
Calls the provided callback function for all water region patches accessible from one particular side...
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.
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.
void VisitWaterRegionPatchNeighbors(const WaterRegionPatchDesc &water_region_patch, TVisitWaterRegionPatchCallBack &callback)
Calls the provided callback function on all accessible water region patches in each cardinal directio...
int CalculateWaterRegionPatchHash(const WaterRegionPatchDesc &water_region_patch)
Calculates a number that uniquely identifies the provided water region patch.
Handles dividing the water in the map into regions to assist pathfinding.