[Freeciv-Dev] (PR#10702) RFC: removing ptile->move_cost

["Jason Short" <jdorje@xxxxxxxxxxxxxxxxxxxxx>]

<URL: http://rt.freeciv.org/Ticket/Display.html?id=10702 >

In the tile structure, there is a move_cost array.  This stores the AI 
cost of moving in each direction.  (The AI cost differs from the 
"actual" cost via some complicated logic I don't really understand.  But 
that's not the point here.)

   signed char move_cost[8]; /* don't know if this helps! */

These values are updated in reset_move_costs.  Keeping them field 
updated is a major pain - we have to remember to do it at some pretty 
inconvenient times.  Comments in the code indicate there have been bugs 
here in the past.  There could be bugs here now for all I know (I 
recently found a possible one in the mapgen code).

So I wondered if it actually does help.  I removed it and replaced all 
its users with calls to tile_move_cost_ai (the underlying function to 
calculate the cost).  Doing this makes my autogame run a surprisingly 
consistent 0.4% slower:

   real    1m24.223s
   real    1m24.514s

in fact if I make tile_move_cost_ai inline then the new code is actually 
faster.  This prompts the question: why?  The most likely reason is that 
since the tile struct is (slightly) smaller, the map is more compact and 
more of it will fit into the CPU memory cache at a time.  However this 
probably varies from system to system, and it would be helpful to 
profile performance on different computers.

Given the complexity of the current system I would really like to remove 
this cache.

jason

? new
? old
? techtree-3.0
? techtree-3.0-examples
Index: ai/aiferry.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/ai/aiferry.c,v
retrieving revision 1.8
diff -u -r1.8 aiferry.c
--- ai/aiferry.c        21 Oct 2004 15:55:45 -0000      1.8
+++ ai/aiferry.c        24 Oct 2004 05:26:12 -0000
@@ -241,7 +241,7 @@
     move_cost = PF_IMPOSSIBLE_MC;
   } else {
     /* Land-to-Land */
-    move_cost = src_tile->move_cost[dir];
+    move_cost = tile_move_cost_ai(src_tile, tgt_tile);
   }
 
   return move_cost;
Index: client/goto.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/client/goto.c,v
retrieving revision 1.77
diff -u -r1.77 goto.c
--- client/goto.c       18 Oct 2004 22:40:02 -0000      1.77
+++ client/goto.c       24 Oct 2004 05:26:13 -0000
@@ -102,7 +102,6 @@
       DRAWN(ptile, dir) = 0;
     }
   } whole_map_iterate_end;
-  initialize_move_costs();
 
   is_init = TRUE;
 }
Index: client/packhand.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/client/packhand.c,v
retrieving revision 1.412
diff -u -r1.412 packhand.c
--- client/packhand.c   23 Oct 2004 20:02:51 -0000      1.412
+++ client/packhand.c   24 Oct 2004 05:26:14 -0000
@@ -218,7 +218,6 @@
 
   ptile = pcity->tile;
   client_remove_city(pcity);
-  reset_move_costs(ptile);
 
   /* update menus if the focus unit is on the tile. */
   if (get_unit_in_focus()) {
@@ -633,8 +632,6 @@
            get_nation_name(city_owner(pcity)->nation),
            pcity->name, pcity->id, TILE_XY(pcity->tile));
   }
-
-  reset_move_costs(pcity->tile);
 }
 
 /**************************************************************************
@@ -1947,8 +1944,6 @@
     }
   }
 
-  reset_move_costs(ptile);
-
   if (ptile->known <= TILE_KNOWN_FOGGED && old_known == TILE_KNOWN) {
     /* This is an error.  So first we log the error, then make an assertion.
      * But for NDEBUG clients we fix the error. */
