Re: pathfinding refueling

Re: pathfinding refueling

[Eric McDonald]

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

Re: pathfinding refueling

[Peter Garrone]

On Thu, Dec 18, 2003 at 12:24:23PM -0500, Eric McDonald wrote:
> 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.

This is helper AI code. If a game designer implements a game that
requires a player to move a unit continually to several distinct
positions to obtain peculiar materials associated with each position,
then fine, but we dont have to set up the helper ai code to automate
that process. The player can always do it manually. No game does it now,
and I doubt any rational game designer would do it. But if they did,
this development that I am proposing does not preclude it, just doesnt
automate it.

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

I am a native english speaker and I do understand what these words mean,
thanks. For someone who doesnt want a flamewar, you sure know how to
irritate. You will have to make your point more directly please.

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

But that does not create the clickathon playability problem that I intend this
code to address. I do not think it is the role of the pathfinding to
address the strategic problem associated with lack of c.

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

As I have pointed out elsewhere, the c problem does not create a
playability problem because it gets resupplied at every turn, if within
range, and aircraft do not ususally crash because they run out of c.

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

But that is not a playability problem.

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

Its irrelevant to the discussion. I obviously am not being direct enough
when making a point. Games do not generally have more than one
fuel-material per unit. c is not a fuel-material because it does not
require the player to move it to a refueling point to get more.

I am proposing to automate only one fuel-material per unit. The game
designer is free to have more, just they will not be automated. But if
there are several, then the one giving the shortest effective range
will be automated. With any others, the player would have to guide them
to refueling 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?

For me range is the number of MP possible given full tanks.

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

I would regard this approach as a bit low-tech.
The pathfinding has a set of open nodes, each node having position and
fuel. At each step in the iteration, it gets the best current node, and
generates all possible child nodes from it. Each child node would have
less fuel than its parent, unless it was at a refueling point where it
would refuel. If a child node runs out of fuel, it gets terminated.

What you dont seem to grasp is that it is necessary to guarantee at the
end of a trip that the unit has the ability to travel to the nearest
refueling point. With multiple points for multiple fuels, we get an
infinite loop. There are probably ways around this, but it gets too
messy. It is only necessary to consider one fuel to achieve 100%
automation.

> 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

Go for it. I dont endorse it, but thats irrelevant. I have better things
to do.

Re: pathfinding refueling

[Eric McDonald]

On Fri, 19 Dec 2003, Peter Garrone wrote:

> this development that I am proposing does not preclude it, just doesnt
> automate it.

I understand this.

> > That is an assumption. Words like "generally" and "usually" are 
> > not the same as "always".
> 
> I am a native english speaker and I do understand what these words mean,
> thanks. For someone who doesnt want a flamewar, you sure know how to
> irritate. You will have to make your point more directly please.

Cool down, mate. I know that the .au flavo[u]r of English is not 
terribly different than my own.

I am not trying to be irritating. Like I said previously, I am 
simply seeking a technical discussion. If I know what to expect, 
I'll know better what to test (and what not to be apprehensive 
about) when I receive your patch, if I receive your patch.

All I was getting at is that you are making a solution aimed at 
what is perceived to be a majority of the cases, but it does not 
cover all of the cases.

> But that does not create the clickathon playability problem that I intend this
> code to address. I do not think it is the role of the pathfinding to
> address the strategic problem associated with lack of c.

Nor do I. I was simply pointing out that one fuel-material may be 
lower than another, even if the "full-tank" range of the lower 
fuel-material is greater.

> > No, I am saying that it is a sort of "fuel".
> 
> As I have pointed out elsewhere, the c problem does not create a
> playability problem because it gets resupplied at every turn, if within
> range, and aircraft do not ususally crash because they run out of c.

"If within range". Here is a key issue. Why should we assume that 
a unit will be within replenishment range at the end of its move?

> > But they could run out of "c".
> 
> But that is not a playability problem.

It's not? So a unit runs out of "c" and then can no longer move, 
and thus cannot refuel at least until the next turn (but possibly 
not then because of fuel attrition), __and that it is not a 
playability problem? Even though the automated movement got the 
unit into that situation?

> > 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".
> 
> Its irrelevant to the discussion.

Agreed. But it seemed that I needed to set the record straight.

> when making a point. Games do not generally have more than one
> fuel-material per unit. c is not a fuel-material because it does not
> require the player to move it to a refueling point to get more.

But, at times, it does. See above example.
It is consumed every movement that a unit makes, and thus I would 
regard it as a fuel based on that property alone.

> I am proposing to automate only one fuel-material per unit. The game
> designer is free to have more, just they will not be automated. But if

I understand this. It has been clear almost since the beginning of 
this discussion.

> For me range is the number of MP possible given full tanks.

OK.

> > 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....
> 
> I would regard this approach as a bit low-tech.

?

> The pathfinding has a set of open nodes, each node having position and
> fuel. At each step in the iteration, it gets the best current node, and
> generates all possible child nodes from it. Each child node would have
> less fuel than its parent, unless it was at a refueling point where it
> would refuel. If a child node runs out of fuel, it gets terminated.

OK. This gives me a much clearer picture into your thinking. 
Thanks.
From a programmer's perspective, I sympathize with your approach. 
From a player's perspective, I don't.

> What you dont seem to grasp is that it is necessary to guarantee at the
> end of a trip that the unit has the ability to travel to the nearest
> refueling point.

I understand this perfectly well. Indeed, I would rather say that 
it is one of the main points of this discussion.

> With multiple points for multiple fuels, we get an
> infinite loop. There are probably ways around this, but it gets too
> messy. 

I also said that for any one leg of the journey, only one 
resupply point for one material-fuel should be considered. I said 
that considering mutliple material-fuels at the same time would be 
messy. Where we seem to differ is that you wish to consider only 
one material-fuel for the entire journey, whereas I would prefer 
to break the journey up into legs depending on which material-fuel 
needs to be addressed, if any.

>It is only necessary to consider one fuel to achieve 100%
> automation.

I agree, if the players are willing to occasionally have their 
units 100% automatically stranded or suicided....

> Go for it. I dont endorse it, but thats irrelevant. I have better things
> to do.

I would rather not have two competing solutions to this problem; 
that is part of the reason I am trying to flesh things out with 
you.

Please understand that I am stating personal preferences on what I 
think the behavior of Xconq ought to be. My opinions are not 
necessarily shared by others who have the power to checkin a patch 
from you. Feel free to shop it around to them when you have it 
ready. I do not have any "veto" power, contrary to an assumption 
made by van Every.

I personally want to see us do what is best as possible within 
reasonable implementation complexity and CPU usage constraints. 
Something that would "usually" work in most cases may not be the 
best we can do....

After I get home from work, I will try to find some time to sit 
down and propose a number of scenarios to you. For each one, I 
will tell you how my proposed solution would deal with it, and 
then you can comment as you see fit.

  Cheers,
    Eric

Re: pathfinding refueling

[Peter Garrone]

On Thu, Dec 18, 2003 at 07:11:55PM -0500, Eric McDonald wrote:
> All I was getting at is that you are making a solution aimed at 
> what is perceived to be a majority of the cases, but it does not 
> cover all of the cases.

I am merely attempting to improve playability by reducing the required
amount of micromanagement. I do not see it as the role of pathfinding to
guarantee that all units remain in supply at all times.

> 
> > But that does not create the clickathon playability problem that I intend this
> > code to address. I do not think it is the role of the pathfinding to
> > address the strategic problem associated with lack of c.
> 
> Nor do I. I was simply pointing out that one fuel-material may be 
> lower than another, even if the "full-tank" range of the lower 
> fuel-material is greater.

Then I assume we agree that the pathfinding does not have to guarantee
supply.

> 
> > > No, I am saying that it is a sort of "fuel".
> > 
> > As I have pointed out elsewhere, the c problem does not create a
> > playability problem because it gets resupplied at every turn, if within
> > range, and aircraft do not ususally crash because they run out of c.
> 
> "If within range". Here is a key issue. Why should we assume that 
> a unit will be within replenishment range at the end of its move?
> 

The pathfinding does not have to guarantee supply, as we agreed. It is
merely improving playability by reducing the number of clicks.

> > > But they could run out of "c".
> > 
> > But that is not a playability problem.
> 
> It's not? So a unit runs out of "c" and then can no longer move, 
> and thus cannot refuel at least until the next turn (but possibly 
> not then because of fuel attrition), __and that it is not a 
> playability problem? Even though the automated movement got the 
> unit into that situation?

