Re: Supply

[Sami P Perttu <perttu@cc.helsinki.fi>]

> It seems like you could also cut the flood fill after a certain
> distance, thus creating limited-length supply lines.  Pre-20th-century
> such as Napoleonics need to have several limits on supply line length,
> as well as the zoning.

Limited-length supply lines would be ideal, but, if supply lines must
have lengths, then there must be a supply zone for each unit that can
act as a supply source - computing those could take a lot of time. (Or do
you mean that there would only be a limit to the consumer's distance to
the nearest supply source in a supply chain? That still generates
overlapping supply zones).

There is also the problem of distributing materials sensibly among many 
overlapping supply zones - I have a feeling that an optimal solution
would require exponential computing time. The same problem persists in
the current supply scheme where you seem to have come up with some
strange-looking heuristics on how to distribute supplies :).

Hmm, more thought must be given to a limited-length algorithm? In the
meantime, I've formalized my ideas on the (considerably) simpler case of
supply lines of unlimited length:

Preliminary Proposal #1

Algorithm:      Supply lines of unlimited length. Distribution of
                supplies takes place in _supply zones_, areas of
                suitable, contiguous cells over and into which supply
                can be traced. Any number of producers and consumers can
                share supplies in a supply zone.
Time:           O(n + u*m), where n is the number of cells in the world,
                u the number of units a side has and m the number of
                material types. Run once per side per turn.
Space:          One scratch layer for recording runtime supply zone
                information; a maximum of two pointers per unit; plus a 
                small amount of constant space.
Implementation: Easy. perttu@cc.helsinki.fi has volunteered to implement
                the algorithm.
Applicability:  Broad enough to warrant inclusion? Doesn't suit all
                types of games.

GDL Keywords

Table: supply-out-threshold u m -> n

If unit u has more of material m than n it can act as a supply source in
a supply zone, the excess materials being distributed among the
consumers, if any. Defaults to -1 which disables supplying.

Table: supply-out-per-turn u m -> n

The maximum amount of material m that a unit of type u can give out to
other units in its supply zone in a given turn. Defaults to -1
(unlimited amount).

Table: supply-in-threshold u m -> n

If unit u has less of material m than n it can receive supplies from
supply sources in the unit's supply zone, but only up to quantity n.
Defaults to 0?

Table: supply-in-per-turn u m -> n

The maximum amount of material m that a unit of type u can receive from
its supply zone in a given turn. Defaults to -1 (unlimited amount).

Table: supply-priority u m -> n
Table: supply-starve-priority u m -> n

The relative supply priority of unit u with respect to material m. The
actual supply priority of a unit is linearly interpolated between
supply-starve-priority and supply-priority according to the amount of
material m the unit has: 0 produces supply-starve-priority, while
supply-in-threshold produces supply-priority. A unit whose supply
priority is twice as high as another unit's receives twice as much of
material m if in the same supply zone (assuming both have an equal
capacity for receiving material m). Both default to 1 which translates
to an equal distribution of supplies among all consumers.

TerrainTypeProperty: supply-zone-into n

A variable denoting if, and on what terms, a supply zone can expand into
the terrain (for cell types), across the terrain (for border types) or
along the terrain (for connection types). A supply zone can always
expand or start in a cell containing a friendly unit capable of acting
as a supply source (so that coastal transports can supply armies on an
island even if supply zones don't normally expand into water etc.; could
have some undesirable side effects). n is a bit field with the following
bit meanings:

0 - allow expansion if the destination cell is under the side's control
1 - allow expansion if the destination cell is under a friendly side's
    control
2 - allow expansion if the destination cell is under a neutral side's
    control
3 - allow expansion if the destination cell is under the independent
    side's control
4 - allow expansion if the destination cell is under nobody's control
5 - allow expansion if the destination cell is under a non-friendly
    side's control

Defaults to?

Other notes:

*A unit can simultaneously act both as a producer and a consumer. In
 theory, a unit could end up distributing supplies to itself, but that
 doesn't matter.

*Rules for supply zone expansion must be symmetric (can_expand(cell1,
 cell2) implies can_expand(cell2, cell1)).

*A cell cannot belong to multiple supply zones.

*Prefix all keywords with "supply-zone" instead of just "supply"?

*Need to add some graphics for displaying the cell control layer! If
 supply zones need to be displayed they can be generated on-the-fly
 quickly enough?

*The algorithm needn't be run at all if all unit and material type
 combinations have a supply-out-threshold of -1.

*The algorithm should be called right after run_economics().

*supply-zone-into could be turned into a table t m -> n but then supply
 zones would have to be calculated separately for each material type.
 ("Food can be distributed anywhere but oil requires pipelines" etc.).

-- 
Sami Perttu                       "Flower chase the sunshine"
perttu@cc.helsinki.fi