Index: client/gui-gtk-2.0/menu.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/client/gui-gtk-2.0/menu.c,v
retrieving revision 1.47
diff -u -r1.47 menu.c
--- client/gui-gtk-2.0/menu.c   23 Oct 2004 20:21:01 -0000      1.47
+++ client/gui-gtk-2.0/menu.c   24 Oct 2004 05:26:14 -0000
@@ -1135,7 +1135,6 @@
   /* Restore the original state of the tile. */
   ptile->terrain = old_terrain;
   ptile->special = old_special;
-  reset_move_costs(ptile);
 
   return text;
 }
Index: common/map.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/map.c,v
retrieving revision 1.202
diff -u -r1.202 map.c
--- common/map.c        18 Oct 2004 22:40:02 -0000      1.202
+++ common/map.c        24 Oct 2004 05:26:14 -0000
@@ -1003,7 +1003,6 @@
        * rivers in oceans, don't clear this! */
       map_clear_special(ptile, S_RIVER);
     }
-    reset_move_costs(ptile);
   }
   map_clear_special(ptile, S_MINE);
 }
@@ -1030,7 +1029,6 @@
        * rivers in oceans, don't clear this! */
       map_clear_special(ptile, S_RIVER);
     }
-    reset_move_costs(ptile);
   }
   map_clear_special(ptile, S_FARMLAND);
   map_clear_special(ptile, S_IRRIGATION);
@@ -1049,8 +1047,6 @@
                                           rivers in oceans, don't clear this! 
*/
   }
 
-  reset_move_costs(ptile);
-
   /* Clear mining/irrigation if resulting terrain type cannot support
      that feature.  (With current rules, this should only clear mines,
      but I'm including both cases in the most general form for possible
@@ -1174,9 +1170,10 @@
     - both tiles are ocean or
     - one of the tiles is ocean and the other is a city or is unknown
 ***************************************************************/
-static int tile_move_cost_ai(struct tile *tile0, struct tile *tile1,
-                            int maxcost)
+int tile_move_cost_ai(const struct tile *tile0, const struct tile *tile1)
 {
+  const int maxcost = 72; /* Arbitrary. */
+
   assert(!is_server
         || (tile0->terrain != T_UNKNOWN && tile1->terrain != T_UNKNOWN));
 
@@ -1202,65 +1199,6 @@
 }
 
 /***************************************************************
- ...
-***************************************************************/
-static void debug_log_move_costs(const char *str, struct tile *tile0)
-{
-  /* the %x don't work so well for oceans, where
-     move_cost[]==-3 ,.. --dwp
-  */
-  freelog(LOG_DEBUG, "%s (%d, %d) [%x%x%x%x%x%x%x%x]", str,
-         tile0->x, tile0->y,
-         tile0->move_cost[0], tile0->move_cost[1],
-         tile0->move_cost[2], tile0->move_cost[3],
-         tile0->move_cost[4], tile0->move_cost[5],
-         tile0->move_cost[6], tile0->move_cost[7]);
-}
-
-/***************************************************************
-  Recalculate tile->move_cost[] for (x,y), and for adjacent
-  tiles in direction back to (x,y).  That is, call this when
-  something has changed on (x,y), eg roads, city, transform, etc.
-***************************************************************/
-void reset_move_costs(struct tile *ptile)
-{
-  int maxcost = 72; /* should be big enough without being TOO big */
-
-  debug_log_move_costs("Resetting move costs for", ptile);
-
-  /* trying to move off the screen is the default */
-  memset(ptile->move_cost, maxcost, sizeof(ptile->move_cost));
-
-  adjc_dir_iterate(ptile, tile1, dir) {
-    ptile->move_cost[dir] = tile_move_cost_ai(ptile, tile1, maxcost);
-    /* reverse: not at all obfuscated now --dwp */
-    tile1->move_cost[DIR_REVERSE(dir)] =
-       tile_move_cost_ai(tile1, ptile, maxcost);
-  } adjc_dir_iterate_end;
-  debug_log_move_costs("Reset move costs for", ptile);
-}
-
-/***************************************************************
-  Initialize tile->move_cost[] for all tiles, where move_cost[i]
-  is the unit-independent cost to move _from_ that tile, to
-  adjacent tile in direction specified by i.
-***************************************************************/
-void initialize_move_costs(void)
-{
-  int maxcost = 72; /* should be big enough without being TOO big */
-
-  whole_map_iterate(ptile) {
-    /* trying to move off the screen is the default */
-    memset(ptile->move_cost, maxcost, sizeof(ptile->move_cost));
-
-    adjc_dir_iterate(ptile, tile1, dir) {
-      ptile->move_cost[dir] = tile_move_cost_ai(ptile, tile1, maxcost);
-    }
-    adjc_dir_iterate_end;
-  } whole_map_iterate_end;
-}
-
-/***************************************************************
   The cost to move punit from where it is to tile x,y.
   It is assumed the move is a valid one, e.g. the tiles are adjacent.
 ***************************************************************/
