docs/linkgraph.md

   1 # Some clarifications about the link graph
   2
   3 `InitializeLinkGraphs` joins all threads, so if the game is abandoned
   4 with some threads still running, they're joined as soon as the next game
   5 (possibly the title game) is started. See also `InitializeGame`.
   6
   7 The MCF (multi-commodity flow) algorithm can be quite CPU-hungry as it's
   8 NP-hard and takes exponential time (though with a very small constant
   9 factor) in the number of nodes.
  10
  11 This is why it is run in a separate thread where possible. However after
  12 some time the thread is joined and if it hasn't finished by then the game
  13 will hang. This problem gets worse if we are running on a platform without
  14 threads. However, as those are usually the ones with less CPU power I
  15 assume the contention for the CPU would make the game hard to play even
  16 with threads or even without cargodist (autosave ...). I might be wrong,
  17 but I won't put any work into this before someone shows me some problem.
  18
  19 You can configure the link graph recalculation time. A link graph
  20 recalculation time of X days means that each link graph job has X days
  21 to run before it is joined. The downside is that the flow stats won't be
  22 updated before the job is finished and thus a high value means less
  23 updates and longer times until changes in capacities are accounted for.
  24 If you play a very large map with a complicated link graph you may want to
  25 raise the time setting to avoid lags. The same holds for systems with slow
  26 CPUs.
  27
  28 Another option to avoid excessive lags is to reduce the accuracy of link
  29 graph calculations. Generally the accuracy is inversely correlated to the
  30 CPU requirements of the MCF algorithm.