Re: pathfinding refueling

[Eric McDonald <mcdonald at phy dot cmich dot edu>]

Hi Peter,

First, a few things:
(1) I am simply seeking a technical discussion, not a flamewar. I 
want to understand what you propose, including its limitations. 
Exploring its limitations is not the same thing as providing 
negative feedback or criticizing it into oblivion.
(2) I am not taking anything personally wrt Bellum or anything 
else. If I cite Bellum as example, it is because it is one of the 
Xconq games I am most familiar with, __and one that has a level of 
complexity that can give rise to odd cases or interesting 
counterexamples.

On Thu, 18 Dec 2003, Peter Garrone wrote:

> > Why only one? In the case of Bellum, c is every bit as important 
> > as f1 or f2. A unit will become paralyzed without c.
> 
> Because when I am ferrying units about in standard, and bellum,
> aircraft run out of one thing generally, fuel. The aim is to avoid

But that need not be the case. A game designer is completely free 
to make a game where 2 materials could be regarded as equally 
important, equally consumed fuels. And I don't think it is our 
privilege to tell the game designer not to do that, or to roll the 
two "fuel" types into one.

> Your assumption that I am ignoring these parameters is incorrect.

OK, then I misunderstood your comment about the distinction 
between the referee and the helper AI, and how it pertained to the 
question at hand.

> > > 3) The distance that the unit can receive the material is zero.
> > 
> > How is this a relevant criterion?
> 
> Because if distance is greater than zero, generally a unit gets resupplied
> by the general resupply code at the end of a turn, and there is not
> usually a problem such as with aircraft of continually moving it to a
> point of resupply.

That is an assumption. Words like "generally" and "usually" are 
not the same as "always".

Take some land units in Bellum, for instance. They can move 
outside their "c" in-length. And if they end up in a combat 
situation outside that radius, they will rapidly become depleted 
of "c", and hence be paralyzed.

> > A unit is not guaranteed to receive more "c" just because the 
> > 'in-length'/'out-length' happens to be > 0. "c" is just as 
> > relevant as "f1", IMO. Any refueling path heuristic should not 
> > assume some hypothetical supply of a material; all calculations 
> > should be done with material in hand.
> 
> OK you thought up c and you are taking it personally that I am assigning
> it less consideration than fuel, right.

No, I am saying that it is a sort of "fuel".

> But if I am ferrying aircraft around, they run out of fuel, not c.

But they could run out of "c".

> Your c represents the attention span and loyalty of the pilot I presume,
> which is less than one tank of fuel? Are you attempting to simulate
> reality or what?

No. I am not attempting to simulate reality. I have attempted to 
make an interesting and fun game. I do not know if I have 
succeeded in that attempt yet. I am still waiting for more 
play-tester feedback.

As far as what "c" means: no, it does not have anything to do with 
loyalty. I would use the side opinion mechanism, if I wanted 
something like that. And it doesn't really mean attention span 
either. It is simply an abstract quantity of "command points".

> fuel, but f would receive priority, because it would imply a shorter
> range. But if c were set up to have a shorter range, then that would be
> the critical fuel. If c and f were identical in range, and had different
> supply unit positions, then it wouldnt work and the planes would crash,
> but it would be a stupid game anyhow and I doubt I would bother playing
> it.

Just to make sure that we are on the same page: here, you are 
referring to "range" as the maximum distance a unit can travel 
before it would have to turn around (or go elsewhere) to resupply 
the fuel in question, right?

> It is possible in the GDL to have
> different units at different positions supplying different materials.

Correct. This is one of the scenarios I have in mind.

> It is not possible to terminate such a path so as to guarantee
> that a unit will be able to have enough fuel to travel to multiple supply
> points. An infinite loop results if more than one fuel type at more than
> one resupply point.

Maybe we need to take a more piecewise approach to path-finding. 
We have a final destination goal B, and a starting point A. Now if 
we determine that we would run short of a fuel while going from A 
to B, then we use an alternate heuristic which drives the "ideal" 
path towards a resupply point C. Then we move from A to C. At C, 
we replenish every relevant material we can get ahold of. Then, we 
try making a path from C to B. Again, if we determine that we 
would run short of a fuel while going from C to B, then we use the 
alternate heuristic to drive the "ideal" path towards a resupply 
point D, and so on and so forth.

So we don't try to calculate the entire path ab initio (which 
would require considering multiple fuel types and would be messy), 
but rather do it in segments....

> You are suggesting a "greedy" algorithm, which of course I imply in my
> carrier fuel and ammo example. I dont see how you can suggest this but argue for
> multiple material types in the pathfinding. You are trying to ride two
> horses.

Not really. A resupply point is not guaranteed to provide more 
than one fuel type that may be necessary for a unit. And I'm not 
sure that we are in a position to judge whether such a game would 
be "stupid" or not.

> how. I am inclined to identify the fuel type giving the shortest range
> for a unit, and only pathfinding for that fuel type.

I would agree except for the already mentioned case where the 
resupply point which provides the shortest-range fuel does not 
provide the longer-range fuels.

> You have not advanced any convincing arguments as to why more than one
> fuel type should be taken into consideration when pathfinding. Unless
> you can convince me that it is important to do so, and also address the path
> termination problem, I will develop for one fuel type only, the fuel giving
> the shortest range for a particular unit type.

My recommendation is piecewise pathfinding, as laid out above. It 
is not computationally complex, since at most one type of fuel is 
motivating any one leg of a journey to a final destination. And, 
it is safer, IMO, since it does not assume that a resupply point 
provides all necessary fuel types for a given unit. (Note that a 
resupply point may even be capable of providing all necessary fuel 
types, but it may simply be out of some, if other units 
already sucked it dry.)

Eric