@@ -1360,10 +1298,6 @@
 void map_set_special(struct tile *ptile, enum tile_special_type spe)
 {
   ptile->special |= spe;
-
-  if (contains_special(spe, S_ROAD) || contains_special(spe, S_RAILROAD)) {
-    reset_move_costs(ptile);
-  }
 }
 
 /***************************************************************
@@ -1372,10 +1306,6 @@
 void map_clear_special(struct tile *ptile, enum tile_special_type spe)
 {
   ptile->special &= ~spe;
-
-  if (contains_special(spe, S_ROAD) || contains_special(spe, S_RAILROAD)) {
-    reset_move_costs(ptile);
-  }
 }
 
 /***************************************************************
Index: common/map.h
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/map.h,v
retrieving revision 1.223
diff -u -r1.223 map.h
--- common/map.h        18 Oct 2004 22:40:02 -0000      1.223
+++ common/map.h        24 Oct 2004 05:26:15 -0000
@@ -55,7 +55,6 @@
   int assigned; /* these can save a lot of CPU usage -- Syela */
   struct city *worked;      /* city working tile, or NULL if none */
   Continent_id continent;
-  signed char move_cost[8]; /* don't know if this helps! */
   struct player *owner;     /* Player owning this tile, or NULL. */
   struct {
     /* Area Selection in client. */
@@ -236,9 +235,6 @@
 void map_set_continent(struct tile *ptile, Continent_id val);
 Continent_id map_get_continent(const struct tile *ptile);
 
-void initialize_move_costs(void);
-void reset_move_costs(struct tile *ptile);
-
 /* Maximum value of index (for sanity checks and allocations) */
 #define MAX_MAP_INDEX (map.xsize * map.ysize)
 
@@ -402,6 +398,7 @@
 bool is_move_cardinal(const struct tile *src_tile,
                      const struct tile *dst_tile);
 int map_move_cost(struct unit *punit, const struct tile *ptile);
+int tile_move_cost_ai(const struct tile *tile0, const struct tile *tile1);
 enum tile_special_type get_special_by_name(const char * name);
 const char *get_special_name(enum tile_special_type type);
 bool is_safe_ocean(const struct tile *ptile);
Index: common/aicore/pf_tools.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/aicore/pf_tools.c,v
retrieving revision 1.24
diff -u -r1.24 pf_tools.c
--- common/aicore/pf_tools.c    20 Oct 2004 18:20:53 -0000      1.24
+++ common/aicore/pf_tools.c    24 Oct 2004 05:26:15 -0000
@@ -37,7 +37,7 @@
                    const struct tile *ptile1, struct pf_parameter *param)
 {
   /* MOVE_COST_FOR_VALID_SEA_STEP means ships can move between */
-  if (ptile->move_cost[dir] == MOVE_COST_FOR_VALID_SEA_STEP
+  if (tile_move_cost_ai(ptile, ptile1) == MOVE_COST_FOR_VALID_SEA_STEP
       || is_non_allied_unit_tile(ptile1, param->owner)
       || is_non_allied_city_tile(ptile1, param->owner)) {
     return SINGLE_MOVE;
@@ -65,7 +65,7 @@
                              struct pf_parameter *param)
 {
   /* MOVE_COST_FOR_VALID_SEA_STEP means ships can move between */
-  if (ptile->move_cost[dir] == MOVE_COST_FOR_VALID_SEA_STEP
+  if (tile_move_cost_ai(ptile, ptile1) == MOVE_COST_FOR_VALID_SEA_STEP
       && !is_non_allied_city_tile(ptile1, param->owner)) {
     return SINGLE_MOVE;
   } else {
@@ -140,7 +140,7 @@
       move_cost = get_tile_type(terrain1)->movement_cost * SINGLE_MOVE;
     }
   } else {
-    move_cost = ptile->move_cost[dir];
+    move_cost = tile_move_cost_ai(ptile, ptile1);
   }
 
   return move_cost;
@@ -189,7 +189,7 @@
       move_cost = SINGLE_MOVE;
     } else {
       /* Normal move */
-      move_cost = src_tile->move_cost[dir];
+      move_cost = tile_move_cost_ai(src_tile, tgt_tile);
     }
   }
 
@@ -225,7 +225,7 @@
   } else if (is_ocean(ptile->terrain)) {
     move_cost = get_tile_type(terrain1)->movement_cost * SINGLE_MOVE;
   } else {
-    move_cost = ptile->move_cost[dir];
+    move_cost = tile_move_cost_ai(ptile, ptile1);
   }
 
   return move_cost;
