Files
@ r22286:86829dfc6695
Branch filter:
Location: cpp/openttd-patchpack/source/src/linkgraph/demands.cpp
r22286:86829dfc6695
7.9 KiB
text/x-c
(svn r27476) -Update from WebTranslator v3.0:
german - 2 changes by mini1025
german - 2 changes by mini1025
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 | /** @file demands.cpp Definition of demand calculating link graph handler. */
#include "../stdafx.h"
#include "demands.h"
#include <list>
#include "../safeguards.h"
typedef std::list<NodeID> NodeList;
/**
* Scale various things according to symmetric/asymmetric distribution.
*/
class Scaler {
public:
void SetDemands(LinkGraphJob &job, NodeID from, NodeID to, uint demand_forw);
};
/**
* Scaler for symmetric distribution.
*/
class SymmetricScaler : public Scaler {
public:
/**
* Constructor.
* @param mod_size Size modifier to be used. Determines how much demands
* increase with the supply of the remote station.
*/
inline SymmetricScaler(uint mod_size) : mod_size(mod_size), supply_sum(0),
demand_per_node(0)
{}
/**
* Count a node's supply into the sum of supplies.
* @param node Node.
*/
inline void AddNode(const Node &node)
{
this->supply_sum += node.Supply();
}
/**
* Calculate the mean demand per node using the sum of supplies.
* @param num_demands Number of accepting nodes.
*/
inline void SetDemandPerNode(uint num_demands)
{
this->demand_per_node = max(this->supply_sum / num_demands, 1U);
}
/**
* Get the effective supply of one node towards another one. In symmetric
* distribution the supply of the other node is weighed in.
* @param from The supplying node.
* @param to The receiving node.
* @return Effective supply.
*/
inline uint EffectiveSupply(const Node &from, const Node &to)
{
return max(from.Supply() * max(1U, to.Supply()) * this->mod_size / 100 / this->demand_per_node, 1U);
}
/**
* Check if there is any acceptance left for this node. In symmetric distribution
* nodes only accept anything if they also supply something. So if
* undelivered_supply == 0 at the node there isn't any demand left either.
* @param to Node to be checked.
* @return If demand is left.
*/
inline bool HasDemandLeft(const Node &to)
{
return (to.Supply() == 0 || to.UndeliveredSupply() > 0) && to.Demand() > 0;
}
void SetDemands(LinkGraphJob &job, NodeID from, NodeID to, uint demand_forw);
private:
uint mod_size; ///< Size modifier. Determines how much demands increase with the supply of the remote station.
uint supply_sum; ///< Sum of all supplies in the component.
uint demand_per_node; ///< Mean demand associated with each node.
};
/**
* A scaler for asymmetric distribution.
*/
class AsymmetricScaler : public Scaler {
public:
/**
* Nothing to do here.
* @param unused.
*/
inline void AddNode(const Node &)
{
}
/**
* Nothing to do here.
* @param unused.
*/
inline void SetDemandPerNode(uint)
{
}
/**
* Get the effective supply of one node towards another one.
* @param from The supplying node.
* @param unused.
*/
inline uint EffectiveSupply(const Node &from, const Node &)
{
return from.Supply();
}
/**
* Check if there is any acceptance left for this node. In asymmetric distribution
* nodes always accept as long as their demand > 0.
* @param to The node to be checked.
* @param to_anno Unused.
*/
inline bool HasDemandLeft(const Node &to) { return to.Demand() > 0; }
};
/**
* Set the demands between two nodes using the given base demand. In symmetric mode
* this sets demands in both directions.
* @param job The link graph job.
* @param from_id The supplying node.
* @param to_id The receiving node.
* @param demand_forw Demand calculated for the "forward" direction.
*/
void SymmetricScaler::SetDemands(LinkGraphJob &job, NodeID from_id, NodeID to_id, uint demand_forw)
{
if (job[from_id].Demand() > 0) {
uint demand_back = demand_forw * this->mod_size / 100;
uint undelivered = job[to_id].UndeliveredSupply();
if (demand_back > undelivered) {
demand_back = undelivered;
demand_forw = max(1U, demand_back * 100 / this->mod_size);
}
this->Scaler::SetDemands(job, to_id, from_id, demand_back);
}
this->Scaler::SetDemands(job, from_id, to_id, demand_forw);
}
/**
* Set the demands between two nodes using the given base demand. In asymmetric mode
* this only sets demand in the "forward" direction.
* @param job The link graph job.
* @param from_id The supplying node.
* @param to_id The receiving node.
* @param demand_forw Demand calculated for the "forward" direction.
*/
inline void Scaler::SetDemands(LinkGraphJob &job, NodeID from_id, NodeID to_id, uint demand_forw)
{
job[from_id].DeliverSupply(to_id, demand_forw);
}
/**
* Do the actual demand calculation, called from constructor.
* @param job Job to calculate the demands for.
* @tparam Tscaler Scaler to be used for scaling demands.
*/
template<class Tscaler>
void DemandCalculator::CalcDemand(LinkGraphJob &job, Tscaler scaler)
{
NodeList supplies;
NodeList demands;
uint num_supplies = 0;
uint num_demands = 0;
for (NodeID node = 0; node < job.Size(); node++) {
scaler.AddNode(job[node]);
if (job[node].Supply() > 0) {
supplies.push_back(node);
num_supplies++;
}
if (job[node].Demand() > 0) {
demands.push_back(node);
num_demands++;
}
}
if (num_supplies == 0 || num_demands == 0) return;
/* Mean acceptance attributed to each node. If the distribution is
* symmetric this is relative to remote supply, otherwise it is
* relative to remote demand. */
scaler.SetDemandPerNode(num_demands);
uint chance = 0;
while (!supplies.empty() && !demands.empty()) {
NodeID from_id = supplies.front();
supplies.pop_front();
for (uint i = 0; i < num_demands; ++i) {
assert(!demands.empty());
NodeID to_id = demands.front();
demands.pop_front();
if (from_id == to_id) {
/* Only one node with supply and demand left */
if (demands.empty() && supplies.empty()) return;
demands.push_back(to_id);
continue;
}
int32 supply = scaler.EffectiveSupply(job[from_id], job[to_id]);
assert(supply > 0);
/* Scale the distance by mod_dist around max_distance */
int32 distance = this->max_distance - (this->max_distance -
(int32)DistanceMaxPlusManhattan(job[from_id].XY(), job[to_id].XY())) *
this->mod_dist / 100;
/* Scale the accuracy by distance around accuracy / 2 */
int32 divisor = this->accuracy * (this->mod_dist - 50) / 100 +
this->accuracy * distance / this->max_distance + 1;
assert(divisor > 0);
uint demand_forw = 0;
if (divisor <= supply) {
/* At first only distribute demand if
* effective supply / accuracy divisor >= 1
* Others are too small or too far away to be considered. */
demand_forw = supply / divisor;
} else if (++chance > this->accuracy * num_demands * num_supplies) {
/* After some trying, if there is still supply left, distribute
* demand also to other nodes. */
demand_forw = 1;
}
demand_forw = min(demand_forw, job[from_id].UndeliveredSupply());
scaler.SetDemands(job, from_id, to_id, demand_forw);
if (scaler.HasDemandLeft(job[to_id])) {
demands.push_back(to_id);
} else {
num_demands--;
}
if (job[from_id].UndeliveredSupply() == 0) break;
}
if (job[from_id].UndeliveredSupply() != 0) {
supplies.push_back(from_id);
} else {
num_supplies--;
}
}
}
/**
* Create the DemandCalculator and immediately do the calculation.
* @param job Job to calculate the demands for.
*/
DemandCalculator::DemandCalculator(LinkGraphJob &job) :
max_distance(DistanceMaxPlusManhattan(TileXY(0,0), TileXY(MapMaxX(), MapMaxY())))
{
const LinkGraphSettings &settings = job.Settings();
CargoID cargo = job.Cargo();
this->accuracy = settings.accuracy;
this->mod_dist = settings.demand_distance;
if (this->mod_dist > 100) {
/* Increase effect of mod_dist > 100 */
int over100 = this->mod_dist - 100;
this->mod_dist = 100 + over100 * over100;
}
switch (settings.GetDistributionType(cargo)) {
case DT_SYMMETRIC:
this->CalcDemand<SymmetricScaler>(job, SymmetricScaler(settings.demand_size));
break;
case DT_ASYMMETRIC:
this->CalcDemand<AsymmetricScaler>(job, AsymmetricScaler());
break;
default:
/* Nothing to do. */
break;
}
}
|