Supply

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

This is the third in a series of slightly whiny, yet constructive posts.
Despite all the implied criticism I think the XConq project is very
impressive; otherwise I wouldn't bother posting stuff here. Keep up the
excellent work.

Support for supply and logistics in XConq is currently inadequate. I
propose a new algorithm (ripped from Advanced Third Reich) that I think
is a major improvement over the old one (at least for the kinds of
modules that I'd like to design). The algorithm would be run once per
side per turn (probably at the beginning of each turn), and could be
used in parallel with the old scheme. The algorithm is easy to
implement.

The idea is that supply is traced from producers to consumers an
arbitrary distance over suitable cells. The world is divided into
_supply zones_, areas of contiguous cells over and into which supply
can be traced. Here is some pseudocode:

for(each cell) { initialize its "zone" property to zero }
for(each unit) { initialize its "zone" property to zero }

n = 1;

/* Go through each cell and establish supply zones. */
for(each cell) {

    if(cell -> zone == 0) {

        /* This cell is not in a supply zone yet. */

	if(eligible_for_supply(cell)) {

	    /* Initiate a new supply zone. */
	    cell -> zone = n;
	    
	    /* Expand the supply zone. */
	    flood_fill(cell, n);
	    
	    n++;
	}
    }
}

eligible_for_supply(cell) would return true if the cell contains
friendly people or if the cell contains a producer of supply.

flood_fill(cell, n) would first process the given cell and then
recursively expand the supply zone to adjacent cells that satisfy
eligible_for_supply().

All the units in a processed cell would have their "zone" property set
to match the zone of the cell. A list could/should be kept of the total
consumption and availability of materials in each supply zone.

The result is a set of distinct supply zones and units belonging to
them. Finally, the available materials should be distributed (equally?)
among the consumers in a supply zone.

For a standard-type game of grand strategy, this would mean that ground
units would be automatically kept in supply if they can trace a supply
line over friendly cells to bases or cities, or possibly transports
(adjacent to coasts) supporting an invasion force. Supply lines could be
cut by moving your ground units (or any unit that can convert the people
in a cell) over vital cells in an enemy's supply zone, cutting it in two
and preventing the units on the other side from getting supplies. A
typical supply zone would be an island (presumably, there are no
friendly people in water cells).

There might be some other criteria for expanding supply zones (for
example, supply zone could not be expanded to an adjacent cell if both
cells are swamp etc.) but that is the general idea. I imagine that the
new algorithm would benefit other types of games also.

Any comments? :) If Stan endorses the supply algorithm I can work out
all the details in terms of GDL and even implement the thing (shouldn't
be difficult at all).

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