[Freeciv-Dev] Re: [RFC] Path finding interface #9

[Raimar Falke <rf13@xxxxxxxxxxxxxxxxx>]

On Sat, May 25, 2002 at 11:56:06AM -0400, Ross W. Wetmore wrote:
> At 01:32 PM 02/05/25 +0200, Raimar Falke wrote:
> >On Sat, May 25, 2002 at 12:51:58AM -0400, Ross W. Wetmore wrote:
> >> To assemble a path vector, you step backwards from a target. 
> >...
> >
> >> Does this make sense? or help in any way?
> >
> >It looks like if we want a proper trieme support we have to start at
> >the destination and so exclude the possibility of the warmap
> >iterator?!
> 
> In general, you produce total move_cost as you iterate outwards in
> the warmap, and paths back by the reverse accumulation of the path
> vector once you have decided on the destination point. This is 
> standard for any move.

move_cost is indead a measure of the length of a path. However I still
think that time to reach destination is better one. The ai/ code also
is calculating this number out of the move_cost but this is only an
approximation.

The SMA will do something like this:
 generate_map
 
 while more positions available {
   time_for_goto=query_map_for_turn_to_reach(pos)
   for each action at the tile {
     actions.add(new Action(action, time_for_goto,...);
   }
 }

So the path is always needed. If we now somehow calculate the path
outwards it would be faster. But only for the non-trieme case.

> Building in trireme move constraints to warmap construction just 
> needs to be done with a trireme move_cost function that is more 
> sophisticated than the normal one. It needs to flag certain moves 
> as invalid and do more sophisticated backtracking to record delays
> at safe tiles before/after going through unsafe or invalid ones.
> 
> The warmap iterator part doesn't change, only the move_cost and
> any associated path collection elements.
> 
> This is one of the reasons why you want to have different move_cost
> functions rather than a single monolithic one. Trireme computations
> will be more expensive and even setup/checking will unnecessarily
> bog down cases that don't need it.
> 
> A "modular" move_cost function in which you push successive constraint
> handlers might be possible as a way of organizing only necessary
> elements efficiently, but this is probably tricky and still may not 
> allow critical coding efficiencies. If one starts with standardized
> template forms for various movecost functions, modules might fall out
> of the system as obvious collective refinements at some point.

The longer I think about this topic the more I think that I dislike
triemes. It looks like we either have to omit triemes or have to
penalize the general case.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "Microsoft DNS service terminates abnormally when it recieves a response
  to a DNS query that was never made.
  Fix Information: Run your DNS service on a different platform."
    -- MS service information on bugtraq