demands.cpp

Go to the documentation of this file.

/*
 * This file is part of OpenTTD.
 * 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.
 * 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.
 * 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 <https://www.gnu.org/licenses/old-licenses/gpl-2.0>.
 */
 
#include "../stdafx.h"
#include "demands.h"
#include "../core/math_func.hpp"
#include <queue>
 
#include "../safeguards.h"
 
typedef std::queue<NodeID> NodeList;
 
class Scaler {
public:
  void SetDemands(LinkGraphJob &job, NodeID from, NodeID to, uint demand_forw);
};
 
class SymmetricScaler : public Scaler {
public:
  inline SymmetricScaler(uint mod_size) : mod_size(mod_size), supply_sum(0),
    demand_per_node(0)
  {}
 
  inline void AddNode(const Node &node)
  {
    this->supply_sum += node.base.supply;
  }
 
  inline void SetDemandPerNode(uint num_demands)
  {
    this->demand_per_node = std::max(this->supply_sum / num_demands, 1U);
  }
 
  inline uint EffectiveSupply(const Node &from, const Node &to)
  {
    return std::max(from.base.supply * std::max(1U, to.base.supply) * this->mod_size / 100 / this->demand_per_node, 1U);
  }
 
  inline bool HasDemandLeft(const Node &to)
  {
    return (to.base.supply == 0 || to.undelivered_supply > 0) && to.base.demand > 0;
  }
 
  void SetDemands(LinkGraphJob &job, NodeID from, NodeID to, uint demand_forw);
 
private:
  uint mod_size;        
  uint supply_sum;      
  uint demand_per_node; 
};
 
class AsymmetricScaler : public Scaler {
public:
  inline void AddNode(const Node &)
  {
  }
 
  inline void SetDemandPerNode(uint)
  {
  }
 
  inline uint EffectiveSupply(const Node &from, const Node &)
  {
    return from.base.supply;
  }
 
  inline bool HasDemandLeft(const Node &to) { return to.base.demand > 0; }
};
 
void SymmetricScaler::SetDemands(LinkGraphJob &job, NodeID from_id, NodeID to_id, uint demand_forw)
{
  if (job[from_id].base.demand > 0) {
    uint demand_back = demand_forw * this->mod_size / 100;
    uint undelivered = job[to_id].undelivered_supply;
    if (demand_back > undelivered) {
      demand_back = undelivered;
      demand_forw = std::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);
}
 
inline void Scaler::SetDemands(LinkGraphJob &job, NodeID from_id, NodeID to_id, uint demand_forw)
{
  job[from_id].DeliverSupply(to_id, demand_forw);
}
 
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].base.supply > 0) {
      supplies.push(node);
      num_supplies++;
    }
    if (job[node].base.demand > 0) {
      demands.push(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();
 
    for (uint i = 0; i < num_demands; ++i) {
      assert(!demands.empty());
      NodeID to_id = demands.front();
      demands.pop();
      if (from_id == to_id) {
        /* Only one node with supply and demand left */
        if (demands.empty() && supplies.empty()) return;
 
        demands.push(to_id);
        continue;
      }
 
      int32_t supply = scaler.EffectiveSupply(job[from_id], job[to_id]);
      assert(supply > 0);
 
      constexpr int32_t divisor_scale = 16;
 
      int32_t scaled_distance = this->base_distance;
      if (this->mod_dist > 0) {
        const int32_t distance = DistanceMaxPlusManhattan(job[from_id].base.xy, job[to_id].base.xy);
        /* Scale distance around base_distance by (mod_dist * (100 / 1024)).
         * mod_dist may be > 1024, so clamp result to be non-negative */
        scaled_distance = std::max(0, this->base_distance + (((distance - this->base_distance) * this->mod_dist) / 1024));
      }
 
      /* Scale the accuracy by distance around accuracy / 2 */
      const int32_t divisor = divisor_scale + ((this->accuracy * scaled_distance * divisor_scale) / (this->base_distance * 2));
      assert(divisor >= divisor_scale);
 
      uint demand_forw = 0;
      if (divisor <= (supply * divisor_scale)) {
        /* 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_scale) / 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 = std::min(demand_forw, job[from_id].undelivered_supply);
 
      scaler.SetDemands(job, from_id, to_id, demand_forw);
 
      if (scaler.HasDemandLeft(job[to_id])) {
        demands.push(to_id);
      } else {
        num_demands--;
      }
 
      if (job[from_id].undelivered_supply == 0) break;
    }
 
    if (job[from_id].undelivered_supply != 0) {
      supplies.push(from_id);
    } else {
      num_supplies--;
    }
  }
}
 
DemandCalculator::DemandCalculator(LinkGraphJob &job) :
  base_distance(IntSqrt(DistanceMaxPlusManhattan(TileXY(0,0), TileXY(Map::MaxX(), Map::MaxY()))))
{
  const LinkGraphSettings &settings = job.Settings();
  CargoType cargo = job.Cargo();
 
  this->accuracy = settings.accuracy;
  this->mod_dist = settings.demand_distance;
  if (this->mod_dist > 100) {
    /* Increase effect of mod_dist > 100.
     * Quadratic:
     *   100 --> 100
     *   150 --> 308
     *   200 --> 933
     *   255 --> 2102
     */
    int over100 = this->mod_dist - 100;
    this->mod_dist = 100 + ((over100 * over100) / 12);
  }
 
  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;
  }
}