On a side note I wish you would give those bellum materials proper
names. c is not an issue, because any aircaft can fill up on c when it
fills up on fuel. An automobile service station usually supplies water air and oil
as well as fuel. Suppose someone were to have a game where such
materials were supplied at different positions. Then the pathfinding
would take care of the material having the shortest effective range, but
the player would have to guide units manually to different positions for
other materials. But such a game is highly unusual, and one could argue
that obviously the designer wants the player to have the vicarious
experience of guiding the unit to get these supplies at differing
locations.

> > when making a point. Games do not generally have more than one
> > fuel-material per unit. c is not a fuel-material because it does not
> > require the player to move it to a refueling point to get more.
> 
> But, at times, it does. See above example.

What example?

> 
> > > 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....
> > 
> > I would regard this approach as a bit low-tech.
> 
> ?

Adhoc, sub-optimal. It is easy to provide cases where it would fail.
It takes no advantage of the optimality of the astar pathfinding
algorithm.

> 
> > The pathfinding has a set of open nodes, each node having position and
> > fuel. At each step in the iteration, it gets the best current node, and
> > generates all possible child nodes from it. Each child node would have
> > less fuel than its parent, unless it was at a refueling point where it
> > would refuel. If a child node runs out of fuel, it gets terminated.
> 
> OK. This gives me a much clearer picture into your thinking. 
> Thanks.
> >From a programmer's perspective, I sympathize with your approach. 
> >From a player's perspective, I don't.

My approach gives the player as much control as previously, and freedom
to kill off units, as is currently the case. It will improve playability
by reducing the enormous amount of micromanagement associated with
ferrying aircraft to the front and in combat where continual refueling
of all combat aircraft is necessary. But the tactical limitations forced
by the need to refuel will continue.

> 
> > What you dont seem to grasp is that it is necessary to guarantee at the
> > end of a trip that the unit has the ability to travel to the nearest
> > refueling point.
> 
> I understand this perfectly well. Indeed, I would rather say that 
> it is one of the main points of this discussion.

But you do not address this issue.

> 
> > With multiple points for multiple fuels, we get an
> > infinite loop. There are probably ways around this, but it gets too
> > messy. 
> 
> I also said that for any one leg of the journey, only one 
> resupply point for one material-fuel should be considered. I said 
> that considering mutliple material-fuels at the same time would be 
> messy. Where we seem to differ is that you wish to consider only 
> one material-fuel for the entire journey, whereas I would prefer 
> to break the journey up into legs depending on which material-fuel 
> needs to be addressed, if any.

This is not a proper description for a workable algorithm.
It certainly does not address the termination problem.
What if you run out of material A while going for material B. What if a
later leg is found to be impassable. How do you determine the most
suitable refueling hops.

I am not interested in implementing this approach myself, so would
prefer not discussing it in this thread.

For all current games, if the unit takes on all possible fuels at each
refueling point, the single fuel approach will work. There would be no
need to side-track for a different fuel.

If the constraint was that the pathfinding must guarantee that no unit
shall ever run out of any sort of material, then the best way would be
to extend the node state. But that is not in fact the constraint. The
constraint is merely to improve the micromanagement.

This is repeating myself, but I am attempting to provide a concrete
example.

Suppose in bellum c was unavailable at the same points as f, 
and the aircraft has to go to a
different point to get c. There are several ways to handle this. If the
pathfinding had to handle it, then the best way would be to extend the
path node state to include two fuel quantities. But this causes a
combinatorial explosion in the number of path nodes in the algorithm.
The best way to handle this hypothetical situation is to simply have the
player ferry the aircraft between the points that supply c, and it will
pick up ordinary fuel in intermediate hops. 

It would be an extremely
unusual and hypothetical game that implemented this sort of thing,
and even if one existed,
then it cannot be said for certain that it is better to automate such
behavior in the pathfinding.

> 
> >It is only necessary to consider one fuel to achieve 100%
> > automation.
> 
> I agree, if the players are willing to occasionally have their 
> units 100% automatically stranded or suicided....

Well units occasionally get stranded and suicided now. The player still
has to think it out. I dont believe that the pathfinding should
guarantee that no unit will ever be lost to lack of supply. Rather it
should automate the micromanagement (credit to Hans for this term) a bit.

Peter

pathfinding refueling 2 (was Re: pathfinding refueling)

[Eric McDonald]

On Sat, 20 Dec 2003, Peter Garrone wrote:

>I do not see it as the role of pathfinding to
> guarantee that all units remain in supply at all times.

So you then think it is OK for a unit following a path to get 
stranded or suicided in some cases?

> > Nor do I. I was simply pointing out that one fuel-material may be 
> > lower than another, even if the "full-tank" range of the lower 
> > fuel-material is greater.
> 
> Then I assume we agree that the pathfinding does not have to guarantee
> supply.

You assume incorrectly, insofar as pathfinding can guarantee 
supply.

> The pathfinding does not have to guarantee supply, as we agreed. 

We did not and do not agree.

>It is
> merely improving playability by reducing the number of clicks.

A laudable goal, but at what sacrifice? A stranded unit here, a 
dead unit there?

> On a side note I wish you would give those bellum materials proper
> names.

They have abbreviated names so that they will properly fit on some 
displays. However, the help for each material mentions what it is 
and what it is good for.

> c is not an issue, because any aircaft can fill up on c when it
> fills up on fuel.

Not necessarily. In a combat zone, the resupply point may have 
already been drained of c.

> An automobile service station usually supplies water air and oil
> as well as fuel. 

"Usually" is key here. A service station may be sold out of any of 
the above.
This working assumption that you keep making about the 
availability of supplies is dangerous and unrealistic.

> materials were supplied at different positions. Then the pathfinding
> would take care of the material having the shortest effective range, 

The scenarios I provided already demonstrate the fallacy of 
that approach. Unless by "effective", you mean material on hand, 
rather than assuming a full-tank supply.

> What example?

The one I gave where a unit runs out of c while in pursuit of f1 
or f2.

> > ?
> 
> Adhoc, sub-optimal. It is easy to provide cases where it would fail.

Please do. I had hoped that our discussion would have been more 
along these lines.

> It takes no advantage of the optimality of the astar pathfinding
> algorithm.

Maybe not from point A to final destination B, but from A to 
resupply destination C, it certainly does.

> My approach gives the player as much control as previously,

Sure, but previously a unit would not be endangered by movement 
unless the player explicitly told it to do the endangering 
movement.

> and freedom
> to kill off units, as is currently the case.

My approach preserves this freedom as well.

> But you do not address this issue.

How not?

> This is not a proper description for a workable algorithm.

It is not a detailed description, but it is a valid 
general description.

> It certainly does not address the termination problem.

How not?

> What if you run out of material A while going for material B. 

Most likely the unit would be going for material A rather than 
material B, if there was a danger of A running out before B.

By contrast, your answer to this case, which I have raised several 
times now, seems to be that you only care about B (assuming that 
it has the shorter full-tank range), and so it doesn't matter what 
happens with A.

>What if a
> later leg is found to be impassable.

A leg cannot be impassable or else it wouldn't be a leg. (Or does 
your implementation of Astar allow for impassable paths to be 
calculated? :-)
But, maybe you are wondering what if the unit cannot reach its 
final destination because of the chosen legs?
Well then, I guess it won't reach its final destination. At least 
the unit is still alive, and didn't die an automated death. It 
would be closer to the final destination.

> How do you determine the most
> suitable refueling hops.

I illustrated this in the scenarios I provided yesterday.

> I am not interested in implementing this approach myself, so would
> prefer not discussing it in this thread.

I renamed the thread....
I am not interested in having two competing approaches. I have 
demonstrated aspects of yours which are unsound. I have yet to be 
shown how mine is unsound.
 
> For all current games, if the unit takes on all possible fuels at each
> refueling point, the single fuel approach will work.

Sure. "If" it takes on. Even if a game is designed to provide all 
the possible fuels at one resupply point, that resupply point is 
not guaranteed to be able to provide them.

So even if someone doesn't design a "stupid" game, it is still 
possible for your approach to do something bad to a unit.

> different point to get c. There are several ways to handle this. If the
> pathfinding had to handle it, then the best way would be to extend the
> path node state to include two fuel quantities.

I have already stated that I think the best way would be to focus 
on whatever was the more critical fuel-material quantity.

Trying to create a path based on two or more fuel-materials 
simultaneously would be a computational nuisance, as I think both 
you and I agree.

> The best way to handle this hypothetical situation is to simply have the
> player ferry the aircraft between the points that supply c, and it will
> pick up ordinary fuel in intermediate hops. 

If it doesn't run out of c en route.

> > I agree, if the players are willing to occasionally have their 
> > units 100% automatically stranded or suicided....
> 
> Well units occasionally get stranded and suicided now.

