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

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

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

Here is the promised movemap structure. Despite the warnings in the code
and the rampant use of pf, I did't measure more than 5% slowdown for
autogames I tested. And that is when this is in addition to the old code
and replaces nothing.

It is accessed using two iterators, movemap_iterate_one_turn(x, y, punit)
and movemap_iterate_two_turn(x, y, punit). These gives you the units that
can reach us within one turn and two turns, respectively. However, the two
turn one does not also contain the one turn ones.

We honour the game.slow_invasions parameter, which is vital for
correctly evaluating ferry dangers.

It handles ferries, although this part of the code is not very elegant. I
tried to beat pf into submission, but gave up. As far as I could see,
there was no way to do it properly.

TODO: More checks to ensure that we don't add eg submarines as overlapping
sea units on land tiles.

Also, I two turn range is probably not enough. A third list might be
necessary, which does not look at ferries, but only pure land and sea
attackers, perhaps filtered to save CPU and get only relevant hits
(eg horsemen and ironclads).

  - Per

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 31 Aug 2004 23:19:21 -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,163 @@
 
 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(struct movemap_type), map.xsize * map.ysize);
+  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);
+}
+
+/**************************************************************************
+  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)
+#define INSERT(list, unit) {                              \
+  bool has_already = FALSE;                               \
+  movemap_list_iterate(list, check) {                     \
+    if (*check == unit->id) { has_already = TRUE; break; }\
+  } movemap_list_iterate_end;                             \
+  if (!has_already) {                                     \
+    movemap_list_insert(&list, &unit->id);                \
+  }                                                       \
+}
+{
+  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) {
+            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) {
+            INSERT(MOVEMAP(pos.x, pos.y).one_turn, passenger);
+          } else {
+            INSERT(MOVEMAP(pos.x, pos.y).two_turn, passenger);
+          }
+        }
+      } pf_iterator_end;
+    } unit_list_iterate_end;
+  }
+}
+#undef INSERT
+
+/**************************************************************************
+  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.  This probably consumes 
+  quite a lot of CPU.
+**************************************************************************/
+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);
+    } 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 31 Aug 2004 23:19:21 -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    31 Aug 2004 23:19:23 -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   31 Aug 2004 23:19:24 -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();
 }
 
 /**************************************************************************