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

[Gregory Berkolaiko <gberkolaiko@xxxxxxxxxxx>]

 --- jdorje@xxxxxxxxxxxxxxxxxxxxx wrote: 
> Gregory Berkolaiko wrote
> 
> >  --- jdorje@xxxxxxxxxxxxxxxxxxxxx wrote: 
> >>Gregory Berkolaiko wrot
> 
> 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.

Exactly.
But Raimar is right, it would be good to make it a constant, something
AIR_ASSUMES_UNKNOWN_SAFE
and
AIR_ASSUMES_FOGGED_SAFE

We should also introduce a check for ai.control: if the plane is
controlled by AI (which doesn't happen now but will be surely added at
some point), it wouldn't care if the tile is not seen -- AI cheats and
peeks under fog.
But for that we should also introduce a constant
AI_SEES_ALL
and later it should probably become a variable in struct player.

> 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.

A manually controlled plane is equally liable to get trapped like this.

> > 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.

yes but calls to dir_ok where deleted and they are as slow as
real_map_distance, no?  But it doesn't matter anyhow.

> 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?

probably not.
Thue would know this.
The only solution would be to move everything to client which is
bothersome.

> 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.

v.g. idea

/**************************************************************************
> + 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)) {

if (!map_get_known(x, y, pplayer) 
        && (!pplayer->ai.control || !AI_SEES_ALL) 
        &&  AIR_ASSUMES_UNKNOWN_SAFE)

I am sure you can find more elegant for though

> +    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)) {

same as above

> +    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, dist;
> +  int total_distance = real_map_distance(src_x, src_y, dest_x,
> dest_y);
>  
> +  freelog(LOG_DEBUG, "air_can_move_between %i,%i -> %i,%i, moves: %i",
> +       src_x, src_y, dest_x, dest_y, moves);
>  
> +  /* 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;
>  
> +    if (!MAPSTEP(nx, ny, x, y, dir) || !airspace_looks_usable(nx, ny,
> pplayer))  {
> +      break;
>      }
> +    x = nx, y = ny;
> +  }
> +  if (dist == 1) {
> +    assert(real_map_distance(x, y, dest_x, dest_y) == 1);

good assert

> +    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, "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)) {
>        adjc_dir_iterate(x, y, x1, y1, dir) {
>       if (warmap.cost[x1][y1] == MAXCOST) {
> +
> +       /* 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. */

/* Planes _always_ use SINLGE_MOVE a time so here we can just use 1
instead of SINGLE_MOVE */

or something like this.
otherwise some overzealous majic-fighter like me or Raahul will change 1
to something like MOVE_COST_ROAD ;)

> +         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, "no route found");

freelog(LOG_DEBUG, "air_can_move_between: no route found");

> +  return -1;
>  }
>  

verdict: 90% ready

Sorry about nitpicking though ;)

G.

__________________________________________________
Do You Yahoo!?
Everything you'll ever need on one web page from News and Sport to Email and 
Music Charts
http://uk.my.yahoo.com