Re: pathfinding refueling

[Peter Garrone <pgarrone at acay dot com dot au>]

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