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

["Per I. Mathisen" <per@xxxxxxxxxxx>]

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

CHANGES:
 - Fixed the stuff Jason noticed (thanks)
 - Fixed bug that marked invaders as two turn under slow invasion rules
when they should be one turn
 - Made INSERT a static inline function instead (much prettier now)

I also left in some debug code in advmilitary.c for testing. Just set a
city to debug to see the new code in action.

  - Per

Index: ai/advmilitary.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/ai/advmilitary.c,v
retrieving revision 1.171
diff -u -r1.171 advmilitary.c
--- ai/advmilitary.c    29 Aug 2004 20:14:41 -0000      1.171
+++ ai/advmilitary.c    1 Sep 2004 12:00:01 -0000
@@ -420,6 +420,15 @@
   int igwall_threat = 0;
   struct tile *ptile = map_get_tile(pcity->x, pcity->y);
 
+if (pcity->debug) {
+  movemap_iterate_one_turn(pcity->x, pcity->y, punit) {
+    UNIT_LOG(LOG_NORMAL, punit, "can reach %s in one turn", pcity->name);
+  } movemap_iterate_one_turn_end;
+  movemap_iterate_two_turn(pcity->x, pcity->y, 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 */
Index: ai/aidata.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/ai/aidata.c,v
retrieving revision 1.36
diff -u -r1.36 aidata.c
--- ai/aidata.c 30 Aug 2004 21:20:33 -0000      1.36
+++ ai/aidata.c 1 Sep 2004 12:00:01 -0000
@@ -30,6 +30,9 @@
 #include "settlers.h"
 #include "unittools.h"
 
+#include "path_finding.h"
+#include "pf_tools.h"
+
 #include "advdiplomacy.h"
 #include "advmilitary.h"
 #include "aicity.h"
@@ -43,6 +46,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(x, y) {
+    movemap_list_init(&MOVEMAP(x, y).one_turn);
+    movemap_list_init(&MOVEMAP(x, y).two_turn);
+  } whole_map_iterate_end;
+}
+
+/**************************************************************************
+  Dealloc.
+**************************************************************************/
+void ai_data_movemap_done(void)
+{
+  /* Clean the slate */
+  whole_map_iterate(x, y) {
+    movemap_list_unlink_all(&MOVEMAP(x, y).one_turn);
+    movemap_list_unlink_all(&MOVEMAP(x, y).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(int x, int y, 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 = map_get_tile(ferry->x, ferry->y);
+
+    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_x = x; /* Suppose it landed right here... */
+      parameter.start_y = y;
+      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.x, pos.y).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.x, pos.y).one_turn, passenger);
+          } else {
+            movemap_insert(&MOVEMAP(pos.x, pos.y).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(x, y) {
+    movemap_list_unlink_all(&MOVEMAP(x, y).one_turn);
+    movemap_list_unlink_all(&MOVEMAP(x, y).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.x, pos.y).one_turn, &punit->id);
+        } else {
+          movemap_list_insert(&MOVEMAP(pos.x, pos.y).two_turn, &punit->id);
+        }
+      } pf_iterator_end;
+    } 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(x, y) {
+    if (is_ocean(map_get_terrain(x, y))) {
+      continue;
+    }
+    /* Check all ferries that can land on this spot in one turn horizon. */
+    movemap_list_iterate(MOVEMAP(x, y).one_turn, id) {
+      movemap_check_ferry(x, y, *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(x, y).two_turn, id) {
+        movemap_check_ferry(x, y, *id, 1);
+      } movemap_list_iterate_end;
+    }
+  } whole_map_iterate_end;
+}
+
 /**************************************************************************
   Make and cache lots of calculations needed for other functions.
 
Index: ai/aidata.h
===================================================================
RCS file: /home/freeciv/CVS/freeciv/ai/aidata.h,v
retrieving revision 1.15
diff -u -r1.15 aidata.h
--- ai/aidata.h 29 Aug 2004 19:43:37 -0000      1.15
+++ ai/aidata.h 1 Sep 2004 12:00:01 -0000
@@ -27,6 +27,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(map_x, map_y) movemap[map_pos_to_index(map_x, map_y)]
+
 enum winning_strategy {
   WIN_OPEN,     /* still undetermined */
   WIN_WAR,      /* we have no other choice than to crush all opposition */
@@ -136,5 +146,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(x, y, punit)             \
+  TYPED_LIST_ITERATE(int, MOVEMAP(x, y).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(x, y, punit)             \
+  TYPED_LIST_ITERATE(int, MOVEMAP(x, y).two_turn, miot) { \
+    struct unit *punit = find_unit_by_id(*miot);          \
+    if (punit) {
+#define movemap_iterate_two_turn_end                      \
+    }                                                     \
+  } LIST_ITERATE_END
+    
 #endif
Index: common/aicore/pf_tools.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/aicore/pf_tools.c,v
retrieving revision 1.20
diff -u -r1.20 pf_tools.c
--- common/aicore/pf_tools.c    25 Aug 2004 18:24:20 -0000      1.20
+++ common/aicore/pf_tools.c    1 Sep 2004 12:00:03 -0000
@@ -520,6 +520,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");
   }
Index: server/srv_main.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/server/srv_main.c,v
retrieving revision 1.184
diff -u -r1.184 srv_main.c
--- server/srv_main.c   29 Aug 2004 19:03:32 -0000      1.184
+++ server/srv_main.c   1 Sep 2004 12:00:04 -0000
@@ -482,6 +482,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);
@@ -1761,6 +1762,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) {
@@ -1798,6 +1800,9 @@
 
   /*** Where the action is. ***/
   main_loop();
+
+  /* Clean up some AI game data. */
+  ai_data_movemap_done();
 }
 
 /**************************************************************************