OpenTTD Source  20241121-master-g67a0fccfad
demands.cpp
Go to the documentation of this file.
1 
3 #include "../stdafx.h"
4 #include "demands.h"
5 #include "../core/math_func.hpp"
6 #include <queue>
7 
8 #include "../safeguards.h"
9 
10 typedef std::queue<NodeID> NodeList;
11 
15 class Scaler {
16 public:
17  void SetDemands(LinkGraphJob &job, NodeID from, NodeID to, uint demand_forw);
18 };
19 
23 class SymmetricScaler : public Scaler {
24 public:
32  {}
33 
38  inline void AddNode(const Node &node)
39  {
40  this->supply_sum += node.base.supply;
41  }
42 
47  inline void SetDemandPerNode(uint num_demands)
48  {
49  this->demand_per_node = std::max(this->supply_sum / num_demands, 1U);
50  }
51 
59  inline uint EffectiveSupply(const Node &from, const Node &to)
60  {
61  return std::max(from.base.supply * std::max(1U, to.base.supply) * this->mod_size / 100 / this->demand_per_node, 1U);
62  }
63 
71  inline bool HasDemandLeft(const Node &to)
72  {
73  return (to.base.supply == 0 || to.undelivered_supply > 0) && to.base.demand > 0;
74  }
75 
76  void SetDemands(LinkGraphJob &job, NodeID from, NodeID to, uint demand_forw);
77 
78 private:
79  uint mod_size;
80  uint supply_sum;
82 };
83 
87 class AsymmetricScaler : public Scaler {
88 public:
93  inline void AddNode(const Node &)
94  {
95  }
96 
101  inline void SetDemandPerNode(uint)
102  {
103  }
104 
110  inline uint EffectiveSupply(const Node &from, const Node &)
111  {
112  return from.base.supply;
113  }
114 
120  inline bool HasDemandLeft(const Node &to) { return to.base.demand > 0; }
121 };
122 
131 void SymmetricScaler::SetDemands(LinkGraphJob &job, NodeID from_id, NodeID to_id, uint demand_forw)
132 {
133  if (job[from_id].base.demand > 0) {
134  uint demand_back = demand_forw * this->mod_size / 100;
135  uint undelivered = job[to_id].undelivered_supply;
136  if (demand_back > undelivered) {
137  demand_back = undelivered;
138  demand_forw = std::max(1U, demand_back * 100 / this->mod_size);
139  }
140  this->Scaler::SetDemands(job, to_id, from_id, demand_back);
141  }
142 
143  this->Scaler::SetDemands(job, from_id, to_id, demand_forw);
144 }
145 
154 inline void Scaler::SetDemands(LinkGraphJob &job, NodeID from_id, NodeID to_id, uint demand_forw)
155 {
156  job[from_id].DeliverSupply(to_id, demand_forw);
157 }
158 
164 template<class Tscaler>
165 void DemandCalculator::CalcDemand(LinkGraphJob &job, Tscaler scaler)
166 {
167  NodeList supplies;
168  NodeList demands;
169  uint num_supplies = 0;
170  uint num_demands = 0;
171 
172  for (NodeID node = 0; node < job.Size(); node++) {
173  scaler.AddNode(job[node]);
174  if (job[node].base.supply > 0) {
175  supplies.push(node);
176  num_supplies++;
177  }
178  if (job[node].base.demand > 0) {
179  demands.push(node);
180  num_demands++;
181  }
182  }
183 
184  if (num_supplies == 0 || num_demands == 0) return;
185 
186  /* Mean acceptance attributed to each node. If the distribution is
187  * symmetric this is relative to remote supply, otherwise it is
188  * relative to remote demand. */
189  scaler.SetDemandPerNode(num_demands);
190  uint chance = 0;
191 
192  while (!supplies.empty() && !demands.empty()) {
193  NodeID from_id = supplies.front();
194  supplies.pop();
195 
196  for (uint i = 0; i < num_demands; ++i) {
197  assert(!demands.empty());
198  NodeID to_id = demands.front();
199  demands.pop();
200  if (from_id == to_id) {
201  /* Only one node with supply and demand left */
202  if (demands.empty() && supplies.empty()) return;
203 
204  demands.push(to_id);
205  continue;
206  }
207 
208  int32_t supply = scaler.EffectiveSupply(job[from_id], job[to_id]);
209  assert(supply > 0);
210 
211  constexpr int32_t divisor_scale = 16;
212 
213  int32_t scaled_distance = this->base_distance;
214  if (this->mod_dist > 0) {
215  const int32_t distance = DistanceMaxPlusManhattan(job[from_id].base.xy, job[to_id].base.xy);
216  /* Scale distance around base_distance by (mod_dist * (100 / 1024)).
217  * mod_dist may be > 1024, so clamp result to be non-negative */
218  scaled_distance = std::max(0, this->base_distance + (((distance - this->base_distance) * this->mod_dist) / 1024));
219  }
220 
221  /* Scale the accuracy by distance around accuracy / 2 */
222  const int32_t divisor = divisor_scale + ((this->accuracy * scaled_distance * divisor_scale) / (this->base_distance * 2));
223  assert(divisor >= divisor_scale);
224 
225  uint demand_forw = 0;
226  if (divisor <= (supply * divisor_scale)) {
227  /* At first only distribute demand if
228  * effective supply / accuracy divisor >= 1
229  * Others are too small or too far away to be considered. */
230  demand_forw = (supply * divisor_scale) / divisor;
231  } else if (++chance > this->accuracy * num_demands * num_supplies) {
232  /* After some trying, if there is still supply left, distribute
233  * demand also to other nodes. */
234  demand_forw = 1;
235  }
236 
237  demand_forw = std::min(demand_forw, job[from_id].undelivered_supply);
238 
239  scaler.SetDemands(job, from_id, to_id, demand_forw);
240 
241  if (scaler.HasDemandLeft(job[to_id])) {
242  demands.push(to_id);
243  } else {
244  num_demands--;
245  }
246 
247  if (job[from_id].undelivered_supply == 0) break;
248  }
249 
250  if (job[from_id].undelivered_supply != 0) {
251  supplies.push(from_id);
252  } else {
253  num_supplies--;
254  }
255  }
256 }
257 
263  base_distance(IntSqrt(DistanceMaxPlusManhattan(TileXY(0,0), TileXY(Map::MaxX(), Map::MaxY()))))
264 {
265  const LinkGraphSettings &settings = job.Settings();
266  CargoID cargo = job.Cargo();
267 
268  this->accuracy = settings.accuracy;
269  this->mod_dist = settings.demand_distance;
270  if (this->mod_dist > 100) {
271  /* Increase effect of mod_dist > 100.
272  * Quadratic:
273  * 100 --> 100
274  * 150 --> 308
275  * 200 --> 933
276  * 255 --> 2102
277  */
278  int over100 = this->mod_dist - 100;
279  this->mod_dist = 100 + ((over100 * over100) / 12);
280  }
281 
282  switch (settings.GetDistributionType(cargo)) {
283  case DT_SYMMETRIC:
284  this->CalcDemand<SymmetricScaler>(job, SymmetricScaler(settings.demand_size));
285  break;
286  case DT_ASYMMETRIC:
287  this->CalcDemand<AsymmetricScaler>(job, AsymmetricScaler());
288  break;
289  default:
290  /* Nothing to do. */
291  break;
292  }
293 }
uint8_t CargoID
Cargo slots to indicate a cargo type within a game.
Definition: cargo_type.h:22
A scaler for asymmetric distribution.
Definition: demands.cpp:87
void AddNode(const Node &)
Nothing to do here.
Definition: demands.cpp:93
uint EffectiveSupply(const Node &from, const Node &)
Get the effective supply of one node towards another one.
Definition: demands.cpp:110
void SetDemandPerNode(uint)
Nothing to do here.
Definition: demands.cpp:101
bool HasDemandLeft(const Node &to)
Check if there is any acceptance left for this node.
Definition: demands.cpp:120
void CalcDemand(LinkGraphJob &job, Tscaler scaler)
Do the actual demand calculation, called from constructor.
Definition: demands.cpp:165
DemandCalculator(LinkGraphJob &job)
Create the DemandCalculator and immediately do the calculation.
Definition: demands.cpp:262
int32_t base_distance
Base distance for scaling purposes.
Definition: demands.h:17
int32_t mod_dist
Distance modifier, determines how much demands decrease with distance.
Definition: demands.h:18
int32_t accuracy
Accuracy of the calculation.
Definition: demands.h:19
Class for calculation jobs to be run on link graphs.
Definition: linkgraphjob.h:29
const LinkGraphSettings & Settings() const
Get the link graph settings for this component.
Definition: linkgraphjob.h:232
NodeID Size() const
Get the size of the underlying link graph.
Definition: linkgraphjob.h:245
CargoID Cargo() const
Get the cargo of the underlying link graph.
Definition: linkgraphjob.h:251
Hash table based node list multi-container class.
Definition: nodelist.hpp:21
Scale various things according to symmetric/asymmetric distribution.
Definition: demands.cpp:15
void SetDemands(LinkGraphJob &job, NodeID from, NodeID to, uint demand_forw)
Set the demands between two nodes using the given base demand.
Definition: demands.cpp:154
Scaler for symmetric distribution.
Definition: demands.cpp:23
uint mod_size
Size modifier. Determines how much demands increase with the supply of the remote station.
Definition: demands.cpp:79
uint EffectiveSupply(const Node &from, const Node &to)
Get the effective supply of one node towards another one.
Definition: demands.cpp:59
uint demand_per_node
Mean demand associated with each node.
Definition: demands.cpp:81
void SetDemandPerNode(uint num_demands)
Calculate the mean demand per node using the sum of supplies.
Definition: demands.cpp:47
void AddNode(const Node &node)
Count a node's supply into the sum of supplies.
Definition: demands.cpp:38
bool HasDemandLeft(const Node &to)
Check if there is any acceptance left for this node.
Definition: demands.cpp:71
void SetDemands(LinkGraphJob &job, NodeID from, NodeID to, uint demand_forw)
Set the demands between two nodes using the given base demand.
Definition: demands.cpp:131
uint supply_sum
Sum of all supplies in the component.
Definition: demands.cpp:80
SymmetricScaler(uint mod_size)
Constructor.
Definition: demands.cpp:30
uint32_t IntSqrt(uint32_t num)
Compute the integer square root.
Definition: math_func.cpp:42
Declaration of demand calculating link graph handler.
fluid_settings_t * settings
FluidSynth settings handle.
Definition: fluidsynth.cpp:21
@ DT_ASYMMETRIC
Asymmetric distribution. Usually cargo will only travel in one direction.
@ DT_SYMMETRIC
Symmetric distribution. The same amount of cargo travels in each direction between each pair of nodes...
uint DistanceMaxPlusManhattan(TileIndex t0, TileIndex t1)
Gets the biggest distance component (x or y) between the two given tiles plus the Manhattan distance,...
Definition: map.cpp:194
static debug_inline TileIndex TileXY(uint x, uint y)
Returns the TileIndex of a coordinate.
Definition: map_func.h:373
uint8_t accuracy
accuracy when calculating things on the link graph. low accuracy => low running time
uint8_t demand_distance
influence of distance between stations on the demand function
Node of the link graph.
Definition: linkgraph.h:90
uint supply
Supply at the station.
Definition: linkgraph.h:91
uint demand
Acceptance at the station.
Definition: linkgraph.h:92
Size related data of the map.
Definition: map_func.h:206