[Freeciv-Dev] Re: Reproducable core dump (PR#1051)
[Top] [All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index] [Thread Index]
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;
}
- [Freeciv-Dev] Re: Reproducable core dump (PR#1051), jdorje, 2001/11/02
- [Freeciv-Dev] Re: Reproducable core dump (PR#1051), jdorje, 2001/11/11
- [Freeciv-Dev] Re: Reproducable core dump (PR#1051), Gregory Berkolaiko, 2001/11/26
- [Freeciv-Dev] Re: Reproducable core dump (PR#1051), jdorje, 2001/11/26
- [Freeciv-Dev] Re: Reproducable core dump (PR#1051), jdorje, 2001/11/27
- [Freeciv-Dev] Re: Reproducable core dump (PR#1051),
jdorje <=
- [Freeciv-Dev] Re: Reproducable core dump (PR#1051), jdorje, 2001/11/28
- [Freeciv-Dev] Re: Reproducable core dump (PR#1051), jdorje, 2001/11/28
|
|
