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

["Raimar Falke" <rf13@xxxxxxxxxxxxxxxxx>]

On Tue, Jun 03, 2003 at 02:36:36PM -0700, ChrisK@xxxxxxxx wrote:
> On Tue, Jun 03, 2003 at 02:02:12PM -0700, Raimar Falke wrote:
> > On Fri, May 30, 2003 at 01:50:54PM -0700, ChrisK@xxxxxxxx wrote:
> > > On Fri, May 30, 2003 at 08:08:14AM -0700, Gregory Berkolaiko wrote:
> > > > 
> > > > client/goto.c:348
> > > > 
> > > > Please experiment with different values for the turn_mode
> > > > (TM_NONE, TM_CAPPED, TM_BEST_TIME, TM_WORST_TIME) and tell us which you 
> > > > like the most.
> > > 
> > > Urghs. I don't understand the diploma thesis in path_finding.h
> > > 
> > > What I *want* is that the chance of reaching tile n+1 from tile n is
> > > weighted with its statistical rate, in computing the move cost.
> > 
> > Let's see if I understood you.
> 
> 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 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

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
  What's nice about GUI is that you see what you manipulate.
  What's bad about GUI is that you can only manipulate what you see.

goto_test2.gz
Description: goto_test2.gz

goto_test4.gz
Description: goto_test4.gz

Index: client/goto.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/client/goto.c,v
retrieving revision 1.52
diff -u -u -r1.52 goto.c
--- client/goto.c       2003/06/02 22:07:18     1.52
+++ client/goto.c       2003/06/06 16:32:43
@@ -354,7 +354,7 @@
   goto_map.template.get_EC = get_EC;
   assert(goto_map.template.get_TB == NULL);
   goto_map.template.get_TB = get_TB;
-  goto_map.template.turn_mode = TM_WORST_TIME;
+  goto_map.template.turn_mode = TM_BEST_TIME;
 
   add_part();
   is_active = TRUE;
Index: common/aicore/path_finding.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/aicore/path_finding.c,v
retrieving revision 1.9
diff -u -u -r1.9 path_finding.c
--- common/aicore/path_finding.c        2003/05/03 13:28:48     1.9
+++ common/aicore/path_finding.c        2003/06/06 16:32:44
@@ -257,6 +257,10 @@
     /* Processing Stage */
     /* The previous position is contained in {x,y} fields of map */
 
+    freelog(LOG_NORMAL, "current pos: (%d,%d) t=%d,ml=%d",
+           pf_map->x, pf_map->y, get_turn(pf_map, node->cost),
+           get_moves_left(pf_map, node->cost));
+
     adjc_dir_iterate(pf_map->x, pf_map->y, x1, y1, dir) {
       mapindex_t index1 = map_pos_to_index(x1, y1);
       struct pf_node *node1 = &pf_map->lattice[index1];
@@ -293,6 +297,10 @@
        if (cost == PF_IMPOSSIBLE_MC) {
          continue;
        }
+
+       freelog(LOG_NORMAL, "  going %s to (%d,%d) costs %d, adjusted=%d",
+               dir_get_name(dir), x1, y1, cost,adjust_cost(pf_map, cost));
+
        cost = adjust_cost(pf_map, cost);
       }