OpenTTD Source  20241120-master-g6d3adc6169
linkgraph.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 <http://www.gnu.org/licenses/>.
6  */
7 
10 #include "../stdafx.h"
11 #include "../core/pool_func.hpp"
12 #include "linkgraph.h"
13 
14 #include "../safeguards.h"
15 
16 /* Initialize the link-graph-pool */
17 LinkGraphPool _link_graph_pool("LinkGraph");
19 
20 
26 LinkGraph::BaseNode::BaseNode(TileIndex xy, StationID st, uint demand)
27 {
28  this->xy = xy;
29  this->supply = 0;
30  this->demand = demand;
31  this->station = st;
32  this->last_update = EconomyTime::INVALID_DATE;
33 }
34 
39 {
40  this->capacity = 0;
41  this->usage = 0;
42  this->travel_time_sum = 0;
45  this->dest_node = dest_node;
46 }
47 
53 void LinkGraph::ShiftDates(TimerGameEconomy::Date interval)
54 {
55  this->last_compression += interval;
56  for (NodeID node1 = 0; node1 < this->Size(); ++node1) {
57  BaseNode &source = this->nodes[node1];
58  if (source.last_update != EconomyTime::INVALID_DATE) source.last_update += interval;
59  for (BaseEdge &edge : this->nodes[node1].edges) {
60  if (edge.last_unrestricted_update != EconomyTime::INVALID_DATE) edge.last_unrestricted_update += interval;
61  if (edge.last_restricted_update != EconomyTime::INVALID_DATE) edge.last_restricted_update += interval;
62  }
63  }
64 }
65 
66 void LinkGraph::Compress()
67 {
68  this->last_compression = (TimerGameEconomy::date + this->last_compression).base() / 2;
69  for (NodeID node1 = 0; node1 < this->Size(); ++node1) {
70  this->nodes[node1].supply /= 2;
71  for (BaseEdge &edge : this->nodes[node1].edges) {
72  if (edge.capacity > 0) {
73  uint new_capacity = std::max(1U, edge.capacity / 2);
74  if (edge.capacity < (1 << 16)) {
75  edge.travel_time_sum = edge.travel_time_sum * new_capacity / edge.capacity;
76  } else if (edge.travel_time_sum != 0) {
77  edge.travel_time_sum = std::max<uint64_t>(1, edge.travel_time_sum / 2);
78  }
79  edge.capacity = new_capacity;
80  edge.usage /= 2;
81  }
82  }
83  }
84 }
85 
91 {
92  TimerGameEconomy::Date age = TimerGameEconomy::date - this->last_compression + 1;
93  TimerGameEconomy::Date other_age = TimerGameEconomy::date - other->last_compression + 1;
94  NodeID first = this->Size();
95  for (NodeID node1 = 0; node1 < other->Size(); ++node1) {
96  Station *st = Station::Get(other->nodes[node1].station);
97  NodeID new_node = this->AddNode(st);
98  this->nodes[new_node].supply = LinkGraph::Scale(other->nodes[node1].supply, age, other_age);
99  st->goods[this->cargo].link_graph = this->index;
100  st->goods[this->cargo].node = new_node;
101 
102  for (BaseEdge &e : other->nodes[node1].edges) {
103  BaseEdge &new_edge = this->nodes[new_node].edges.emplace_back(first + e.dest_node);
104  new_edge.capacity = LinkGraph::Scale(e.capacity, age, other_age);
105  new_edge.usage = LinkGraph::Scale(e.usage, age, other_age);
106  new_edge.travel_time_sum = LinkGraph::Scale(e.travel_time_sum, age, other_age);
107  }
108  }
109  delete other;
110 }
111 
116 void LinkGraph::RemoveNode(NodeID id)
117 {
118  assert(id < this->Size());
119 
120  NodeID last_node = this->Size() - 1;
121  Station::Get(this->nodes[last_node].station)->goods[this->cargo].node = id;
122  /* Erase node by swapping with the last element. Node index is referenced
123  * directly from station goods entries so the order and position must remain. */
124  this->nodes[id] = this->nodes.back();
125  this->nodes.pop_back();
126  for (auto &n : this->nodes) {
127  /* Find iterator position where an edge to id would be. */
128  auto [first, last] = std::equal_range(n.edges.begin(), n.edges.end(), id);
129  /* Remove potential node (erasing an empty range is safe). */
130  auto insert = n.edges.erase(first, last);
131  /* As the edge list is sorted, a potential edge to last_node will always be the last edge. */
132  if (!n.edges.empty() && n.edges.back().dest_node == last_node) {
133  /* Change dest ID and move into the spot of the deleted edge. */
134  n.edges.back().dest_node = id;
135  n.edges.insert(insert, n.edges.back());
136  n.edges.pop_back();
137  }
138  }
139 }
140 
149 NodeID LinkGraph::AddNode(const Station *st)
150 {
151  const GoodsEntry &good = st->goods[this->cargo];
152 
153  NodeID new_node = this->Size();
154  this->nodes.emplace_back(st->xy, st->index, HasBit(good.status, GoodsEntry::GES_ACCEPTANCE));
155 
156  return new_node;
157 }
158 
167 void LinkGraph::BaseNode::AddEdge(NodeID to, uint capacity, uint usage, uint32_t travel_time, EdgeUpdateMode mode)
168 {
169  assert(!this->HasEdgeTo(to));
170 
171  BaseEdge &edge = *this->edges.emplace(std::upper_bound(this->edges.begin(), this->edges.end(), to), to);
172  edge.capacity = capacity;
173  edge.usage = usage;
174  edge.travel_time_sum = static_cast<uint64_t>(travel_time) * capacity;
177 }
178 
186 void LinkGraph::BaseNode::UpdateEdge(NodeID to, uint capacity, uint usage, uint32_t travel_time, EdgeUpdateMode mode)
187 {
188  assert(capacity > 0);
189  assert(usage <= capacity);
190  if (!this->HasEdgeTo(to)) {
191  this->AddEdge(to, capacity, usage, travel_time, mode);
192  } else {
193  this->GetEdge(to)->Update(capacity, usage, travel_time, mode);
194  }
195 }
196 
202 {
203  auto [first, last] = std::equal_range(this->edges.begin(), this->edges.end(), to);
204  this->edges.erase(first, last);
205 }
206 
217 void LinkGraph::BaseEdge::Update(uint capacity, uint usage, uint32_t travel_time, EdgeUpdateMode mode)
218 {
219  assert(this->capacity > 0);
220  assert(capacity >= usage);
221 
222  if (mode & EUM_INCREASE) {
223  if (this->travel_time_sum == 0) {
224  this->travel_time_sum = static_cast<uint64_t>(this->capacity + capacity) * travel_time;
225  } else if (travel_time == 0) {
226  this->travel_time_sum += this->travel_time_sum / this->capacity * capacity;
227  } else {
228  this->travel_time_sum += static_cast<uint64_t>(travel_time) * capacity;
229  }
230  this->capacity += capacity;
231  this->usage += usage;
232  } else if (mode & EUM_REFRESH) {
233  if (this->travel_time_sum == 0) {
234  this->capacity = std::max(this->capacity, capacity);
235  this->travel_time_sum = static_cast<uint64_t>(travel_time) * this->capacity;
236  } else if (capacity > this->capacity) {
237  this->travel_time_sum = this->travel_time_sum / this->capacity * capacity;
238  this->capacity = capacity;
239  }
240  this->usage = std::max(this->usage, usage);
241  }
242  if (mode & EUM_UNRESTRICTED) this->last_unrestricted_update = TimerGameEconomy::date;
243  if (mode & EUM_RESTRICTED) this->last_restricted_update = TimerGameEconomy::date;
244 }
245 
251 void LinkGraph::Init(uint size)
252 {
253  assert(this->Size() == 0);
254  this->nodes.resize(size);
255 }
constexpr debug_inline bool HasBit(const T x, const uint8_t y)
Checks if a bit in a value is set.
A connected component of a link graph.
Definition: linkgraph.h:37
void Merge(LinkGraph *other)
Merge a link graph with another one.
Definition: linkgraph.cpp:90
void Init(uint size)
Resize the component and fill it with empty nodes and edges.
Definition: linkgraph.cpp:251
CargoID cargo
Cargo of this component's link graph.
Definition: linkgraph.h:264
NodeVector nodes
Nodes in the component.
Definition: linkgraph.h:266
void ShiftDates(TimerGameEconomy::Date interval)
Shift all dates by given interval.
Definition: linkgraph.cpp:53
NodeID AddNode(const Station *st)
Add a node to the component and create empty edges associated with it.
Definition: linkgraph.cpp:149
NodeID Size() const
Get the current size of the component.
Definition: linkgraph.h:230
void RemoveNode(NodeID id)
Remove a node from the link graph by overwriting it with the last node.
Definition: linkgraph.cpp:116
static uint Scale(uint val, TimerGameEconomy::Date target_age, TimerGameEconomy::Date orig_age)
Scale a value from a link graph of age orig_age for usage in one of age target_age.
Definition: linkgraph.h:186
TimerGameEconomy::Date last_compression
Last time the capacities and supplies were compressed.
Definition: linkgraph.h:265
static constexpr TimerGame< struct Economy >::Date INVALID_DATE
Representation of an invalid date.
static Date date
Current date in days (day counter).
Declaration of link graph classes used for cargo distribution.
LinkGraphPool _link_graph_pool
The actual pool with link graphs.
EdgeUpdateMode
Special modes for updating links.
@ EUM_REFRESH
Refresh capacity.
@ EUM_INCREASE
Increase capacity.
@ EUM_RESTRICTED
Use restricted link.
@ EUM_UNRESTRICTED
Use unrestricted link.
#define INSTANTIATE_POOL_METHODS(name)
Force instantiation of pool methods so we don't get linker errors.
Definition: pool_func.hpp:237
TileIndex xy
Base tile of the station.
Stores station stats for a single cargo.
Definition: station_base.h:166
@ GES_ACCEPTANCE
Set when the station accepts the cargo currently for final deliveries.
Definition: station_base.h:173
NodeID node
ID of node in link graph referring to this goods entry.
Definition: station_base.h:214
LinkGraphID link_graph
Link graph this station belongs to.
Definition: station_base.h:215
uint8_t status
Status of this cargo, see GoodsEntryStatus.
Definition: station_base.h:217
An edge in the link graph.
Definition: linkgraph.h:42
TimerGameEconomy::Date last_restricted_update
When the restricted part of the link was last updated.
Definition: linkgraph.h:47
uint64_t travel_time_sum
Sum of the travel times of the link, in ticks.
Definition: linkgraph.h:45
NodeID dest_node
Destination of the edge.
Definition: linkgraph.h:48
uint usage
Usage of the link.
Definition: linkgraph.h:44
BaseEdge(NodeID dest_node=INVALID_NODE)
Create an edge.
Definition: linkgraph.cpp:38
TimerGameEconomy::Date last_unrestricted_update
When the unrestricted part of the link was last updated.
Definition: linkgraph.h:46
void Update(uint capacity, uint usage, uint32_t time, EdgeUpdateMode mode)
Update an edge.
Definition: linkgraph.cpp:217
uint capacity
Capacity of the link.
Definition: linkgraph.h:43
Node of the link graph.
Definition: linkgraph.h:90
TimerGameEconomy::Date last_update
When the supply was last updated.
Definition: linkgraph.h:95
void AddEdge(NodeID to, uint capacity, uint usage, uint32_t time, EdgeUpdateMode mode)
Fill an edge with values from a link.
Definition: linkgraph.cpp:167
void UpdateEdge(NodeID to, uint capacity, uint usage, uint32_t time, EdgeUpdateMode mode)
Creates an edge if none exists yet or updates an existing edge.
Definition: linkgraph.cpp:186
void RemoveEdge(NodeID to)
Remove an outgoing edge from this node.
Definition: linkgraph.cpp:201
Tindex index
Index of this pool item.
Definition: pool_type.hpp:238
Base class for all pools.
Definition: pool_type.hpp:80
static Station * Get(size_t index)
Gets station with given index.
Station data structure.
Definition: station_base.h:439
GoodsEntry goods[NUM_CARGO]
Goods at this station.
Definition: station_base.h:468