Sometimes a unit may get stranded due to changing game 
circumstances (as Hans said, war is a dynamic situation), but 
there isn't a thing you can do about that (except possibly play 
better :-). And, of course, a player may choose to suicide a 
unit....

> has to think it out. I dont believe that the pathfinding should
> guarantee that no unit will ever be lost to lack of supply. 

It cannot guarantee that, but it should not be callous about it 
either.

>Rather it
> should automate the micromanagement (credit to Hans for this term) a bit.

Agreed.

Eric

Re: pathfinding refueling

[Hans Ronne]

I think we need to refocus this discussion on how to handle refueling in
the best way. Peter's inital analysis had a lot of good points in it, but
so do some of Eric's comments. Here are my own reflections:

>Refueling points are units whose capacity and current supply exceeds the
>travelling units capacity, are either immobile or have a "refueling"
>task.

I would consider anything that has excess fuel a refueling point, even if
mobile and on a move-to task. Think of a carrier moving across the ocean on
its way to the enemy shore. It must be able to launch combat air patrols
while in transit and the latter must be able to find their way back to the
carrier for refueling.

What should be considered excess fuel is the key question. In the standard
game, I found some time ago that airplanes almost never resupplied from
carriers, since the threshold was too high. I therefore lowered it. See
ChangeLog 2003-08-17  for details.

> > >1) The storage of that material is greater than zero
> >
> > Does this include treasury storage?
>
>Its not a fuel if it is not consumed every turn or hex.

I think Eric was making the point that it is possible for fuel to be
consumed every turn or hex, but then filled up again at the start of each
turn from the treasury. This is a valid point, but it should be relatively
easy to handle.

>Maybe we need to take a more piecewise approach to path-finding.
> <snip>
>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....

This is an interesting point not only with respect to refueling, but for
path finding in general. One problem with the new path code is that if a
unit cannot find a path to its destination, it does not move at all. It
just sits where it is and accumulates failed move-to tasks. With the old
code, a unit would move in the direction of its target even if it could not
get there. Problems such as blocking enemy units or a lack of transports
(maybe because the necessary advances had not yet been researched) would
frequently get solved while the unit was on its way, and the side would
gain time, which is always important.

The point here is that a war is a very dynamic situation. Tactical
decisions, including path finding, should be reconsidered frequently since
conditions may change rapidly. It could therefore make sense, as Eric
suggests, to recompute paths on every leg of a journey, and also to
reconsider what material is currently limiting the range (and thus to be
considered as fuel) for this unit here and now. To this I would add that if
a clear path to the destination cannot be found, any move that takes the
unit closer to its destination should be considered.

The notion of precomputing a complex path involving perhaps both ferry
tasks and visits to multiple resupply points is very neat. I am therefore
not saying that one should not calculate the entire path ab initio (as Eric
put it). What I am suggesting is that a unit should stop at each leg on its
journey and dynamically reconsider how to best get where it wants to go,
just like a human would do. This would not be overly burdensome and it
would make path finding much more adaptive.

A final comment is that this is also how the combat code has evolved over
the last few years. The strategy code was originally much more important. A
unit would get assigned to a theater, move there, and hold a position, with
no consideration for what would happen on the way. A unit in transit would
not attack enemy units or come to the rescue of beleaguered cities. This
lack of flexibility made it very easy to beat the mplayer. For this reason,
we added the action-reaction code which dynamically reassesses what the
unit should do.

I think that in general, an AI that dynamically recomputes its tasks
(within reasonable limits) will do much better than a static AI which
adheres to a precomputed grand plan for each of its units.

Hans

Re: pathfinding refueling

[Peter Garrone]

On Fri, Dec 19, 2003 at 02:42:58AM +0100, Hans Ronne wrote:
> I think we need to refocus this discussion on how to handle refueling in
> the best way. Peter's inital analysis had a lot of good points in it, but
> so do some of Eric's comments. Here are my own reflections:
> 
> >Refueling points are units whose capacity and current supply exceeds the
> >travelling units capacity, are either immobile or have a "refueling"
> >task.
> 
> I would consider anything that has excess fuel a refueling point, even if
> mobile and on a move-to task. Think of a carrier moving across the ocean on
> its way to the enemy shore. It must be able to launch combat air patrols
> while in transit and the latter must be able to find their way back to the
> carrier for refueling.
> 
> What should be considered excess fuel is the key question. In the standard
> game, I found some time ago that airplanes almost never resupplied from
> carriers, since the threshold was too high. I therefore lowered it. See
> ChangeLog 2003-08-17  for details.

What if the path was precalculated several turns before and the unit has
moved on. A plane could run out of fuel and crash. It becomes a
coordination problem if the carrier is moving. If you can tell me how to
solve this, I'll do it your way.

> 
> > > >1) The storage of that material is greater than zero
> > >
> > > Does this include treasury storage?
> >
> >Its not a fuel if it is not consumed every turn or hex.
> 
> I think Eric was making the point that it is possible for fuel to be
> consumed every turn or hex, but then filled up again at the start of each
> turn from the treasury. This is a valid point, but it should be relatively
> easy to handle.

I would not consider it a fuel for pathfinding purposes in that situation because
there is no need to go to a supply point and refill. I would assume
that the supply code would replenish each turn.

> 
> >Maybe we need to take a more piecewise approach to path-finding.
> > <snip>
> >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....
> 
> This is an interesting point not only with respect to refueling, but for
> path finding in general. One problem with the new path code is that if a
> unit cannot find a path to its destination, it does not move at all. It
> just sits where it is and accumulates failed move-to tasks. With the old
> code, a unit would move in the direction of its target even if it could not
> get there. Problems such as blocking enemy units or a lack of transports
> (maybe because the necessary advances had not yet been researched) would
> frequently get solved while the unit was on its way, and the side would
> gain time, which is always important.

Segmentation makes the whole thing suboptimal. It is relatively
straightforward to allow ferries to be constructed and even developed in
the pathfinding code so I hope that addresses the situation.

> 
> The point here is that a war is a very dynamic situation. Tactical
> decisions, including path finding, should be reconsidered frequently since
> conditions may change rapidly. It could therefore make sense, as Eric
> suggests, to recompute paths on every leg of a journey, and also to
> reconsider what material is currently limiting the range (and thus to be
> considered as fuel) for this unit here and now. To this I would add that if
> a clear path to the destination cannot be found, any move that takes the
> unit closer to its destination should be considered.

I disagree somewhat. If there is no way, then that is simply that. The
ai or whatever should assign the unit a different task. What if a ferry
is assigned a hit-unit task on an enemy aircraft in the middle of a
continent?
> 
> The notion of precomputing a complex path involving perhaps both ferry
> tasks and visits to multiple resupply points is very neat. I am therefore
> not saying that one should not calculate the entire path ab initio (as Eric
> put it). What I am suggesting is that a unit should stop at each leg on its
> journey and dynamically reconsider how to best get where it wants to go,
> just like a human would do. This would not be overly burdensome and it
> would make path finding much more adaptive.

I would agree actually. Not every hex, perhaps every other turn or
something like that.

> 
> A final comment is that this is also how the combat code has evolved over
> the last few years. The strategy code was originally much more important. A
> unit would get assigned to a theater, move there, and hold a position, with
> no consideration for what would happen on the way. A unit in transit would
> not attack enemy units or come to the rescue of beleaguered cities. This
> lack of flexibility made it very easy to beat the mplayer. For this reason,
> we added the action-reaction code which dynamically reassesses what the
> unit should do.

The AI is preety interesting in that often extremely simple algorithms
have the best effect. It is somewhay beyond my conceptual capacities at
the moment though. Obviously we need to stop it losing aircraft etc to
lack of fuel.

> 
> I think that in general, an AI that dynamically recomputes its tasks
> (within reasonable limits) will do much better than a static AI which
> adheres to a precomputed grand plan for each of its units.
> 
> Hans

Agreed.

Peter
> 
> 
> 
> 
> 
> 

Re: pathfinding refueling

[Hans Ronne]

>> What should be considered excess fuel is the key question. In the standard
>> game, I found some time ago that airplanes almost never resupplied from
>> carriers, since the threshold was too high. I therefore lowered it. See
>> ChangeLog 2003-08-17  for details.
>
>What if the path was precalculated several turns before and the unit has
>moved on. A plane could run out of fuel and crash. It becomes a
>coordination problem if the carrier is moving. If you can tell me how to
>solve this, I'll do it your way.

This is something I also worried about when I was working on the old
resupply code this summer. It turned out not to be such a big problem,
after all. Airplanes generally move faster than carriers, and in most cases
the return trip takes only a single turn. Which means we are actually
dealing with a static target, provided that the path is recomputed each
turn.

