[Freeciv-Dev] Re: (PR#6094) assert in path finding

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

On Tue, 16 Sep 2003, Jason Short wrote:

> [glip - Mon Sep 15 19:17:16 2003]:
> 
> > I still don't know what causes your unhappiness.  Can you point me to
> > the
> > places which you would like to see changed?  Alternatively, provide
> > your
> > own patch.
> 
> I do not know the PF code enough to make these changes.

Don't underestimate yourself ;)

> But what I am saying is that when "negative cost" happens, that's not
> because of bug in the calling code but a bug in the PF code.  The code
> that generates the nodes assumes that the unit's moves_left <=
> move_rate.  This is why we get negative costs, which must be accounted
> for via off-by-one correction, rather than getting the correct costs.
> 
> I think with the correct cost get_turn would look something like:
> 
>   if (cost < pf_map->moves_left_initially)
>     return 0;
>   else
>     return 1 + (cost - pf_map->moves_left_initially)
>                / pf_map->params->move_rate;

Which is exactly what is done now, only 
cost_jason = cost_gregory + moves_left_initially - move_rate

The correction remains constant, so it doesn't matter how the cost is 
stored.

I do not remember why I did it like this, but in my approach we have one 
subtraction less (or even two) per every call to get_turn.  

Perhaps a weightier reason is this:
When the PF is extended to handle multiple starting points, they will, in 
general, have different moves_left.  If we use my cost, the get_turn 
doesn't change.  If we use yours, we would need to tag each cost with the 
initial point from which it is calculated and the corresponding initial 
cost.  While this information is calculatable from the map, storing it in 
every node of the map too will lead to bigger memory footprint -> worse 
performance.

G.