[Freeciv-Dev] Re: Reproducable core dump (PR#1051)

[jdorje@xxxxxxxxxxxxxxxxxxxxx]

Gregory Berkolaiko wrote:

> Hi Jason,
>
> I think the patch is ready.  I have few comments on the comments but they
> shouldn't stand in the way of the acception.

Here's a fifth and hopefully final version.

Changes:

- Declared airspace_looks_usable static and prototyped it.

- Added comment about ai_handicap.  It's unnecessarily verbose, but 
should prevent future misunderstandings.
- Changed comments/freelog as GB suggested.

- Added a new comment into find_the_shortest_patch suggesting that it 
use airspace_looks_usable.  This is really GB's domain, I think, I just 
didn't want it to be forgotten about.
jason

? diff
? old
? topology
Index: common/player.h
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/player.h,v
retrieving revision 1.65
diff -u -r1.65 player.h
--- common/player.h     2001/09/25 19:58:13     1.65
+++ common/player.h     2001/12/01 21:24:10
@@ -42,8 +42,9 @@
 /* below this point are milder handicaps that I can actually implement -- 
Syela */
   H_RATES=256, /* can't set its rates beyond government limits */
   H_TARGETS=512, /* can't target anything it doesn't know exists */
-  H_HUTS=1024 /* doesn't know which unseen tiles have huts on them */
+  H_HUTS=1024, /* doesn't know which unseen tiles have huts on them */
 /* anything else I have forgotten?  Let me know. -- Syela */
+  H_FOG=2048, /* can't see through fog of war */
 };
 
 struct player_economic {
Index: server/gotohand.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/server/gotohand.c,v
retrieving revision 1.122
diff -u -r1.122 gotohand.c
--- server/gotohand.c   2001/10/08 12:11:17     1.122
+++ server/gotohand.c   2001/12/01 21:24:12
@@ -38,6 +38,15 @@
 /* These are used for airplane GOTOs with waypoints */
 #define MAXFUEL 100
 
+/* These should be either true or false.  They are used for finding routes
+    for airplanes - the airplane doesn't want to fly through occupied
+    territory, but most territory will be either fogged or unknown entirely.
+    See airspace_looks_usable().  Note that this is currently only used
+    by the move-counting function air_can_move_between(), not by
+    the path-finding function (whatever that may be). */
+#define AIR_ASSUMES_UNKNOWN_SAFE       TRUE
+#define AIR_ASSUMES_FOGGED_SAFE        TRUE
+
 enum refuel_type {
   FUEL_START = 0, FUEL_GOAL, FUEL_CITY, FUEL_AIRBASE
 };
@@ -56,6 +65,7 @@
 static void make_list_of_refuel_points(struct player *pplayer);
 static void dealloc_refuel_stack(void);
 static int find_air_first_destination(struct unit *punit, int *dest_x, int 
*dest_y);
+static int airspace_looks_usable(int x, int y, struct player *pplayer);
 
 /* These are used for all GOTO's */
 
@@ -763,6 +773,7 @@
        /* Planes could run out of fuel, therefore we don't care if territory
           is unknown. Also, don't attack except at the destination. */
 
+       /* This should probably use airspace_looks_usable instead. */
        if (is_non_allied_unit_tile(pdesttile, unit_owner(punit))) {
          if (x1 != dest_x || y1 != dest_y) {
            continue;
@@ -1429,6 +1440,42 @@
 }
 
 /**************************************************************************
+ Returns true if the given map position has airspace that _looks_
+ usable to the player.  The airspace is unusable if the player
+ believes there is an enemy unit on it.  This is tricky, since we have to
+ consider what the player knows/doesn't know.
+**************************************************************************/
+static int airspace_looks_usable(int x, int y, struct player *pplayer)
+{
+  struct tile * ptile = map_get_tile(x, y);
+
+  /* We do handicap checks for the player with ai_handicap().  This function 
returns true
+      if the player is handicapped.  For human players they'll always return 
true.  This is the
+      desired behavior. */
+
+  /* If the tile's unknown, we (may) assume it's empty. */
+  if (ai_handicap(pplayer, H_MAP) &&
+       !map_get_known(x, y, pplayer)) {
+    return AIR_ASSUMES_UNKNOWN_SAFE;
+  }
+
+  /* This is bad: there could be a city there that the player doesn't
+      know about.  How can we check that? */
+  if (is_non_allied_city_tile(ptile, pplayer)) {
+    return 0;
+  }
+
+  /* If the tile's fogged we again (may) assume it's empty. */
+  if (ai_handicap(pplayer, H_FOG) &&
+      !map_get_known_and_seen(x, y, pplayer)) {
+    return AIR_ASSUMES_FOGGED_SAFE;
+  }
+
+  /* Finally, we check to see if there's an enemy unit on the tile. */
+  return !is_non_allied_unit_tile(ptile, pplayer);
+}
+
+/**************************************************************************
  Returns #moves left when player playerid is moving a unit from src_x,src_y to
  dest_x,dest_y in moves moves. [Kero]
  If there was no way to move between returns -1.
@@ -1436,124 +1483,85 @@
 The function has 3 stages:
 Try to rule out the possibility in O(1) time              else
 Try to quickly verify in O(moves) time                    else
-Create a movemap to decide with certainty in O(moves2) time.
-Each step should catch the vast majority of tries.
+Do an A* search using the warmap to completely search for the path.
 **************************************************************************/
 int air_can_move_between(int moves, int src_x, int src_y,
                         int dest_x, int dest_y, struct player *pplayer)
 {
-  int x, y, go_x, go_y, i, movescount;
-  struct tile *ptile;
-  freelog(LOG_DEBUG, "naive_air_can_move_between %i,%i -> %i,%i, moves: %i",
-         src_x, src_y, dest_x, dest_y, moves);
-
-  /* O(1) */
-  if (real_map_distance(src_x, src_y, dest_x, dest_y) > moves) return -1;
-  if (real_map_distance(src_x, src_y, dest_x, dest_y) == 0) return moves;
-
-  /* O(moves). Try to go to the destination in a ``straight'' line. */
-  x = src_x; y = src_y;
-  movescount = moves;
-  while (real_map_distance(x, y, dest_x, dest_y) > 1) {
-    if (movescount <= 1)
-      goto TRYFULL;
-
-    go_x = (x > dest_x ?
-           (x-dest_x < map.xsize/2 ? -1 : 1) :
-           (dest_x-x < map.xsize/2 ? 1 : -1));
-    go_y = (dest_y > y ? 1 : -1);
-
-    freelog(LOG_DEBUG, "%i,%i to %i,%i. go_x: %i, go_y:%i",
-           x, y, dest_x, dest_y, go_x, go_y);
-    if (x == dest_x) {
-      for (i = x-1 ; i <= x+1; i++)
-       if ((ptile = map_get_tile(i, y+go_y))
-           /* && is_real_tile(i, y+go_y) */
-           && ! is_non_allied_unit_tile(ptile, pplayer)) {
-         x = i;
-         y += go_y;
-         goto NEXTCYCLE;
-       }
-      goto TRYFULL;
-    } else if (y == dest_y) {
-      for (i = y-1 ; i <= y+1; i++)
-       if ((ptile = map_get_tile(x+go_x, i))
-           && is_real_tile(x+go_x, i)
-           && ! is_non_allied_unit_tile(ptile, pplayer)) {
-         x += go_x;
-         y = i;
-         goto NEXTCYCLE;
-       }
-      goto TRYFULL;
-    }
+  int x, y, dist;
+  int total_distance = real_map_distance(src_x, src_y, dest_x, dest_y);
 
-    /* (x+go_x, y+go_y) is always real, given (x, y) is real */
-    ptile = map_get_tile(x+go_x, y+go_y);
-    if (! is_non_allied_unit_tile(ptile, pplayer)) {
-      x += go_x;
-      y += go_y;
-      goto NEXTCYCLE;
-    }
+  freelog(LOG_DEBUG, "air_can_move_between: %i,%i -> %i,%i, moves: %i",
+         src_x, src_y, dest_x, dest_y, moves);
 
-    /* (x+go_x, y) is always real, given (x, y) is real */
-    ptile = map_get_tile(x+go_x, y);
-    if (! is_non_allied_unit_tile(ptile, pplayer)) {
-      x += go_x;
-      goto NEXTCYCLE;
-    }
+  /* First we do some very simple O(1) checks. */
+  if (total_distance > moves) return -1;
+  if (total_distance == 0) return moves;
+
+  /* Then we do a fast O(n) straight-line check.  It'll work so long as the 
straight-line
+      doesn't cross any unreal tiles, unknown tiles, or enemy-controlled 
tiles.  So, it
+      should work most of the time. */
+  x = src_x, y = src_y;
+  /* We don't check the endpoint of the goto, since it's legal for a unit to 
be there.
+      But we do check that all points in between are empty. */
+  for (dist =  total_distance; dist > 1; dist--)  {
+
+    /* Warning: straightest_direction may not actually follow the straight 
line. */
+    int dir = straightest_direction(x, y, dest_x, dest_y);
+    int nx, ny;
 
-    /* (x, y+go_y) is always real, given (x, y) is real */
-    ptile = map_get_tile(x, y+go_y);
-    if (! is_non_allied_unit_tile(ptile, pplayer)) {
-      y += go_y;
-      goto NEXTCYCLE;
+    if (!MAPSTEP(nx, ny, x, y, dir) || !airspace_looks_usable(nx, ny, 
pplayer))  {
+      break;
     }
-
-    /* we didn't advance.*/
-    goto TRYFULL;
-
-  NEXTCYCLE:
-    movescount--;
+    x = nx, y = ny;
   }
-  /* if this loop stopped we made it! We found a way! */
-  freelog(LOG_DEBUG, "end of loop; success");
-  return movescount-1;
-
-  /* Nope, we couldn't find a quick way. Lets do the full monty.
-     Copied from find_the_shortest_path. If you want to know how
-     it works refer to the documentation there */
- TRYFULL:
-  freelog(LOG_DEBUG, "didn't work. Lets try full");
-  {
-    int cost;
-    struct unit *penemy;
+  if (dist == 1) {
+    /* Looks like the O(n) quicksearch worked. */
+    assert(real_map_distance(x, y, dest_x, dest_y) == 1);
+    return moves - total_distance;
+  }
+
+  /* Finally, we do a full A* search if nothing else worked.  This is copied 
from
+      find_the_shortest_path but we use real_map_distance as a minimum
+      distance estimator for the A* search.  This distance estimator is used 
for
+      the cost value in the queue, but is not stored in the warmap itself. */
+  /* Note, A* is possible here but not in a normal FreeCiv search because 
planes
+      always take 1 movement unit to move - which is not true of land units. */
+  freelog(LOG_DEBUG, "air_can_move_between: quick search didn't work. Lets try 
full.");
 
     init_warmap(src_x, src_y, AIR_MOVING);
+    /* The 0 is inaccurate under A*, but it doesn't matter. */
     add_to_mapqueue(0, src_x, src_y);
 
     while (get_from_mapqueue(&x, &y)) {
-      if (warmap.cost[x][y] > moves /* no chance */
-         || warmap.cost[dest_x][dest_y] != MAXCOST) /* found route */
-       break;
-
       adjc_dir_iterate(x, y, x1, y1, dir) {
-       if (warmap.cost[x1][y1] <= warmap.cost[x][y])
-         continue; /* No need for all the calculations */
-
        if (warmap.cost[x1][y1] == MAXCOST) {
-         ptile = map_get_tile(x1, y1);
-         penemy = is_non_allied_unit_tile(ptile, pplayer);
-         if (!penemy
-             || (x1 == dest_x && y1 == dest_y)) { /* allow attack goto's */
-           cost = warmap.cost[x1][y1] = warmap.cost[x][y] + 1;
-           add_to_mapqueue(cost, x1, y1);
+
+         /* This comes before the airspace_looks_usable check because it's okay
+             to goto into an enemy. */
+         if (x1 == dest_x && y1 == dest_y) {
+           /* We're there! */
+           freelog(LOG_DEBUG, "air_can_move_between: movecost: %i", 
warmap.cost[x][y] + 1);
+           /* The -1 is because we haven't taken the final step yet. */
+           return moves - warmap.cost[x][y] - 1;
          }
+
+         /* We refuse to goto through unusable airspace. */
+         if (airspace_looks_usable(x1, y1, pplayer)) {
+           /* Planes _always_ use SINLGE_MOVE a time so here
+               we can just use 1 instead of SINGLE_MOVE */
+           int cost = warmap.cost[x1][y1] = warmap.cost[x][y] + 1;
+
+           /* Now for A* we find the minimum total cost. */
+           cost += real_map_distance(x1, y1, dest_x, dest_y);
+           if (cost <= moves) {
+             add_to_mapqueue(cost, x1, y1);
+           }
+         }
        }
       } adjc_dir_iterate_end;
     }
 
-    freelog(LOG_DEBUG, "movecost: %i", warmap.cost[dest_x][dest_y]);
-  }
-  return (warmap.cost[dest_x][dest_y] <= moves)?
-    moves - warmap.cost[dest_x][dest_y]: -1;
+  freelog(LOG_DEBUG, "air_can_move_between: no route found");
+  return -1;
 }