>> I think Eric was making the point that it is possible for fuel to be
>> consumed every turn or hex, but then filled up again at the start of each
>> turn from the treasury. This is a valid point, but it should be relatively
>> easy to handle.
>
>I would not consider it a fuel for pathfinding purposes in that situation
>because
>there is no need to go to a supply point and refill. I would assume
>that the supply code would replenish each turn.

That's fine. But this is true only if there is stuff in the treasury. So we
would have to check the treasury when the path is recomputed and eliminate
those materials that are currently available from further consideration.

>> The point here is that a war is a very dynamic situation. Tactical
>> decisions, including path finding, should be reconsidered frequently since
>> conditions may change rapidly. It could therefore make sense, as Eric
>> suggests, to recompute paths on every leg of a journey, and also to
>> reconsider what material is currently limiting the range (and thus to be
>> considered as fuel) for this unit here and now. To this I would add that if
>> a clear path to the destination cannot be found, any move that takes the
>> unit closer to its destination should be considered.
>
>I disagree somewhat. If there is no way, then that is simply that. The
>ai or whatever should assign the unit a different task. What if a ferry
>is assigned a hit-unit task on an enemy aircraft in the middle of a
>continent?

Assigning a new task is what I had in mind. A move-to task to the closest
point on the failed path. Which means that the path-finding code would have
to return that point to the AI when it fails.

As for ships getting tasks that they cannot possibly reach, this is really
an AI problem. I would say that the best way to handle that is to let the
AI use the landsea_regions area layer to check if a possible destination is
reachable for a unit that cannot be ferried.

>> The notion of precomputing a complex path involving perhaps both ferry
>> tasks and visits to multiple resupply points is very neat. I am therefore
>> not saying that one should not calculate the entire path ab initio (as Eric
>> put it). What I am suggesting is that a unit should stop at each leg on its
>> journey and dynamically reconsider how to best get where it wants to go,
>> just like a human would do. This would not be overly burdensome and it
>> would make path finding much more adaptive.
>
>I would agree actually. Not every hex, perhaps every other turn or
>something like that.

Yes. It depends on how big the computational load is. The optimal solution
would be once each turn, right before the unit moves, so that the tactical
situation always is up-to-date. This is how the action-reaction code works.
But if we cannot afford that, I would suggest at least at the following
points:

1. When the unit leaves a resupply point (so that it may check what
material is currently limiting its movement and use it as fuel in the path
calculation).
2. When a unit leaves a ferry.
3. When its movement is obstructed in any way.

>The AI is preety interesting in that often extremely simple algorithms
>have the best effect. It is somewhay beyond my conceptual capacities at
>the moment though. Obviously we need to stop it losing aircraft etc to
>lack of fuel.

I had the resupply code working at one point. By working I mean no
airplanes ran out of fuel, not even when chasing down a carrier. I'm sure
we could get it to work again with your new path-finding code.

Hans

Re: pathfinding refueling

[Peter Garrone]

On Sat, Dec 20, 2003 at 12:54:18PM +0100, Hans Ronne wrote:
> >> What should be considered excess fuel is the key question. In the standard
> >> game, I found some time ago that airplanes almost never resupplied from
> >> carriers, since the threshold was too high. I therefore lowered it. See
> >> ChangeLog 2003-08-17  for details.
> >
> >What if the path was precalculated several turns before and the unit has
> >moved on. A plane could run out of fuel and crash. It becomes a
> >coordination problem if the carrier is moving. If you can tell me how to
> >solve this, I'll do it your way.
> 
> This is something I also worried about when I was working on the old
> resupply code this summer. It turned out not to be such a big problem,
> after all. Airplanes generally move faster than carriers, and in most cases
> the return trip takes only a single turn. Which means we are actually
> dealing with a static target, provided that the path is recomputed each
> turn.

This heuristic should work. After refueling successfully at a refueling
point, a units checks its next refueling point by examining the cached
path.

If it has insufficient movement points
to reach the next point in the move, and it has used some mp this turn,
and the next point is a mobile
unit, it goes into reserve for that turn,
and rechecks at the start of its next turn.

It checks if the next point is still there if mobile, and if there
is enough fuel to fill its tanks if mobile or not.
The constraint on fuel being a supply
length of zero is relaxed, so it will examine any material required
for turn survival and/or movement. If all is not
well, it does another pathfind.

If the next refuel point is mobile, it pushes a temporary
hold on the unit to stop it moving out of range. The mobile refuel point
will generally not lose any mp because it will still be able to move
after the unit has refueled. 

Obviously there are some extraordinary situations that would defeat
this. Too many aircraft could such the carrier dry. The carrier could be
sunk, or die somehow. But we only want something simple that mostly
works.

> 
> >> I think Eric was making the point that it is possible for fuel to be
> >> consumed every turn or hex, but then filled up again at the start of each
> >> turn from the treasury. This is a valid point, but it should be relatively
> >> easy to handle.
> >
> >I would not consider it a fuel for pathfinding purposes in that situation
> >because
> >there is no need to go to a supply point and refill. I would assume
> >that the supply code would replenish each turn.
> 
> That's fine. But this is true only if there is stuff in the treasury. So we
> would have to check the treasury when the path is recomputed and eliminate
> those materials that are currently available from further consideration.

I dont think it is up to the pathfinding to ensure supply, otherwise it
replicates the supply code. Rather the human or ai player should not
send units on extended moveto tasks if running out. However the
pathfinding could ensure that units skirt around local shortages of
av-fuel, sea-oil, "c".

Rather the pathfind checks when doing the whole path, that each
refueling point has enough fuel to fill the tanks. Also when travelling
on a cached path, it will check if the next point has enough fuel to
fill the tanks. 

> 
> >> The point here is that a war is a very dynamic situation. Tactical
> >> decisions, including path finding, should be reconsidered frequently since
> >> conditions may change rapidly. It could therefore make sense, as Eric
> >> suggests, to recompute paths on every leg of a journey, and also to
> >> reconsider what material is currently limiting the range (and thus to be
> >> considered as fuel) for this unit here and now. To this I would add that if
> >> a clear path to the destination cannot be found, any move that takes the
> >> unit closer to its destination should be considered.
> >
> >I disagree somewhat. If there is no way, then that is simply that. The
> >ai or whatever should assign the unit a different task. What if a ferry
> >is assigned a hit-unit task on an enemy aircraft in the middle of a
> >continent?
> 
> Assigning a new task is what I had in mind. A move-to task to the closest
> point on the failed path. Which means that the path-finding code would have
> to return that point to the AI when it fails.
> 
> As for ships getting tasks that they cannot possibly reach, this is really
> an AI problem. I would say that the best way to handle that is to let the
> AI use the landsea_regions area layer to check if a possible destination is
> reachable for a unit that cannot be ferried.

No. If the pathfinding fails, then there really will be no way for that
task to succeed, not even by developing the technology to build a ferry
and by building a ferry. The ai would be better off selecting a completely
different mission for that unit. The pathfinding means that the ai has
much better ability to determine which missions have any chance and which
have none.

> 
> >> The notion of precomputing a complex path involving perhaps both ferry
> >> tasks and visits to multiple resupply points is very neat. I am therefore
> >> not saying that one should not calculate the entire path ab initio (as Eric
> >> put it). What I am suggesting is that a unit should stop at each leg on its
> >> journey and dynamically reconsider how to best get where it wants to go,
> >> just like a human would do. This would not be overly burdensome and it
> >> would make path finding much more adaptive.
> >
> >I would agree actually. Not every hex, perhaps every other turn or
> >something like that.
> 
> Yes. It depends on how big the computational load is. The optimal solution
> would be once each turn, right before the unit moves, so that the tactical
> situation always is up-to-date. This is how the action-reaction code works.
> But if we cannot afford that, I would suggest at least at the following
> points:
> 
> 1. When the unit leaves a resupply point (so that it may check what
> material is currently limiting its movement and use it as fuel in the path
> calculation).

I think my suggested heuristic ovecomes this. It investigates the next cached
resupply point, and if it is out of any sort of fuel, or has moved, then
recalculate.

> 2. When a unit leaves a ferry.

I am not in complete agreement here.
The ferry will drop a unit off at its planned point.
Perhaps when a ferry drops off a unit, a recalculation for all
other occupants might be justified, because the current dropdown point might
be better than the scheduled point for a unit. This should provide sufficient
tactical flexibility.

> 3. When its movement is obstructed in any way.

