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

["Benedict Adamson" <badamson@xxxxxxxxxxx>]

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

I wrote:
...
> The movemap structure seems to mishandle deleted units.
...
> The list[s] actually 
> holds pointers to the unit IDs (&punit->id), which is no safer than 
> holding the pointers to the units themselves (punit).
...

Subsequent investigation confirmed my suspicion. Attached is a corrected 
version of Per's movemap patch. This version uses a genlist rather than 
a speclist. This should be applicable to the CVS development version of 
2004-12-18. However, I had to extract the patch from my own, greatly 
modified version of the code, so it 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-12-12 01:35:05.000000000 
+0000
+++ freeciv.PR9610-2/ai/advmilitary.c   2004-12-19 17:26:13.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-12-18 11:48:35.000000000 +0000
+++ freeciv.PR9610-2/ai/aidata.c        2004-12-19 17:26:13.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"
@@ -45,6 +48,166 @@
 static struct ai_data aidata[MAX_NUM_PLAYERS + MAX_NUM_BARBARIANS];
 
 /**************************************************************************
+  Fill movemap with data.  This consumes a lot of CPU.
+**************************************************************************/
+void ai_data_movemap_init(void)
+{
+  movemap = fc_calloc(sizeof(*movemap), MAP_INDEX_SIZE);
+  whole_map_iterate(ptile) {
+    genlist_init(&MOVEMAP(ptile).one_turn);
+    genlist_init(&MOVEMAP(ptile).two_turn);
+  } whole_map_iterate_end;
+}
+
+/**************************************************************************
+  Dealloc.
+**************************************************************************/
+void ai_data_movemap_done(void)
+{
+  /* Clean the slate */
+  whole_map_iterate(ptile) {
+    genlist_unlink_all(&MOVEMAP(ptile).one_turn);
+    genlist_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(movemap_list_type *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) {
+    genlist_insert(list, (void *)punit->id, 0);
+  }
+}
+/**************************************************************************
+  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;
+      pf_destroy_map(pfmap);
+    } 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) {
+    genlist_unlink_all(&MOVEMAP(ptile).one_turn);
+    genlist_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) {
+          genlist_insert(&MOVEMAP(pos.tile).one_turn, (void *)punit->id, 0);
+        } else {
+          genlist_insert(&MOVEMAP(pos.tile).two_turn, (void *)punit->id, 0);
+        }
+      } 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'
   if we want to run a full test on them, as 'estimate' if we just want
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-12-18 11:48:35.000000000 +0000
+++ freeciv.PR9610-2/ai/aidata.h        2004-12-19 17:26:13.000000000 +0000
@@ -16,6 +16,7 @@
 /* max size of a short */
 #define MAX_NUM_ID 32767
 
+#include "genlist.h"
 #include "shared.h"            /* bool type */
 
 #include "fc_types.h"
@@ -26,6 +27,14 @@
  * start of every turn. 
  */
 
+typedef struct genlist movemap_list_type;
+
+struct movemap_type {
+  movemap_list_type one_turn;
+  movemap_list_type 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 +158,35 @@
 
 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_list_iterate(movelist, num)             \
+  {       \
+  struct genlist_link *myiter = movelist.head_link;\
+  void *var;                                              \
+  for(; ITERATOR_PTR(myiter);) {                           \
+    var=ITERATOR_PTR(myiter);                     \
+    ITERATOR_NEXT(myiter); \
+    int num = (int)var;
+#define movemap_list_iterate_end                      \
+  } }
+
+#define movemap_iterate_one_turn(ptile, punit)             \
+  movemap_list_iterate(MOVEMAP(ptile).one_turn, miot) {       \
+    struct unit *punit = find_unit_by_id(miot);          \
+    if (punit) {
+#define movemap_iterate_one_turn_end                      \
+    }                                                     \
+  } movemap_list_iterate_end
+
+#define movemap_iterate_two_turn(ptile, punit)             \
+  movemap_list_iterate(MOVEMAP(ptile).two_turn, miot) {       \
+    struct unit *punit = find_unit_by_id(miot);          \
+    if (punit) {
+#define movemap_iterate_two_turn_end                      \
+    }                                                     \
+  } movemap_list_iterate_end
+    
 #endif
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-12-19 17:26:12.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");
   }
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-12-18 11:48:32.000000000 
+0000
+++ freeciv.PR9610-2/server/srv_main.c  2004-12-19 17:25:44.000000000 +0000
@@ -514,6 +514,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);
@@ -1854,6 +1855,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) {
@@ -1890,6 +1892,9 @@
 
   /*** Where the action is. ***/
   main_loop();
+
+  /* Clean up some AI game data. */
+  ai_data_movemap_done();
 }
 
 /**************************************************************************