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

[jdorje@xxxxxxxxxxxxxxxxxxxxx]

Raimar Falke wrote:

> On Wed, Nov 28, 2001 at 09:46:45AM -0800, jdorje@xxxxxxxxxxxxxxxxxxxxx wrote:
>
> > No problem...
> >
> > I'll make another patch as soon as we decide these issues.
> Have these issues been resolved? What is the status of the patch?

Here's a new patch.

Changes:

- Constants AIR_ASSUMES_UNKNOWN_SAFE and AIR_ASSUMES_FOGGED safe are 
used.  These are defined at the top of gotohand.c.  They are used by 
both AI and human players - but note that they're not used by whatever 
function is used to eventually find the path, only by this function 
which tests if a path exists.  So they are incomplete.
- An ai_handicap check is done for both unknown and fogged tiles.  I 
created a new handicap type H_FOG.  I'm not quite sure if this is the 
right thing to do, but using H_MAP for the fogged case didn't seem quite 
right.
- I made a few tiny changes elsewhere, mostly cleaning up comments IIRC.

- There are no parameters passed in - all the different cases are 
handled as above.  Of course, it'd be pretty easy to change 
AIR_ASSUMES_UNKNOWN_SAFE and AIR_ASSUMES_FOGGED_SAFE laster to use 
player-specific values.
I'm not sure if that's all the issues, but it's all I remember.

I haven't done any testing with the new version - although I did with an 
older version.  Some testing would be nice, but since the current code 
doesn't work anyway testing it in the field isn't all that bad.
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/11/30 20:12:24
@@ -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/11/30 20:12:27
@@ -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
 };
@@ -1429,6 +1438,38 @@
 }
 
 /**************************************************************************
+ 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.
+**************************************************************************/
+int airspace_looks_usable(int x, int y, struct player *pplayer)
+{
+  struct tile * ptile = map_get_tile(x, y);
+
+  /* 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 +1477,84 @@
 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) {
+    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: 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;
 }