What do you mean by obstruction? The pathfinding will naturally move
around terrain obstructions, and also calculate optimal paths based on
friendly units moving out of the way to an extent. But if an action
suggested by the pathfinding fails, then it would probably be reasonable
for a re-calculation.

I think some doctrinal supply tests may have been skipped somehow, and
this disadvantages the ai player. So perhaps if a unit is running short
on some material, this test is not being carried out as it should,
so will check this. The ai player should resupply itself, then
recalculate its path.

> 
> >The AI is preety interesting in that often extremely simple algorithms
> >have the best effect. It is somewhay beyond my conceptual capacities at
> >the moment though. Obviously we need to stop it losing aircraft etc to
> >lack of fuel.
> 
> I had the resupply code working at one point. By working I mean no
> airplanes ran out of fuel, not even when chasing down a carrier. I'm sure
> we could get it to work again with your new path-finding code.

The hueristic I mentioned earlier should go a long way towards
addressing the situation.

One point is that with refueling and a more sophisticated
transportation ferrying model, pathfinding will become quite expensive.
There are some very big games in the library, so some care needs to be
taken.

Thanks for your consideration
 Peter

Re: pathfinding refueling

[Hans Ronne]

>This heuristic should work. After refueling successfully at a refueling
>point, a units checks its next refueling point by examining the cached
>path.
>
>If it has insufficient movement points
>to reach the next point in the move, and it has used some mp this turn,
>and the next point is a mobile
>unit, it goes into reserve for that turn,
>and rechecks at the start of its next turn.

Yes, if fuel consumption is per-move. If it is per-turn, going into reserve
makes little sense. Unless it can resupply itself from the terrain, of
course.

>Obviously there are some extraordinary situations that would defeat
>this. Too many aircraft could such the carrier dry. The carrier could be
>sunk, or die somehow. But we only want something simple that mostly
>works.

Agreed. Accidents happen in real life, too.

>I dont think it is up to the pathfinding to ensure supply, otherwise it
>replicates the supply code. Rather the human or ai player should not
>send units on extended moveto tasks if running out. However the
>pathfinding could ensure that units skirt around local shortages of
>av-fuel, sea-oil, "c".

Yes. But we must still check the treasury in order to decide what materials
should at all be considered as fuel.

>> Assigning a new task is what I had in mind. A move-to task to the closest
>> point on the failed path. Which means that the path-finding code would have
>> to return that point to the AI when it fails.
>>
>> As for ships getting tasks that they cannot possibly reach, this is really
>> an AI problem. I would say that the best way to handle that is to let the
>> AI use the landsea_regions area layer to check if a possible destination is
>> reachable for a unit that cannot be ferried.
>
>No. If the pathfinding fails, then there really will be no way for that
>task to succeed, not even by developing the technology to build a ferry
>and by building a ferry. The ai would be better off selecting a completely
>different mission for that unit. The pathfinding means that the ai has
>much better ability to determine which missions have any chance and which
>have none.

I think getting closer to the enemy is generally  a good idea, even if you
cannot reach him. At least, you can perhaps stop him from invading you by
massing your troops on the beaches. However, finding a new plan is a good
alternative. The problem is that the AI will do neither. It will keep the
plan, typically a PLAN_OFFENSIVE which assigns the unit to hold an area
which it cannot reach, and then set the same move-to task resulting in the
same path failure over and over again.

This is what I meant when I said that it is really an AI problem rather
than a path-finding problem. The AI should check if a point is at all
reachable already at the plan level. This could be done by using the
landsea_regions area layer, path-finding, or a combination of both. If the
plan goal is not possible, the AI should replan instead of proceeding with
impossible tasks.

>> Yes. It depends on how big the computational load is. The optimal solution
>> would be once each turn, right before the unit moves, so that the tactical
>> situation always is up-to-date. This is how the action-reaction code works.
>> But if we cannot afford that, I would suggest at least at the following
>> points:
>>
>> 1. When the unit leaves a resupply point (so that it may check what
>> material is currently limiting its movement and use it as fuel in the path
>> calculation).
>
>I think my suggested heuristic ovecomes this. It investigates the next cached
>resupply point, and if it is out of any sort of fuel, or has moved, then
>recalculate.
>
>> 2. When a unit leaves a ferry.
>
>I am not in complete agreement here.
>The ferry will drop a unit off at its planned point.
>Perhaps when a ferry drops off a unit, a recalculation for all
>other occupants might be justified, because the current dropdown point might
>be better than the scheduled point for a unit. This should provide sufficient
>tactical flexibility.

My thinking was that after the unit has been sitting x number of turns on a
ferry, the tactical situation has changed. And it is the unit that gets off
that has to worry about blocking enemy units etc. So a path recalculation
at this point seemed like a good idea.

>> 3. When its movement is obstructed in any way.
>
>What do you mean by obstruction? The pathfinding will naturally move
>around terrain obstructions, and also calculate optimal paths based on
>friendly units moving out of the way to an extent. But if an action
>suggested by the pathfinding fails, then it would probably be reasonable
>for a re-calculation.

That's what I meant. The prime example being an enemy unit that blocks the
path.

>One point is that with refueling and a more sophisticated
>transportation ferrying model, pathfinding will become quite expensive.
>There are some very big games in the library, so some care needs to be
>taken.

I agree. Only testing can tell what we can afford in the end. And I think
getting the path cache to work without desync problems will be critical.
The code is much faster with it.

Hans

Re: pathfinding refueling

[Peter Garrone]

On Sun, Dec 21, 2003 at 01:27:22AM +0100, Hans Ronne wrote:
> >This heuristic should work. After refueling successfully at a refueling
> >point, a units checks its next refueling point by examining the cached
> >path.
> >
> >If it has insufficient movement points
> >to reach the next point in the move, and it has used some mp this turn,
> >and the next point is a mobile
> >unit, it goes into reserve for that turn,
> >and rechecks at the start of its next turn.
> 
> Yes, if fuel consumption is per-move. If it is per-turn, going into reserve
> makes little sense. Unless it can resupply itself from the terrain, of
> course.

Thanks. Of course in the roman game, food is consumed per turn. But that
would never be a problem because there arent any mobile land-based
resupply points. But I will certainly check for that in the code.

> 
> Yes. But we must still check the treasury in order to decide what materials
> should at all be considered as fuel.

I am planning on testing all materials for all materials, once at the
start. If any materials are consumed and required per turn or per move,
then it is a fuel. If any fuels have a receive-from distance of zero,
then it is a controlled fuel. The controlled fuel giving the shortest
range is the one that is controlled in the path-finding. But all
refueling points must be able to replenish all fuels required, otherwise
it is ignored as a refueling point. I am not planning to do a global
treasury check. Actually I am not completely sure what you mean, which
is why i am reiterating the proposed algorithm, hopefully it covers what
you mean.

> 
> 
> >> Yes. It depends on how big the computational load is. The optimal solution
> >> would be once each turn, right before the unit moves, so that the tactical
> >> situation always is up-to-date. This is how the action-reaction code works.
> >> But if we cannot afford that, I would suggest at least at the following
> >> points:
> >>
> >> 1. When the unit leaves a resupply point (so that it may check what
> >> material is currently limiting its movement and use it as fuel in the path
> >> calculation).
> >
> >I think my suggested heuristic ovecomes this. It investigates the next cached
> >resupply point, and if it is out of any sort of fuel, or has moved, then
> >recalculate.
> >
> >> 2. When a unit leaves a ferry.
> >
> >I am not in complete agreement here.
> >The ferry will drop a unit off at its planned point.
> >Perhaps when a ferry drops off a unit, a recalculation for all
> >other occupants might be justified, because the current dropdown point might
> >be better than the scheduled point for a unit. This should provide sufficient
> >tactical flexibility.
> 
> My thinking was that after the unit has been sitting x number of turns on a
> ferry, the tactical situation has changed. And it is the unit that gets off
> that has to worry about blocking enemy units etc. So a path recalculation
> at this point seemed like a good idea.

Ferry dropdowns are relatively rare, so I dont really have a problem
doing this.

> 
> >> 3. When its movement is obstructed in any way.
> >
> >What do you mean by obstruction? The pathfinding will naturally move
> >around terrain obstructions, and also calculate optimal paths based on
> >friendly units moving out of the way to an extent. But if an action
> >suggested by the pathfinding fails, then it would probably be reasonable
> >for a re-calculation.
> 
> That's what I meant. The prime example being an enemy unit that blocks the
> path.

OK.

> 
> >One point is that with refueling and a more sophisticated
> >transportation ferrying model, pathfinding will become quite expensive.
> >There are some very big games in the library, so some care needs to be
> >taken.
> 
> I agree. Only testing can tell what we can afford in the end. And I think
> getting the path cache to work without desync problems will be critical.
> The code is much faster with it.