@@ -287,7 +287,8 @@
       move_cost = MOVE_COST_ROAD;
     }
   } else {
-    move_cost = (ptile->move_cost[dir] != 0 ? MOVE_COST_ROAD : 0);
+    move_cost = (tile_move_cost_ai(ptile, ptile1) != 0
+                ? MOVE_COST_ROAD : 0);
   }
   return move_cost;
 }
Index: server/citytools.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/server/citytools.c,v
retrieving revision 1.277
diff -u -r1.277 citytools.c
--- server/citytools.c  19 Oct 2004 06:46:57 -0000      1.277
+++ server/citytools.c  24 Oct 2004 05:26:16 -0000
@@ -837,7 +837,6 @@
                      kill_outside, transfer_unit_verbose);
   /* The units themselves are allready freed by transfer_city_units. */
   unit_list_unlink_all(&old_city_units);
-  reset_move_costs(pcity->tile);
 
   if (resolve_stack && !pplayers_allied(pgiver, ptaker)) {
     resolve_unit_stacks(pgiver, ptaker, transfer_unit_verbose);
@@ -1025,13 +1024,6 @@
   map_clear_special(ptile, S_FORTRESS);
   update_tile_knowledge(ptile);
 
-  reset_move_costs(ptile);
-/* I stupidly thought that setting S_ROAD took care of this, but of course
-the city_id isn't set when S_ROAD is set, so reset_move_costs doesn't allow
-sea movement at the point it's called.  This led to a problem with the
-warmap (but not the GOTOmap warmap) which meant the AI was very reluctant
-to use ferryboats.  I really should have identified this sooner. -- Syela */
-
   pcity->synced = FALSE;
   send_city_info(NULL, pcity);
   sync_cities(); /* Will also send pcity. */
@@ -1167,8 +1159,6 @@
 
   map_fog_pseudo_city_area(pplayer, ptile);
 
-  reset_move_costs(ptile);
-
   /* Update available tiles in adjacent cities. */
   map_city_radius_iterate(ptile, tile1) {
     /* For every tile the city could have used. */
Index: server/gotohand.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/server/gotohand.c,v
retrieving revision 1.186
diff -u -r1.186 gotohand.c
--- server/gotohand.c   29 Sep 2004 02:24:23 -0000      1.186
+++ server/gotohand.c   24 Oct 2004 05:26:16 -0000
@@ -314,15 +314,18 @@
          move_cost = igter ? MOVE_COST_ROAD : MIN(base_cost, 
unit_move_rate(punit));
         } else if (igter)
          /* NOT c = 1 (Syela) [why not? - Thue] */
-         move_cost = (ptile->move_cost[dir] != 0 ? SINGLE_MOVE : 0);
+         move_cost = (tile_move_cost_ai(ptile, tile1) != 0
+                      ? SINGLE_MOVE : 0);
         else if (punit)
-         move_cost = MIN(ptile->move_cost[dir], unit_move_rate(punit));
+         move_cost = MIN(tile_move_cost_ai(ptile, tile1),
+                         unit_move_rate(punit));
        /* else c = ptile->move_cost[k]; 
           This led to a bad bug where a unit in a swamp was considered too far 
away */
         else { /* we have a city */
-         int tmp = tile1->move_cost[DIR_REVERSE(dir)];
-          move_cost = (ptile->move_cost[dir] + tmp +
-                      (ptile->move_cost[dir] > tmp ? 1 : 0))/2;
+         int tmp = tile_move_cost_ai(tile1, ptile);
+         int tmp2 = tile_move_cost_ai(ptile, tile1);
+
+          move_cost = (tmp2 + tmp + (tmp2 > tmp ? 1 : 0)) / 2;
         }
 
         move_cost += cost;
@@ -341,7 +344,8 @@
             can move between we allow for shore bombardment/transport
             to inland positions/etc. */
           WARMAP_SEACOST(tile1) = move_cost;
-         if (ptile->move_cost[dir] == MOVE_COST_FOR_VALID_SEA_STEP) {
+         if (tile_move_cost_ai(ptile, tile1)
+             == MOVE_COST_FOR_VALID_SEA_STEP) {
            add_to_mapqueue(move_cost, tile1);
          }
        }
@@ -646,9 +650,11 @@
          int base_cost = get_tile_type(pdesttile->terrain)->movement_cost * 
SINGLE_MOVE;
          move_cost = igter ? 1 : MIN(base_cost, unit_move_rate(punit));
        } else if (igter)
