Posted at: 2021-08-17, 05:58
I have a proposal to improve how extra wares are distributed among the
warehouses. It is similar in spirit to
#4935, but with important
Just as in #4935, I am primarily thinking of the Barbarian tribe, though the
concept probably has value for other tribes, as well. When building on the
outskirts of my territory, it often takes a long time for basic building
materials to arrive (I am mostly thinking of logs, blackwood, stone). There are
also situations where it would be nice to be able to pre-fetch resources at a
nearby warehouse to feed hungry consumers. For example, a charcoal kiln is best
placed near a warehouse that has a ready supply of logs. Otherwise, it can lose
a lot of time waiting to be refilled for the next job.
Like #4935, I am thinking of each warehouse as having its own economy, but I am
not thinking of the warehouses as being consumers in the sense that a shortage
at a warehouse triggers a producer to create a ware. Rather, I am thinking more
in terms of automatically redistributing whatever wares happen to already be
assigned to warehouses, in order to shift available wares to the warehouses that
need them most.
In broad strokes, I imagine it working something like this:
Each warehouse allows the user to assign a target number of wares of each
type to keep in stock. Each type can have a different target stock, and all
targets default to zero. The user may change the targets at will. A global
control would allow the user to alter defaults for newly constructed warehouses.
For example, the user might declare that all new warehouses have targets of 5
logs and 2 blackwood, leaving other ware types at zero.
Periodically, a thread runs that captures the inventory of all the warehouses
at the same time. If possible, this would include any wares that are en route
to each warehouse.
Distances between all the pairs of warehouses are computed (real cost in time
to traverse, if possible, but approximations if it is too CPU intensive).
For each ware:
A. An algorithm runs to compute a plan for which wares to send from each
warehouse to every other warehouse.
B. The resulting plan is implemented by assigning each participating warehouse
to send the designated wares to the desired destination warehouses.
For most wares, there would be absolutely nothing to do. For example, fishing
poles don't need to be stored in any particular warehouse. They might as well
be stored in the nearest available warehouse after they are produced. It's
primarily core building materials, builders, and soldiers that are important to
spread throughout the map to avoid large transit times. For example, I imagine
having a global default that each warehouse would be stocked with something
- 5 logs
- 2 blackwood
- 1 stone
- 1 grout
- 1 reed
- 1 builder
- 1 soldier
That way, any time I build something the materials don't take long to get there.
A few seconds later, a re-balancing job would run, replenishing the resources
used, subject to availability.
If a particular warehouse is near a charcoal kiln or wood burner I would
increase its target supply of logs. If it's near the frontier, I would increase
the target for soldiers, etc.
By implementing this as a periodic (cron) job, this can all be done without
changing anything related to economies or current warehouse storage policies.
Those can all still work exactly as they already do.
A naive algorithm
I have implemented a candidate algorithm for step A. It is simple and could
certainly be improved, but it is fairly speedy in the examples I have done. It
works like this, for a given ware:
For the given ware, each warehouse has one of three states:
Shortage: STOCK is less than (or equal to) TARGET.
Surplus: STOCK is more than TARGET (regardless of whether TARGET is zero)
Exempt: STOCK == TARGET == 0. These warehouses are simply ignored.
If no warehouse is in shortage then the ware is simply skipped.
Each non-exempt warehouse is assigned an affinity:
Shortage: AFFINITY = (1 - STOCK / TARGET). This is just the percentage of
TARGET that is missing from STOCK. It is always non-negative, indicating that
it wants to attract more wares.
Surplus: AFFINITY = - (average affinity of all warehouses in shortage) Note that
it is always negative, indicating that it is happy to have wares taken away, and
all warehouses in surplus have the same affinity.
For each pair of non-exempt warehouses, compute the SLOPE:
(AFFINITY_A - AFFINITY_B) / (distance from A to B)
Beginning with a pair of warehouses with the largest (absolute value) slope,
assign one ware to be shifted in the direction that reduces the slope.
Recompute the affinities for A and B, along with the associated slopes, and
repeat (again, with the largest slope) until done.
With each iteration, the ware is only shifted if there is one in stock, and only
if shifting it will result in a slope that is smaller in absolute value.
Eventually, we will reach a point where passing a ware from any warehouse to any
other results in an increased slope, signaling that we should stop.
When computing the affinity, STOCK is understood to include any wares that are
in transit to the warehouse. Otherwise, the periodic rebalancing could
gradually flood the transport network, not knowing that the needed wares are
already on the way. If the game makes it hard to compute the number in transit,
we will have to have some sort of surrogate mechanism to prevent superfluous
wares being sent
There are conditions where the plan allows un-shifting a ware that has been
committed because other adjacent pairs of warehouses have changed affinities
enough to reverse the sign of the slope. The algorithm has provisions for this.
By using the slope in this way, we favor transfers between pairs of
warehouses that either
have greatly different affinities, i.e., one warehouse is much fuller than
are separated by short distances.
In other words, warehouses will tend to pull from close neighbors that have
greater stock (as a percentage of the target). Put differently, long transfers
don't arise often. Rather, a shift from A to B (with C "between") will often
naturally be implemented as a shift from A to C and a shift from C to B. That
is, two shorter legs rather than one long one. This means that warehouses
approach their targets more quickly.
After the basic algorithm runs, there is a refactoring step that looks for
opportunities to break especially long transfers into multiple stages in order
to reduce latency at the cost of causing more wares to be in transit.
By the time a plan is computed, the warehouse inventories may be slightly
different from when the snapshot was taken, so we just attempt all the planned
transfers, subject to continued availability of wares at each warehouse.
There is a question of how often the rebalancing should be redone. This will
take some experimentation to get right. It probably should be at least once per
minute, but preferably more like every 5-15 seconds if it can be done without
harming performance. Perhaps a user setting?
On my 11-year-old laptop (Intel(R) Core(TM)2 Duo CPU T9400
@ 2.53GHz) it takes about 1.5 milliseconds (using one core) to compute the plan
for one ware with 20 warehouses whose targets range between 0 and 10. I don't
yet know how much time it will take to gather all the input data. Computing all
the path-distances between warehouses and counting the wares on route may take
much more work than computing the plan.
Again, I imagine that most warehouses will have zero targets and zero stock for
most wares, so most will be exempt for most wares. The algorithm is inherently
quadratic, but even with a large number of warehouses the number that
participate will often be small.
It is probably reasonable to cache the pairwise distances between warehouses
so that they don't need to be recomputed all the time. They should be
recomputed from time to time, though, as the network evolves.
Warehouse A is tasked to send a ware to warehouse B. There is a ware en
route to A with distance(ware, < distance(A, B). It would be cool to catch
this and simply re-assign the ware to go to B. The problem is that it would
require computing the distance to B from all wares in transit to A. At least,
until a suitable one is found.
I implemented an enhanced heap structure that allows efficient computation of
largest slope, etc.
This algorithm would need to operate separately on connected components of
the road network. This adds overhead, but it also tempers the effects of
Ports are an interesting special case. A first pass might look something like this:
Apply the balancing algorithm to each component individually as usual. Ports
behave as normal warehouses.
Apply the balancing algorithm to the set of connected components (at least,
ones that have ports). That is, create a mock "PORT/WAREHOUSE" that represents
the net affinity of the component. Compute a balancing plan for that set and
then for each component choose a port to represent it, minimizing shipping
distances, and have the ports pull from each other to resolve those slopes.
Alternatively, if a component has multiple ports, the assigned wares could be
divided up evenly. It's probably better to use nearest ports, though, when