I was thinking of trying to set a global flag that determines if the
function is called locally or should be pushed globally, so that it is
easy to determine if caching should occur or not. Another way would be
to set a bit in the "flags" parameter that determines if the function is
invoked from the mplayer/ai code or not, and that can control caching,
so you might do that as a temporary fix there. I will eventually be
looking at these options.

Peter

Re: pathfinding refueling

[Hans Ronne]

>> Yes. But we must still check the treasury in order to decide what materials
>> should at all be considered as fuel.
>
>I am planning on testing all materials for all materials, once at the
>start. If any materials are consumed and required per turn or per move,
>then it is a fuel. If any fuels have a receive-from distance of zero,
>then it is a controlled fuel. The controlled fuel giving the shortest
>range is the one that is controlled in the path-finding. But all
>refueling points must be able to replenish all fuels required, otherwise
>it is ignored as a refueling point. I am not planning to do a global
>treasury check. Actually I am not completely sure what you mean, which
>is why i am reiterating the proposed algorithm, hopefully it covers what
>you mean.

After looking at the code, I can understand if you were puzzled by my
comment. The way the treasury is supposed to work, a unit will take the
difference between the material it needs for any type of action and its own
supply from the treasury. However, this is not implemented for move
actions: consume_move_supplies only uses the unit's supply. This is clearly
a bug, which I will fix.

In any case, a material that is consumed per turn or per move and has a
receive-from distance of zero can still have a treasury. So once the bug
has been fixed, the algorithm would have to check the treasury. Or to be
more specific: check if a treasury exists for m and if
um_takes_from_treasury is greater than zero. In that case, m should
probably not be considered a controlled fuel.

I say probably, because it is possible to have some units give material to
the treasury and some hoard it (depending on um_gives_to_treasury). If the
units who produce m also hoard it, then we a situation resembling the
normal case. I don't think any games use this possibility now, however, so
we can perhaps worry about this complication later.

Hans

Re: pathfinding refueling

[Lincoln Peters]

On Sat, 2003-12-20 at 23:38, Peter Garrone wrote:
> > >If it has insufficient movement points
> > >to reach the next point in the move, and it has used some mp this turn,
> > >and the next point is a mobile
> > >unit, it goes into reserve for that turn,
> > >and rechecks at the start of its next turn.
> > 
> > Yes, if fuel consumption is per-move. If it is per-turn, going into reserve
> > makes little sense. Unless it can resupply itself from the terrain, of
> > course.
> 
> Thanks. Of course in the roman game, food is consumed per turn. But that
> would never be a problem because there arent any mobile land-based
> resupply points. But I will certainly check for that in the code.

What about the wandering barbarian tribes?  The last time I played
roman.g (when I was testing the pathfinding code), I used a tribe to
carry an invasion force across a desert (I piled infantry into the
tribe, then moved it across the desert).  The tribe remains productive,
even when in a desert and on the move (although less prodctive than a
stationary tribe in plains).

-- 
Lincoln Peters <sampln@sbcglobal.net>

Re: pathfinding refueling

[Peter Garrone]

On Sun, Dec 21, 2003 at 03:10:31PM -0800, Lincoln Peters wrote:
> On Sat, 2003-12-20 at 23:38, Peter Garrone wrote:
> > > >If it has insufficient movement points
> > > >to reach the next point in the move, and it has used some mp this turn,
> > > >and the next point is a mobile
> > > >unit, it goes into reserve for that turn,
> > > >and rechecks at the start of its next turn.
> > > 
> > > Yes, if fuel consumption is per-move. If it is per-turn, going into reserve
> > > makes little sense. Unless it can resupply itself from the terrain, of
> > > course.
> > 
> > Thanks. Of course in the roman game, food is consumed per turn. But that
> > would never be a problem because there arent any mobile land-based
> > resupply points. But I will certainly check for that in the code.
> 
> What about the wandering barbarian tribes?  The last time I played
> roman.g (when I was testing the pathfinding code), I used a tribe to
> carry an invasion force across a desert (I piled infantry into the
> tribe, then moved it across the desert).  The tribe remains productive,
> even when in a desert and on the move (although less prodctive than a
> stationary tribe in plains).
> 
> -- 
> Lincoln Peters <sampln@sbcglobal.net>

This development will be a long way from guaranteeing no unit will ever
starve. Hopefully it will increase playability by vastly reducing the
clicking on aircraft units and also as a way of minimising the losses
the ai incurs. it might work on the roman game to automate this
behavior, but I doubt its much of a problem. I think the roman game will
be fine as long as ships find their way round the med, and army units
drop in for food at cities on the way. Actually my main problem with it
is getting all the troops to jump into the transports at the start.

Seriously, it is beyond my ability, and desire, to replicate the supply code in the
pathfinding, so i hope noone expects this. Instead fairly simple
approaches are used to optimise playability.

Peter

Re: pathfinding refueling

[Eric McDonald]

OK, here are the scenarios. For the purposes of this discussion, I 
have a couple working definitions:
(1) Fuel-Material: Any material which must be consumed during 
normal movement of a unit.
(2) Range: The distance a unit can go, consuming a fuel-material, 
before it must resupply that fuel-material.

And the scenarios are:
(1) Suppose that a unit has just finished with combat and is now 
low on two fuel-materials, fuel1 and fuel2. The unit is at point 
A. The unit would like to move to point B. Destination C has an 
available supply of fuel1, but no available fuel2. Destination D 
has an available supply of fuel2, but no available fuel1. The unit 
consumes fuel1 and fuel2 at the rate of 1 per move. The unit has 3 
out of 10 fuel1 and 4 out of 8 fuel2. The distance from A to C is 
3, from A to D is 4, and C to D is 2.
  Under your proposal, fuel2 would be regarded as the critical 
fuel-material. However, because fuel1 is in a low supply 
condition, either you would have to wait for the player to request 
the destination again to override a safeguard (similar to the 
existing behavior), or else you would have to ignore it under the 
assumption that it would be replenished at the end of the turn. If 
you ignored it, then you seem to suggest that the unit would be 
directed towards destination D (because fuel2 has the shorter 
range). However, in that case, the unit would never make it, 
because it would run out of fuel1 first.
  Under my proposal, I would make sure that the player was aware 
of the fuel-materials situation by perhaps making him/her 
re-request a destination. If given the re-request, then the 
pathfinder would recognize that fuel1, not fuel2, was the most 
critically needed, and would direct the unit towards destination 
C, not D. The unit would arrive at C and refuel. After that, the 
unit would still be in a predicament because it would have only 1 
fuel2 left to reach D with, __not enough. However, it would have a 
better chance at regaining mobility or just surviving because it 
was able to replenish fuel1 (at least to some extent).

(2) Consider scenario 1 with the following modification. The unit 
now has 6 out of 8 fuel2.
  Under your proposal, the unit would attempt to reach destination 
D (as in scenario 1) and would fail because it ran out of fuel1 
first (as in scenario 1).
  Under my proposal, the pathfinder would recognize that fuel1 was 
the more critical and would attempt to reach destination C. The 
unit would reach destination C, refuel, and then attempt to move 
to B. Having only 3 of 8 fuel2, it would then divert to D (or 
possibly a destination E, if E was within range, had available 
fuel2, and was closer to B than D). There, it would refuel, and 
then attempt to move onward to final destination B. In this 
circumstance, my proposal is a clear win, because the unit 
remains mobile and intact.

I have a few other scenarios in mind, but I am getting tired, so I 
will leave them for another day (perhaps tomorrow).

Eric

Re: pathfinding refueling

[Peter Garrone]

