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

["Gregory Berkolaiko" <Gregory.Berkolaiko@xxxxxxxxxxxx>]

On Tue, 10 Jun 2003, Raimar Falke wrote:

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

I agree that this approach will theoretically produce the right results.
Implementing it in practice...  well, good luck.

G.