diff -Nur -X/home/thue/freeciv-dev/no.freeciv freeciv/ai/advmilitary.c gtk_etc/ai/advmilitary.c --- freeciv/ai/advmilitary.c Wed Apr 26 16:30:50 2000 +++ gtk_etc/ai/advmilitary.c Wed Apr 26 16:15:45 2000 @@ -17,7 +17,6 @@ #include "government.h" #include "log.h" #include "map.h" -#include "player.h" #include "citytools.h" #include "cityturn.h" diff -Nur -X/home/thue/freeciv-dev/no.freeciv freeciv/client/civclient.c gtk_etc/client/civclient.c --- freeciv/client/civclient.c Wed Apr 26 16:14:41 2000 +++ gtk_etc/client/civclient.c Wed Apr 26 16:19:57 2000 @@ -338,6 +338,10 @@ case PACKET_DIPLOMAT_ACTION: handle_diplomat_action((struct packet_diplomat_action *)packet); break; + + case PACKET_ADVANCE_FOCUS: + handle_advance_focus((struct packet_generic_integer *)packet); + break; default: freelog(LOG_FATAL, _("Received unknown packet from server!")); diff -Nur -X/home/thue/freeciv-dev/no.freeciv freeciv/client/control.c gtk_etc/client/control.c --- freeciv/client/control.c Wed Apr 26 16:14:41 2000 +++ gtk_etc/client/control.c Wed Apr 26 16:19:57 2000 @@ -60,6 +60,16 @@ static struct unit *find_best_focus_candidate(void); /************************************************************************** +... +**************************************************************************/ +void handle_advance_focus(struct packet_generic_integer *packet) +{ + struct unit *punit = find_unit_by_id(packet->value); + if (punit && punit_focus == punit) + advance_unit_focus(); +} + +/************************************************************************** note: punit can be NULL We make sure that the previous focus unit is refreshed, if necessary, _after_ setting the new focus unit (otherwise if the previous unit is diff -Nur -X/home/thue/freeciv-dev/no.freeciv freeciv/client/control.h gtk_etc/client/control.h --- freeciv/client/control.h Wed Apr 26 16:14:41 2000 +++ gtk_etc/client/control.h Wed Apr 26 16:19:57 2000 @@ -22,6 +22,7 @@ int do_goto(int xtile, int ytile); void do_map_click(int xtile, int ytile); +void handle_advance_focus(struct packet_generic_integer *packet); void request_center_focus_unit(void); void request_move_unit_direction(struct unit *punit, int dx, int dy); /* used by key_xxx */ void request_new_unit_activity(struct unit *punit, enum unit_activity act); diff -Nur -X/home/thue/freeciv-dev/no.freeciv freeciv/common/packets.c gtk_etc/common/packets.c --- freeciv/common/packets.c Wed Apr 26 16:14:56 2000 +++ gtk_etc/common/packets.c Wed Apr 26 16:19:57 2000 @@ -235,6 +235,7 @@ case PACKET_CITY_REFRESH: case PACKET_INCITE_INQ: case PACKET_CITY_NAME_SUGGEST_REQ: + case PACKET_ADVANCE_FOCUS: return receive_packet_generic_integer(pc); case PACKET_ALLOC_NATION: diff -Nur -X/home/thue/freeciv-dev/no.freeciv freeciv/common/packets.h gtk_etc/common/packets.h --- freeciv/common/packets.h Wed Apr 26 16:14:56 2000 +++ gtk_etc/common/packets.h Wed Apr 26 16:19:57 2000 @@ -108,6 +108,7 @@ PACKET_RULESET_CITY, PACKET_UNIT_CONNECT, PACKET_SABOTAGE_LIST, + PACKET_ADVANCE_FOCUS, PACKET_LAST /* leave this last */ }; diff -Nur -X/home/thue/freeciv-dev/no.freeciv freeciv/server/gotohand.c gtk_etc/server/gotohand.c --- freeciv/server/gotohand.c Wed Apr 26 16:15:03 2000 +++ gtk_etc/server/gotohand.c Wed Apr 26 18:04:51 2000 @@ -40,6 +40,20 @@ struct stack_element { unsigned char x, y; }; + +#define MAXFUEL 100 + +enum refuel_type { + FUEL_START = 0, FUEL_GOAL, FUEL_CITY, FUEL_AIRBASE +}; + +struct refuel { + enum refuel_type type; + unsigned int x, y; + int turns; + struct refuel *coming_from; +}; + static struct stack_element warstack[WARSTACK_DIM]; /* This wastes ~20K of memory and should really be fixed but I'm lazy -- Syela @@ -53,6 +67,15 @@ static unsigned int warstacksize; static unsigned int warnodes; +static struct refuel *refuels[MAP_MAX_WIDTH*MAP_MAX_HEIGHT]; /* enought :P */ +static unsigned int refuelstacksize; + +static void make_list_of_refuel_points(struct player *pplayer); +static void dealloc_refuel_stack(); +static int find_air_first_destination(struct unit *punit, int *dest_x, int *dest_y); +static int naive_air_can_move_between(int moves, int src_x, int src_y, + int dest_x, int dest_y, int playerid); + /************************************************************************** ... **************************************************************************/ @@ -832,13 +855,23 @@ map_get_terrain(x, y) != T_OCEAN && !map_get_city(x, y) && !is_terrain_near_tile(x, y, T_OCEAN)) { return(0); - } /* end pre-emption subroutine. */ + } + return(1); } /************************************************************************** -... +If we have an air unit we use +find_air_first_destination(punit, &waypoint_x, &waypoint_y) +to get a waypoint to goto. The actual goto is still done with +find_the_shortest_path(pplayer, punit, waypoint_x, waypoint_y, restriction) + +There was a really oogy if here. Mighty Mouse told me not to axe it +because it would cost oodles of CPU time. He's right for the most part +but Peter and others have recommended more flexibility, so this is a little +different but should still pre-empt calculation of impossible GOTO's. + -- Syela **************************************************************************/ void do_unit_goto(struct player *pplayer, struct unit *punit, enum goto_move_restriction restriction) @@ -847,17 +880,16 @@ int ii[8] = { -1, 0, 1, -1, 1, -1, 0, 1 }; int jj[8] = { -1, -1, -1, 0, 0, 1, 1, 1 }; char *d[] = { "NW", "N", "NE", "W", "E", "SW", "S", "SE" }; + int unit_id, dest_x, dest_y, waypoint_x, waypoint_y; + struct unit *penemy = NULL; - int id=punit->id; - -/* there was a really oogy if here. Mighty Mouse told me not to axe it -because it would cost oodles of CPU time. He's right for the most part -but Peter and others have recommended more flexibility, so this is a little -different but should still pre-empt calculation of impossible GOTO's. -- Syela */ - - if (same_pos(punit->x, punit->y, punit->goto_dest_x, punit->goto_dest_y) || - !goto_is_sane(pplayer, punit, punit->goto_dest_x, punit->goto_dest_y, 0)) { - punit->activity=ACTIVITY_IDLE; + unit_id = punit->id; + dest_x = waypoint_x = punit->goto_dest_x; + dest_y = waypoint_y = punit->goto_dest_y; + + if (same_pos(punit->x, punit->y, dest_x, dest_y) || + !goto_is_sane(pplayer, punit, dest_x, dest_y, 0)) { + punit->activity = ACTIVITY_IDLE; punit->connecting = 0; send_unit_info(0, punit); return; @@ -868,12 +900,23 @@ return; } - if(find_the_shortest_path(pplayer, punit, - punit->goto_dest_x, punit->goto_dest_y, - restriction)) { + if (is_air_unit(punit)) + if (!find_air_first_destination(punit, &waypoint_x, &waypoint_y)) { + freelog(LOG_VERBOSE, "Did not find an airroute for " + "%s's %s at (%d, %d) -> (%d, %d)", + pplayer->name, unit_types[punit->type].name, + punit->x, punit->y, dest_x, dest_y); + punit->activity = ACTIVITY_IDLE; + punit->connecting = 0; + send_unit_info(0, punit); + return; + } + /* This has the side effect of marking the warmap with the possible paths */ + if (find_the_shortest_path(pplayer, punit, + waypoint_x, waypoint_y, restriction)) { do { - if(!punit->moves_left) return; + if (!punit->moves_left) return; k = find_a_direction(punit, restriction); if (k < 0) { freelog(LOG_DEBUG, "%s#%d@(%d,%d) stalling so it won't be killed.", @@ -886,6 +929,9 @@ freelog(LOG_DEBUG, "Going %s", d[k]); x = map_adjust_x(punit->x + ii[k]); y = punit->y + jj[k]; /* no need to adjust this */ + penemy = unit_list_get(&(map_get_tile(x,y)->units), 0); + if (penemy && penemy->owner == pplayer->player_no) + penemy = NULL; if(!punit->moves_left) return; if(!handle_unit_move_request(pplayer, punit, x, y, FALSE)) { @@ -898,9 +944,17 @@ } else { freelog(LOG_DEBUG, "Handled."); } - if(!player_find_unit_by_id(pplayer, id)) + if (!player_find_unit_by_id(pplayer, unit_id)) return; /* unit died during goto! */ + /* Don't attack more than once per goto*/ + if (penemy && !pplayer->ai.control) { /* Should I cancel for ai's too? */ + punit->activity = ACTIVITY_IDLE; + send_unit_info(0, punit); + return; + } + + if(punit->x!=x || punit->y!=y) { freelog(LOG_DEBUG, "Aborting, out of movepoints."); send_unit_info(0, punit); @@ -911,15 +965,13 @@ if (punit->connecting && can_unit_do_activity (punit, punit->activity)) return; - freelog(LOG_DEBUG, "Moving on."); - } while(!(x==punit->goto_dest_x && y==punit->goto_dest_y)); - } - else { + } while(!(x==waypoint_x && y==waypoint_y)); + } else { freelog(LOG_VERBOSE, "Did not find the shortest path for " - "%s's %s at (%d, %d) -> (%d, %d)", - pplayer->name, unit_types[punit->type].name, - punit->x, punit->y, punit->goto_dest_x, punit->goto_dest_y); + "%s's %s at (%d, %d) -> (%d, %d)", + pplayer->name, unit_types[punit->type].name, + punit->x, punit->y, dest_x, dest_y); } /* ensure that the connecting unit will perform it's activity @@ -927,7 +979,17 @@ if (punit->connecting && can_unit_do_activity(punit, punit->activity)) return; - punit->activity=ACTIVITY_IDLE; + /* normally we would just do this unconditionally, but if we had an + airplane goto we might not be finished even if the loop exited */ + if (punit->x == dest_x && punit->y == dest_y) + punit->activity=ACTIVITY_IDLE; + else if (punit->moves_left) { + struct packet_generic_integer packet; + packet.value = punit->id; + send_packet_generic_integer(pplayer->conn, PACKET_ADVANCE_FOCUS, + &packet); + } + punit->connecting=0; send_unit_info(0, punit); } @@ -969,4 +1031,393 @@ : warmap.seacost[dest_x][dest_y]; } +} + +/************************************************************************** +This list should probably be made by having a list of airbase and then +adding the players cities. It takes a little time to iterate over the map +as it is now, but as it is only used in the players turn that does not +matter. +FIXME: to make the airplanes gotos more straight it would be practical to +have the refuel points closest to the destination first. This wouldn't be +needed if we prioritizes between routes of equal lenght in +find_air_first_destination, which is a preferable solution. +**************************************************************************/ +static void make_list_of_refuel_points(struct player *pplayer) +{ + int x,y; + int playerid = pplayer->player_no; + struct refuel *prefuel; + struct city *pcity; + struct tile *ptile; + + refuelstacksize = 0; + + for (x = 0; x < map.xsize; x++) { + for (y = 0; y < map.ysize; y++) { + if ((pcity = map_get_city(x,y)) && pcity->owner == playerid) { + prefuel = fc_malloc(sizeof(struct refuel)); + prefuel->x = x; prefuel->y = y; + prefuel->type = FUEL_CITY; + prefuel->turns = 255; + prefuel->coming_from = NULL; + refuels[refuelstacksize++] = prefuel; + continue; + } + if ((ptile = map_get_tile(x,y))->special&S_AIRBASE) { + if ((unit_list_get(&(ptile->units), 0))->owner != playerid) + continue; + prefuel = fc_malloc(sizeof(struct refuel)); + prefuel->x = x; prefuel->y = y; + prefuel->type = FUEL_AIRBASE; + prefuel->turns = 255; + prefuel->coming_from = NULL; + refuels[refuelstacksize++] = prefuel; + } + } + } +} + +/************************************************************************** +... +**************************************************************************/ +static void dealloc_refuel_stack(void) +{ + int i; + for (i = 0; i < refuelstacksize; i++) + free(refuels[i]); +} + +/************************************************************************** +We need to find a route that our airplane can use without crashing. The +first waypoint of this route is returned inside the arguments dest_x and +dest_y. + +First we create a list of all possible refuel points (friendly cities and +airbases on the map). Then the destination is added to this stack. +We keep a list of the refuel points we have reached (been_there[]). this is +initialized with the unit position. +We have an array of pointer into the been_there[] stack, indicating where +we shall start and stop (fuelindex[]). fuelindex[0] is pointing at the top +of the stack, and fuelindex[i] is pointing at where we should start to +iterate if we want to try a goto using i fuel. For i>0 these are initialized +to zero. + +We the have a while(1) loop. This is exited once we have found a route or +there is no hope of ever finding one (the pointers into the stack of +been_there nodes all point at the top). We have a "turns" variable that +indicates how many turns we have used to build up the current been_there[] +stack. The trick is that for each while loop we find exactly those refuel +nodes that we can get to in "turns" turns. This is done by the way the +pointers into been_there are arranged; for example the pointers +fuelindex[i] and fuelindex[i+1] points to those nodes we reached i and i+1 +turns ago. So by iterating from fuelindex[i] to fuelindex[i+1] in the +been_there stack (the for loop inside the while does this for all pairs +(i, i+1), i <=fullfuel), and multiplying the moves with i (the fuel we can use), +we can simulate a move over i+1 turns using i+1 fuel. Because this node +has already waited i turns before it was used, using it will result in a +route that takes exactly "turns turns". + +The starting node is handled as a special case as it might not have full +fuel or movepoints. Note that once we have used another node as a waypoint +we can be sure when starting from there to have full fuel and moves again. + +At the end of each while loop we advance the indices in fuelindex[]. +For each refuel point we check in the been_there[] stack we try to move +between it and all unused nodes in the refuelstack[]. (this is usually quite +quick). If we can it is marked as used and the pointer to the node from the +been_there stack we came from is saved in it, and the new node put onto the +been_there[] stack. Since we at a given iteration of the while loop are as +far as we can get with the given number of turns, it means that if a node is +already marked there already exist a faster or just as fast way to get to it, +and we need not compare the two. +Since we iterate through the been_there stack starting with those jumps that +only use 1 fuel these are marked first, and therefore preferred over routes +of equal length that use 2 fuel. + +Once we reach the pgoal node we stop (set found_goal to 1). Since each node +now has exactly one pointer to a previous node, we can just follow the +pointers all the way back to the start node. The node immediately before +(after) the startnode is our first waypoint, and is returned. + +Possible changes: +I think the turns member of refuel points is not needed if we just deleted +the points as they can no longer be the shortest route, i.e. after the for +loop if they have been added inside the for loop. That would just be a +stack of numbers corresponding to indices in the refuel_stack array +(and then making the entries in refuel_stack nulpointers). +We might want compare routes of equal length, so that routes using cities +are preferred over routes using airports which in turn are better than +routes with long jumps. Now routes using cities or airports are preferred +over long jumps, but cities and airports are equal. It should also be made +so that the goto of the list of gotos of equal length that left the largest +amount of move points were selected. +We might also make sure that fx a fighter will have enough fuel to fly back +to a city after reaching it's destination. This could be done by making a +list of goal from which the last jump on the route could be done +satisfactory. We should also make sure that bombers given an order to +attack a unit will not make the attack on it's last fuel point etc. etc. +These last points would be necessary to make the AI use planes. +the list of extra goals would also in most case stop the algorithm from +iterating over all cities in the case of an impossible goto. In fact those +extra goal are so smart that you should implement them! :) + +note: The turns variabe in the refuel struct is currently not used for +anything but a boolean marker. + -Thue +**************************************************************************/ +static int find_air_first_destination(struct unit *punit, int *dest_x, int *dest_y) +{ + struct player *pplayer = unit_owner(punit); + static struct refuel *been_there[MAP_MAX_HEIGHT*MAP_MAX_WIDTH]; + unsigned int fuelindex[MAXFUEL+1]; /* +1: stack top pointer */ + struct refuel *prefuel, *pgoal; + struct refuel start; + unsigned int found_goal = 0; + unsigned int fullmoves = get_unit_type(punit->type)->move_rate/3; + unsigned int fullfuel = get_unit_type(punit->type)->fuel; + int turns = 0; + int i, j; + + assert(fullfuel <= MAXFUEL); + for (i = 1; i <= fullfuel; i++) + fuelindex[i] = 0; + fuelindex[0] = 1; + + start.x = punit->x; + start.y = punit->y; + start.type = FUEL_START; + start.turns = 0; + been_there[0] = &start; + + make_list_of_refuel_points(pplayer); + + pgoal = fc_malloc(sizeof(struct refuel)); + pgoal->x = punit->goto_dest_x; + pgoal->y = punit->goto_dest_y; + pgoal->type = FUEL_GOAL; + pgoal->turns = 255; + pgoal->coming_from = NULL; + refuels[refuelstacksize++] = pgoal; + + freelog(LOG_DEBUG, "stacksize = %i", refuelstacksize); + + do { /* until we find no new nodes or we found a path */ + int new_nodes, total_moves, from, to; + struct refuel *pfrom, *pto; + int usefuel; + enum refuel_type type; + + freelog(LOG_DEBUG, "round we go: %i", turns); + + new_nodes = 0; + usefuel = 1; + + while(usefuel <= fullfuel) { /* amount of fuel we use */ + total_moves = fullmoves * usefuel; + from = fuelindex[usefuel]; + to = fuelindex[usefuel - 1]; + freelog(LOG_DEBUG, "from = %i, to = %i, fuel = %i, total_moves = %i\n", + from, to, usefuel, total_moves); + + for (i = from; itype; + switch (type) { + case FUEL_START: + if (usefuel > punit->fuel) + continue; + total_moves = punit->moves_left/3 + (usefuel-1) * fullmoves; + default: + ; + }; + + for (j = 0; j < refuelstacksize; j++) { /* try to move to all of the nodes */ + pto = refuels[j]; + if (pto->turns >= 255 + && naive_air_can_move_between(total_moves, pfrom->x, pfrom->y, + pto->x, pto->y, pplayer->player_no)) { + freelog(LOG_DEBUG, "inserting from = %i,%i | to = %i,%i", + pfrom->x,pfrom->y,pto->x,pto->y); + + been_there[fuelindex[0] + new_nodes++] = pto; + pto->coming_from = pfrom; + pto->turns = turns; + if (pto->type == FUEL_GOAL) + found_goal = 1; + } + } + } /* end for */ + usefuel++; + } /* end while(usefuel <= fullfuel) */ + + turns++; + + for (i = fullfuel; i > 0; i--) + fuelindex[i] = fuelindex[i-1]; + fuelindex[0] += new_nodes; + + freelog(LOG_DEBUG, "new_nodes = %i, turns = %i, found_goal = %i", + new_nodes, turns, found_goal); + + } while (!found_goal && fuelindex[0] != fuelindex[fullfuel]); + + freelog(LOG_DEBUG, "backtracking"); + /* backtrack */ + if (found_goal) { + while ((prefuel = pgoal->coming_from)->type != FUEL_START) { + pgoal = prefuel; + freelog(LOG_DEBUG, "%i,%i", pgoal->x, pgoal->y); + } + freelog(LOG_DEBUG, "success"); + } else + freelog(LOG_DEBUG, "no success"); + freelog(LOG_DEBUG, "air goto done"); + + *dest_x = pgoal->x; + *dest_y = pgoal->y; + + dealloc_refuel_stack(); + + return found_goal; +} + +/************************************************************************** +Decides whether we can move from src_x,src_y to dest_x,dest_y in moves +moves. +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. +**************************************************************************/ +static int naive_air_can_move_between(int moves, int src_x, int src_y, + int dest_x, int dest_y, int playerid) +{ + 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); + + /* Do we have the chances of a snowball in hell? */ + if (real_map_distance(src_x, src_y, dest_x, dest_y) > moves) + return 0; + + /* Yep. Lets first try a quick and direct + approch that will almost allways work */ + x = src_x; y = src_y; + movescount = moves; + while (real_map_distance(x, y, dest_x, dest_y) > 1) { + struct unit *punit; + + 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) */ + && (!(punit = unit_list_get(&(ptile->units), 0)) + || punit->owner == playerid)) { + x = i; + 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) + && (!(punit = unit_list_get(&(ptile->units), 0)) + || punit->owner == playerid)) { + 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); + punit = unit_list_get(&(ptile->units), 0); + if (!punit || punit->owner == playerid) { + 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); + punit = unit_list_get(&(ptile->units), 0); + if (!punit || punit->owner == playerid) { + 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); + punit = unit_list_get(&(ptile->units), 0); + if (!punit || punit->owner == playerid) { + y += go_y; + goto NEXTCYCLE; + } + + /* we didn't advance.*/ + goto TRYFULL; + + NEXTCYCLE: + movescount--; + } + /* if this loop stopped we made it! We found a way! */ + freelog(LOG_DEBUG, "end of loop; success"); + return 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 excellent documentation there */ + TRYFULL: + freelog(LOG_DEBUG, "didn't work. Lets try full"); + { + int ii[8] = { 0, 1, 2, 0, 2, 0, 1, 2 }; + int jj[8] = { 0, 0, 0, 1, 1, 2, 2, 2 }; + int xx[3], yy[3], x1, y1, k; + struct unit *punit; + + init_gotomap(src_x, src_y); + warstacksize = 0; + warnodes = 0; + add_to_stack(src_x, src_y); + + do { + get_from_warstack(warnodes, &x, &y); + warnodes++; + map_calc_adjacent_xy(x, y, xx, yy); + + for (k = 0; k < 8; k++) { + x1 = xx[ii[k]]; + y1 = yy[jj[k]]; + + if (warmap.cost[x1][y1] == 255) { + ptile = map_get_tile(x1,y1); + punit = unit_list_get(&(ptile->units), 0); + if (!punit || punit->owner == playerid + || (x1 == dest_x && y1 == dest_y)) {/* allow attack goto's */ + warmap.cost[x1][y1] = warmap.cost[x][y] + 1; + add_to_stack(x1, y1); + } + } + } /* end for */ + } while (warmap.cost[x][y] <= moves + && warmap.cost[dest_x][dest_y] == 255); + + freelog(LOG_DEBUG, "movecost: %i", warmap.cost[dest_x][dest_y]); + } + return (warmap.cost[dest_x][dest_y] <= moves); }