[freeciv-ai] Re: (PR#9610) AI movemap

["Benedict Adamson" <badamson@xxxxxxxxxxx>]

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

valgrind found a severe memory leak in the movemap code, a missing 
pf_destroy_map call.

Here is a fixed and updated version of the movemap patch. The original 
was named
movemap2.diff, posted by Per on 2004-09-01. This version is applicable
to the CVS development version of 2004-11-25.

Unfortunately, I found this bug while working on some new AI bodyguard 
code, and back ported the correction, so the patch as-such is untested.

diff -ru -Xvendor.freeciv.current/diff_ignore 
vendor.freeciv.current/ai/advmilitary.c freeciv.PR9610-2/ai/advmilitary.c
--- vendor.freeciv.current/ai/advmilitary.c     2004-11-26 00:05:04.000000000 
+0000
+++ freeciv.PR9610-2/ai/advmilitary.c   2004-11-26 00:09:20.000000000 +0000
@@ -449,6 +449,15 @@
   int igwall_threat = 0;
   struct tile *ptile = pcity->tile;
 
+if (pcity->debug) {
+  movemap_iterate_one_turn(pcity->tile, punit) {
+    UNIT_LOG(LOG_NORMAL, punit, "can reach %s in one turn", pcity->name);
+  } movemap_iterate_one_turn_end;
+  movemap_iterate_two_turn(pcity->tile, punit) {
+    UNIT_LOG(LOG_NORMAL, punit, "can reach %s in two turns", pcity->name);
+  } movemap_iterate_two_turn_end;
+}
+
   memset(&danger, 0, sizeof(danger));
 
   generate_warmap(pcity, NULL);        /* generates both land and sea maps */
diff -ru -Xvendor.freeciv.current/diff_ignore 
vendor.freeciv.current/ai/aidata.c freeciv.PR9610-2/ai/aidata.c
--- vendor.freeciv.current/ai/aidata.c  2004-10-26 21:24:46.000000000 +0100
+++ freeciv.PR9610-2/ai/aidata.c        2004-11-26 00:01:02.000000000 +0000
@@ -31,6 +31,9 @@
 #include "settlers.h"
 #include "unittools.h"
 
+#include "path_finding.h"
+#include "pf_tools.h"
+
 #include "advdiplomacy.h"
 #include "advmilitary.h"
 #include "aicity.h"
@@ -44,6 +47,169 @@
 
 static struct ai_data aidata[MAX_NUM_PLAYERS + MAX_NUM_BARBARIANS];
 
+#define movemap_list_iterate(movelist, num) \
+  TYPED_LIST_ITERATE(int, movelist, num)
+#define movemap_list_iterate_end  LIST_ITERATE_END
+
+/**************************************************************************
+  Fill movemap with data.  This consumes a lot of CPU.
+**************************************************************************/
+void ai_data_movemap_init(void)
+{
+  movemap = fc_calloc(sizeof(*movemap), MAX_MAP_INDEX);
+  whole_map_iterate(ptile) {
+    movemap_list_init(&MOVEMAP(ptile).one_turn);
+    movemap_list_init(&MOVEMAP(ptile).two_turn);
+  } whole_map_iterate_end;
+}
+
+/**************************************************************************
+  Dealloc.
+**************************************************************************/
+void ai_data_movemap_done(void)
+{
+  /* Clean the slate */
+  whole_map_iterate(ptile) {
+    movemap_list_unlink_all(&MOVEMAP(ptile).one_turn);
+    movemap_list_unlink_all(&MOVEMAP(ptile).two_turn);
+  } whole_map_iterate_end;
+
+  free(movemap);
+}
+
+/**************************************************************************
+  Insert unit into list unless it is already there. Expensive operation
+  but necessary.
+**************************************************************************/
+static inline void movemap_insert(struct movemap_list *list, struct unit 
*punit)
+{
+  bool has_already = FALSE;
+  movemap_list_iterate(*list, check) {
+    if (*check == punit->id) {
+      has_already = TRUE;
+      break;
+    }
+  } movemap_list_iterate_end;
+  if (!has_already) {
+    movemap_list_insert(list, &punit->id);
+  }
+}
+/**************************************************************************
+  Check where passengers onboard ferries can go.  turns is the number of
+  turns the passenger can walk on land in a two turn horizon, ie either 
+  one or two.
+
+  We have to check that we don't accidentially insert a unit into a list
+  where it already exists. This is cumbersome but I see no other way.
+**************************************************************************/
+static void movemap_check_ferry(struct tile *ptile1, int id, int turns)
+{
+  struct unit *ferry = find_unit_by_id(id);
+
+  if (get_transporter_occupancy(ferry) > 0
+      && is_sailing_unit(ferry)) {
+    struct tile *ptile = ferry->tile;
+
+    unit_list_iterate(ptile->units, passenger) {
+      struct pf_map *pfmap;
+      struct pf_parameter parameter;
+      int moverate = unit_move_rate(passenger);
+
+      if (!is_ground_unit(passenger)
+          || passenger->transported_by != ferry->id) {
+        continue;
+      }
+      pft_fill_unit_attack_param(&parameter, passenger);
+      parameter.start_tile = ptile1; /* Suppose it landed right here... */
+      pfmap = pf_create_map(&parameter);
+      pf_iterator(pfmap, pos) {
+        if (turns == 1) {
+          /* We lost one turn landing on the beach or driving the ferry. */
+          if (pos.total_MC > moverate) {
+            /* This is too far */
+            break;
+          } else if (pos.total_MC <= moverate) {
+            movemap_insert(&MOVEMAP(pos.tile).two_turn, passenger);
+          }
+        } else { /* turns == 2 */
+          if (pos.total_MC > moverate * 2) {
+            /* This is too far */
+            break;
+          } else if (pos.total_MC <= moverate) {
+            movemap_insert(&MOVEMAP(pos.tile).one_turn, passenger);
+          } else {
+            movemap_insert(&MOVEMAP(pos.tile).two_turn, passenger);
+          }
+        }
+      } pf_iterator_end;
+    } unit_list_iterate_end;
+  }
+}
+
+/**************************************************************************
+  The movemap structure is a quick way to find threats on the map.  Use
+  the iterators defined in the header file to iterate over units that
+  can reach a tile in one or two turns (as specified).  We correctly 
+  calculate in the possibility of travel by ferry.
+
+  This function fills the movemap with data.  It is rather CPU intensive.
+**************************************************************************/
+void ai_data_movemap_recalculate(void)
+{
+  /* Clean the slate */
+  whole_map_iterate(ptile) {
+    movemap_list_unlink_all(&MOVEMAP(ptile).one_turn);
+    movemap_list_unlink_all(&MOVEMAP(ptile).two_turn);
+  } whole_map_iterate_end;
+
+  players_iterate(pplayer) {
+    unit_list_iterate(pplayer->units, punit) {
+      struct pf_map *pfmap;
+      struct pf_parameter parameter;
+      int moverate = unit_move_rate(punit);
+
+      if (get_transporter_occupancy(punit) > 0
+          && is_sailing_unit(punit)) {
+        pft_fill_unit_overlap_param(&parameter, punit);
+      } else {
+        pft_fill_unit_attack_param(&parameter, punit);
+      }
+      pfmap = pf_create_map(&parameter);
+      pf_iterator(pfmap, pos) {
+        if (pos.total_MC > moverate * 2) {
+          /* This is too far */
+          break;
+        } else if (pos.total_MC <= moverate) {
+          movemap_list_insert(&MOVEMAP(pos.tile).one_turn, &punit->id);
+        } else {
+          movemap_list_insert(&MOVEMAP(pos.tile).two_turn, &punit->id);
+        }
+      } pf_iterator_end;
+      pf_destroy_map(pfmap);
+    } unit_list_iterate_end;
+  } players_iterate_end;
+
+  /* Now do ferries. This is ugly, but correct. I gave up on beating
+   * pf into submission. It is also probably very very slow. */
+  whole_map_iterate(ptile) {
+    if (is_ocean(map_get_terrain(ptile))) {
+      continue;
+    }
+    /* Check all ferries that can land on this spot in one turn horizon. */
+    movemap_list_iterate(MOVEMAP(ptile).one_turn, id) {
+      movemap_check_ferry(ptile, *id, 2 - game.slow_invasions);
+    } movemap_list_iterate_end;
+    /* If game.slow_invasions is set, we do not need to fear ferries two
+     * turns away, since any units they drop off cannot move until the
+     * third turn, and the third turn is none of our responsibility. */
+    if (!game.slow_invasions) {
+      movemap_list_iterate(MOVEMAP(ptile).two_turn, id) {
+        movemap_check_ferry(ptile, *id, 1);
+      } movemap_list_iterate_end;
+    }
+  } whole_map_iterate_end;
+}
+
 /**************************************************************************
   Precalculates some important data about the improvements in the game
   that we use later in ai/aicity.c.  We mark improvements as 'calculate'
diff -ru -Xvendor.freeciv.current/diff_ignore 
vendor.freeciv.current/ai/aidata.h freeciv.PR9610-2/ai/aidata.h
--- vendor.freeciv.current/ai/aidata.h  2004-10-26 21:24:46.000000000 +0100
+++ freeciv.PR9610-2/ai/aidata.h        2004-11-20 17:45:18.000000000 +0000
@@ -26,6 +26,16 @@
  * start of every turn. 
  */
 
+#define SPECLIST_TAG movemap
+#define SPECLIST_TYPE int
+#include "speclist.h"
+
+struct movemap_type {
+  struct movemap_list one_turn;
+  struct movemap_list two_turn;
+} *movemap;
+#define MOVEMAP(ptile) movemap[map_pos_to_index(ptile->x, ptile->y)]
+
 enum ai_improvement_status {
   AI_IMPR_CALCULATE, /* Calculate exactly its effect */
   AI_IMPR_ESTIMATE,  /* Estimate its effect using wild guesses */
@@ -149,4 +159,24 @@
 
 struct ai_data *ai_data_get(struct player *pplayer);
 
+void ai_data_movemap_recalculate(void);
+void ai_data_movemap_init(void);
+void ai_data_movemap_done(void);
+
+#define movemap_iterate_one_turn(ptile, punit)             \
+  TYPED_LIST_ITERATE(int, MOVEMAP(ptile).one_turn, miot) { \
+    struct unit *punit = find_unit_by_id(*miot);          \
+    if (punit) {
+#define movemap_iterate_one_turn_end                      \
+    }                                                     \
+  } LIST_ITERATE_END
+    
+#define movemap_iterate_two_turn(ptile, punit)             \
+  TYPED_LIST_ITERATE(int, MOVEMAP(ptile).two_turn, miot) { \
+    struct unit *punit = find_unit_by_id(*miot);          \
+    if (punit) {
+#define movemap_iterate_two_turn_end                      \
+    }                                                     \
+  } LIST_ITERATE_END
+    
 #endif
Only in freeciv.PR9610-2/client: freeciv.desktop
diff -ru -Xvendor.freeciv.current/diff_ignore 
vendor.freeciv.current/common/aicore/pf_tools.c 
freeciv.PR9610-2/common/aicore/pf_tools.c
--- vendor.freeciv.current/common/aicore/pf_tools.c     2004-10-22 
23:16:36.000000000 +0100
+++ freeciv.PR9610-2/common/aicore/pf_tools.c   2004-11-20 17:45:18.000000000 
+0000
@@ -515,6 +515,10 @@
   case SEA_MOVING:
     parameter->get_MC = sea_attack_move;
     break;
+  case AIR_MOVING:
+  case HELI_MOVING:
+    parameter->get_MC = single_airmove; /* very crude */
+    break;    
   default:
     die("Unsupported move_type");
   }
Only in freeciv.PR9610-2/data: Freeciv
Only in freeciv.PR9610-2: freeciv.spec
diff -ru -Xvendor.freeciv.current/diff_ignore 
vendor.freeciv.current/server/srv_main.c freeciv.PR9610-2/server/srv_main.c
--- vendor.freeciv.current/server/srv_main.c    2004-11-26 00:05:00.000000000 
+0000
+++ freeciv.PR9610-2/server/srv_main.c  2004-11-26 00:09:17.000000000 +0000
@@ -518,6 +518,7 @@
 
   conn_list_do_buffer(&game.game_connections);
 
+  ai_data_movemap_recalculate();
   players_iterate(pplayer) {
     freelog(LOG_DEBUG, "beginning player turn for #%d (%s)",
            pplayer->player_no, pplayer->name);
@@ -1857,6 +1858,7 @@
 
   initialize_move_costs(); /* this may be the wrong place to do this */
   init_settlers(); /* create minimap and other settlers.c data */
+  ai_data_movemap_init();
 
   if (!game.is_new_game) {
     players_iterate(pplayer) {
@@ -1893,6 +1895,9 @@
 
   /*** Where the action is. ***/
   main_loop();
+
+  /* Clean up some AI game data. */
+  ai_data_movemap_done();
 }
 
 /**************************************************************************