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

[jdorje@xxxxxxxxxxxxxxxxxxxxx]

Gregory Berkolaiko wrote:

<snip: air goto bugfix>


> Below is the report on your patch.
>
> It seems to be correctly achieving what it strives to achieve.  It
> simplifies the code quite a bit but there are some issues which I would
> like to raise:
>
> 1. I was told that using goto is a very bad style.  You can get rid of
> them quite simply but you don't.  Why not?

Goto gets a bad rep because it's often used sloppily.  There were 
originally 2 goto's in this code, and they were sloppy :-).  I removed 
one of them, but it seemed more elegant to leave the other.  I'll give 
it another look.

> 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?
BTW, why is this part of the server code instead of client code? 
Shouldn't the client be picking the goto route?  Then there would be no 
problem with fog-of-war.  (Of course, the server should have similar 
code for the AI to use planes, so maybe it should go in common/).

> 3. You use direction vectors to check that you are going in the right
> direction.  This is a correct but not the most transperent and fast way. 
> I would propose to choose the direction basing on whether we get closer
> to the aim or not.  The "direction choice" cycle becomes
>
>   best = real_map_distance(x, y, dest_x, dest_y) + 1;
>   adjc_dir_iterate(x, y, nx, ny, dir) {
>     int value, dir_dx, dir_dy;
>       
>     if (is_non_allied_unit_tile(map_get_tile(nx, ny), pplayer)) 
>       continue;
>     }
>       
>     value = real_map_distance(nx, ny, dest_x, dest_y);
>       
>     if (value < best) {
>       best = value;
>       best_dir = dir;
>     }
>   } adjc_dir_iterate_end;
>
> You get rid of few lines and variables outside the cycle as well.  You
> may use straightest_direction as the tie-breaker if you wish.

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

> To summarise, the patch is good but not ready yet.

I don't know this code very well, so maybe I'm not the best person to be 
making sweeping changes here.  But anyway...
I don't see the point of having separate cases for a depth-first-search 
(sans backtracking) and a full warmap search.  An A* search should have 
all the good points of both (although it will use more memory than the 
depth-first, but I don't think that's an issue).  However, it will be 
significantly slower than the current algorithm (though still O(n) in 
cases where the simple algotirhm would succeed), so perhaps it's 
worthwhile to leave in the simple algorithm.
In either case, though, the warmap-style search should be an A* search. 
 We have a simple minimum distance estimator, so we might as well use it.

Okay, forget all that.  The new patch gets rid of the goto cleanly, and 
also cleans up the code quite nicely (and I've tried to comment 
thoroughly).  It includes the quick-search, but it's been trimmed down 
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.
Another review is definitely necessary.

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/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.
 **************************************************************************/
 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;
+  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);
-
-  /* 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;
-    }
-
-    /* (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;
-    }
-
-    /* (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;
-    }
 
-    /* (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;
+  /* 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. 
*/
+    int dir = straightest_direction(x, y, dest_x, dest_y);
+    int nx, ny;
+
+    if (!MAPSTEP(nx, ny, x, y, dir) ||
+        !map_get_known(nx, ny, pplayer) ||
+        (map_get_known_and_seen(nx, ny, pplayer) && 
is_non_allied_unit_tile(map_get_tile(nx, ny), pplayer)))  {
+      break;
     }
-
-    /* we didn't advance.*/
-    goto TRYFULL;
-
-  NEXTCYCLE:
-    movescount--;
+    x = nx, y = ny;
+  }
+  if (dist == 0) {
+    assert(x == dest_x && y == dest_y);
+    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.  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");
-  {
-    int cost;
-    struct unit *penemy;
 
     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);
 
     while (get_from_mapqueue(&x, &y)) {
@@ -1537,23 +1493,22 @@
        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
+         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 */
-           cost = warmap.cost[x1][y1] = warmap.cost[x][y] + 1;
-           add_to_mapqueue(cost, x1, y1);
+           int cost = warmap.cost[x1][y1] = warmap.cost[x][y] + 1;
+           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;
 }