-         move_cost = (psrctile->move_cost[dir] != 0 ? SINGLE_MOVE : 0);
+         move_cost = (tile_move_cost_ai(psrctile, pdesttile) != 0
+                      ? SINGLE_MOVE : 0);
        else
-         move_cost = MIN(psrctile->move_cost[dir], unit_move_rate(punit));
+         move_cost = MIN(tile_move_cost_ai(psrctile, pdesttile),
+                         unit_move_rate(punit));
 
        if (!pplayer->ai.control && !map_is_known(tile1, pplayer)) {
          /* Don't go into the unknown. 5*SINGLE_MOVE is an arbitrary 
deterrent. */
@@ -708,7 +714,8 @@
          continue; /* No need for all the calculations */
 
        /* allow ships to target a shore */
-       if (psrctile->move_cost[dir] != MOVE_COST_FOR_VALID_SEA_STEP
+       if (tile_move_cost_ai(psrctile, pdesttile)
+           != MOVE_COST_FOR_VALID_SEA_STEP
            && !same_pos(tile1, dest_tile)) {
          continue;
        } else if (unit_loss_pct(unit_owner(punit), tile1, punit) > 0) {
@@ -981,7 +988,7 @@
     if (is_ground_unit(punit)) {
       /* assuming move is valid, but what if unit is trying to board? 
         -- GB */
-      base_move_cost = punit->tile->move_cost[dir];
+      base_move_cost = tile_move_cost_ai(punit->tile, ptile);
     } else {
       base_move_cost = SINGLE_MOVE;
     }
Index: server/srv_main.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/server/srv_main.c,v
retrieving revision 1.204
diff -u -r1.204 srv_main.c
--- server/srv_main.c   18 Oct 2004 23:49:27 -0000      1.204
+++ server/srv_main.c   24 Oct 2004 05:26:16 -0000
@@ -1841,7 +1841,6 @@
    } players_iterate_end;
   }
 
-  initialize_move_costs(); /* this may be the wrong place to do this */
   init_settlers(); /* create minimap and other settlers.c data */
 
   if (!game.is_new_game) {