OpenTTD Source 20261112-master-gbcbec5e63f
yapf_river_builder.cpp
Go to the documentation of this file.
1/*
2 * This file is part of OpenTTD.
3 * OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
4 * OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
5 * See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <https://www.gnu.org/licenses/old-licenses/gpl-2.0>.
6 */
7
9
10#include "../../stdafx.h"
11
12#include "../../water.h"
13#include "../../genworld.h"
15#include "yapf.hpp"
16
17#include "../../safeguards.h"
18
19/* River builder pathfinder node. */
20struct YapfRiverBuilderNode : CYapfNodeT<CYapfNodeKeyTrackDir, YapfRiverBuilderNode> {};
21
24
25/* We don't need a follower but YAPF requires one. */
27
28/* We don't need a vehicle but YAPF requires one. */
30
32
35 using Tpf = YapfRiverBuilder;
36 using TrackFollower = RiverBuilderFollower;
37 using NodeList = RiverBuilderNodeList;
38 using VehicleType = DummyVehicle;
39};
40
42class YapfRiverBuilder
43 : public CYapfBaseT<RiverBuilderTypes>
44 , public CYapfSegmentCostCacheNoneT<RiverBuilderTypes>
45{
46public:
47 using Node = RiverBuilderTypes::NodeList::Item;
48 using Key = Node::Key;
49
50protected:
52
53 inline YapfRiverBuilder &Yapf()
54 {
55 return *static_cast<YapfRiverBuilder *>(this);
56 }
57
58public:
60 {
61 this->end_tile = end_tile;
62
63 Node &node = Yapf().CreateNewNode();
64 node.Set(nullptr, start_tile, Trackdir::Invalid, false);
65 Yapf().AddStartupNode(node);
66 }
67
69 inline bool PfDetectDestination(Node &n) const
70 {
71 return n.GetTile() == this->end_tile;
72 }
73
75 inline bool PfCalcCost(Node &n, [[maybe_unused]] const RiverBuilderFollower *follower)
76 {
77 n.cost = n.parent->cost + 1 + RandomRange(_settings_game.game_creation.river_route_random);
78 return true;
79 }
80
82 inline bool PfCalcEstimate(Node &n)
83 {
84 n.estimate = n.cost + DistanceManhattan(this->end_tile, n.GetTile());
85 assert(n.estimate >= n.parent->estimate);
86 return true;
87 }
88
90 inline void PfFollowNode(Node &old_node)
91 {
93 const TileIndex t = old_node.GetTile() + TileOffsByDiagDir(d);
94 if (IsValidTile(t) && RiverFlowsDown(old_node.GetTile(), t)) {
95 Node &node = Yapf().CreateNewNode();
96 node.Set(&old_node, t, Trackdir::Invalid, true);
98 }
99 }
100 }
101
103 inline char TransportTypeChar() const
104 {
105 return '~';
106 }
107
108 static void BuildRiver(TileIndex start_tile, TileIndex end_tile, TileIndex spring_tile, bool main_river)
109 {
110 YapfRiverBuilder pf(start_tile, end_tile);
111 if (pf.FindPath(nullptr) == false) return; // No path found
112
113 /* First, build the river without worrying about its width. */
114 for (Node *node = pf.GetBestNode(); node != nullptr; node = node->parent) {
115 TileIndex tile = node->GetTile();
116 if (!IsWaterTile(tile)) {
118 }
119 }
120
121 /* If the river is a main river, go back along the path to widen it.
122 * Don't make wide rivers if we're using the original landscape generator.
123 */
125 const uint long_river_length = _settings_game.game_creation.min_river_length * 4;
126
127 for (Node *node = pf.GetBestNode(); node != nullptr; node = node->parent) {
128 const TileIndex center_tile = node->GetTile();
129
130 /* Check if we should widen river depending on how far we are away from the source. */
131 uint current_river_length = DistanceManhattan(spring_tile, center_tile);
132 uint diameter = std::min(3u, (current_river_length / (long_river_length / 3u)) + 1u);
133 if (diameter <= 1) continue;
134
135 for (auto tile : SpiralTileSequence(center_tile, diameter)) {
136 RiverMakeWider(tile, center_tile);
137 }
138 }
139 }
140 }
141};
142
150void YapfBuildRiver(TileIndex start_tile, TileIndex end_tile, TileIndex spring_tile, bool main_river)
151{
152 YapfRiverBuilder::BuildRiver(start_tile, end_tile, spring_tile, main_river);
153}
void AddNewNode(Node &n, const TrackFollower &follower)
AddNewNode() - called by Tderived::PfFollowNode() for each child node.
Node & CreateNewNode()
Calls NodeList::CreateNewNode() - allocates new node that can be filled and used as argument for AddS...
void AddStartupNode(Node &n)
Add new node (created by CreateNewNode and filled with data) into open list.
CYapfSegmentCostCacheNoneT - the formal only yapf cost cache provider that implements PfNodeCacheFetc...
Iterate a range of enum values.
Hash table based node list multi-container class.
Definition nodelist.hpp:21
River builder pathfinder implementation.
char TransportTypeChar() const
Return debug report character to identify the transportation type.
TileIndex end_tile
End tile of the river.
bool PfCalcEstimate(Node &n)
Called by YAPF to calculate cost estimate.
bool PfDetectDestination(Node &n) const
Called by YAPF to detect if node ends in the desired destination.
bool PfCalcCost(Node &n, const RiverBuilderFollower *follower)
Called by YAPF to calculate the cost from the origin to the given node.
void PfFollowNode(Node &old_node)
Called by YAPF to move from the given node to the next tile.
DiagDirection
Enumeration for diagonal directions.
@ End
Used for iterations.
Functions related to world/map generation.
@ LG_ORIGINAL
The original landscape generator.
Definition genworld.h:19
bool RiverFlowsDown(TileIndex begin, TileIndex end)
Check whether a river at begin could (logically) flow down to end.
void RiverMakeWider(TileIndex tile, TileIndex origin_tile)
Widen a river by expanding into adjacent tiles via circular tile search.
uint DistanceManhattan(TileIndex t0, TileIndex t1)
Gets the Manhattan distance between the two given tiles.
Definition map.cpp:168
TileIndexDiff TileOffsByDiagDir(DiagDirection dir)
Convert a DiagDirection to a TileIndexDiff.
Definition map_func.h:574
uint32_t RandomRange(uint32_t limit, const std::source_location location=std::source_location::current())
Pick a random number between 0 and limit - 1, inclusive.
A number of safeguards to prevent using unsafe methods.
GameSettings _settings_game
Game settings of a running game or the scenario editor.
Definition settings.cpp:61
Definition of base types and functions in a cross-platform compatible way.
Yapf Node base.
Definition yapf_node.hpp:61
uint8_t min_river_length
the minimum river length
uint8_t land_generator
the landscape generator
GameCreationSettings game_creation
settings used during the creation of a game (map)
Types struct required for YAPF components.
Vehicle(VehicleID index, VehicleType type=VehicleType::Invalid)
Vehicle constructor.
Definition vehicle.cpp:381
bool IsValidTile(Tile tile)
Checks if a tile is valid.
Definition tile_map.h:161
StrongType::Typedef< uint32_t, struct TileIndexTag, StrongType::Compare, StrongType::Integer, StrongType::Compatible< int32_t >, StrongType::Compatible< int64_t > > TileIndex
The index/ID of a Tile.
Definition tile_type.h:92
Type for iterating a sprial tile area.
@ Invalid
Flag for an invalid trackdir.
Definition track_type.h:82
Functions related to water management.
void MakeRiverAndModifyDesertZoneAround(TileIndex tile)
Make a river tile and remove desert directly around it.
bool IsWaterTile(Tile t)
Is it a water tile with plain water?
Definition water_map.h:194
Base includes/functions for YAPF.
void YapfBuildRiver(TileIndex start_tile, TileIndex end_tile, TileIndex spring_tile, bool main_river)
Builds a river from the start tile to the end tile.
NodeList< YapfRiverBuilderNode, 8, 10 > RiverBuilderNodeList
River builder pathfinder node list.