+/*
+ * 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 (is_coastal(sectx[c][i], secty[c][i]))
+ bfs_enqueue(c, sectx[c][i], secty[c][i], 0);
+ }
+}
+
+/*
+ * Enqueue spheres of influence borders for breadth-first search.
+ */
+static void
+bfs_enqueue_border(void)
+{
+ int x, y, off, dir, nx, ny, noff;
+
+ for (y = 0; y < WORLD_Y; y++) {
+ for (x = y % 2; x < WORLD_X; x += 2) {
+ off = XYOFFSET(x, y);
+ if (distance[off] <= id + 1)
+ continue;
+ if (closest[off] == (natid)-1)
+ continue;
+ for (dir = DIR_FIRST; dir <= DIR_LAST; dir++) {
+ nx = new_x(x + diroff[dir][0]);
+ ny = new_y(y + diroff[dir][1]);
+ noff = XYOFFSET(nx, ny);
+ if (closest[noff] != closest[off]) {
+ bfs_enqueue(closest[off], x, y, id + 1);
+ break;
+ }
+ }
+ }
+ }
+}
+
+/*
+ * 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 minimum of the distance to the
+ * closest coastal land sector and the distance to just outside the
+ * sphere of influence plus @id. For sea sectors within a continent's
+ * sphere of influence, distance[off] - id is the distance to the
+ * border of the area where additional islands can be placed.
+ */
+static void
+init_spheres_of_influence(void)
+{
+ int c;
+
+ bfs_init();
+ for (c = 0; c < nc; c++)
+ bfs_enqueue_island(c);
+ bfs_run_queue();
+ bfs_enqueue_border();
+ bfs_run_queue();
+}
+
+/*
+ * Precompute distance to coast
+ * Set distance[XYOFFSET(x, y)] to the distance to the closest coastal
+ * land sector.
+ * Set closest[XYOFFSET(x, y)] to the closest continent's number,
+ * -1 if no single continent is closest.
+ */
+static void
+init_distance_to_coast(void)
+{
+ int c;
+
+ bfs_init();
+ for (c = 0; c < nc + ni; c++)
+ bfs_enqueue_island(c);
+ bfs_run_queue();
+}
+
+/*
+ * Is @x,@y in the same sphere of influence as island @c?
+ * Always true when @c is a continent.
+ */
+static int
+is_in_sphere(int c, int x, int y)
+{
+ return c < nc || closest[XYOFFSET(x, y)] == c % nc;
+}