OpenTTD Source  12.0-beta2
demands.cpp
Go to the documentation of this file.
1 
3 #include "../stdafx.h"
4 #include "demands.h"
5 #include <queue>
6 
7 #include "../safeguards.h"
8 
9 typedef std::queue<NodeID> NodeList;
10 
14 class Scaler {
15 public:
16  void SetDemands(LinkGraphJob &job, NodeID from, NodeID to, uint demand_forw);
17 };
18 
22 class SymmetricScaler : public Scaler {
23 public:
31  {}
32 
37  inline void AddNode(const Node &node)
38  {
39  this->supply_sum += node.Supply();
40  }
41 
46  inline void SetDemandPerNode(uint num_demands)
47  {
48  this->demand_per_node = std::max(this->supply_sum / num_demands, 1U);
49  }
50 
58  inline uint EffectiveSupply(const Node &from, const Node &to)
59  {
60  return std::max(from.Supply() * std::max(1U, to.Supply()) * this->mod_size / 100 / this->demand_per_node, 1U);
61  }
62 
70  inline bool HasDemandLeft(const Node &to)
71  {
72  return (to.Supply() == 0 || to.UndeliveredSupply() > 0) && to.Demand() > 0;
73  }
74 
75  void SetDemands(LinkGraphJob &job, NodeID from, NodeID to, uint demand_forw);
76 
77 private:
78  uint mod_size;
79  uint supply_sum;
81 };
82 
86 class AsymmetricScaler : public Scaler {
87 public:
92  inline void AddNode(const Node &)
93  {
94  }
95 
100  inline void SetDemandPerNode(uint)
101  {
102  }
103 
109  inline uint EffectiveSupply(const Node &from, const Node &)
110  {
111  return from.Supply();
112  }
113 
119  inline bool HasDemandLeft(const Node &to) { return to.Demand() > 0; }
120 };
121 
130 void SymmetricScaler::SetDemands(LinkGraphJob &job, NodeID from_id, NodeID to_id, uint demand_forw)
131 {
132  if (job[from_id].Demand() > 0) {
133  uint demand_back = demand_forw * this->mod_size / 100;
134  uint undelivered = job[to_id].UndeliveredSupply();
135  if (demand_back > undelivered) {
136  demand_back = undelivered;
137  demand_forw = std::max(1U, demand_back * 100 / this->mod_size);
138  }
139  this->Scaler::SetDemands(job, to_id, from_id, demand_back);
140  }
141 
142  this->Scaler::SetDemands(job, from_id, to_id, demand_forw);
143 }
144 
153 inline void Scaler::SetDemands(LinkGraphJob &job, NodeID from_id, NodeID to_id, uint demand_forw)
154 {
155  job[from_id].DeliverSupply(to_id, demand_forw);
156 }
157 
163 template<class Tscaler>
164 void DemandCalculator::CalcDemand(LinkGraphJob &job, Tscaler scaler)
165 {
166  NodeList supplies;
167  NodeList demands;
168  uint num_supplies = 0;
169  uint num_demands = 0;
170 
171  for (NodeID node = 0; node < job.Size(); node++) {
172  scaler.AddNode(job[node]);
173  if (job[node].Supply() > 0) {
174  supplies.push(node);
175  num_supplies++;
176  }
177  if (job[node].Demand() > 0) {
178  demands.push(node);
179  num_demands++;
180  }
181  }
182 
183  if (num_supplies == 0 || num_demands == 0) return;
184 
185  /* Mean acceptance attributed to each node. If the distribution is
186  * symmetric this is relative to remote supply, otherwise it is
187  * relative to remote demand. */
188  scaler.SetDemandPerNode(num_demands);
189  uint chance = 0;
190 
191  while (!supplies.empty() && !demands.empty()) {
192  NodeID from_id = supplies.front();
193  supplies.pop();
194 
195  for (uint i = 0; i < num_demands; ++i) {
196  assert(!demands.empty());
197  NodeID to_id = demands.front();
198  demands.pop();
199  if (from_id == to_id) {
200  /* Only one node with supply and demand left */
201  if (demands.empty() && supplies.empty()) return;
202 
203  demands.push(to_id);
204  continue;
205  }
206 
207  int32 supply = scaler.EffectiveSupply(job[from_id], job[to_id]);
208  assert(supply > 0);
209 
210  /* Scale the distance by mod_dist around max_distance */
211  int32 distance = this->max_distance - (this->max_distance -
212  (int32)DistanceMaxPlusManhattan(job[from_id].XY(), job[to_id].XY())) *
213  this->mod_dist / 100;
214 
215  /* Scale the accuracy by distance around accuracy / 2 */
216  int32 divisor = this->accuracy * (this->mod_dist - 50) / 100 +
217  this->accuracy * distance / this->max_distance + 1;
218 
219  assert(divisor > 0);
220 
221  uint demand_forw = 0;
222  if (divisor <= supply) {
223  /* At first only distribute demand if
224  * effective supply / accuracy divisor >= 1
225  * Others are too small or too far away to be considered. */
226  demand_forw = supply / divisor;
227  } else if (++chance > this->accuracy * num_demands * num_supplies) {
228  /* After some trying, if there is still supply left, distribute
229  * demand also to other nodes. */
230  demand_forw = 1;
231  }
232 
233  demand_forw = std::min(demand_forw, job[from_id].UndeliveredSupply());
234 
235  scaler.SetDemands(job, from_id, to_id, demand_forw);
236 
237  if (scaler.HasDemandLeft(job[to_id])) {
238  demands.push(to_id);
239  } else {
240  num_demands--;
241  }
242 
243  if (job[from_id].UndeliveredSupply() == 0) break;
244  }
245 
246  if (job[from_id].UndeliveredSupply() != 0) {
247  supplies.push(from_id);
248  } else {
249  num_supplies--;
250  }
251  }
252 }
253 
259  max_distance(DistanceMaxPlusManhattan(TileXY(0,0), TileXY(MapMaxX(), MapMaxY())))
260 {
261  const LinkGraphSettings &settings = job.Settings();
262  CargoID cargo = job.Cargo();
263 
264  this->accuracy = settings.accuracy;
265  this->mod_dist = settings.demand_distance;
266  if (this->mod_dist > 100) {
267  /* Increase effect of mod_dist > 100 */
268  int over100 = this->mod_dist - 100;
269  this->mod_dist = 100 + over100 * over100;
270  }
271 
272  switch (settings.GetDistributionType(cargo)) {
273  case DT_SYMMETRIC:
274  this->CalcDemand<SymmetricScaler>(job, SymmetricScaler(settings.demand_size));
275  break;
276  case DT_ASYMMETRIC:
277  this->CalcDemand<AsymmetricScaler>(job, AsymmetricScaler());
278  break;
279  default:
280  /* Nothing to do. */
281  break;
282  }
283 }
SymmetricScaler::demand_per_node
uint demand_per_node
Mean demand associated with each node.
Definition: demands.cpp:80
AsymmetricScaler::SetDemandPerNode
void SetDemandPerNode(uint)
Nothing to do here.
Definition: demands.cpp:100
DemandCalculator::DemandCalculator
DemandCalculator(LinkGraphJob &job)
Create the DemandCalculator and immediately do the calculation.
Definition: demands.cpp:258
DemandCalculator::accuracy
int32 accuracy
Accuracy of the calculation.
Definition: demands.h:19
LinkGraph::Node
Updatable node class.
Definition: linkgraph.h:380
DT_SYMMETRIC
@ DT_SYMMETRIC
Symmetric distribution. The same amount of cargo travels in each direction between each pair of nodes...
Definition: linkgraph_type.h:28
LinkGraphJob::Settings
const LinkGraphSettings & Settings() const
Get the link graph settings for this component.
Definition: linkgraphjob.h:322
LinkGraphJob
Class for calculation jobs to be run on link graphs.
Definition: linkgraphjob.h:30
demands.h
DemandCalculator::mod_dist
int32 mod_dist
Distance modifier, determines how much demands decrease with distance.
Definition: demands.h:18
DT_ASYMMETRIC
@ DT_ASYMMETRIC
Asymmetric distribution. Usually cargo will only travel in one direction.
Definition: linkgraph_type.h:26
LinkGraphSettings
Definition: settings_type.h:525
LinkGraphJob::Size
NodeID Size() const
Get the size of the underlying link graph.
Definition: linkgraphjob.h:335
AsymmetricScaler::HasDemandLeft
bool HasDemandLeft(const Node &to)
Check if there is any acceptance left for this node.
Definition: demands.cpp:119
DemandCalculator::max_distance
int32 max_distance
Maximum distance possible on the map.
Definition: demands.h:17
SymmetricScaler::AddNode
void AddNode(const Node &node)
Count a node's supply into the sum of supplies.
Definition: demands.cpp:37
SymmetricScaler::SetDemandPerNode
void SetDemandPerNode(uint num_demands)
Calculate the mean demand per node using the sum of supplies.
Definition: demands.cpp:46
DemandCalculator::CalcDemand
void CalcDemand(LinkGraphJob &job, Tscaler scaler)
Do the actual demand calculation, called from constructor.
Definition: demands.cpp:164
Scaler
Scale various things according to symmetric/asymmetric distribution.
Definition: demands.cpp:14
LinkGraph::NodeWrapper::Demand
uint Demand() const
Get demand of wrapped node.
Definition: linkgraph.h:159
AsymmetricScaler::EffectiveSupply
uint EffectiveSupply(const Node &from, const Node &)
Get the effective supply of one node towards another one.
Definition: demands.cpp:109
settings
fluid_settings_t * settings
FluidSynth settings handle.
Definition: fluidsynth.cpp:21
AsymmetricScaler::AddNode
void AddNode(const Node &)
Nothing to do here.
Definition: demands.cpp:92
SymmetricScaler::EffectiveSupply
uint EffectiveSupply(const Node &from, const Node &to)
Get the effective supply of one node towards another one.
Definition: demands.cpp:58
LinkGraphSettings::accuracy
uint8 accuracy
accuracy when calculating things on the link graph. low accuracy => low running time
Definition: settings_type.h:532
MapMaxY
static uint MapMaxY()
Gets the maximum Y coordinate within the map, including MP_VOID.
Definition: map_func.h:111
TileXY
static TileIndex TileXY(uint x, uint y)
Returns the TileIndex of a coordinate.
Definition: map_func.h:163
SymmetricScaler::SymmetricScaler
SymmetricScaler(uint mod_size)
Constructor.
Definition: demands.cpp:29
MapMaxX
static uint MapMaxX()
Gets the maximum X coordinate within the map, including MP_VOID.
Definition: map_func.h:102
Scaler::SetDemands
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:153
CargoID
byte CargoID
Cargo slots to indicate a cargo type within a game.
Definition: cargo_type.h:20
SymmetricScaler
Scaler for symmetric distribution.
Definition: demands.cpp:22
LinkGraphJob::Cargo
CargoID Cargo() const
Get the cargo of the underlying link graph.
Definition: linkgraphjob.h:341
SymmetricScaler::HasDemandLeft
bool HasDemandLeft(const Node &to)
Check if there is any acceptance left for this node.
Definition: demands.cpp:70
DistanceMaxPlusManhattan
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:205
AsymmetricScaler
A scaler for asymmetric distribution.
Definition: demands.cpp:86
SymmetricScaler::mod_size
uint mod_size
Size modifier. Determines how much demands increase with the supply of the remote station.
Definition: demands.cpp:78
SymmetricScaler::SetDemands
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:130
SymmetricScaler::supply_sum
uint supply_sum
Sum of all supplies in the component.
Definition: demands.cpp:79
LinkGraph::NodeWrapper::Supply
uint Supply() const
Get supply of wrapped node.
Definition: linkgraph.h:153
LinkGraphSettings::demand_distance
uint8 demand_distance
influence of distance between stations on the demand function
Definition: settings_type.h:534