From 5adb0176fa25dec7c7ec59cccb529da2b307efa6 Mon Sep 17 00:00:00 2001 From: "Eric S. Raymond" Date: Fri, 30 Mar 1990 10:02:08 +0000 Subject: [PATCH] Initial revision --- map.c | 1215 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 1215 insertions(+) create mode 100644 map.c diff --git a/map.c b/map.c new file mode 100644 index 0000000..b9271a7 --- /dev/null +++ b/map.c @@ -0,0 +1,1215 @@ +/* $Id$ - (c) Copyright 1987, 1988 Chuck Simmons */ + +/* + * Copyright (C) 1987, 1988 Chuck Simmons + * + * See the file COPYING, distributed with empire, for restriction + * and warranty information. + */ + +/* +map.c + +This file contains routines for playing around with view_maps, +real_maps, path_maps, and cont_maps. +*/ + +#ifdef SYSV +#include +#else +#include +#endif + +#include "empire.h" +#include "extern.h" + +#ifndef PROFILE +#define STATIC static +#else +#define STATIC +/* can't get accurate profile when procedures are static */ +#endif + +#define SWAP(a,b) { \ + perimeter_t *x; \ + x = a; a = b; b = x; \ +} + +STATIC void expand_perimeter(); +STATIC void expand_prune(); +STATIC void expand_dest_perimeter(); +STATIC int objective_cost(); +STATIC int terrain_type(); +STATIC void start_perimeter(); +STATIC void add_cell(); + +static perimeter_t p1; /* perimeter list for use as needed */ +static perimeter_t p2; +static perimeter_t p3; +static perimeter_t p4; + +static int best_cost; /* cost and location of best objective */ +static long best_loc; + +/* +Map out a continent. We are given a location on the continent. +We mark each square that is part of the continent and unexplored +territory adjacent to the continent. By adjusting the value of +'bad_terrain', this routine can map either continents of land, +or lakes. +*/ + +void +vmap_cont (cont_map, vmap, loc, bad_terrain) +int *cont_map; +view_map_t *vmap; +long loc; +char bad_terrain; +{ + (void) bzero ((char *)cont_map, MAP_SIZE * sizeof (int)); + vmap_mark_up_cont (cont_map, vmap, loc, bad_terrain); +} + +/* +Mark all squares of a continent and the squares that are adjacent +to the continent which are on the board. Our passed location is +known to be either on the continent or adjacent to the continent. +*/ + +void +vmap_mark_up_cont (cont_map, vmap, loc, bad_terrain) +int *cont_map; +view_map_t *vmap; +long loc; +char bad_terrain; +{ + int i, j; + long new_loc; + char this_terrain; + perimeter_t *from, *to; + + from = &p1; + to = &p2; + + from->len = 1; /* init perimeter */ + from->list[0] = loc; + cont_map[loc] = 1; /* loc is on continent */ + + while (from->len) { + to->len = 0; /* nothing in new perimeter yet */ + + for (i = 0; i < from->len; i++) /* expand perimeter */ + FOR_ADJ_ON(from->list[i], new_loc, j) + if (!cont_map[new_loc]) { + /* mark, but don't expand, unexplored territory */ + if (vmap[new_loc].contents == ' ') + cont_map[new_loc] = 1; + else { + if (vmap[new_loc].contents == '+') this_terrain = '+'; + else if (vmap[new_loc].contents == '.') this_terrain = '.'; + else this_terrain = map[new_loc].contents; + + if (this_terrain != bad_terrain) { /* on continent? */ + cont_map[new_loc] = 1; + to->list[to->len] = new_loc; + to->len += 1; + } + } + } + SWAP (from, to); + } +} + +/* +Map out a continent. We are given a location on the continent. +We mark each square that is part of the continent. +By adjusting the value of +'bad_terrain', this routine can map either continents of land, +or lakes. +*/ + +static void rmap_mark_up_cont(); + +void +rmap_cont (cont_map, loc, bad_terrain) +int *cont_map; +long loc; +char bad_terrain; +{ + (void) bzero ((char *)cont_map, MAP_SIZE * sizeof (int)); + rmap_mark_up_cont (cont_map, loc, bad_terrain); +} + +/* +Mark all squares of a continent and the squares that are adjacent +to the continent which are on the board. Our passed location is +known to be either on the continent or adjacent to the continent. + +Someday this should be tweaked to use perimeter lists. +*/ + +static void +rmap_mark_up_cont (cont_map, loc, bad_terrain) +int *cont_map; +long loc; +char bad_terrain; +{ + int i; + long new_loc; + + if (!map[loc].on_board) return; /* off board */ + if (cont_map[loc]) return; /* already marked */ + if (map[loc].contents == bad_terrain) return; /* off continent */ + + cont_map[loc] = 1; /* on continent */ + + FOR_ADJ (loc, new_loc, i) + rmap_mark_up_cont (cont_map, new_loc, bad_terrain); +} + +/* +Scan a continent recording items of interest on the continent. + +This could be done as we mark up the continent. +*/ + +#define COUNT(c,item) case c: item += 1; break + +scan_counts_t +vmap_cont_scan (cont_map, vmap) +int *cont_map; +view_map_t *vmap; +{ + scan_counts_t counts; + long i; + + (void) bzero ((char *)&counts, sizeof (scan_counts_t)); + + for (i = 0; i < MAP_SIZE; i++) { + if (cont_map[i]) { /* cell on continent? */ + counts.size += 1; + + switch (vmap[i].contents) { + COUNT (' ', counts.unexplored); + COUNT ('O', counts.user_cities); + COUNT ('A', counts.user_objects[ARMY]); + COUNT ('F', counts.user_objects[FIGHTER]); + COUNT ('P', counts.user_objects[PATROL]); + COUNT ('D', counts.user_objects[DESTROYER]); + COUNT ('S', counts.user_objects[SUBMARINE]); + COUNT ('T', counts.user_objects[TRANSPORT]); + COUNT ('C', counts.user_objects[CARRIER]); + COUNT ('B', counts.user_objects[BATTLESHIP]); + COUNT ('X', counts.comp_cities); + COUNT ('a', counts.comp_objects[ARMY]); + COUNT ('f', counts.comp_objects[FIGHTER]); + COUNT ('p', counts.comp_objects[PATROL]); + COUNT ('d', counts.comp_objects[DESTROYER]); + COUNT ('s', counts.comp_objects[SUBMARINE]); + COUNT ('t', counts.comp_objects[TRANSPORT]); + COUNT ('c', counts.comp_objects[CARRIER]); + COUNT ('b', counts.comp_objects[BATTLESHIP]); + COUNT ('*', counts.unowned_cities); + case '+': break; + case '.': break; + default: /* check for city underneath */ + if (map[i].contents == '*') { + switch (map[i].cityp->owner) { + COUNT (USER, counts.user_cities); + COUNT (COMP, counts.comp_cities); + COUNT (UNOWNED, counts.unowned_cities); + } + } + } + } + } + return counts; +} + +/* +Scan a real map as above. Only the 'size' and 'unowned_cities' +fields are valid. +*/ + +scan_counts_t +rmap_cont_scan (cont_map) +int *cont_map; +{ + scan_counts_t counts; + long i; + + (void) bzero ((char *)&counts, sizeof (scan_counts_t)); + + for (i = 0; i < MAP_SIZE; i++) { + if (cont_map[i]) { /* cell on continent? */ + counts.size += 1; + if (map[i].contents == '*') + counts.unowned_cities += 1; + } + } + return counts; +} + +/* +Return TRUE if a location is on the edge of a continent. +*/ + +int +map_cont_edge (cont_map, loc) +int *cont_map; +long loc; +{ + long i, j; + + if (!cont_map[loc]) return FALSE; /* not on continent */ + + FOR_ADJ (loc, j, i) + if (!cont_map[j]) return TRUE; /* edge of continent */ + + return FALSE; +} + +/* +Find the nearest objective for a piece. This routine actually does +some real work. This code represents my fourth rewrite of the +algorithm. This algorithm is central to the strategy used by the +computer. + +Given a view_map, we create a path_map. On the path_map, we record +the distance from a location to the nearest objective. We are +given information about what the interesting objectives are, and +how interesting each objective is. + +We use a breadth first search to find the nearest objective. +We maintain something called a "perimeter list". This list +initially contains a list of squares that we can reach in 'n' moves. +On each pass through our loop, we add all squares that are adjacent +to the perimeter list and which lie outside the perimeter to our +list. (The loop is only slightly more complicated for armies and +transports.) + +When our perimeter list becomes empty, or when the distance to +the current perimeter is at least as large as the weighted distance +to the best objective, we return the location of the best objective +found. + +The 'cost' field in a path_map must be INFINITY if the cell lies +outside of the current perimeter. The cost for cells that lie +on or within the current perimeter doesn't matter, except that +the information must be consistent with the needs of 'vmap_mark_path'. +*/ + +/* Find an objective over a single type of terrain. */ + +long +vmap_find_xobj (path_map, vmap, loc, move_info, start, expand) +path_map_t path_map[]; +view_map_t *vmap; +long loc; +move_info_t *move_info; +int start; +int expand; +{ + perimeter_t *from; + perimeter_t *to; + int cur_cost; + + from = &p1; + to = &p2; + + start_perimeter (path_map, from, loc, start); + cur_cost = 0; /* cost to reach current perimeter */ + + for (;;) { + to->len = 0; /* nothing in perim yet */ + expand_perimeter (path_map, vmap, move_info, from, expand, + cur_cost, 1, 1, to, to); + + if (trace_pmap) + print_pzoom ("After xobj loop:", path_map, vmap); + + cur_cost += 1; + if (to->len == 0 || best_cost <= cur_cost) + return best_loc; + + SWAP (from, to); + } +} + +/* Find an objective for a piece that crosses land and water. */ + +long +vmap_find_aobj (path_map, vmap, loc, move_info) +path_map_t path_map[]; +view_map_t *vmap; +long loc; +move_info_t *move_info; +{ + return vmap_find_xobj (path_map, vmap, loc, move_info, T_LAND, T_AIR); +} + +/* Find an objective for a piece that crosses only water. */ + +long +vmap_find_wobj (path_map, vmap, loc, move_info) +path_map_t path_map[]; +view_map_t *vmap; +long loc; +move_info_t *move_info; +{ + return vmap_find_xobj (path_map, vmap, loc, move_info, T_WATER, T_WATER); +} + +/* Find an objective for a piece that crosses only land. */ + +long +vmap_find_lobj (path_map, vmap, loc, move_info) +path_map_t path_map[]; +view_map_t *vmap; +long loc; +move_info_t *move_info; +{ + return vmap_find_xobj (path_map, vmap, loc, move_info, T_LAND, T_LAND); +} + +/* +Find an objective moving from land to water. +This is mildly complicated. It costs 2 to move on land +and one to move on water. To handle this, we expand our current +perimeter by one cell, where land can be expanded to either +land or water, and water is only expanded to water. Then +we expand any water one more cell. + +We have different objectives depending on whether the objective +is being approached from the land or the water. +*/ + +long +vmap_find_lwobj (path_map, vmap, loc, move_info, beat_cost) +path_map_t path_map[]; +view_map_t *vmap; +long loc; +move_info_t *move_info; +int beat_cost; +{ + perimeter_t *cur_land; + perimeter_t *cur_water; + perimeter_t *new_land; + perimeter_t *new_water; + int cur_cost; + + cur_land = &p1; + cur_water = &p2; + new_water = &p3; + new_land = &p4; + + start_perimeter (path_map, cur_land, loc, T_LAND); + cur_water->len = 0; + best_cost = beat_cost; /* we can do this well */ + cur_cost = 0; /* cost to reach current perimeter */ + + for (;;) { + /* expand current perimeter one cell */ + new_water->len = 0; + new_land->len = 0; + expand_perimeter (path_map, vmap, move_info, cur_water, + T_WATER, cur_cost, 1, 1, new_water, NULL); + + expand_perimeter (path_map, vmap, move_info, cur_land, + T_AIR, cur_cost, 1, 2, new_water, new_land); + + /* expand new water one cell */ + cur_water->len = 0; + expand_perimeter (path_map, vmap, move_info, new_water, + T_WATER, cur_cost+1, 1, 1, cur_water, NULL); + + if (trace_pmap) + print_pzoom ("After lwobj loop:", path_map, vmap); + + cur_cost += 2; + if (cur_water->len == 0 && new_land->len == 0 || best_cost <= cur_cost) { + return best_loc; + } + + SWAP (cur_land, new_land); + } +} + +/* +Return the cost to reach the adjacent cell of the correct type +with the lowest cost. +*/ + +STATIC int +best_adj (pmap, loc, type) +path_map_t *pmap; +long loc; +int type; +{ + int i; + long new_loc; + int best; + + best = INFINITY; + + FOR_ADJ (loc, new_loc, i) + if (pmap[new_loc].terrain == type && pmap[new_loc].cost < best) + best = pmap[new_loc].cost; + + return best; +} + +/* +Find an objective moving from water to land. +Here, we expand water to either land or water. +We expand land only to land. + +We cheat ever so slightly, but this cheating accurately reflects +the mechanics o moving. The first time we expand water we can +expand to land or water (army moving off tt or tt moving on water), +but the second time, we only expand water (tt taking its second move). +*/ + +long +vmap_find_wlobj (path_map, vmap, loc, move_info) +path_map_t path_map[]; +view_map_t *vmap; +long loc; +move_info_t *move_info; +{ + perimeter_t *cur_land; + perimeter_t *cur_water; + perimeter_t *new_land; + perimeter_t *new_water; + int cur_cost; + + cur_land = &p1; + cur_water = &p2; + new_water = &p3; + new_land = &p4; + + start_perimeter (path_map, cur_water, loc, T_WATER); + cur_land->len = 0; + cur_cost = 0; /* cost to reach current perimeter */ + + for (;;) { + /* expand current perimeter one cell */ + new_water->len = 0; + new_land->len = 0; + expand_perimeter (path_map, vmap, move_info, cur_water, + T_AIR, cur_cost, 1, 2, new_water, new_land); + + expand_perimeter (path_map, vmap, move_info, cur_land, + T_LAND, cur_cost, 1, 2, NULL, new_land); + + /* expand new water one cell to water */ + cur_water->len = 0; + expand_perimeter (path_map, vmap, move_info, new_water, + T_WATER, cur_cost+1, 1, 1, cur_water, NULL); + + if (trace_pmap) + print_pzoom ("After wlobj loop:", path_map, vmap); + + cur_cost += 2; + if (cur_water->len == 0 && new_land->len == 0 || best_cost <= cur_cost) { + return best_loc; + } + SWAP (cur_land, new_land); + } +} + +/* +Initialize the perimeter searching. + +This routine was taking a significant amount of the program time (10%) +doing the initialization of the path map. We now use an external +constant and 'memcpy'. +*/ + +static path_map_t pmap_init[MAP_SIZE]; +static int init_done = 0; + +STATIC void +start_perimeter (pmap, perim, loc, terrain) +path_map_t *pmap; +perimeter_t *perim; +long loc; +int terrain; +{ + int i; + + /* zap the path map */ + if (!init_done) { + init_done = 1; + for (i = 0; i < MAP_SIZE; i++) { + pmap_init[i].cost = INFINITY; /* everything lies outside perim */ + pmap_init[i].terrain = T_UNKNOWN; + } + } + (void) memcpy ((char *)pmap, (char *)pmap_init, sizeof (pmap_init)); + + /* put first location in perimeter */ + pmap[loc].cost = 0; + pmap[loc].inc_cost = 0; + pmap[loc].terrain = terrain; + + perim->len = 1; + perim->list[0] = loc; + + best_cost = INFINITY; /* no best yet */ + best_loc = loc; /* if nothing found, result is current loc */ +} + +/* +Expand the perimeter. + +Note that 'waterp' and 'landp' may be the same. + +For each cell of the current perimeter, we examine each +cell adjacent to that cell which lies outside of the current +perimeter. If the adjacent cell is an objective, we update +best_cost and best_loc. If the adjacent cell is of the correct +type, we turn place the adjacent cell in either the new water perimeter +or the new land perimeter. + +We set the cost to reach the current perimeter. +*/ + +STATIC void +expand_perimeter (pmap, vmap, move_info, curp, type, cur_cost, inc_wcost, inc_lcost, waterp, landp) +path_map_t *pmap; /* path map to update */ +view_map_t *vmap; +move_info_t *move_info; /* objectives and weights */ +perimeter_t *curp; /* perimeter to expand */ +int type; /* type of terrain to expand */ +int cur_cost; /* cost to reach cells on perimeter */ +int inc_wcost; /* cost to enter new water cells */ +int inc_lcost; /* cost to enter new land cells */ +perimeter_t *waterp; /* pointer to new water perimeter */ +perimeter_t *landp; /* pointer to new land perimeter */ +{ + long i; + int j; + long new_loc; + int obj_cost; + int new_type; + + for (i = 0; i < curp->len; i++) /* for each perimeter cell... */ + FOR_ADJ_ON (curp->list[i], new_loc, j) /* for each adjacent cell... */ + if (pmap[new_loc].cost == INFINITY) { + new_type = terrain_type (pmap, vmap, move_info, curp->list[i], new_loc); + + if (new_type == T_LAND && (type & T_LAND)) + add_cell (pmap, new_loc, landp, new_type, cur_cost, inc_lcost); + else if (new_type == T_WATER && (type & T_WATER)) + add_cell (pmap, new_loc, waterp, new_type, cur_cost, inc_wcost); + else if (new_type == T_UNKNOWN) { /* unreachable cell? */ + pmap[new_loc].terrain = new_type; + pmap[new_loc].cost = cur_cost + INFINITY/2; + pmap[new_loc].inc_cost = INFINITY/2; + } + if (pmap[new_loc].cost != INFINITY) { /* did we expand? */ + obj_cost = objective_cost (vmap, move_info, new_loc, cur_cost); + if (obj_cost < best_cost) { + best_cost = obj_cost; + best_loc = new_loc; + if (new_type == T_UNKNOWN) { + pmap[new_loc].cost = cur_cost + 2; + pmap[new_loc].inc_cost = 2; + } + } + } + } +} + +/* Add a cell to a perimeter list. */ + +STATIC void +add_cell (pmap, new_loc, perim, terrain, cur_cost, inc_cost) +path_map_t *pmap; +long new_loc; +perimeter_t *perim; +int terrain; +int cur_cost; +int inc_cost; +{ + pmap[new_loc].terrain = terrain; + pmap[new_loc].inc_cost = inc_cost; + pmap[new_loc].cost = cur_cost + inc_cost; + + perim->list[perim->len] = new_loc; + perim->len += 1; +} + +/* Compute the cost to move to an objective. */ + +STATIC int +objective_cost (vmap, move_info, loc, base_cost) +view_map_t *vmap; +move_info_t *move_info; +long loc; +int base_cost; +{ + char *p; + int w; + city_info_t *cityp; + + p = strchr (move_info->objectives, vmap[loc].contents); + if (!p) return INFINITY; + + w = move_info->weights[p - move_info->objectives]; + if (w >= 0) return w + base_cost; + + switch (w) { + case W_TT_BUILD: + /* handle special case of moving to tt building city */ + cityp = find_city (loc); + if (!cityp) return base_cost + 2; /* tt is already here */ + if (cityp->prod != TRANSPORT) return base_cost + 2; /* just finished a tt */ + + /* compute time to wait for tt to be built */ + w = piece_attr[TRANSPORT].build_time - cityp->work; + w *= 2; /* had to cross land to get here */ + if (w < base_cost + 2) w = base_cost + 2; + return w; + + default: + ABORT; + /* NOTREACHED */ + } +} + +/* +Return the type of terrain at a vmap location. +*/ + +STATIC int +terrain_type (pmap, vmap, move_info, from_loc, to_loc) +path_map_t *pmap; +view_map_t *vmap; +move_info_t *move_info; +long from_loc; +long to_loc; +{ + if (vmap[to_loc].contents == '+') return T_LAND; + if (vmap[to_loc].contents == '.') return T_WATER; + if (vmap[to_loc].contents == '%') return T_UNKNOWN; /* magic objective */ + if (vmap[to_loc].contents == ' ') return pmap[from_loc].terrain; + + switch (map[to_loc].contents) { + case '.': return T_WATER; + case '+': return T_LAND; + case '*': + if (map[to_loc].cityp->owner == move_info->city_owner) + return T_WATER; + else return T_UNKNOWN; /* cannot cross */ + } + ABORT; + /*NOTREACHED*/ +} + +/* +Prune unexplored territory. We take a view map and we modify it +so that unexplored territory that is adjacent to a lot of land +or a lot of water is marked as being either that land or water. +So basically, we are making a predicition about what we expect +for land and water. We iterate this algorithm until either +the next iteration would remove all unexplored territory, or +there is nothing more about which we can make an assumption. + +First, we use a pathmap to save the number of adjacent land +and water cells for each unexplored cell. Cells which have +adjacent explored territory are placed in a perimeter list. +We also count the number of cells that are not unexplored. + +We now take this perimeter list and make high-probability +predictions. + +Then we round things off by making one pass of medium +probability predictions. + +Then we make multiple passes extending our predictions. + +We stop if at any point all remaining unexplored cells are +in a perimeter list, or if no predictions were made during +one of the final passes. + +Unlike other algorithms, here we deal with "off board" locations. +So be careful. +*/ + +void +vmap_prune_explore_locs (vmap) +view_map_t *vmap; +{ + path_map_t pmap[MAP_SIZE]; + perimeter_t *from, *to; + int explored; + long loc, new_loc; + long i; + long copied; + + (void) bzero (pmap, sizeof (pmap)); + from = &p1; + to = &p2; + from->len = 0; + explored = 0; + + /* build initial path map and perimeter list */ + for (loc = 0; loc < MAP_SIZE; loc++) { + if (vmap[loc].contents != ' ') explored += 1; + else { /* add unexplored cell to perim */ + FOR_ADJ (loc, new_loc, i) { + if (new_loc < 0 || new_loc >= MAP_SIZE); /* ignore off map */ + else if (vmap[new_loc].contents == ' '); /* ignore adjacent unexplored */ + else if (map[new_loc].contents != '.') + pmap[loc].cost += 1; /* count land */ + else pmap[loc].inc_cost += 1; /* count water */ + } + if (pmap[loc].cost || pmap[loc].inc_cost) { + from->list[from->len] = loc; + from->len += 1; + } + } + } + + if (print_vmap == 'I') print_xzoom (vmap); + + for (;;) { /* do high probability predictions */ + if (from->len + explored == MAP_SIZE) return; + to->len = 0; + copied = 0; + + for (i = 0; i < from->len; i++) { + loc = from->list[i]; + if (pmap[loc].cost >= 5) + expand_prune (vmap, pmap, loc, T_LAND, to, &explored); + else if (pmap[loc].inc_cost >= 5) + expand_prune (vmap, pmap, loc, T_WATER, to, &explored); + else if ((loc < MAP_WIDTH || loc >= MAP_SIZE-MAP_WIDTH) && pmap[loc].cost >= 3) + expand_prune (vmap, pmap, loc, T_LAND, to, &explored); + else if ((loc < MAP_WIDTH || loc >= MAP_SIZE-MAP_WIDTH) && pmap[loc].inc_cost >= 3) + expand_prune (vmap, pmap, loc, T_WATER, to, &explored); + else if ((loc == 0 || loc == MAP_SIZE-1) && pmap[loc].cost >= 2) + expand_prune (vmap, pmap, loc, T_LAND, to, &explored); + else if ((loc == 0 || loc == MAP_SIZE-1) && pmap[loc].inc_cost >= 2) + expand_prune (vmap, pmap, loc, T_WATER, to, &explored); + else { /* copy perimeter cell */ + to->list[to->len] = loc; + to->len += 1; + copied += 1; + } + } + if (copied == from->len) break; /* nothing expanded */ + SWAP (from, to); + } + + if (print_vmap == 'I') print_xzoom (vmap); + + /* one pass for medium probability predictions */ + if (from->len + explored == MAP_SIZE) return; + to->len = 0; + + for (i = 0; i < from->len; i++) { + loc = from->list[i]; + if (pmap[loc].cost > pmap[loc].inc_cost) + expand_prune (vmap, pmap, loc, T_LAND, to, &explored); + else if (pmap[loc].cost < pmap[loc].inc_cost) + expand_prune (vmap, pmap, loc, T_WATER, to, &explored); + else { /* copy perimeter cell */ + to->list[to->len] = loc; + to->len += 1; + } + } + SWAP (from, to); + + if (print_vmap == 'I') print_xzoom (vmap); + + /* multiple low probability passes */ + for (;;) { + /* return if very little left to explore */ + if (from->len + explored >= MAP_SIZE - MAP_HEIGHT) { + if (print_vmap == 'I') print_xzoom (vmap); + return; + } + to->len = 0; + copied = 0; + + for (i = 0; i < from->len; i++) { + loc = from->list[i]; + if (pmap[loc].cost >= 4 && pmap[loc].inc_cost < 4) + expand_prune (vmap, pmap, loc, T_LAND, to, &explored); + else if (pmap[loc].inc_cost >= 4 && pmap[loc].cost < 4) + expand_prune (vmap, pmap, loc, T_WATER, to, &explored); + else if ((loc < MAP_WIDTH || loc >= MAP_SIZE-MAP_WIDTH) && pmap[loc].cost > pmap[loc].inc_cost) + expand_prune (vmap, pmap, loc, T_LAND, to, &explored); + else if ((loc < MAP_WIDTH || loc >= MAP_SIZE-MAP_WIDTH) && pmap[loc].inc_cost > pmap[loc].cost) + expand_prune (vmap, pmap, loc, T_WATER, to, &explored); + else { /* copy perimeter cell */ + to->list[to->len] = loc; + to->len += 1; + copied += 1; + } + } + if (copied == from->len) break; /* nothing expanded */ + SWAP (from, to); + } + if (print_vmap == 'I') print_xzoom (vmap); +} + +/* +Expand an unexplored cell. We increment the land or water count +of each neighbor. Any neighbor that acquires a non-zero count +is added to the 'to' perimiter list. The count of explored +territory is incremented. + +Careful: 'loc' may be "off board". +*/ + +STATIC void +expand_prune (vmap, pmap, loc, type, to, explored) +view_map_t *vmap; +path_map_t *pmap; +long loc; +int type; +perimeter_t *to; +int *explored; +{ + int i; + long new_loc; + + *explored += 1; + + if (type == T_LAND) vmap[loc].contents = '+'; + else vmap[loc].contents = '.'; + + FOR_ADJ (loc, new_loc, i) + if (new_loc >= 0 && new_loc < MAP_SIZE && vmap[new_loc].contents == ' ') { + if (!pmap[new_loc].cost && !pmap[new_loc].inc_cost) { + to->list[to->len] = new_loc; + to->len += 1; + } + if (type == T_LAND) + pmap[new_loc].cost += 1; + else pmap[new_loc].inc_cost += 1; + } +} + +/* +Find the shortest path from the current location to the +destination which passes over valid terrain. We return +the destination if a path exists. Otherwise we return the +origin. + +This is similar to 'find_objective' except that we know our destination. +*/ + +long +vmap_find_dest (path_map, vmap, cur_loc, dest_loc, owner, terrain) +path_map_t path_map[]; +view_map_t vmap[]; +long cur_loc; /* current location of piece */ +long dest_loc; /* destination of piece */ +int owner; /* owner of piece being moved */ +int terrain; /* terrain we can cross */ +{ + perimeter_t *from; + perimeter_t *to; + int cur_cost; + int start_terrain; + move_info_t move_info; + char old_contents; + + old_contents = vmap[dest_loc].contents; + vmap[dest_loc].contents = '%'; /* mark objective */ + move_info.city_owner = owner; + move_info.objectives = "%"; + move_info.weights[0] = 1; + + from = &p1; + to = &p2; + + if (terrain == T_AIR) start_terrain = T_LAND; + else start_terrain = terrain; + + start_perimeter (path_map, from, cur_loc, start_terrain); + cur_cost = 0; /* cost to reach current perimeter */ + + for (;;) { + to->len = 0; /* nothing in perim yet */ + expand_perimeter (path_map, vmap, &move_info, from, + terrain, cur_cost, 1, 1, to, to); + cur_cost += 1; + if (to->len == 0 || best_cost <= cur_cost) { + vmap[dest_loc].contents = old_contents; + return best_loc; + } + SWAP (from, to); + } +} + +/* +Starting with the destination, we recursively back track toward the source +marking all cells which are on a shortest path between the start and the +destination. To do this, we know the distance from the destination to +the start. The destination is on a path. We then find the cells adjacent +to the destination and nearest to the source and place them on the path. + +If we know square P is on the path, then S is on the path if S is +adjacent to P, the cost to reach S is less than the cost to reach P, +and the cost to move from S to P is the difference in cost between +S and P. + +Someday, this routine should probably use perimeter lists as well. +*/ + +void +vmap_mark_path (path_map, vmap, dest) +path_map_t *path_map; +view_map_t *vmap; +long dest; +{ + int n; + long new_dest; + + if (path_map[dest].cost == 0) return; /* reached end of path */ + if (path_map[dest].terrain == T_PATH) return; /* already marked */ + + path_map[dest].terrain = T_PATH; /* this square is on path */ + + /* loop to mark adjacent squares on shortest path */ + FOR_ADJ (dest, new_dest, n) + if (path_map[new_dest].cost == path_map[dest].cost - path_map[dest].inc_cost) + vmap_mark_path (path_map, vmap, new_dest); + +} + +/* +Create a marked path map. We mark those squares adjacent to the +starting location which are on the board. 'find_dir' must be +invoked to decide which squares are actually valid. +*/ + +void +vmap_mark_adjacent (path_map, loc) +path_map_t path_map[]; +long loc; +{ + int i; + long new_loc; + + FOR_ADJ_ON (loc, new_loc, i) + path_map[new_loc].terrain = T_PATH; +} + +/* +Modify a marked path map. We mark those squares adjacent to the +starting location which are on the board and which are adjacent +to a location on the existing shortest path. +*/ + +void +vmap_mark_near_path (path_map, loc) +path_map_t path_map[]; +long loc; +{ + int i, j; + long new_loc, xloc; + int hit_loc[8]; + + (void) bzero ((char *)hit_loc, sizeof(int)*8); + + FOR_ADJ_ON (loc, new_loc, i) { + FOR_ADJ_ON (new_loc, xloc, j) + if (xloc != loc && path_map[xloc].terrain == T_PATH) { + hit_loc[i] = 1; + break; + } + } + for (i = 0; i < 8; i++) + if (hit_loc[i]) + path_map[loc + dir_offset[i]].terrain = T_PATH; +} + +/* +Look at each neighbor of 'loc'. Select the first marked cell which +is on a short path to the desired destination, and which holds a valid +terrain. Note that while this terrain is matched against a 'vmap', +it differs slightly from terrains used above. This terrain is the +terrain to which we can move immediately, and does not include terrain +for which we would have to wait for another piece to move off of. + +We prefer diagonal moves, and we try to have as many squares +as possible containing something in 'adj_char'. + +For tie-breaking, we prefer moving to cells that are adjacent to +as many other squares on the path. This should have a few benefits: + +1) Fighters are less likely to be blocked from reaching a city +because they stay in the center of the path and increase the number +of options for subsequent moves. + +2) Transports will approach a city so that as many armies +as possible can hop off the tt on one turn to take a valid +path toward the city. + +3) User pieces will move more intuitively by staying in the +center of the best path. +*/ + +static int order[] = {NORTHWEST, NORTHEAST, SOUTHWEST, SOUTHEAST, + WEST, EAST, NORTH, SOUTH}; + +long +vmap_find_dir (path_map, vmap, loc, terrain, adj_char) +path_map_t path_map[]; +view_map_t *vmap; +long loc; +char *terrain; +char *adj_char; +{ + int i, count, bestcount; + long bestloc, new_loc; + int path_count, bestpath; + char *p; + + if (trace_pmap) + print_pzoom ("Before vmap_find_dir:", path_map, vmap); + + bestcount = -INFINITY; /* no best yet */ + bestpath = -1; + bestloc = loc; + + for (i = 0; i < 8; i++) { /* for each adjacent square */ + new_loc = loc + dir_offset[order[i]]; + if (path_map[new_loc].terrain == T_PATH) { /* which is on path */ + p = strchr (terrain, vmap[new_loc].contents); + + if (p != NULL) { /* desirable square? */ + count = vmap_count_adjacent (vmap, new_loc, adj_char); + path_count = vmap_count_path (path_map, new_loc); + + /* remember best location */ + if (count > bestcount + || count == bestcount && path_count > bestpath) { + bestcount = count; + bestpath = path_count; + bestloc = new_loc; + } + } + } + } + return (bestloc); +} + +/* +Count the number of adjacent squares of interest. +Squares are weighted so that the first in the list +is the most interesting. +*/ + +int +vmap_count_adjacent (vmap, loc, adj_char) +view_map_t *vmap; +long loc; +char *adj_char; +{ + int i, count; + long new_loc; + char *p; + int len; + + len = strlen (adj_char); + + count = 0; + + FOR_ADJ_ON (loc, new_loc, i) { + p = strchr (adj_char, vmap[new_loc].contents); + if (p) count += 8 * (len - (p - adj_char)); + } + return (count); +} + +/* +Count the number of adjacent cells that are on the path. +*/ + +static int +vmap_count_path (pmap, loc) +path_map_t *pmap; +long loc; +{ + int i, count; + long new_loc; + + count = 0; + + FOR_ADJ_ON (loc, new_loc, i) + if (pmap[new_loc].terrain == T_PATH) + count += 1; + + return (count); +} + +/* +See if a location is on the shore. We return true if a surrounding +cell contains water and is on the board. +*/ + +int +rmap_shore (loc) +long loc; +{ + long i, j; + + FOR_ADJ_ON (loc, j, i) + if (map[j].contents == '.') return (TRUE); + + return (FALSE); +} + +int +vmap_shore (vmap, loc) +view_map_t *vmap; +long loc; +{ + long i, j; + + FOR_ADJ_ON (loc, j, i) + if (vmap[j].contents != ' ' && vmap[j].contents != '+' && map[j].contents == '.') + return (TRUE); + + return (FALSE); +} + +/* +Return true if a location is surrounded by ocean. Off board locations +which cannot be moved to are treated as ocean. +*/ + +int +vmap_at_sea (vmap, loc) +view_map_t *vmap; +long loc; +{ + long i, j; + + FOR_ADJ_ON (loc, j, i) + if (vmap[j].contents == ' ' || vmap[j].contents == '+' || map[j].contents != '.') + return (FALSE); + + return (TRUE); +} + +int +rmap_at_sea (loc) +long loc; +{ + long i, j; + + FOR_ADJ_ON (loc, j, i) { + if (map[j].contents != '.') return (FALSE); + } + return (TRUE); +} + -- 2.43.0