--- settlers.c-old 2007-11-25 15:59:06.000000000 -0800 +++ settlers.c 2007-12-08 05:38:23.828125000 -0800 @@ -61,12 +61,46 @@ * flees */ #define WORKER_FEAR_FACTOR 2 +/* settlers can't stack more than this number on a space when autosettling */ +#define MAX_SETTLER_STACK 1 + struct settlermap { + int enroute[MAX_SETTLER_STACK]; + int eta[MAX_SETTLER_STACK]; + /* eta should always be in increasing order */ +}; - int enroute; /* unit ID of settler en route to this tile */ - int eta; /* estimated number of turns until enroute arrives */ +/************************************************************************** + settlermap utility: find the index of the slowest settler headed to + that location. +**************************************************************************/ -}; +static int index_of_slowest_settler(struct settlermap* map, int location) +{ + int j = MAX_SETTLER_STACK-1; + while (j >= -1 && map[location].enroute[j] == -1) { + j--; + } + return j; +} + +/************************************************************************** + settlermap utility: insert the given unit_id and its eta into the + settlermap. Note that ties are broken somewhat arbitrarily; this + saves us a lookup comparing actual distances. +**************************************************************************/ + +static void insert_into_settlermap(struct settlermap* map, int location, + int unit_id, int unit_eta) { + int j = 1 + index_of_slowest_settler(map, location); + while (j > 0 && (map[location].eta[j-1] > unit_eta)) { + map[location].enroute[j] = map[location].enroute[j-1]; + map[location].eta[j] = map[location].eta[j-1]; + j--; + } + map[location].enroute[j] = unit_id; + map[location].eta[j] = unit_eta; +} /************************************************************************** Build a city and initialize AI infrastructure cache. @@ -837,7 +871,7 @@ int best_newv = 0; - /* closest worker, if any, headed towards target tile */ + /* slowest worker, if any, headed towards target tile */ struct unit *enroute = NULL; generate_warmap(mycity, punit); @@ -846,6 +880,7 @@ /* try to work near the city */ city_map_checked_iterate(pcity->tile, cx, cy, ptile) { bool consider = TRUE; + int eta = FC_INFINITY; if (get_worker_city(pcity, cx, cy) == C_TILE_UNAVAILABLE || terrain_has_flag(pcity->tile->terrain, TER_UNSAFE)) { @@ -853,27 +888,32 @@ continue; } - /* do not go to tiles that already have workers there */ + /* do not go to tiles that already have MAX_SETTLER_STACK workers there */ + int worker_count = 0; unit_list_iterate(ptile->units, aunit) { if (unit_owner(aunit) == pplayer && aunit->id != punit->id && unit_has_type_flag(aunit, F_SETTLERS)) { - consider = FALSE; + worker_count++; } } unit_list_iterate_end; + if (worker_count >= MAX_SETTLER_STACK) consider = FALSE; in_use = (get_worker_city(pcity, cx, cy) == C_TILE_WORKER); if (state) { - enroute = player_find_unit_by_id(pplayer, - state[ptile->index].enroute); + int slowest = index_of_slowest_settler(state, ptile->index); + if (slowest != -1) { + enroute = player_find_unit_by_id(pplayer, + state[ptile->index].enroute[slowest]); + eta = state[ptile->index].eta[slowest]; + } } if (consider && tile_get_continent(ptile) == ucont && WARMAP_COST(ptile) <= THRESHOLD * mv_rate) { - int eta = FC_INFINITY, inbound_distance = FC_INFINITY, time; + int inbound_distance = FC_INFINITY, time; if (enroute) { - eta = state[ptile->index].eta; inbound_distance = real_map_distance(ptile, enroute->tile); } mv_turns = WARMAP_COST(ptile) / mv_rate; @@ -953,6 +993,7 @@ best_newv /= WORKER_FACTOR; + best_newv = MAX(best_newv, 0); /* sanity */ if (best_newv > 0) { @@ -989,7 +1030,6 @@ int completion_time = 0; if (recursion > unit_list_size(pplayer->units)) { - assert(recursion <= unit_list_size(pplayer->units)); ai_unit_new_role(punit, AIUNIT_NONE, NULL); set_unit_activity(punit, ACTIVITY_IDLE); send_unit_info(NULL, punit); @@ -1099,32 +1139,34 @@ if (punit->ai.ai_role == AIUNIT_AUTO_SETTLER) { /* Mark the square as taken. */ if (best_tile) { - struct unit *displaced - = player_find_unit_by_id(pplayer, state[best_tile->index].enroute); - - if (displaced) { - assert(state[best_tile->index].enroute == displaced->id); - assert(state[best_tile->index].eta > completion_time - || (state[best_tile->index].eta == completion_time - && (real_map_distance(best_tile, punit->tile) - < real_map_distance(best_tile, displaced->tile)))); + int slow_index = index_of_slowest_settler(state, best_tile->index); + struct unit *displaced = NULL; + int displaced_eta = 0; + + if (slow_index == MAX_SETTLER_STACK-1) { + /* we are displacing someone. */ + displaced = player_find_unit_by_id(pplayer, + state[best_tile->index].enroute[slow_index]); + displaced_eta = state[best_tile->index].eta[slow_index]; + assert(displaced_eta > completion_time + || (displaced_eta == completion_time)); UNIT_LOG(LOG_DEBUG, punit, "%d (%d,%d) has displaced %d (%d,%d) on %d,%d", punit->id, completion_time, real_map_distance(best_tile, punit->tile), - displaced->id, state[best_tile->index].eta, + displaced->id, displaced_eta, real_map_distance(best_tile, displaced->tile), TILE_XY(best_tile)); } - state[best_tile->index].enroute = punit->id; - state[best_tile->index].eta = completion_time; + insert_into_settlermap(state, best_tile->index, + punit->id, completion_time); - if (displaced) { + if (slow_index == MAX_SETTLER_STACK-1) { int saved_id = punit->id; + displaced->goto_tile = NULL; + auto_settler_findwork(pplayer, displaced, state, recursion + 1); - displaced->goto_tile = NULL; - auto_settler_findwork(pplayer, displaced, state, recursion + 1); if (player_find_unit_by_id(pplayer, saved_id) == NULL) { /* Actions of the displaced settler somehow caused this settler * to die. (maybe by recursively giving control back to this unit) @@ -1247,8 +1289,11 @@ } whole_map_iterate(ptile) { - state[ptile->index].enroute = -1; - state[ptile->index].eta = FC_INFINITY; + int j; + for (j = 0; j < MAX_SETTLER_STACK; ++j) { + state[ptile->index].enroute[j] = -1; + state[ptile->index].eta[j] = FC_INFINITY; + } } whole_map_iterate_end; /* Initialize the infrastructure cache, which is used shortly. */