From: Markus Armbruster Date: Sun, 9 Aug 2020 15:13:33 +0000 (+0200) Subject: fairland: Compute spheres of influence X-Git-Tag: v4.4.1~110 X-Git-Url: http://git.pond.sub.org/?p=empserver;a=commitdiff_plain;h=d9425bb5da262875ce6d585767a3cabf805ec374 fairland: Compute spheres of influence A continent's sphere of influence is the set of sectors closer to it than to any other continent. The next commit needs this. Compute the spheres with a breadth-first search. Signed-off-by: Markus Armbruster --- diff --git a/src/util/fairland.c b/src/util/fairland.c index 7f96e282a..1d3b7acc5 100644 --- a/src/util/fairland.c +++ b/src/util/fairland.c @@ -217,6 +217,20 @@ static short *xzone; static unsigned *seen; static unsigned cur_seen; +/* + * Closest continent and "distance" + * closest[XYOFFSET(x, y)] is the closest continent's number. + * distance[] is complicated; see init_spheres_of_influence(). + */ +static natid *closest; +static unsigned short *distance; + +/* + * Queue for breadth-first search + */ +static int *bfs_queue; +static int bfs_queue_head, bfs_queue_tail; + static int **elev; /* elevation of the sectors */ static int **sectx, **secty; /* the sectors for each continent */ static int **sectc; /* which sectors are on the coast? */ @@ -251,6 +265,8 @@ static void grow_islands(void); /* Debugging aids: */ void print_own_map(void); void print_xzone_map(void); +void print_closest_map(void); +void print_distance_map(void); void print_elev_map(void); /**************************************************************************** @@ -512,6 +528,9 @@ allocate_memory(void) adj_land = malloc(WORLD_SZ() * sizeof(*adj_land)); xzone = malloc(WORLD_SZ() * sizeof(*xzone)); seen = calloc(WORLD_SZ(), sizeof(*seen)); + closest = malloc(WORLD_SZ() * sizeof(*closest)); + distance = malloc(WORLD_SZ() * sizeof(*distance)); + bfs_queue = malloc(WORLD_SZ() * sizeof(*bfs_queue)); elev = calloc(WORLD_X, sizeof(int *)); for (i = 0; i < WORLD_X; ++i) { own[i] = calloc(WORLD_Y, sizeof(int)); @@ -782,6 +801,106 @@ xzone_init(int n) xzone_around_island(c, id); } +/* + * Initialize breadth-first search. + */ +static void +bfs_init(void) +{ + int i; + + for (i = 0; i < WORLD_SZ(); i++) { + closest[i] = -1; + distance[i] = USHRT_MAX; + } + + bfs_queue_head = bfs_queue_tail = 0; +} + +/* + * Add sector @x,@y to the BFS queue. + * It's closest to @c, with distance @dist. + */ +static void +bfs_enqueue(int c, int x, int y, int dist) +{ + int off = XYOFFSET(x, y); + + assert(dist < distance[off]); + closest[off] = c; + distance[off] = dist; + bfs_queue[bfs_queue_tail] = off; + bfs_queue_tail++; + if (bfs_queue_tail >= WORLD_SZ()) + bfs_queue_tail = 0; + assert(bfs_queue_tail != bfs_queue_head); +} + +/* + * Search breadth-first until the queue is empty. + */ +static void +bfs_run_queue(void) +{ + int off, dist, i, noff, nx, ny; + coord x, y; + + while (bfs_queue_head != bfs_queue_tail) { + off = bfs_queue[bfs_queue_head]; + bfs_queue_head++; + if (bfs_queue_head >= WORLD_SZ()) + bfs_queue_head = 0; + dist = distance[off] + 1; + sctoff2xy(&x, &y, off); + for (i = DIR_FIRST; i <= DIR_LAST; i++) { + nx = new_x(x + diroff[i][0]); + ny = new_y(y + diroff[i][1]); + noff = XYOFFSET(nx, ny); + if (dist < distance[noff]) { + bfs_enqueue(closest[off], nx, ny, dist); + } else if (distance[noff] == dist) { + if (closest[off] != closest[noff]) + closest[noff] = (natid)-1; + } else + assert(distance[noff] < dist); + } + } +} + +/* + * Add island @c's coastal sectors to the BFS queue, with distance 0. + */ +static void +bfs_enqueue_island(int c) +{ + int i; + + for (i = 0; i < isecs[c]; i++) { + if (sectc[c][i]) + bfs_enqueue(c, sectx[c][i], secty[c][i], 0); + } +} + +/* + * Compute spheres of influence + * A continent's sphere of influence is the set of sectors closer to + * it than to any other continent. + * Set closest[XYOFFSET(x, y)] to the closest continent's number, + * -1 if no single continent is closest. + * Set distance[XYOFFSET(x, y)] to the distance to the closest coastal + * land sector. + */ +static void +init_spheres_of_influence(void) +{ + int c; + + bfs_init(); + for (c = 0; c < nc; c++) + bfs_enqueue_island(c); + bfs_run_queue(); +} + /* * Can island @c grow at @x,@y? */ @@ -971,6 +1090,7 @@ grow_islands(void) int c, secs, isiz; xzone_init(nc); + init_spheres_of_influence(); for (c = nc; c < nc + ni; ++c) { if (!place_island(c)) { @@ -1394,6 +1514,62 @@ print_xzone_map(void) } } +/* + * Print a map to help visualize closest[]. + * This is for debugging. + */ +void +print_closest_map(void) +{ + int sx, sy, x, y, off; + + for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) { + y = YNORM(sy); + printf("%4d ", sy); + for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) { + x = XNORM(sx); + off = XYOFFSET(x, y); + if ((x + y) & 1) + putchar(' '); + else if (closest[off] == (natid)-1) + putchar('.'); + else if (!distance[off]) { + assert(closest[off] == own[x][y]); + putchar('-'); + } else { + putchar(numletter[closest[off] % 62]); + } + } + printf("\n"); + } +} + +void +print_distance_map(void) +{ + int sx, sy, x, y, off; + + for (sy = -WORLD_Y / 2; sy < WORLD_Y / 2; sy++) { + y = YNORM(sy); + printf("%4d ", sy); + for (sx = -WORLD_X / 2; sx < WORLD_X / 2; sx++) { + x = XNORM(sx); + off = XYOFFSET(x, y); + if ((x + y) & 1) + putchar(' '); + else if (closest[off] == (natid)-1) + putchar('.'); + else if (!distance[off]) { + assert(closest[off] == own[x][y]); + putchar('-'); + } else { + putchar(numletter[distance[off] % 62]); + } + } + printf("\n"); + } +} + /*************************************************************************** WRITE A SCRIPT FOR PLACING CAPITALS