src/linkgraph/linkgraph.cpp

   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
   8 /** @file linkgraph.cpp Definition of link graph classes used for cargo distribution. */
   9
  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");
  18 INSTANTIATE_POOL_METHODS(LinkGraph)
  19
  20 /**
  21  * Create a node or clear it.
  22  * @param xy Location of the associated station.
  23  * @param st ID of the associated station.
  24  * @param demand Demand for cargo at the station.
  25  */
  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
  35 /**
  36  * Create an edge.
  37  */
  38 LinkGraph::BaseEdge::BaseEdge(NodeID dest_node)
  39 {
  40         this->capacity = 0;
  41         this->usage = 0;
  42         this->travel_time_sum = 0;
  43         this->last_unrestricted_update = EconomyTime::INVALID_DATE;
  44         this->last_restricted_update = EconomyTime::INVALID_DATE;
  45         this->dest_node = dest_node;
  46 }
  47
  48 /**
  49  * Shift all dates by given interval.
  50  * This is useful if the date has been modified with the cheat menu.
  51  * @param interval Number of days to be added or subtracted.
  52  */
  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
  86 /**
  87  * Merge a link graph with another one.
  88  * @param other LinkGraph to be merged into this one.
  89  */
  90 void LinkGraph::Merge(LinkGraph *other)
  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
 112 /**
 113  * Remove a node from the link graph by overwriting it with the last node.
 114  * @param id ID of the node to be removed.
 115  */
 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
 141 /**
 142  * Add a node to the component and create empty edges associated with it. Set
 143  * the station's last_component to this component. Calculate the distances to all
 144  * other nodes. The distances to _all_ nodes are important as the demand
 145  * calculator relies on their availability.
 146  * @param st New node's station.
 147  * @return New node's ID.
 148  */
 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
 159 /**
 160  * Fill an edge with values from a link. Set the restricted or unrestricted
 161  * update timestamp according to the given update mode.
 162  * @param to Destination node of the link.
 163  * @param capacity Capacity of the link.
 164  * @param usage Usage to be added.
 165  * @param mode Update mode to be used.
 166  */
 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;
 175         if (mode & EUM_UNRESTRICTED)  edge.last_unrestricted_update = TimerGameEconomy::date;
 176         if (mode & EUM_RESTRICTED) edge.last_restricted_update = TimerGameEconomy::date;
 177 }
 178
 179 /**
 180  * Creates an edge if none exists yet or updates an existing edge.
 181  * @param to Target node.
 182  * @param capacity Capacity of the link.
 183  * @param usage Usage to be added.
 184  * @param mode Update mode to be used.
 185  */
 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
 197 /**
 198  * Remove an outgoing edge from this node.
 199  * @param to ID of destination node.
 200  */
 201 void LinkGraph::BaseNode::RemoveEdge(NodeID to)
 202 {
 203         auto [first, last] = std::equal_range(this->edges.begin(), this->edges.end(), to);
 204         this->edges.erase(first, last);
 205 }
 206
 207 /**
 208  * Update an edge. If mode contains UM_REFRESH refresh the edge to have at
 209  * least the given capacity and usage, otherwise add the capacity, usage and travel time.
 210  * In any case set the respective update timestamp(s), according to the given
 211  * mode.
 212  * @param capacity Capacity to be added/updated.
 213  * @param usage Usage to be added.
 214  * @param travel_time Travel time to be added, in ticks.
 215  * @param mode Update mode to be applied.
 216  */
 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
 246 /**
 247  * Resize the component and fill it with empty nodes and edges. Used when
 248  * loading from save games. The component is expected to be empty before.
 249  * @param size New size of the component.
 250  */
 251 void LinkGraph::Init(uint size)
 252 {
 253         assert(this->Size() == 0);
 254         this->nodes.resize(size);
 255 }