Complete.Org: Mailing Lists: Archives: freeciv-dev: November 2001:
[Freeciv-Dev] Re: Reproducable core dump (PR#1051)
Home

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

[Top] [All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index] [Thread Index]
To: freeciv-dev@xxxxxxxxxxx
Cc: bugs@xxxxxxxxxxxxxxxxxxx
Subject: [Freeciv-Dev] Re: Reproducable core dump (PR#1051)
From: jdorje@xxxxxxxxxxxxxxxxxxxxx
Date: Tue, 27 Nov 2001 11:16:06 -0800 (PST)

Gregory Berkolaiko wrote

--- jdorje@xxxxxxxxxxxxxxxxxxxxx wrote:
Gregory Berkolaiko wrot


2. This piece of code is used by human palyers (AI doesn't fly) but
it peeks under the FOW absolutely shamelessly.  You don't attempt to
fix it.
Why not?


Ouch.  I did not realize this was a problem - I just blindly duplicated
the original functionality :-(.  The goto should also avoid going
across unknown tiles, right?


It is a problem, largerly unfixed.  I have a patch fixing it in
find_the_best_path, but it's in the waiting.

As for unknown tiles, there is a comment at
http://www.freeciv.org/lxr/source/server/gotohand.c?v=cvs#L763
with which I agree.  There is also a maximalist's and minimalist's
approach to the problem of avoiding enemy.  You seem to follow
maximalist: if you don't know the tile, you assume it's enemy-occupied. I think it is more wise to do the minimalist's "if I don't see the enemy,
I hope it's not there" approach with the planes, otherwise you don't get
anywhere (in particular to some airfield -- it doesn't give you vision). So what I had in mind is more like: if (!MAPSTEP(nx, ny, x, y, dir) || (map_get_known_and_seen(nx, ny, pplayer) && is_non_allied_unit_tile(map_get_tile(nx, ny), pplayer)
        && !((nx==dest_x) && (ny==dest_y))))  {
  break;
}
Note that we don't care if our destination is occupied !


Hmm, I'll have to double-check the destination occupied situation.

My current implementation isn't completely minimalist: it will refuse to fly through unknown tiles but will happily fly through known, fogged tiles assuming no enemy is there. Is this wise? Really, a fogged tile is just as likely to contain an enemy as an unknown tile.

The plane is a problem in particular because it has limited feul. Does this mean it should rush to its destination, or be careful that it doesn't run out of feul? A plane could try to fly through a straight gap only to find its way completely blocked by enemy units, and not have enough feul to make it back to a safe point. But I don't really see that this is avoidable.


Yes, that's very wise. I think the code will be slower, but much more structurally sound.


Why the code would be slower?


Calling real_map_distance every time isn't as fast as just comparing to an already-known preferred_direction. This is moot since I restructured the quicksearch.


even more.  The full search has been changed to an A*.  I'm a bit
unsure of the "known" checking, though: the code will refuse to send

the > plane

through an unknown tile, but will happily send the plane over a known, fogged tile assuming no enemy is there. But this assumption is bad: for instance you shouldn't send the plane over a known city (although it will most likely be okay since you'll realize the mistake once you get in sight of the city, but...). I'm not quite sure how to handle this.


Yes, city is bad...
please add (is_tile_known() && is_non_allied_city_tile())
condition too.
This is how it's done in find_the_shortest_path.


OK, this is better. But still: it only checks if the player knows the tile, not if the player knows there's a city there. If there's a fogged tile with a city on it, the player may or may not remember that the city is there. The player may remember there being a city there when the city has been destroyed. The server probably doesn't even track this information, right?


? topology
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/26 19:21:59
@@ -1436,99 +1436,55 @@
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.
+Do an A* search using the warmap to completely search for the path.
Each step should catch the vast majority of tries.

   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
what would that mean?


"Each step should catch the vast majority of tries" I think means that in each of the 3 steps we're supposed to catch most of the cases. But this isn't really true since the O(1) checks will only work occasionally. I've removed it.


**************************************************************************/

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, dist;
+  int total_distance = real_map_distance(src_x, src_y, dest_x,
dest_y);
+
  freelog(LOG_DEBUG, "naive_air_can_move_between %i,%i -> %i,%i,
moves: %i",
          src_x, src_y, dest_x, dest_y, moves);


Raimar had different log message here


?


+  /* 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;
+  for (dist =  total_distance; dist > 0; dist--)  {
+    /* FIXME: straightest_direction doesn't actually follow the
straight line. */


it's not really FIXME, it's just a warning, no?


I suppose so. It should be a FIXME for straightest_direction, though. Actually, I think the comment is wrong though.


  }
+
+  /* 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.  We could
+      add yet another optimization by having the warmap store the full
cost (current
+      cost + minimum leftover cost). */
+  /* 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, "didn't work. Lets try full");

    init_warmap(src_x, src_y, AIR_MOVING);
+    /* The 0 is inaccurate, but it doesn't matter. */
    add_to_mapqueue(0, src_x, src_y);


why 0 is inaccurate?


A* uses current_cost + real_map_distance(x, y, dest_x, dest_y). Here current_cost == 0 and we just ignore the real_map_distance (not that it matters anyway).


    while (get_from_mapqueue(&x, &y)) {
@@ -1537,23 +1493,22 @@
        break;

      adjc_dir_iterate(x, y, x1, y1, dir) {
        if (warmap.cost[x1][y1] == MAXCOST) {
+         struct tile *ptile = map_get_tile(x1, y1);
+         struct unit *enemy = map_get_known_and_seen(x1, y1, pplayer)  ?
is_non_allied_unit_tile(ptile, pplayer) : NULL;
+
+         /* We allow attack goto's, but otherwise we'll refuse to goto
+             through unknown territory or an enemy unit. */
+         if ((map_get_known(x1, y1, pplayer) && !enemy)
              || (x1 == dest_x && y1 == dest_y)) { /* allow attack goto's */
+           int cost = warmap.cost[x1][y1] = warmap.cost[x][y] + 1;


Maybe add a comment that using 1 instead of SINGLE_MOVE is ok here
because we only deal with the planes?


OK.


+           add_to_mapqueue(cost + real_map_distance(x1, y1, dest_x, dest_y),
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;
}


I think you improved the code _a_lot_.


Yes, the old code was very unwieldy. A* is also much faster than breadth-first search.

However we should test the patch
after the final version is reached.


Yes. It'd be nice if we could compare the algorithm times, but that doesn't seem easy to do.

How about this version? I improve the A* search even more, and make most of the other changes you suggest. A new function, airspace_looks_usable(), is created.

jason


? old
? topology
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/27 19:15:13
@@ -1429,6 +1429,37 @@
 }
 
 /**************************************************************************
+ 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 assume/hope it's empty. */
+  if (!map_get_known(x, y, pplayer)) {
+    return 1;
+  }
+
+  /* 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;
+  }
+
+  /* We assume that any fogged tile probably doesn't contain an
+      enemy. */
+  if (!map_get_known_and_seen(x, y, pplayer)) {
+    return 1;
+  }
+
+  /* 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 +1467,82 @@
 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 (dist == 1) {
+    assert(real_map_distance(x, y, dest_x, dest_y) == 1);
+    return moves - total_distance;
   }
-  /* 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:
+
+  /* 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, "didn't work. Lets try full");
-  {
-    int cost;
-    struct unit *penemy;
 
     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, "movecost: %i", warmap.cost[x][y] + 1);
+           return moves - warmap.cost[x][y] - 1;
          }
+
+         /* We refuse to goto through unusable airspace  */
+         if (airspace_looks_usable(x1, y1, pplayer)) {
+           /* Planes always move 1 space at a time; this wouldn't work for 
other units. */
+           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, "no route found");
+  return -1;
 }

[Prev in Thread] Current Thread [Next in Thread]