[Freeciv-Dev] Re: (PR#4326) Pathfinding

["Raimar Falke" <rf13@xxxxxxxxxxxxxxxxx>]

On Mon, Jun 09, 2003 at 04:37:00AM -0700, Gregory Berkolaiko wrote:
> 
> On Sun, 8 Jun 2003, Raimar Falke wrote:
> 
> > > But it seems it could be approximated by 
> > > (a) using TM_BEST_TIME normally
> > > (b) using the time from TM_WORST_TIME for tie-breaking.
> > 
> > This seems like a good solution.
> 
> But still not what Christian wants.  For example,

Yes I know.

> Unfortunately, I really don't see a way of computing the real average time 
> in PF.

To clarify this: it is easy to calculate the weighted cost of a single
step if you have a "concrete" state (turn and moves left are
integers). However after the first step such you don't have this. You
have something like (turn=0,moves_left=1.47). So it is hard/imopssible
to calculate the weighted cost of the next step.

Multiple steps form a tree:

 1. step costs:
    4 move points in 40% of the cases
       2. step costs:
         4 move points in 100% of the cases
           3. step ....
             .....
    5 move points in 60% of the cases
       2. step costs:
         3 move points in 1/3 of the cases
           3. step ....
             .....
         4 move points in 2/3 of the cases
           3. step ....
             .....

This looks complex but it isn't. Because you can merge/condense after
each step:

costs after step 1:
  4 in 40%
  5 in 60%
which is a weighted cost of 4.6

costs after step 2:
  4+4 in 40%*100% == 8 in 40%
  5+3 in 60%*1/3  == 8 in 20%
  5+4 in 60%*2/3  == 9 in 40%
this is:
  8 in 60%
  9 in 40%
which is a weighted cost of 8.4

So we would keep track of the cost outcome of each step with a list of
(cost, probability) tuples. The weighted cost will be the total_mc and
so be used for the Dijkstra sorting of the queue.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "Python 2.0 beta 1 is now available [...]. There is a long list of new 
  features since Python 1.6, released earlier today. We don't plan on 
  any new releases in the next 24 hours."
    -- Jeremy Hylton at Slashdot