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

On 1/17/07, Marko Lindqvist <[EMAIL PROTECTED]> wrote:
>  This patch removes segment_length and step completely. When segment
> or path length is needed, it's determined by extra iteration. I'm
> afraid this is unavoidable performance hit. This version of the patch
> is for S2_0 since problem was easist to reproduce there.

 - Variable length in danger_construct_path() now truly is *length*
and not length - 1.


 - ML

diff -Nurd -X.diff_ignore freeciv/common/aicore/path_finding.c freeciv/common/aicore/path_finding.c
--- freeciv/common/aicore/path_finding.c	2006-07-17 23:56:45.000000000 +0300
+++ freeciv/common/aicore/path_finding.c	2007-01-17 22:18:21.000000000 +0200
@@ -68,9 +68,6 @@
 struct danger_node {
   bool is_dangerous;
   bool waited;			/* TRUE if waited to get here */
-  int step;                     /* # of steps we took to get here */
-  int segment_length;           /* only used for dangerous tiles, the length 
-                                 * of the current dangerous streak */
   struct pf_danger_pos {
     enum direction8 dir;
     int cost;
@@ -503,8 +500,6 @@
   if (pf_map->params->is_pos_dangerous) {
     /* The starting point is safe */
     pf_map->d_lattice[pf_map->tile->index].is_dangerous = FALSE;
-    /* Initialize step counter */
-    pf_map->d_lattice[pf_map->tile->index].step = 0;
   }
 
   return pf_map;
@@ -823,19 +818,35 @@
 /***********************************************************************
   Creating path segment going back from d_node1 to a safe tile.
 ***********************************************************************/
-static void create_danger_segment(struct pf_map *pf_map, enum direction8 dir,
-                                  struct danger_node *d_node1, int length)
+static void create_danger_segment(struct pf_map *pf_map,
+                                  struct danger_node *d_node1)
 {
   int i;
   struct tile *ptile = pf_map->tile;
   struct pf_node *node = &pf_map->lattice[ptile->index];
+  struct danger_node *d_node = &pf_map->d_lattice[ptile->index];
+  int length = 0;
 
   /* Allocating memory */
   if (d_node1->danger_segment) {
     freelog(LOG_ERROR, "Possible memory leak in create_danger_segment");
   }
+
+  /* First iteration for determining segment length */
+  while(d_node->is_dangerous) {
+    length++;
+    ptile = mapstep(ptile, DIR_REVERSE(node->dir_to_here));
+    node = &pf_map->lattice[ptile->index];
+    d_node = &pf_map->d_lattice[ptile->index];
+  }
+
+  /* Allocate memory for segment */
   d_node1->danger_segment = fc_malloc(length * sizeof(struct pf_danger_pos));
 
+  /* Reset tile and node pointers for main iteration */
+  ptile = pf_map->tile;
+  node = &pf_map->lattice[ptile->index];
+
   /* Now fill the positions */
   for (i = 0; i < length; i++) {
     /* Record the direction */
@@ -928,11 +939,6 @@
     int loc_cost
 	= (pf_map->status[pf_map->tile->index] != NS_WAITING ? node->cost
 	   : node->cost + get_moves_left(pf_map, node->cost));
-    /* Step number at xy taking into account waiting 
-     * (waiting counts as one step) */
-    int loc_step
-        = (pf_map->status[pf_map->tile->index] != NS_WAITING ? d_node->step
-           : d_node->step + 1);
 
     /* The previous position is contained in {x,y} fields of map */
     adjc_dir_iterate(pf_map->tile, tile1, dir) {
@@ -1002,7 +1008,6 @@
 	  node1->extra_cost = extra;
 	  node1->cost = cost;
 	  node1->dir_to_here = dir;
-          d_node1->step = loc_step + 1;
           /* Clear the previously recorded path back */
           if (d_node1->danger_segment) {
             free(d_node1->danger_segment);
@@ -1010,15 +1015,11 @@
           }
 	  if (d_node->is_dangerous) {
 	    /* Transition from red to blue, need to record the path back */
-	    create_danger_segment(pf_map, dir, d_node1, 
-                                  d_node->segment_length);
+	    create_danger_segment(pf_map, d_node1);
 	  } else {
             /* We don't consider waiting to get to a safe tile as 
              * "real" waiting */
 	    d_node1->waited = FALSE;
-            if (pf_map->status[pf_map->tile->index] == NS_WAITING) {
-              d_node1->step--;
-            }
 	  }
 	  pf_map->status[index1] = NS_NEW;
 	  pq_insert(pf_map->queue, index1, -cost_of_path);
@@ -1039,14 +1040,6 @@
 	  node1->extra_cost = extra;
 	  node1->cost = cost;
 	  node1->dir_to_here = dir;
-          d_node1->step = loc_step + 1;
-          if (d_node->is_dangerous) {
-            /* Increment the number of steps we are making across danger */
-            d_node1->segment_length = d_node->segment_length + 1;
-          } else {
-            /* We just moved into the danger area */
-            d_node1->segment_length = 1;
-          }
 	  pf_map->status[index1] = NS_NEW;
 	  d_node1->waited = (pf_map->status[pf_map->tile->index]
 			     == NS_WAITING);
@@ -1119,6 +1112,8 @@
   bool waited = FALSE;
   struct pf_node *node = &pf_map->lattice[ptile->index];
   struct danger_node *d_node = &pf_map->d_lattice[ptile->index];
+  int length = 1;
+  struct tile *iter_tile = ptile;
 
   if (pf_map->params->turn_mode != TM_BEST_TIME &&
       pf_map->params->turn_mode != TM_WORST_TIME) {
@@ -1126,11 +1121,47 @@
     return NULL;
   }
 
+  /* First iterate to find path length */
+  while(!same_pos(iter_tile, pf_map->params->start_tile)) {
+
+    if (!d_node->is_dangerous && d_node->waited) {
+      length += 2;
+    } else {
+      length++;
+    }
+
+    if (!d_node->is_dangerous) {
+      /* We are in the normal node and dir_to_here field is valid */
+      dir_next = node->dir_to_here;
+      /* d_node->danger_segment is the indicator of what lies ahead
+       * if it's non-NULL, we are entering a danger segment, 
+       * if it's NULL, we are not on one so danger_seg should be NULL */
+      danger_seg = d_node->danger_segment;
+      segment_index = 0;
+    } else {
+      /* We are in a danger segment */
+      dir_next = danger_seg[segment_index].dir;
+      segment_index++;
+    }
+
+    /* Step backward */
+    iter_tile = mapstep(iter_tile, DIR_REVERSE(dir_next));
+    node = &pf_map->lattice[iter_tile->index];
+    d_node = &pf_map->d_lattice[iter_tile->index];
+  }
+
+  /* Allocate memory for path */
   path->positions 
-    = fc_malloc((d_node->step + 1) * sizeof(struct pf_position));
-  path->length = d_node->step + 1;
+    = fc_malloc(length * sizeof(struct pf_position));
+  path->length = length;
 
-  for (i = d_node->step; i >= 0; i--) {
+  /* Reset variables for main iteration */
+  iter_tile = ptile;
+  node = &pf_map->lattice[ptile->index];
+  d_node = &pf_map->d_lattice[ptile->index];
+  waited = FALSE;
+
+  for (i = length - 1; i >= 0; i--) {
     bool old_waited = FALSE;
 
     /* 1: Deal with waiting */
@@ -1138,7 +1169,7 @@
       if (waited) {
         /* Waited at _this_ tile, need to record it twice in the path.
          * Here we record our state _after_ waiting (e.g. full move points) */
-        path->positions[i].tile = ptile;
+        path->positions[i].tile = iter_tile;
         path->positions[i].total_EC = node->extra_cost;
         path->positions[i].turn = get_turn(pf_map, node->cost) + 1;
         path->positions[i].moves_left = get_move_rate(pf_map->params);
@@ -1157,7 +1188,7 @@
     }
 
     /* 2: Fill the current position */
-    path->positions[i].tile = ptile;
+    path->positions[i].tile = iter_tile;
     if (!d_node->is_dangerous) {
       path->positions[i].total_MC = node->cost;
       path->positions[i].total_EC = node->extra_cost;
@@ -1178,7 +1209,7 @@
     /* 3: Check if we finished */
     if (i == 0) {
       /* We should be back at the start now! */
-      assert(same_pos(ptile, pf_map->params->start_tile));
+      assert(same_pos(iter_tile, pf_map->params->start_tile));
       return path;
     }
 
@@ -1198,9 +1229,9 @@
     }
 
     /* 5: Step further back */
-    ptile = mapstep(ptile, DIR_REVERSE(dir_next));
-    node = &pf_map->lattice[ptile->index];
-    d_node = &pf_map->d_lattice[ptile->index];
+    iter_tile = mapstep(iter_tile, DIR_REVERSE(dir_next));
+    node = &pf_map->lattice[iter_tile->index];
+    d_node = &pf_map->d_lattice[iter_tile->index];
 
   }
 
diff -Nurd -X.diff_ignore freeciv/common/aicore/path_finding.c freeciv/common/aicore/path_finding.c
--- freeciv/common/aicore/path_finding.c	2007-01-13 00:55:11.000000000 +0200
+++ freeciv/common/aicore/path_finding.c	2007-01-17 22:19:40.000000000 +0200
@@ -67,9 +67,6 @@
 struct danger_node {
   bool is_dangerous;
   bool waited;			/* TRUE if waited to get here */
-  int step;                     /* # of steps we took to get here */
-  int segment_length;           /* only used for dangerous tiles, the length 
-                                 * of the current dangerous streak */
   struct pf_danger_pos {
     enum direction8 dir;
     int cost;
@@ -468,8 +465,6 @@
   if (pf_map->params->is_pos_dangerous) {
     /* The starting point is safe */
     pf_map->d_lattice[pf_map->tile->index].is_dangerous = FALSE;
-    /* Initialize step counter */
-    pf_map->d_lattice[pf_map->tile->index].step = 0;
   }
 
   return pf_map;
@@ -762,12 +757,14 @@
 /***********************************************************************
   Creating path segment going back from d_node1 to a safe tile.
 ***********************************************************************/
-static void create_danger_segment(struct pf_map *pf_map, enum direction8 dir,
-                                  struct danger_node *d_node1, int length)
+static void create_danger_segment(struct pf_map *pf_map,
+                                  struct danger_node *d_node1)
 {
   int i;
   struct tile *ptile = pf_map->tile;
   struct pf_node *node = &pf_map->lattice[ptile->index];
+  struct danger_node *d_node = &pf_map->d_lattice[ptile->index];
+  int length = 0;
 
   /* Allocating memory */
   if (d_node1->danger_segment) {
@@ -777,8 +774,22 @@
      * PR#10613. */
     free(d_node1->danger_segment);
   }
+
+  /* First iteration for determining segment length */
+  while(d_node->is_dangerous) {
+    length++;
+    ptile = mapstep(ptile, DIR_REVERSE(node->dir_to_here));
+    node = &pf_map->lattice[ptile->index];
+    d_node = &pf_map->d_lattice[ptile->index];
+  }
+
+  /* Allocate memory for segment */
   d_node1->danger_segment = fc_malloc(length * sizeof(struct pf_danger_pos));
 
+  /* Reset tile and node pointers for main iteration */
+  ptile = pf_map->tile;
+  node = &pf_map->lattice[ptile->index];
+
   /* Now fill the positions */
   for (i = 0; i < length; i++) {
     /* Record the direction */
@@ -869,11 +880,6 @@
     int loc_cost
 	= (pf_map->status[pf_map->tile->index] != NS_WAITING ? node->cost
 	   : node->cost + get_moves_left(pf_map, node->cost));
-    /* Step number at xy taking into account waiting 
-     * (waiting counts as one step) */
-    int loc_step
-        = (pf_map->status[pf_map->tile->index] != NS_WAITING ? d_node->step
-           : d_node->step + 1);
 
     /* The previous position is contained in {x,y} fields of map */
     adjc_dir_iterate(pf_map->tile, tile1, dir) {
@@ -943,11 +949,9 @@
 	  node1->extra_cost = extra;
 	  node1->cost = cost;
 	  node1->dir_to_here = dir;
-          d_node1->step = loc_step + 1;
 	  if (d_node->is_dangerous) {
 	    /* Transition from red to blue, need to record the path back */
-	    create_danger_segment(pf_map, dir, d_node1, 
-                                  d_node->segment_length);
+	    create_danger_segment(pf_map, d_node1);
 	  } else {
 	    /* Clear the path back */
 	    if (d_node1->danger_segment) {
@@ -957,9 +961,6 @@
             /* We don't consider waiting to get to a safe tile as 
              * "real" waiting */
 	    d_node1->waited = FALSE;
-            if (pf_map->status[pf_map->tile->index] == NS_WAITING) {
-              d_node1->step--;
-            }
 	  }
 	  pf_map->status[index1] = NS_NEW;
 	  pq_insert(pf_map->queue, index1, -cost_of_path);
@@ -980,14 +981,6 @@
 	  node1->extra_cost = extra;
 	  node1->cost = cost;
 	  node1->dir_to_here = dir;
-          d_node1->step = loc_step + 1;
-          if (d_node->is_dangerous) {
-            /* Increment the number of steps we are making across danger */
-            d_node1->segment_length = d_node->segment_length + 1;
-          } else {
-            /* We just moved into the danger area */
-            d_node1->segment_length = 1;
-          }
 	  pf_map->status[index1] = NS_NEW;
 	  d_node1->waited = (pf_map->status[pf_map->tile->index]
 			     == NS_WAITING);
@@ -1060,6 +1053,8 @@
   bool waited = FALSE;
   struct pf_node *node = &pf_map->lattice[ptile->index];
   struct danger_node *d_node = &pf_map->d_lattice[ptile->index];
+  int length = 1;
+  struct tile *iter_tile = ptile;
 
   if (pf_map->params->turn_mode != TM_BEST_TIME &&
       pf_map->params->turn_mode != TM_WORST_TIME) {
@@ -1067,11 +1062,47 @@
     return NULL;
   }
 
+  /* First iterate to find path length */
+  while(!same_pos(iter_tile, pf_map->params->start_tile)) {
+
+    if (!d_node->is_dangerous && d_node->waited) {
+      length += 2;
+    } else {
+      length++;
+    }
+
+    if (!d_node->is_dangerous) {
+      /* We are in the normal node and dir_to_here field is valid */
+      dir_next = node->dir_to_here;
+      /* d_node->danger_segment is the indicator of what lies ahead
+       * if it's non-NULL, we are entering a danger segment, 
+       * if it's NULL, we are not on one so danger_seg should be NULL */
+      danger_seg = d_node->danger_segment;
+      segment_index = 0;
+    } else {
+      /* We are in a danger segment */
+      dir_next = danger_seg[segment_index].dir;
+      segment_index++;
+    }
+
+    /* Step backward */
+    iter_tile = mapstep(iter_tile, DIR_REVERSE(dir_next));
+    node = &pf_map->lattice[iter_tile->index];
+    d_node = &pf_map->d_lattice[iter_tile->index];
+  }
+
+  /* Allocate memory for path */
   path->positions 
-    = fc_malloc((d_node->step + 1) * sizeof(struct pf_position));
-  path->length = d_node->step + 1;
+    = fc_malloc(length * sizeof(struct pf_position));
+  path->length = length;
 
-  for (i = d_node->step; i >= 0; i--) {
+  /* Reset variables for main iteration */
+  iter_tile = ptile;
+  node = &pf_map->lattice[ptile->index];
+  d_node = &pf_map->d_lattice[ptile->index];
+  waited = FALSE;
+
+  for (i = length - 1; i >= 0; i--) {
     bool old_waited = FALSE;
 
     /* 1: Deal with waiting */
@@ -1079,7 +1110,7 @@
       if (waited) {
         /* Waited at _this_ tile, need to record it twice in the path.
          * Here we record our state _after_ waiting (e.g. full move points) */
-        path->positions[i].tile = ptile;
+        path->positions[i].tile = iter_tile;
         path->positions[i].total_EC = node->extra_cost;
         path->positions[i].turn = get_turn(pf_map, node->cost) + 1;
         path->positions[i].moves_left = pf_map->params->move_rate;
@@ -1097,7 +1128,7 @@
     }
 
     /* 2: Fill the current position */
-    path->positions[i].tile = ptile;
+    path->positions[i].tile = iter_tile;
     if (!d_node->is_dangerous) {
       path->positions[i].total_MC = node->cost;
       path->positions[i].total_EC = node->extra_cost;
@@ -1117,7 +1148,7 @@
     /* 3: Check if we finished */
     if (i == 0) {
       /* We should be back at the start now! */
-      assert(same_pos(ptile, pf_map->params->start_tile));
+      assert(same_pos(iter_tile, pf_map->params->start_tile));
       return path;
     }
 
@@ -1137,9 +1168,9 @@
     }
 
     /* 5: Step further back */
-    ptile = mapstep(ptile, DIR_REVERSE(dir_next));
-    node = &pf_map->lattice[ptile->index];
-    d_node = &pf_map->d_lattice[ptile->index];
+    iter_tile = mapstep(iter_tile, DIR_REVERSE(dir_next));
+    node = &pf_map->lattice[iter_tile->index];
+    d_node = &pf_map->d_lattice[iter_tile->index];
 
   }
 
_______________________________________________
Freeciv-dev mailing list
Freeciv-dev@gna.org
https://mail.gna.org/listinfo/freeciv-dev

Reply via email to