On Thu, Dec 18, 2003 at 11:12:33PM -0500, Eric McDonald wrote:
> 
> OK, here are the scenarios. For the purposes of this discussion, I 
> have a couple working definitions:
> (1) Fuel-Material: Any material which must be consumed during 
> normal movement of a unit.
> (2) Range: The distance a unit can go, consuming a fuel-material, 
> before it must resupply that fuel-material.
> 
> And the scenarios are:
> (1) Suppose that a unit has just finished with combat and is now 
> low on two fuel-materials, fuel1 and fuel2. The unit is at point 
> A. The unit would like to move to point B. Destination C has an 
> available supply of fuel1, but no available fuel2. Destination D 
> has an available supply of fuel2, but no available fuel1. The unit 
> consumes fuel1 and fuel2 at the rate of 1 per move. The unit has 3 
> out of 10 fuel1 and 4 out of 8 fuel2. The distance from A to C is 
> 3, from A to D is 4, and C to D is 2.
>   Under your proposal, fuel2 would be regarded as the critical 
> fuel-material. However, because fuel1 is in a low supply 
> condition, either you would have to wait for the player to request 
> the destination again to override a safeguard (similar to the 
> existing behavior), or else you would have to ignore it under the 
> assumption that it would be replenished at the end of the turn. If 
> you ignored it, then you seem to suggest that the unit would be 
> directed towards destination D (because fuel2 has the shorter 
> range). However, in that case, the unit would never make it, 
> because it would run out of fuel1 first.
>   Under my proposal, I would make sure that the player was aware 
> of the fuel-materials situation by perhaps making him/her 
> re-request a destination. If given the re-request, then the 
> pathfinder would recognize that fuel1, not fuel2, was the most 
> critically needed, and would direct the unit towards destination 
> C, not D. The unit would arrive at C and refuel. After that, the 
> unit would still be in a predicament because it would have only 1 
> fuel2 left to reach D with, __not enough. However, it would have a 
> better chance at regaining mobility or just surviving because it 
> was able to replenish fuel1 (at least to some extent).
> 
> (2) Consider scenario 1 with the following modification. The unit 
> now has 6 out of 8 fuel2.
>   Under your proposal, the unit would attempt to reach destination 
> D (as in scenario 1) and would fail because it ran out of fuel1 
> first (as in scenario 1).
>   Under my proposal, the pathfinder would recognize that fuel1 was 
> the more critical and would attempt to reach destination C. The 
> unit would reach destination C, refuel, and then attempt to move 
> to B. Having only 3 of 8 fuel2, it would then divert to D (or 
> possibly a destination E, if E was within range, had available 
> fuel2, and was closer to B than D). There, it would refuel, and 
> then attempt to move onward to final destination B. In this 
> circumstance, my proposal is a clear win, because the unit 
> remains mobile and intact.
> 
> I have a few other scenarios in mind, but I am getting tired, so I 
> will leave them for another day (perhaps tomorrow).
> 
> Eric

These scenarios are not from any game in the library.
No rational game would have
separate sorts of extremely limited range fuels refueled from different
points like this. Nevertheless my following comments do apply to these
situations.

You would do better by creating a hypothetical situation from bellum
where both f and c are in short supply, some f is available at one spot,
some c at another, and an aircraft has to jump through calculation hoops
to work out what to do.

In such situations the player guides the unit to refueling points
(wo)manually and presses t for take. This sort of combat situation where
fuel etc is short should not be automated but it is the fun of the game
for the player to fix the situation directly by guiding the unit to
appropriate refueling points and allocating scarse resources as best
they can. 

But if the requirement were that all such situations should be
automated, then the approach I have advocated would be in error. But
that is not what I am trying to achieve anyway. I dont think its what
you would really like either, Eric.

No matter what situation you can postulate, I can always reply that the
player just does what is done now. But the approach I am outlining
simply reduces the micromanagement associated with
1) ferrying aircraft from point of production to the front.
2) combat situations where aircraft have to continuously get fuel almost
every turn.

I have spent hours on all these emails. I would rather just code up my
approach now thanks. Fat chance.
Peter

Re: pathfinding refueling

[Eric McDonald]

On Sat, 20 Dec 2003, Peter Garrone wrote:

> These scenarios are not from any game in the library.

Correct. And I did not claim they were. Nonetheless, they are 
valid hypothetical scenarios.

(And actually, if you look at the amount of c and f1 that are 
available to land units in Bellum, you might recognize how close 
this is to the fuel1 and fuel2 of the proposed scenarios.)

> No rational game would have
> separate sorts of extremely limited range fuels refueled from different
> points like this. 

So I guess Bellum isn't rational....
Please let me know how you would do things differently.

> In such situations the player guides the unit to refueling points
> (wo)manually and presses t for take. 

The player could do that if he or she wished to, but as I stated, 
the player was requesting a final destination B from the 
pathfinder. So, the question is, how would the pathfinder deal 
with this?

>This sort of combat situation where
> fuel etc is short should not be automated

How do you prevent it from being automated if automation was 
requested?

> But if the requirement were that all such situations should be
> automated, then the approach I have advocated would be in error.

If the player requests automation, then automation is indeed a 
requirement. (And this is no different than present behavior.)

> that is not what I am trying to achieve anyway. I dont think its what
> you would really like either, Eric.

In a scenario 1-like situation, I would probably move the unit by 
hand. In a scenario 2-like situation, I might let the automation 
do the work to a avoid the "clickathon".

> player just does what is done now. But the approach I am outlining
> simply reduces the micromanagement associated with
> 1) ferrying aircraft from point of production to the front.

As Bruno would probably mention, standing orders also do this. 
(Though they take some effort to set up initially).
But, I agree, that your approach would likely work well in dealing 
with this case.

> 2) combat situations where aircraft have to continuously get fuel almost
> every turn.

It is less clear how your proposal would help here. I think that 
the second scenario (or variations thereof) might show up fairly 
frequently in this case.

> I have spent hours on all these emails. I would rather just code up my
> approach now thanks. Fat chance.

So then code it up. I already told you that I am not stopping you 
(I cannot stop you). Just don't expect me to check it in; I think 
your proposed solution is a bit narrow-minded in some cases.

Re: pathfinding refueling

[Hans Ronne]

>> I have spent hours on all these emails. I would rather just code up my
>> approach now thanks. Fat chance.
>
>So then code it up. I already told you that I am not stopping you
>(I cannot stop you). Just don't expect me to check it in; I think
>your proposed solution is a bit narrow-minded in some cases.

I think it is perhaps time to conclude this discussion and move on. The new
path-finding code is a significant improvement, and I would very much like
it to be included in the 7.5 release. However, there are three problems
that must be solved first:

1. Sync errors (unless the cache is disabled).
2. Ferry problems.
3. Resupply problems.

If Peter can fix these problems, this will be a major contribution which is
certainly welcome. Maybe it doesn't address all possible scenarios, but we
can't let perfection be the enemy of good. Further improvements to the code
can always be made later, if necessary.

As for supporting more than one fuel, which is what much of the discussion
has been about, it is easy to do so if the path is recomputed when the unit
reaches a resupply point. And we already agreed that frequent
recalculations of the path is a good idea. All it would take is to check
what material is currently limiting the range, and use it as "fuel" in the
new path calculation. This would allow more than one material type to be
considered as fuel, and at the same time avoid the computational problems
that several fuel types would cause in any given path calculation.

I would therefore encourage Peter to go ahead with his scheme but include
dynamic recalculations of the path as often as is practical, and also make
the choice of which material type should be considered as "fuel" dynamic,
depending on the unit's supplies.

Hans

Re: pathfinding refueling

[Peter Garrone]

On Sat, Dec 20, 2003 at 11:48:59PM +0100, Hans Ronne wrote:
> >> I have spent hours on all these emails. I would rather just code up my
> >> approach now thanks. Fat chance.
> >
> >So then code it up. I already told you that I am not stopping you
> >(I cannot stop you). Just don't expect me to check it in; I think
> >your proposed solution is a bit narrow-minded in some cases.
> 
> I think it is perhaps time to conclude this discussion and move on.

There are many constructive comments in this thread, particularly from
Hans. This is very helpful. It is tricky territory though.

> The new
> path-finding code is a significant improvement, and I would very much like
> it to be included in the 7.5 release. However, there are three problems
> that must be solved first:
> 
> 1. Sync errors (unless the cache is disabled).
> 2. Ferry problems.
> 3. Resupply problems.
> 
> If Peter can fix these problems, this will be a major contribution which is
> certainly welcome. Maybe it doesn't address all possible scenarios, but we
> can't let perfection be the enemy of good. Further improvements to the code
> can always be made later, if necessary.

I am trying to address all these. I think we should accept that it will
be a major development though. I should have some time over the next few
weeks.

> 
> As for supporting more than one fuel, which is what much of the discussion
> has been about, it is easy to do so if the path is recomputed when the unit
> reaches a resupply point. And we already agreed that frequent
> recalculations of the path is a good idea. All it would take is to check
> what material is currently limiting the range, and use it as "fuel" in the
> new path calculation. This would allow more than one material type to be
> considered as fuel, and at the same time avoid the computational problems
> that several fuel types would cause in any given path calculation.

Perhaps dynamically changing the fuel type is the way but I cant see it right
now. For now I plan to implement a multiple refuel of all material types
that could constrain movement at resupply points, and if it is out of any
such material in that it could not top up the unit, disallow that resupply point, both in the path-finding,
and in the actual movement. But only the fuel type giving the minimal
range will be actually tracked in the path-finding node state.
It should be unnecessary to change fuel types in this manner because if
the unit cannot be supplied with sufficient quantities of all fuel
types, then both the pathfind will fail or the actual move task will
fail.
I do not think i was planning to do this before this thread, so this has
developed anyhow.

