Re: pathfinding refueling

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

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