I have a proposal to improve how extra wares are distributed among the warehouses. It is similar in spirit to #4935, but with important differences.

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.

High-level view

In broad strokes, I imagine it working something like this:

1. 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.

2. 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.

3. 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 like:

• 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.

Notes

1. 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.

2. 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

3. 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.

4. 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 the other.

   • 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.

5. 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.

6. 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.

7. 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.

Potential optimizations

1. 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.

2. 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.

3. I implemented an enhanced heap structure that allows efficient computation of largest slope, etc.

Other considerations

1. This algorithm would need to operate separately on connected components of the road network. This adds overhead, but it also tempers the effects of quadratic growth.

2. 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 possible.

Top

Quote