There is no way to tell in the pathfind that some other material than
the tracked fuel is in short supply, because only the main fuel is
tracked.

> 
> I would therefore encourage Peter to go ahead with his scheme but include
> dynamic recalculations of the path as often as is practical, and also make
> the choice of which material type should be considered as "fuel" dynamic,
> depending on the unit's supplies.
> 
> Hans
> 

Thanks for your contribution. But I would urge anyone who has any input
to continue to provide it. If an algorithm is suggested, and I cannot
think of a reason good why it wouldnt work, then I would use it.
It is actually quite helpful to knock suggested algorithms over.
 Peter

Re: pathfinding refueling

[Peter Garrone]

On Sat, Dec 20, 2003 at 11:09:08AM -0500, Eric McDonald wrote:
> On Sat, 20 Dec 2003, Peter Garrone wrote:
> 
> > These scenarios are not from any game in the library.
> 
> Correct. And I did not claim they were. Nonetheless, they are 
> valid hypothetical scenarios.
> 
> (And actually, if you look at the amount of c and f1 that are 
> available to land units in Bellum, you might recognize how close 
> this is to the fuel1 and fuel2 of the proposed scenarios.)
> 
> > No rational game would have
> > separate sorts of extremely limited range fuels refueled from different
> > points like this. 
> 
> So I guess Bellum isn't rational....
> Please let me know how you would do things differently.

But none of the units in bellum use more than one sort of fuel.
This example is not from bellum. I didnt say bellum was irrational,
but dont jump to inferences here.

> 
> > In such situations the player guides the unit to refueling points
> > (wo)manually and presses t for take. 
> 
> The player could do that if he or she wished to, but as I stated, 
> the player was requesting a final destination B from the 
> pathfinder. So, the question is, how would the pathfinder deal 
> with this?

It will refuel with the material it has decided is the fuel.
However if it could not take on board all materials necessary for its
survival, for a turn anyway, it would fail the task and sit there blinking stupidly.

> 
> >This sort of combat situation where
> > fuel etc is short should not be automated
> 
> How do you prevent it from being automated if automation was 
> requested?
> 
> > But if the requirement were that all such situations should be
> > automated, then the approach I have advocated would be in error.
> 
> If the player requests automation, then automation is indeed a 
> requirement. (And this is no different than present behavior.)

I am not developing a totally automated and integrated
pathfinding/supply environment. It is not my requirement.
It may be your requirement. That is not a cause for disagreement.

> 
> 
> > 2) combat situations where aircraft have to continuously get fuel almost
> > every turn.
> 
> It is less clear how your proposal would help here. I think that 
> the second scenario (or variations thereof) might show up fairly 
> frequently in this case.

I am happy to answer well posed questions, but this comment does not
qualify.  Your scenarios are not from any game.

> your proposed solution is a bit narrow-minded in some cases.

Thanks Eric, I'll take that on board, and try to be more broad-minded in
future. We cant all be renaissance genius's such as yourself.

Re: pathfinding refueling

[Mark A. Flacy]

>>>>> "Peter" == Peter Garrone <pgarrone@acay.com.au> writes:
Peter> 
Peter> But none of the units in bellum use more than one sort of fuel.

Eh?  *Every* unit in bellum uses a fuel and "command and control" points to
perform movement.  They *both* constrain the maximum possible distance that
a unit can move.

And from my experiences with bellum, "c" is a bigger constraint than fuel
for non-aircraft units.  My "clickathons" are due to "c" rather than "f1"
or "f2".

When I send units across the map, there is NOTHING more irritating than it
stopping because it ran out of "c" along the way to ask me what to do.  I
still want the #$@!!$! unit to move across the map to same place that I
told it to move to earlier.

I only want units to stop if they are low on something that will kill
them.  That's fuel for aircraft as well as the "s" for everything else.  If
they run out of something else along the way, they can wait for me to
establish a supply line hopefully without forgetting the original mission.

That's what happens when real military units run out of fuel; you continue
with the previous mission unless you've been told differently.


-- 
 Mark A. Flacy
 Any opinions expressed above are my own.  Any facts expressed above
 would imply that I know what I'm writing about.  Sometimes, I do!
"Yes, but every time I try to see things your way, I get a headache."
  --Unknown

pathfinding refueling

[Peter Garrone]

There was some discussion on another thread about refueling,
so I though I would attempt to tie this together in its own thread.

I propose that only one material per unit type be considered for
refueling control during pathfinding. In the standard game, this
would be fuel. In bellum, there appears to be marine fuel and aircraft
fuel. If a unit type is under refueling control, then a path is invalid
if the unit does not have enough fuel to travel to a refuelling point at the
end of its trip, and it would have enough at the start.

The pathfinding is helper-ai, not "refereed" code, so we try to keep it out
of the GDL. A material is a candidate for "fuel" for a unit if
1) The storage of that material is greater than zero
2) The consumption per move, or base consumption, is greater than zero
3) The distance that the unit can receive the material is zero.

I cannot see any units that require more than one type of fuel. In
bellum for example, the "c" material is not a fuel because it has a
send/receive distance greater than zero. In the roman game, food is a
fuel though it is only consumed per turn.

The main reason only one material can be a fuel are as follows:
- To be within range, a final untaken trip is calculated to a supply
  point, and having multiple supply points makes it all too difficult.
- It would require a variable length array to be added to pathfinding
  structures, making it a bit cumbersome.

Refueling points are units whose capacity and current supply exceeds the
travelling units capacity, are either immobile or have a "refueling"
task. So an aircraft carrier could be assigned a refueling task to
support an invasion. It just sits there doing nothing while aircraft
automatically go to it, refuel, get ammo, and return to the attack.

I would add some code to take ammo as well if refueling.

Peter

Re: pathfinding refueling

[Eric McDonald]

On Wed, 17 Dec 2003, Peter Garrone wrote:

> I propose that only one material per unit type be considered for
> refueling control during pathfinding.

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.

> The pathfinding is helper-ai, not "refereed" code, so we try to keep it out
> of the GDL. 

'material-to-move' and 'consumption-per-move' are part of GDL. I 
see no reason why the pathfinding should not pay attention to 
those very important tables, even if the referee must as well.

> 1) The storage of that material is greater than zero

Does this include treasury storage?

> 2) The consumption per move, or base consumption, is greater than zero

Fair enough.

> 3) The distance that the unit can receive the material is zero.

How is this a relevant criterion?

> I cannot see any units that require more than one type of fuel. In
> bellum for example, the "c" material is not a fuel because it has a
> send/receive distance greater than zero. 

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.

> The main reason only one material can be a fuel are as follows:
> - To be within range, a final untaken trip is calculated to a supply
>   point, and having multiple supply points makes it all too difficult.

One can always choose to be greedy, meaning that when a unit stops 
to resupply one material, it also tries to grab any others 
relevant to its journey.

Also, if the journey is sufficiently long, then one must indeed 
have multiple supply points, even if for one material.

> - It would require a variable length array to be added to pathfinding
>   structures, making it a bit cumbersome.

I hope this doesn't sound too harsh, but I would prefer 
correctness over not doing something because it is a "bit 
cumbersome".

> task. So an aircraft carrier could be assigned a refueling task to
> support an invasion. It just sits there doing nothing while aircraft
> automatically go to it, refuel, get ammo, and return to the attack.

OK. That is somewhat appealing.

> I would add some code to take ammo as well if refueling.

Sure, might as well.

  Regards,
    Eric

Re: pathfinding refueling

[Jim Kingdon]

> 3) The distance that the unit can receive the material is zero.

This would mean that infantry and armor in the standard game would
have no fuel material.

Kind of a problem trying to pathfind them through a desert.

Re: pathfinding refueling

[Peter Garrone]

On Thu, Dec 18, 2003 at 01:00:40PM -0500, Jim Kingdon wrote:
> > 3) The distance that the unit can receive the material is zero.
> 
> This would mean that infantry and armor in the standard game would
> have no fuel material.
> 
> Kind of a problem trying to pathfind them through a desert.

My aim in the exercise is to improve playability by reducing the amount
of clicking and micromanagement necessary. It is not necessary to guide
infantry or armor to particular resupply points, and so far as I am
concerned there is no particular problem with these units, so I am
proposing to do nothing with them.

I do not think it should be the role of the path-finding to ensure that
all units remain in supply at all times. The development I am interested
in is simply to improve playability by reducing all the aircraft
management.