[Freeciv-Dev] (PR#6283) New path-finding structure: punit->pf

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

This patch introduces punit->pf as the place where we keep pf maps stored
and cached, and a mechanism for updating pf maps when necessary. This
framework is built for preserving CPU speed, but does consume some
considerable memory with large games.

In order to preserve as much CPU as possible, we do not recalculate pf
maps when we do not have to. "Have to" is here defined as having moved or
lost movement points *and* we are at a new turn start or we want to
physically move somewhere. We do *not* recalculate the pf map just because
we have moved and want to look around. The pf map will be skewed but the
deviation is acceptable.

The big "but" with this patch is memory usage. We keep pf maps in memory
for all AI units at all times. For a very large game, this can easily
double the size of civserver, from 15mb to 30mb on my computer. I think
this is acceptable.

As a proof of concept, I have turned rampage and explorer to use this new
data. This means a lot of memory usage for very little usage, but look at
this at the beginning of a total pf'ification of the AI, and the impending
death of warmaps.

  - Per

Index: ai/aitools.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/ai/aitools.c,v
retrieving revision 1.89
diff -u -r1.89 aitools.c
--- ai/aitools.c        25 Sep 2003 17:51:33 -0000      1.89
+++ ai/aitools.c        25 Sep 2003 18:04:48 -0000
@@ -36,6 +36,8 @@
 #include "cityturn.h"
 #include "gotohand.h"
 #include "maphand.h"
+#include "path_finding.h"
+#include "pf_tools.h"
 #include "plrhand.h"
 #include "settlers.h"
 #include "unithand.h"
@@ -88,6 +90,35 @@
           || pplayer->diplstates[aplayer->player_no].has_reason_to_cancel
           || ai->diplomacy.acceptable_reputation > aplayer->reputation
           || adip->is_allied_with_enemy);
+}
+
+ /**************************************************************************
+  Ensure that our map is sane. If not, recreate. Call this always before 
+  you reuse a punit->pf pf_map for path-execution unless you *know* where 
+  it has been before and that punit has not moved. Note that all 
+  parameters in the map may be reset here.
+**************************************************************************/
+void update_unit_map(struct unit *punit)
+{
+  struct pf_parameter *param = NULL;
+
+  if (punit->pf) {
+    param = pf_get_parameter(punit->pf);
+  }
+
+  CHECK_UNIT(punit);
+  if (!param || param->start_x != punit->x || param->start_y != punit->y
+      || param->moves_left_initially != punit->moves_left) {
+    /* We have moved since we created this pf_map. So recreate it. */
+    struct pf_parameter new_param;
+
+    if (punit->pf) {
+      pf_destroy_map(punit->pf);
+    }
+    pft_fill_default_parameter(&new_param);
+    pft_fill_unit_parameter(&new_param, punit);
+    punit->pf = pf_create_map(&new_param);
+  }
 }
 
 /**************************************************************************
Index: ai/aitools.h
===================================================================
RCS file: /home/freeciv/CVS/freeciv/ai/aitools.h,v
retrieving revision 1.38
diff -u -r1.38 aitools.h
--- ai/aitools.h        5 May 2003 12:41:39 -0000       1.38
+++ ai/aitools.h        25 Sep 2003 18:04:48 -0000
@@ -41,6 +41,7 @@
                       int value, int delay, int build_cost);
 int stack_cost(struct unit *pdef);
 
+void update_unit_map(struct unit *punit);
 bool ai_unit_gothere(struct unit *punit);
 bool ai_unit_goto(struct unit *punit, int x, int y);
 void ai_unit_new_role(struct unit *punit, enum ai_unit_task task, int x, int 
y);
Index: ai/aiunit.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/ai/aiunit.c,v
retrieving revision 1.293
diff -u -r1.293 aiunit.c
--- ai/aiunit.c 25 Sep 2003 17:55:05 -0000      1.293
+++ ai/aiunit.c 25 Sep 2003 18:04:48 -0000
@@ -548,23 +548,21 @@
   int best_x = -1, best_y = -1;
 
   /* Path-finding stuff */
-  struct pf_map *map;
-  struct pf_parameter parameter;
+  struct pf_parameter *parameter;
 
 #define DIST_FACTOR   0.6
 
