#ifdef HAVE_CONFIG_H #include #endif #include #include #include #include #include "city.h" #include "packets.h" #include "clinet.h" #include "log.h" #include "civclient.h" #include "attribute.h" #include "mem.h" #include "shared.h" /* for MIN() */ #include "hash.h" #include "packhand.h" #include "fcintl.h" #include "agents.h" #include "goto_agent.h" #define SPECLIST_TAG cell #include "speclist.h" #define SPECLIST_TAG cell #include "speclist_c.h" /******* defines, structs, globals, forward declarations ************/ #define HASH_ACTIONS_LOG_LEVEL LOG_DEBUG #define DEBUG_MAIN_DIJKSTRA 0 #define PRINT_RETURNED_PATHS 0 /* * Terms used: * - step: one movement step which brings us from source to the destination * - turn: obvious * - point: one movement point (a knight has 2) * - railroad: used to compare routes, since railroad doesn't cost * anything, there is the danger of circular loop * - path: a list of steps which leads from the start to the end * - best path: a path which has the minimum of turns and if two have * equal turns, the maximum remaining points at the end and the * minimal railroad field. */ struct position { int x, y; }; struct cell { struct position pos; int turns, points_left, railroad, steps; struct cell *prev; int dir_from_prev_to_pos; }; struct ga_map { /* * Maps from position to cells. */ struct hash_table *known_cells; }; struct path_execution { int starting_turn; struct ga_path path; }; /**** static methods *********************************************/ static unsigned int hash_function(const void *key, unsigned int num_buckets) { const struct position *pos = (const struct position *) key; assert(sizeof(unsigned int) >= 4); return ((pos->x << 16) + pos->y) % num_buckets; } static int hash_cmp_function(const void *value1, const void *value2) { const struct position *pos1, *pos2; pos1 = (const struct position *) value1; pos2 = (const struct position *) value2; if ((pos1->x == pos2->x) && (pos1->y == pos2->y)) return 0; return 1; } static int cmp_function(const void *value1, const void *value2) { const struct cell *cell1, *cell2; cell1 = (const struct cell *) value1; cell2 = (const struct cell *) value2; if (cell1->turns != cell2->turns) return cell1->turns - cell2->turns; if (cell1->points_left != cell2->points_left) return -(cell1->points_left - cell2->points_left); if (cell1->railroad != cell2->railroad) return cell1->railroad - cell2->railroad; return 0; } static int list_cmp_function(const void *value1, const void *value2) { return cmp_function(*(const void **) value1, *(const void **) value2); } static struct cell *create_cell(int pos_x, int pos_y, int turns, int points_left, int railroad, int steps, struct cell *prev, int dir_from_prev_to_pos) { struct cell *result = fc_malloc(sizeof(struct cell)); assert(result); result->pos.x = pos_x; result->pos.y = pos_y; result->turns = turns; result->points_left = points_left; result->railroad = railroad; result->steps = steps; result->prev = prev; result->dir_from_prev_to_pos = dir_from_prev_to_pos; return result; } static struct cell *create_uninitialized_cell() { return create_cell(-1, -1, -1, -1, -1, -1, NULL, -1); } static void destroy_cell(struct cell *cell) { memset(cell, 0xDA, sizeof(struct cell)); free(cell); } static void insert_cell_into_hash(struct hash_table *hash, struct cell *cell) { int inserted; freelog(HASH_ACTIONS_LOG_LEVEL,"try to insert cell(%d,%d) into %p", cell->pos.x,cell->pos.y,hash); assert(!hash_key_exists(hash, &cell->pos)); inserted = hash_insert(hash, &cell->pos, cell); assert(inserted); } static void remove_cell_from_hash(struct hash_table *hash, struct cell *cell) { void *old_data; freelog(HASH_ACTIONS_LOG_LEVEL,"try to remove cell(%d,%d) from %p", cell->pos.x,cell->pos.y,hash); assert(hash_key_exists(hash, &cell->pos)); old_data = hash_delete_entry(hash, &cell->pos); assert(old_data == cell); } static struct cell *get_cell_from_hash(struct hash_table *hash, struct position *pos) { struct cell *result; freelog(HASH_ACTIONS_LOG_LEVEL,"try to look up cell(%d,%d) in %p", pos->x,pos->y,hash); result = (struct cell *) hash_lookup_data(hash, pos); freelog(HASH_ACTIONS_LOG_LEVEL,"%s",result?"yes":"no"); return result; } /* * Stripped down version of server/unithand.c:handle_unit_move_request() */ static int can_unit_type_move_from_to(Unit_Type_id type, int src_x, int src_y, int dest_x, int dest_y) { struct player *pplayer = game.player_ptr; /* ignored special case */ assert(!unit_flag(type, F_DIPLOMAT)); /* ignored special case */ assert(!unit_flag(type, F_CARAVAN)); /* ignored special case of attacking */ /*attacking=(pdefender && players_at_war(punit->owner, pdefender->owner)); assert(!attacking);*/ /* ignored special case */ /* city_take_over=(pcity && !players_allied(pcity->owner, punit->owner)); assert(!city_take_over);*/ return test_unit_move_to_tile(type, pplayer, ACTIVITY_IDLE, 0, src_x, src_y, dest_x, dest_y, 0) == MR_OK; } /* * Modified version of common/map.c:tile_move_cost_ptrs() */ /*************************************************************** The basic cost to move punit from tile t1 to tile t2. That is, tile_move_cost(), with pre-calculated tile pointers; the tiles are assumed to be adjacent, and the (x,y) values are used only to get the river bonus correct. May also be used with punit==NULL, in which case punit tests are not done (for unit-independent results). ***************************************************************/ static int tile_move_cost_ptrs2(Unit_Type_id type, struct tile *t1, struct tile *t2, int x1, int y1, int x2, int y2) { int cardinal_move; if (!is_ground_unittype(type)) return SINGLE_MOVE; if ((t1->special & S_RAILROAD) && (t2->special & S_RAILROAD)) return MOVE_COST_RAIL; /* return (unit_move_rate(punit)/RAIL_MAX) */ if (unit_flag(type, F_IGTER)) return SINGLE_MOVE / 3; if ((t1->special & S_ROAD) && (t2->special & S_ROAD)) return MOVE_COST_ROAD; if (((t1->terrain == T_RIVER) && (t2->terrain == T_RIVER)) || ((t1->special & S_RIVER) && (t2->special & S_RIVER))) { cardinal_move = (y1 == y2 || map_adjust_x(x1) == map_adjust_x(x2)); switch (terrain_control.river_move_mode) { case RMV_NORMAL: break; case RMV_FAST_STRICT: if (cardinal_move) return MOVE_COST_RIVER; break; case RMV_FAST_RELAXED: if (cardinal_move) return MOVE_COST_RIVER; else return 2 * MOVE_COST_RIVER; case RMV_FAST_ALWAYS: return MOVE_COST_RIVER; default: break; } } return (get_tile_type(t2->terrain)->movement_cost * SINGLE_MOVE); } /* * Modified version of common/map.c:map_move_cost() */ /*************************************************************** The cost to move punit from where it is to tile x,y. It is assumed the move is a valid one, e.g. the tiles are adjacent. ***************************************************************/ static int map_move_cost2(Unit_Type_id type, int src_x, int src_y, int dest_x, int dest_y) { return tile_move_cost_ptrs2(type, map_get_tile(src_x, src_y), map_get_tile(dest_x, dest_y), src_x, src_y, dest_x, dest_y); } /* * Stripped down version of client/goto.c:create_goto_map() */ static void calculate_costs_for_move(struct cell *src, struct cell *dest, Unit_Type_id type) { struct tile *psrctile = map_get_tile(src->pos.x, src->pos.y); struct tile *pdesttile = map_get_tile(dest->pos.x, dest->pos.y); int cost_in_points = map_move_cost2(type, src->pos.x, src->pos.y, dest->pos.x, dest->pos.y); int move_rate = get_unit_type(type)->move_rate; dest->turns = src->turns; dest->points_left = src->points_left; dest->railroad = src->railroad; dest->steps = src->steps; dest->steps++; if ((psrctile->special & S_RAILROAD) && (pdesttile->special & S_RAILROAD)) dest->railroad++; if (dest->points_left >= cost_in_points) dest->points_left -= cost_in_points; else { if (dest->points_left == move_rate) dest->points_left = 0; else { dest->turns++; dest->points_left = move_rate - cost_in_points; if (dest->points_left < 0) dest->points_left = 0; } } } static char *direction_to_string(int direction) { static char *tmp[] = { "NW", "N", "NE", "W", "E", "SW", "S", "SE", "invalid" }; if (direction < 0 || direction > 7) direction = 8; return tmp[direction]; } static void print_cell(char *msg, struct cell *cell) { freelog(LOG_NORMAL, "%s: cell (at %p) is at (%d,%d) with (t=%d,p=%d,r=%d,s=%d) dir=%s", msg, cell, cell->pos.x, cell->pos.y, cell->turns, cell->points_left, cell->railroad, cell->steps, direction_to_string(cell->dir_from_prev_to_pos)); } static void set_plan(int unit_id, struct path_execution *parameter) { if (!parameter) { attr_unit_set(ATTR_UNIT_GA_START_TURN, unit_id, 0, NULL); attr_unit_set(ATTR_UNIT_GA_POSITIONS, unit_id, 0, NULL); } else { attr_unit_set_int(ATTR_UNIT_GA_START_TURN, unit_id, parameter->starting_turn); attr_unit_set(ATTR_UNIT_GA_POSITIONS, unit_id, parameter->path.positions_used * sizeof(struct ga_position), ¶meter->path.positions); } } static int fill_plan(int unit_id, struct path_execution *parameter) { int len, tmp; len = attr_unit_get_int(ATTR_UNIT_GA_START_TURN, unit_id, &tmp); if (len == 0) return 0; if(parameter==NULL) return 1; parameter->starting_turn = tmp; len = attr_unit_get(ATTR_UNIT_GA_POSITIONS, unit_id, sizeof(parameter->path.positions), ¶meter->path.positions); assert(len > 0); assert((len % sizeof(struct ga_position)) == 0); parameter->path.positions_used = len / sizeof(struct ga_position); parameter->path.found_a_valid = 1; return 1; } static void handle_unit(int unit_id) { struct unit *punit; struct path_execution parameter; int pos_index; struct ga_position *current_pos, *next_pos; struct packet_move_unit move; punit = find_unit_by_id(unit_id); assert(punit); if(!fill_plan(unit_id,¶meter)) return; freelog(LOG_NORMAL, "GA-%d: handle_unit()", unit_id); for (;;) { current_pos = NULL; for (pos_index = 0; pos_index < parameter.path.positions_used; pos_index++) { current_pos = ¶meter.path.positions[pos_index]; if (current_pos->x == punit->x && current_pos->y == punit->y) break; current_pos = NULL; } assert(current_pos); ga_print_path("saved path", ¶meter.path); freelog(LOG_NORMAL, "GA-%d: current turn: %d", unit_id, game.turn - parameter.starting_turn); freelog(LOG_NORMAL, "GA-%d: moves_left: %d", unit_id, punit->moves_left); freelog(LOG_NORMAL, "GA-%d: current pos=(%d,%d)", unit_id, punit->x, punit->y); /* assert(current_pos->turn + parameter.starting_turn == game.turn); assert(current_pos->remaining_move_points == punit->moves_left); */ if (current_pos == LAST_POSITION(¶meter.path)) { freelog(LOG_NORMAL, "GA-%d: arrived", unit_id); ga_cancel_action(unit_id); break; } next_pos = ¶meter.path.positions[pos_index + 1]; move.unid = punit->id; move.x = next_pos->x; move.y = next_pos->y; freelog(LOG_NORMAL, "GA-%d: sending move-to-(%d,%d) command", unit_id, next_pos->x, next_pos->y); wait_for_unit_request("GA",send_packet_move_unit(&aconnection, &move)); if (punit->x == next_pos->x && punit->y == next_pos->y) { freelog(LOG_NORMAL, "GA-%d: unit is now at (%d,%d)", unit_id, punit->x, punit->y); } else { freelog(LOG_NORMAL, "GA-%d: move failed; will wait", unit_id); if (game.turn - parameter.starting_turn > current_pos->turn) { freelog(LOG_NORMAL, "game.turn=%d parameter.starting_turn=%d current_pos->turn=%d", game.turn, parameter.starting_turn, current_pos->turn); freelog(LOG_NORMAL, "GA-%d: WARNING: worse than planned", unit_id); } if (game.turn - parameter.starting_turn < current_pos->turn || punit->moves_left > current_pos->remaining_move_points) { freelog(LOG_NORMAL, "GA-%d: WARNING: better than planned", unit_id); } break; } } } static void remove_unit(int unit_id) { freelog(LOG_NORMAL,"GA: WARNING: unexpected removal of unit %d",unit_id); } /**** public methods *********************************************/ void ga_init(void) { struct unit_agent agent; strcpy(agent.name,"GA"); agent.is_agent_controlling_unit=ga_is_agent_moving_unit; agent.handle_unit=handle_unit; agent.remove_unit=remove_unit; add_unit_agent(&agent); #define T(_type_) freelog(LOG_NORMAL, "sizeof(" __STRING(_type_) ")=%d bytes",sizeof(_type_)); T(struct ga_path); T(struct ga_position); #undef T } void ga_print_path(char *msg, struct ga_path *path) { int i; freelog(LOG_NORMAL, "GA: %s: path (at %p) is %s", msg, path, path->found_a_valid ? "valid" : "invalid"); if (!path->found_a_valid) return; freelog(LOG_NORMAL, "GA: consists of %d positions:", path->positions_used); for (i = 0; i < path->positions_used; i++) { freelog(LOG_NORMAL, "GA: %d/%d: (%d,%d) (t=%d,p=%d) dir=%s", i, path->positions_used, path->positions[i].x, path->positions[i].y, path->positions[i].turn, path->positions[i].remaining_move_points, direction_to_string(path-> positions[i].direction_for_next_position)); } } ga_map_t ga_get_map(int unit_id) { struct unit *punit = find_unit_by_id(unit_id); struct hash_table *frontier = hash_new(hash_function, hash_cmp_function); struct cell_list flat_frontier; struct hash_table *known_cells = hash_new(hash_function, hash_cmp_function); ga_map_t result = fc_malloc(sizeof(struct ga_map)); struct cell *tmp_cell; int iterations; assert(punit); assert(frontier); assert(known_cells); assert(result); freelog(LOG_NORMAL, "GA-%d: ga_get_map(unit is at (%d,%d))", unit_id, punit->x, punit->y); cell_list_init(&flat_frontier); result->known_cells = known_cells; /* * add start to frontier */ tmp_cell = create_cell(punit->x, punit->y, 0, punit->moves_left, 0, 0, NULL, -1); insert_cell_into_hash(frontier, tmp_cell); cell_list_insert(&flat_frontier, tmp_cell); for (iterations = 0;; iterations++) { struct cell *current_cell; int dir; if (hash_num_entries(frontier) == 0) { assert(cell_list_size(&flat_frontier) == 0); break; } cell_list_sort(&flat_frontier, list_cmp_function); if (DEBUG_MAIN_DIJKSTRA) { int k, size = cell_list_size(&flat_frontier); freelog(LOG_NORMAL, "Cells after sorting"); for (k = 0; k < size; k++) { print_cell("", cell_list_get(&flat_frontier, k)); } freelog(LOG_NORMAL, "FINISH"); } current_cell = cell_list_get(&flat_frontier, 0); assert(current_cell); cell_list_unlink(&flat_frontier, current_cell); remove_cell_from_hash(frontier, current_cell); insert_cell_into_hash(known_cells, current_cell); if (DEBUG_MAIN_DIJKSTRA) print_cell("current_cell", current_cell); for (dir = 0; dir < 8; dir++) { struct cell *neighbour; struct cell *possible_neighbour = create_uninitialized_cell(); possible_neighbour->pos.x = current_cell->pos.x + DIR_DX[dir]; possible_neighbour->pos.y = current_cell->pos.y + DIR_DY[dir]; normalize_map_pos(&possible_neighbour->pos.x, &possible_neighbour->pos.y); possible_neighbour->prev = current_cell; possible_neighbour->dir_from_prev_to_pos = dir; if (!tile_is_known(possible_neighbour->pos.x, possible_neighbour->pos.y)) { freelog(LOG_DEBUG, " dir=%d, pos=(%d,%d): unknown", dir, possible_neighbour->pos.x, possible_neighbour->pos.y); continue; } if (!can_unit_type_move_from_to(punit->type, current_cell->pos.x, current_cell->pos.y, possible_neighbour->pos.x, possible_neighbour->pos.y)) { freelog(LOG_DEBUG, " dir=%d, pos=(%d,%d): move not possible", dir, possible_neighbour->pos.x, possible_neighbour->pos.y); continue; } calculate_costs_for_move(current_cell, possible_neighbour, punit->type); neighbour = get_cell_from_hash(known_cells, &possible_neighbour->pos); if (neighbour) { assert(cmp_function(neighbour, possible_neighbour) < 0); if (DEBUG_MAIN_DIJKSTRA && 0) { print_cell("current", current_cell); print_cell("existing neighbour (fixed)", neighbour); print_cell("new possible neighbour", possible_neighbour); } continue; } neighbour = get_cell_from_hash(frontier, &possible_neighbour->pos); if (neighbour == NULL) { insert_cell_into_hash(frontier, possible_neighbour); cell_list_insert(&flat_frontier, possible_neighbour); } else { /* * possible_neighbour is better than neighbour */ if (DEBUG_MAIN_DIJKSTRA) { print_cell("compare existing ", neighbour); print_cell("with possible new", possible_neighbour); } if (cmp_function(neighbour, possible_neighbour) > 0) { #define COPY(field) neighbour->field=possible_neighbour->field; COPY(turns); COPY(points_left); COPY(railroad); COPY(steps); COPY(prev); COPY(dir_from_prev_to_pos); if (DEBUG_MAIN_DIJKSTRA) freelog(LOG_NORMAL, "new wins"); } else { if (DEBUG_MAIN_DIJKSTRA) freelog(LOG_NORMAL, "old wins"); } destroy_cell(possible_neighbour); } } } /* * Cleanup */ hash_free(frontier); return result; } void ga_get_path_from_map(ga_map_t ga_map, int dest_x, int dest_y, struct ga_path *path) { struct position pos_as_key; struct cell *cell; int i; assert(ga_map); /*printf("ga_get_path_from_map(dest=(%d,%d))\n",dest_x,dest_y); */ pos_as_key.x = dest_x; pos_as_key.y = dest_y; cell = get_cell_from_hash(ga_map->known_cells, &pos_as_key); if (!cell) { path->found_a_valid = 0; return; } if(0) { struct cell *c=cell; int j; for(j=0;;j++) { freelog(LOG_NORMAL, " %d: cell at (%d,%d) with (t=%d,p=%d,r=%d,s=%d) %s", j, c->pos.x, c->pos.y, c->turns, c->points_left, c->railroad, c->steps, direction_to_string(c->dir_from_prev_to_pos)); c=c->prev; if(!c) break; } } assert(cell->steps < MAX_PATH_LENGTH); path->found_a_valid = 1; path->positions_used = cell->steps+1; for (i = path->positions_used - 1; i >= 0; i--) { assert(cell); if (i > 0) path->positions[i - 1].direction_for_next_position = cell->dir_from_prev_to_pos; path->positions[i].x = cell->pos.x; path->positions[i].y = cell->pos.y; path->positions[i].turn = cell->turns; path->positions[i].remaining_move_points = cell->points_left; cell = cell->prev; } LAST_POSITION(path)->direction_for_next_position = -1; assert(cell == NULL); assert(LAST_POSITION(path)->x == dest_x); assert(LAST_POSITION(path)->y == dest_y); if(PRINT_RETURNED_PATHS) ga_print_path("path found",path); } void ga_destroy_map(ga_map_t ga_map) { assert(ga_map); for (;;) { struct cell *current_cell, *tmp_cell; if (hash_num_entries(ga_map->known_cells) == 0) break; current_cell = (struct cell *) hash_value_by_number(ga_map->known_cells, 0); tmp_cell = hash_delete_entry(ga_map->known_cells, ¤t_cell->pos); assert(tmp_cell && tmp_cell == current_cell); destroy_cell(current_cell); } memset(ga_map, 0xDB, sizeof(struct ga_map)); free(ga_map); } void ga_get_path(int unit_id, int dest_x, int dest_y, struct ga_path *path) { ga_map_t ga_map = ga_get_map(unit_id); ga_get_path_from_map(ga_map, dest_x, dest_y, path); ga_destroy_map(ga_map); } int ga_is_agent_moving_unit(int unit_id) { return fill_plan(unit_id, NULL); } void ga_apply_path(int unit_id, struct ga_path *path) { struct unit *punit; struct path_execution parameter; assert(!ga_is_agent_moving_unit(unit_id)); assert(path->found_a_valid); assert(path->positions_used > 0); punit = find_unit_by_id(unit_id); assert(punit); assert(punit->x == path->positions[0].x); assert(punit->y == path->positions[0].y); memcpy(¶meter.path, path, sizeof(*path)); parameter.starting_turn = game.turn; set_plan(unit_id, ¶meter); call_handle_unit_for_agent(unit_id, "GA"); } void ga_cancel_action(int unit_id) { assert(ga_is_agent_moving_unit(unit_id)); set_plan(unit_id,NULL); } void ga_show_report(void) { int size = 0/*, i = 0*/; unit_list_iterate(game.player_ptr->units, punit) { if (ga_is_agent_moving_unit(punit->id)) size++; } unit_list_iterate_end; freelog(LOG_NORMAL, "GA managaging %d units", size); /* unit_list_iterate(game.player_ptr->units, punit) { struct sma_action_execution plan; int len; if (!ga_is_agent_moving_unit(punit->id)) continue; len = attr_unit_get(ATTR_UNIT_SMA_PLAN, punit->id, sizeof(plan), &plan); assert(len == sizeof(plan)); freelog(LOG_NORMAL, " %d/%d: %s at (%d,%d) with id %d", i, size, unit_types[punit->type].name, punit->x, punit->y,punit->id); freelog(LOG_NORMAL, " action: %s at (%d,%d)", action_to_name[plan.plan.action.action_type], plan.plan.action.target_x, plan.plan.action.target_y); freelog(LOG_NORMAL, " phase %d", plan.phase); i++; } unit_list_iterate_end;*/ }