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

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

On Fri, 6 Jun 2003, Raimar Falke wrote:

> On Tue, Jun 03, 2003 at 02:36:36PM -0700, ChrisK@xxxxxxxx wrote:
> > You didn't.
> > 
> > Ex.1 (settler)
> >   way 1: street - street - grassland
> >     33%: 1 move
> >     67%: 2 moves
> >   way 2: mountains - grassland
> >     100%: 2 moves
> >
> > --> should choose way 1, actually chooses way 2
> 
> See the attached savegame. With TB_BEST_TIME the way 2 is choosen.
> 
> > Ex.2 (diplomat)
> >   way 1: mountains - grassland - forest - grassland
> >     50%: 3 moves
> >     50%: 4 moves
> >   way 2: hills - forest - grassland - grassland
> >     100%: 3 moves
> > 
> > --> should choose way 2, actually chooses way 1 (tested with TB_BEST_TIME,
> >                                                  whatever that means)
> > 
> > The task of GOTO is: Get there as quick as possible.

I ratyher suspect that what Chris wants is not possible to implement.

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.

I haven't looked at it in much detail and I also feel that implementing it 
will put much more cruft into the PF.

> I have attached a smaller testcase. This shows a shortcoming of the
> current path-finding. With the attached patch (Greg we really have
> zero debug code in path_finding.c!!) I get this:
> 
> 2: current pos: (11,18) t=0,ml=6
> 2:   going NE to (12,17) costs 9, adjusted=6
> 2:   going SE to (12,19) costs 6, adjusted=6
> 2: current pos: (12,17) t=1,ml=6
> 2:   going SE to (13,18) costs 3, adjusted=3
> 2: current pos: (12,19) t=1,ml=6
> 2:   going NE to (13,18) costs 3, adjusted=3
> 
> So both are equal after the adjustment. This is bad.
> 
> Greg: do you have suggestions?
> 
>       Raimar
> 
>