-  pft_fill_default_parameter(&parameter);
-  pft_fill_unit_parameter(&parameter, punit);
-  parameter.get_TB = no_fights_or_unknown;
+  update_unit_map(punit);
+  parameter = pf_get_parameter(punit->pf);
+  parameter->get_TB = no_fights_or_unknown;
   /* When exploring, even AI should pretend to not cheat. */
-  parameter.omniscience = FALSE;
+  parameter->omniscience = FALSE;
 
-  map = pf_create_map(&parameter);
-  while (pf_next(map)) {
+  while (pf_next(punit->pf)) {
     float desirable;
     struct pf_position pos;
 
-    pf_next_get_position(map, &pos);
+    pf_next_get_position(punit->pf, &pos);
     
     /* Our callback should insure this. */
     assert(map_is_known(pos.x, pos.y, pplayer));
@@ -594,7 +592,6 @@
       break;
     }
   }
-  pf_destroy_map(map);
 
   /* Go to the best tile found. */
   if (most_desirable > 0) {
@@ -1007,26 +1004,21 @@
 static struct pf_path *find_rampage_target(struct unit *punit, 
                                            int thresh_adj, int thresh_move)
 {
-  struct pf_map *tgt_map;
   struct pf_path *path = NULL;
-  struct pf_parameter parameter;
   /* Coordinates of the best target (initialize to silence compiler) */
   int x = punit->x, y = punit->y;
   /* Want of the best target */
   int max_want = 0;
   struct player *pplayer = unit_owner(punit);
- 
-  pft_fill_default_parameter(&parameter);  
-  pft_fill_unit_attack_param(&parameter, punit);
-  
-  tgt_map = pf_create_map(&parameter);
-  while (pf_next(tgt_map)) {
+
+  update_unit_map(punit);
+  while (pf_next(punit->pf)) {
     struct pf_position pos;
     int want;
     bool move_needed;
     int thresh;
  
-    pf_next_get_position(tgt_map, &pos);
+    pf_next_get_position(punit->pf, &pos);
     
     if (pos.total_MC > punit->moves_left) {
       /* This is too far */
@@ -1059,12 +1051,10 @@
 
   if (max_want > 0) {
     /* We found something */
-    path = pf_get_path(tgt_map, x, y);
+    path = pf_get_path(punit->pf, x, y);
     assert(path);
   }
 
-  pf_destroy_map(tgt_map);
-  
   return path;
 }
 
@@ -2837,6 +2827,15 @@
 **************************************************************************/
 void ai_manage_units(struct player *pplayer) 
 {
+  unit_list_iterate(pplayer->units, punit) {
+    if (is_ground_unit(punit) || is_sailing_unit(punit)) {
+      /* Allocate a pf_map to the unit here, so that we can avoid
+       * doing it twice over and also can look at the pf maps of
+       * other units without worrying about them not existing. 
+       * This might consume some memory, but really saves CPU time. */
+      update_unit_map(punit);
+    }
+  } unit_list_iterate_end;
   ai_airlift(pplayer);
   unit_list_iterate_safe(pplayer->units, punit) {
     ai_manage_unit(pplayer, punit);
Index: common/unit.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/unit.c,v
retrieving revision 1.183
diff -u -r1.183 unit.c
--- common/unit.c       22 Sep 2003 16:54:09 -0000      1.183
+++ common/unit.c       25 Sep 2003 18:04:49 -0000
@@ -1477,6 +1477,7 @@
   punit->bribe_cost = -1; /* flag value */
   punit->transported_by = -1;
   punit->pgr = NULL;
+  punit->pf = NULL;
   punit->focus_status = FOCUS_AVAIL;
   punit->ord_map = 0;
   punit->ord_city = 0;
@@ -1495,7 +1496,9 @@
   if (punit->pgr) {
     free(punit->pgr->pos);
     free(punit->pgr);
-    punit->pgr = NULL;
+  }
+  if (punit->pf) {
+    free(punit->pf);
   }
   free(punit);
 }
Index: common/unit.h
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/unit.h,v
retrieving revision 1.100
diff -u -r1.100 unit.h
--- common/unit.h       22 Sep 2003 16:54:09 -0000      1.100
+++ common/unit.h       25 Sep 2003 18:04:49 -0000
@@ -139,6 +139,7 @@
   int transported_by;
   int occupy; /* number of units that occupy transporter */
   struct goto_route *pgr;
+  struct pf_map *pf; /* path-finding map */
 };
 
 /* Wrappers for accessing the goto destination of a unit.  This goto_dest