[Freeciv-Dev] (PR#13718) New borders behaviour

["Per I. Mathisen" <per@xxxxxxxxxxx>]

<URL: http://bugs.freeciv.org/Ticket/Display.html?id=13718 >

This is a first draft of a patch to implement the new borders behaviour
that has been discussed:
 - Fortresses extend borders.
 - Once a border claim has been made, it is not changed unless the source
   of this claim, which can be a city or a fortress, disappears.
 - On turn end, each border source tries to grab new unclaimed tiles.
 - If a source detects an enemy unit inside their claim range, they will
   not grab any tiles that turn. This prevents unexpected unit bouncing.
   There is intentially no message for this failure, since this could
   generate too many messages.
 - How far cities extend their border depends on their size.
 - You always see changes to terrain, and you always know the extent of
   your own borders.

TODO: Change ownership of fortresses (by moving into them with hostile
unit). More testing.

Feedback, please. Please test it and report back how it feels. I like it
(but I'm biased).

  - Per

Index: common/game.h
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/game.h,v
retrieving revision 1.198
diff -u -r1.198 game.h
--- common/game.h       18 Aug 2005 06:44:28 -0000      1.198
+++ common/game.h       20 Aug 2005 18:30:48 -0000
@@ -207,9 +207,8 @@
 
 #define GAME_DEFAULT_FOGOFWAR        TRUE
 
-/* 0 means no national borders.  Performance dropps quickly as the border
- * distance increases (o(n^2) or worse). */
-#define GAME_DEFAULT_BORDERS         7
+/* 0 means no national borders. */
+#define GAME_DEFAULT_BORDERS         5
 #define GAME_MIN_BORDERS             0
 #define GAME_MAX_BORDERS             24
 
Index: common/map.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/map.c,v
retrieving revision 1.232
diff -u -r1.232 map.c
--- common/map.c        14 Jul 2005 19:25:45 -0000      1.232
+++ common/map.c        20 Aug 2005 18:30:49 -0000
@@ -276,6 +276,7 @@
   ptile->worked   = NULL; /* pointer to city working tile */
   ptile->owner    = NULL; /* Tile not claimed by any nation. */
   ptile->spec_sprite = NULL;
+  ptile->owner_source = NULL;
 }
 
 /****************************************************************************
Index: common/tile.h
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/tile.h,v
retrieving revision 1.12
diff -u -r1.12 tile.h
--- common/tile.h       11 Aug 2005 04:51:09 -0000      1.12
+++ common/tile.h       20 Aug 2005 18:30:50 -0000
@@ -36,6 +36,7 @@
   struct city *worked;      /* city working tile, or NULL if none */
   Continent_id continent;
   struct player *owner;     /* Player owning this tile, or NULL. */
+  struct tile *owner_source; /* what makes it owned by owner */
   char *spec_sprite;
 };
 
Index: server/citytools.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/server/citytools.c,v
retrieving revision 1.342
diff -u -r1.342 citytools.c
--- server/citytools.c  1 Aug 2005 23:09:36 -0000       1.342
+++ server/citytools.c  20 Aug 2005 18:30:55 -0000
@@ -808,9 +808,6 @@
   pcity->owner = ptaker;
   city_list_prepend(ptaker->cities, pcity);
 
-  /* Update the national borders. */
-  map_update_borders_city_change(pcity);
-
   transfer_city_units(ptaker, pgiver, old_city_units,
                      pcity, NULL,
                      kill_outside, transfer_unit_verbose);
@@ -922,6 +919,9 @@
 
   freelog(LOG_DEBUG, "Creating city %s", name);
 
+  /* Ensure that we claim the ground we stand on */
+  map_claim_ownership(ptile, pplayer);
+
   if (terrain_control.may_road) {
     tile_set_special(ptile, S_ROAD);
     if (player_knows_techs_with_flag(pplayer, TF_RAILROAD)) {
@@ -978,10 +978,6 @@
     }
   }
 
-  /* Update the national borders.  This updates the citymap tile
-   * status and so must be done after the above. */
-  map_update_borders_city_change(pcity);
-
   /* Place a worker at the city center; this is the free-worked tile.
    * This must be done before the city refresh (below) so that the city
    * is in a sane state. */
@@ -1135,7 +1131,6 @@
      acceptable. */
 
   game_remove_city(pcity);
-  map_update_borders_city_destroyed(ptile);
 
   players_iterate(other_player) {
     if (map_is_known_and_seen(ptile, other_player)) {
Index: server/maphand.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/server/maphand.c,v
retrieving revision 1.172
diff -u -r1.172 maphand.c
--- server/maphand.c    13 Aug 2005 05:27:24 -0000      1.172
+++ server/maphand.c    20 Aug 2005 18:30:57 -0000
@@ -1201,7 +1201,7 @@
 {
   /* Players */
   players_iterate(pplayer) {
-    if (map_is_known_and_seen(ptile, pplayer)) {
+    if (map_is_known_and_seen(ptile, pplayer) || ptile->owner == pplayer) {
       if (update_player_tile_knowledge(pplayer, ptile)) {
         send_tile_info(pplayer->connections, ptile);
       }
@@ -1591,71 +1591,44 @@
 
     /* New continent numbers for all tiles to all players */
     send_all_known_tiles(NULL);
-    
-    map_update_borders_landmass_change(ptile);
-  }
-}
-
-/*************************************************************************
-  Return pointer to the oldest adjacent city to this tile.  If
-  there is a city on the exact tile, that is returned instead.
-*************************************************************************/
-static struct city *map_get_adjc_city(struct tile *ptile)
-{
-  struct city *closest = NULL;   /* Closest city */
-
-  if (ptile->city) {
-    return ptile->city;
   }
-
-  adjc_iterate(ptile, tile1) {
-    if (tile1->city && 
-         (!closest || tile1->city->turn_founded < closest->turn_founded)) {
-      closest = tile1->city;
-    }
-  } adjc_iterate_end;
-
-  return closest;
 }
 
 /*************************************************************************
   Ocean tile can be claimed iff one of the following conditions stands:
   a) it is an inland lake not larger than MAXIMUM_OCEAN_SIZE
   b) it is adjacent to only one continent and not more than two ocean tiles
-  c) It is one tile away from a city (This function doesn't check it)
-  The city, which claims the ocean has to be placed on the correct continent.
+  c) It is one tile away from a city
+  The source which claims the ocean has to be placed on the correct continent.
   in case a) The continent which surrounds the inland lake
   in case b) The only continent which is adjacent to the tile
   The correct continent is returned in *contp.
 *************************************************************************/
-static bool is_claimed_ocean(struct tile *ptile, Continent_id *contp)
+static bool is_claimable_ocean(struct tile *ptile, struct tile *source)
 {
   Continent_id cont = tile_get_continent(ptile);
-  Continent_id cont2, other;
+  Continent_id source_cont = tile_get_continent(source);
+  Continent_id cont2;
   int ocean_tiles;
-  
-  if (get_ocean_size(-cont) <= MAXIMUM_CLAIMED_OCEAN_SIZE &&
-      lake_surrounders[-cont] > 0) {
-    *contp = lake_surrounders[-cont];
+
+  if (get_ocean_size(-cont) <= MAXIMUM_CLAIMED_OCEAN_SIZE
+      && lake_surrounders[-cont] == source_cont) {
     return TRUE;
   }
   
-  other = 0;
   ocean_tiles = 0;
   adjc_iterate(ptile, tile2) {
     cont2 = tile_get_continent(tile2);
+    if (tile2 == source) {
+      return TRUE;
+    }
     if (cont2 == cont) {
       ocean_tiles++;
-    } else {
-      if (other == 0) {
-        other = cont2;
-      } else if (other != cont2) {
-        return FALSE;
-      }
+    } else if (cont2 != source_cont) {
+      return FALSE; /* two land continents adjacent, punt! */
     }
   } adjc_iterate_end;
   if (ocean_tiles <= 2) {
-    *contp = other;
     return TRUE;
   } else {
     return FALSE;
@@ -1663,48 +1636,6 @@
 }
 
 /*************************************************************************
-  Return pointer to the closest city to this tile, which must be
-  on the same continent if the city is not immediately adjacent.
-  If two or more cities are equally distant, then return the
-  oldest (i.e. the one with the lowest id). This also correctly
-  works for water bases in SMAC mode, and allows coastal cities
-  to claim one square of ocean. Inland lakes and long inlets act in
-  the same way as the surrounding continent's land tiles. If no cities
-  are within game.info.borders distance, returns NULL.
-
-  NOTE: The behaviour of this function will eventually depend
-  upon some planned ruleset options.
-*************************************************************************/
-static struct city *map_get_closest_city(struct tile *ptile)
-{
-  struct city *closest;  /* Closest city */
-
-  closest = map_get_adjc_city(ptile);
-  if (!closest) {
-    int distsq;                /* Squared distance to city */
-    /* integer arithmetic equivalent of (borders+0.5)**2 */
-    int cldistsq = game.info.borders * (game.info.borders + 1);
-    Continent_id cont = tile_get_continent(ptile);
-
-    if (!is_ocean(tile_get_terrain(ptile)) || is_claimed_ocean(ptile, &cont)) {
-      cities_iterate(pcity) {
-       if (tile_get_continent(pcity->tile) == cont) {
-          distsq = sq_map_distance(pcity->tile, ptile);
-          if (distsq < cldistsq ||
-               (distsq == cldistsq &&
-                (!closest || closest->turn_founded > pcity->turn_founded))) {
-            closest = pcity;
-            cldistsq = distsq;
-          } 
-        }
-      } cities_iterate_end;
-    }
-  }
-
-  return closest;
-}
-
-/*************************************************************************
   Update tile worker states for all cities that have the given map tile
   within their radius. Does not sync with client.
 
@@ -1721,143 +1652,136 @@
 }
 
 /*************************************************************************
-  Recalculate the borders around a given position.
+  Add any unique home city not found in list but found on tile to the 
+  list.
 *************************************************************************/
-static void map_update_borders_recalculate_position(struct tile *ptile)
+static void add_unique_homecities(struct city_list *cities_to_refresh, 
+                           struct tile *tile1)
 {
-  struct city_list* cities_to_refresh = NULL;
-  
-  if (game.info.happyborders > 0) {
-    cities_to_refresh = city_list_new();
-  }
-  
-  if (game.info.borders > 0) {
-    iterate_outward(ptile, game.info.borders, tile1) {
-      struct city *pccity = map_get_closest_city(tile1);
-      struct player *new_owner = pccity ? pccity->owner : NULL;
-
-      if (new_owner != tile_get_owner(tile1)) {
-       tile_set_owner(tile1, new_owner);
-        update_tile_knowledge(tile1);
-       tile_update_owner(tile1);
-       /* Update happiness */
-       if (game.info.happyborders > 0) {
-         unit_list_iterate(tile1->units, unit) {
-           struct city* homecity = find_city_by_id(unit->homecity);
-           bool already_listed = FALSE;
-           
-           if (!homecity) {
-             continue;
-           }
-           
-           city_list_iterate(cities_to_refresh, city2) {
-             if (city2 == homecity) {
-               already_listed = TRUE;
-               break;
-             }
-           } city_list_iterate_end;
+  /* Update happiness */
+       unit_list_iterate(tile1->units, unit) {
+    struct city* homecity = find_city_by_id(unit->homecity);
+         bool already_listed = FALSE;
            
-           if (!already_listed) {
-             city_list_prepend(cities_to_refresh, homecity);
-           }
-
-         } unit_list_iterate_end;
-       }
+    if (!homecity) {
+      continue;
+    }
+         city_list_iterate(cities_to_refresh, city2) {
+      if (city2 == homecity) {
+        already_listed = TRUE;
+        break;
       }
-    } iterate_outward_end;
-  }
- 
-  /* Update happiness in all homecities we have collected */ 
-  if (game.info.happyborders > 0) {
-    city_list_iterate(cities_to_refresh, to_refresh) {
-      city_refresh(to_refresh);
-      send_city_info(city_owner(to_refresh), to_refresh);
     } city_list_iterate_end;
-    
-    city_list_unlink_all(cities_to_refresh);
-    city_list_free(cities_to_refresh);
-  }
-}
 
-/*************************************************************************
-  Modify national territories as resulting from a city being destroyed.
-  x,y coords for (already deleted) city's location.
-  Tile worker states are updated as necessary, but not sync'd with client.
-*************************************************************************/
-void map_update_borders_city_destroyed(struct tile *ptile)
-{
-  map_update_borders_recalculate_position(ptile);
+         if (!already_listed) {
+          city_list_prepend(cities_to_refresh, homecity);
+         }
+  } unit_list_iterate_end;
 }
 
 /*************************************************************************
-  Modify national territories resulting from a change of landmass.
-  Tile worker states are updated as necessary, but not sync'd with client.
+  Claim ownership of a single tile.  This does no checks.
 *************************************************************************/
-void map_update_borders_landmass_change(struct tile *ptile)
+void map_claim_ownership(struct tile *ptile, struct player *owner)
 {
-  map_update_borders_recalculate_position(ptile);
+  ptile->owner_source = ptile; /* beware of recursion! */
+  tile_set_owner(ptile, owner);
+  update_tile_knowledge(ptile);
+  tile_update_owner(ptile);
 }
 
 /*************************************************************************
-  Modify national territories resulting from new city or change of city
-  ownership.
-  Tile worker states are updated as necessary, but not sync'd with client.
-*************************************************************************/
-void map_update_borders_city_change(struct city *pcity)
-{
-  map_update_borders_recalculate_position(pcity->tile);
-}
+  Update borders for all sources.  Call this on turn end.
 
-/*************************************************************************
-  Delete the territorial claims to all tiles.
+  We will remove claim to land whose source is gone, and claim
+  land with sources in range, unless there are enemy units within
+  this range.
 *************************************************************************/
-static void map_clear_borders(void)
+void map_calculate_borders()
 {
+  struct city_list *cities_to_refresh = NULL;
+
+  if (game.info.borders == 0) {
+    return;
+  }
+
+  if (game.info.happyborders > 0) {
+    cities_to_refresh = city_list_new();
+  }
+
+  /* First remove undue ownership */
   whole_map_iterate(ptile) {
-    tile_set_owner(ptile, NULL);
+    if (ptile->owner
+        && (ptile->owner != ptile->owner_source->owner
+            || (!ptile->owner_source->city
+                && !tile_has_special(ptile->owner_source, S_FORTRESS)))) {
+      /* Ownership source gone */
+      map_claim_ownership(ptile, NULL);
+    }
   } whole_map_iterate_end;
-}
 
-/*************************************************************************
-  Minimal code that calculates all national territories from scratch.
-*************************************************************************/
-static void map_calculate_territory(void)
-{
-  /* Clear any old territorial claims. */
-  map_clear_borders();
-
-  if (game.info.borders > 0) {
-    /* Loop over all cities and claim territory. */
-    cities_iterate(pcity) {
-      /* Loop over all map tiles within this city's sphere of influence. */
-      iterate_outward(pcity->tile, game.info.borders, ptile) {
-       struct city *pccity = map_get_closest_city(ptile);
+  /* Now claim ownership of unclaimed tiles for all sources */
+  whole_map_iterate(ptile) {
+    if (ptile->city || tile_has_special(ptile, S_FORTRESS)) {
+      /* Ensure that we own our ownership source */
+      assert(ptile->owner != NULL);
+    }
+    if (ptile->owner
+        && (ptile->city || tile_has_special(ptile, S_FORTRESS))) {
+      /* We have an ownership source */
+      int range;
+      bool failure = FALSE; /* to claim borders */
+
+      if (ptile->city) {
+        range = MIN(ptile->city->size + 1, game.info.borders);
+        if (ptile->city->size > game.info.borders) {
+          range += (ptile->city->size - game.info.borders) / 2;
+        }
+      } else {
+        range = game.info.borders;
+      }
 
-       if (pccity) {
-         tile_set_owner(ptile, pccity->owner);
-       }
+      iterate_outward(ptile, range, atile) {
+        unit_list_iterate(atile->units, punit) {
+          if (!pplayers_allied(unit_owner(punit), ptile->owner)) {
+            /* We cannot expand borders when enemy units are
+             * present within our border range. */
+            failure = TRUE;
+            break;
+          }
+        } unit_list_iterate_end;
       } iterate_outward_end;
-    } cities_iterate_end;
-  }
-}
+      if (failure) {
+        /* This could be happening way too often for a failure
+         * notification to player. */
+        continue;
+      }
 
-/*************************************************************************
-  Calculate all national territories from scratch.  This can be slow, but
-  is only performed occasionally, i.e. after loading a saved game. Doesn't
-  send any tile information to the clients. Tile worker states are updated
-  as necessary, but not sync'd with client.
-*************************************************************************/
-void map_calculate_borders(void)
-{
-  if (game.info.borders > 0) {
-    map_calculate_territory();
+      iterate_outward(ptile, range, atile) {
+        if (map_is_known(atile, ptile->owner) 
+            && atile->owner == NULL) {
+          if (!is_ocean(atile->terrain)
+              || is_claimable_ocean(atile, ptile)) {
+            map_claim_ownership(atile, ptile->owner);
+            atile->owner_source = ptile;
+            if (game.info.happyborders > 0) {
+              add_unique_homecities(cities_to_refresh, atile);
+            }
+          }
+        }
+      } iterate_outward_end;
+    }
+  } whole_map_iterate_end;
 
-    /* Fix tile worker states. */
-    cities_iterate(pcity) {
-      map_city_radius_iterate(pcity->tile, tile1) {
-        update_city_tile_status_map(pcity, tile1);
-      } map_city_radius_iterate_end;
-    } cities_iterate_end;
+  /* Update happiness in all homecities we have collected */ 
+  if (game.info.happyborders > 0) {
+    city_list_iterate(cities_to_refresh, to_refresh) {
+      city_refresh(to_refresh);
+      send_city_info(city_owner(to_refresh), to_refresh);
+    } city_list_iterate_end;
+    
+    city_list_unlink_all(cities_to_refresh);
+    city_list_free(cities_to_refresh);
   }
 }
 
Index: server/maphand.h
===================================================================
RCS file: /home/freeciv/CVS/freeciv/server/maphand.h,v
retrieving revision 1.61
diff -u -r1.61 maphand.h
--- server/maphand.h    13 Aug 2005 05:27:24 -0000      1.61
+++ server/maphand.h    20 Aug 2005 18:30:57 -0000
@@ -97,10 +97,8 @@
 void enable_fog_of_war(void);
 void disable_fog_of_war(void);
 
-void map_update_borders_city_destroyed(struct tile *ptile);
-void map_update_borders_city_change(struct city *pcity);
-void map_update_borders_landmass_change(struct tile *ptile);
 void map_calculate_borders(void);
+void map_claim_ownership(struct tile *ptile, struct player *owner);
 
 void check_terrain_change(struct tile *ptile, struct terrain *oldter);
 int get_continent_size(Continent_id id);
Index: server/sanitycheck.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/server/sanitycheck.c,v
retrieving revision 1.72
diff -u -r1.72 sanitycheck.c
--- server/sanitycheck.c        18 Aug 2005 06:53:31 -0000      1.72
+++ server/sanitycheck.c        20 Aug 2005 18:30:59 -0000
@@ -75,6 +75,10 @@
     }
 
     SANITY_CHECK(pterrain->index >= T_FIRST && pterrain->index < T_COUNT);
+
+    if (contains_special(special, S_FORTRESS)) {
+      SANITY_CHECK(ptile->owner != NULL);
+    }
   } whole_map_iterate_end;
 }
 
@@ -139,6 +143,13 @@
     CHECK_MAP_POS(ptile->x, ptile->y);
     CHECK_NATIVE_POS(ptile->nat_x, ptile->nat_y);
 
+    if (ptile->city) {
+      SANITY_CHECK(ptile->owner != NULL);
+    }
+    if (ptile->owner != NULL) {
+      SANITY_CHECK(ptile->owner_source != NULL);
+    }
+
     index_to_map_pos(&x, &y, ptile->index);
     SANITY_CHECK(x == ptile->x && y == ptile->y);
 
Index: server/srv_main.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/server/srv_main.c,v
retrieving revision 1.287
diff -u -r1.287 srv_main.c
--- server/srv_main.c   18 Aug 2005 06:53:31 -0000      1.287
+++ server/srv_main.c   20 Aug 2005 18:31:00 -0000
@@ -667,6 +667,8 @@
     } players_iterate_end;
   }
 
+  map_calculate_borders();
+
   freelog(LOG_DEBUG, "Season of native unrests");
   summon_barbarians(); /* wild guess really, no idea where to put it, but
                          I want to give them chance to move their units */
Index: server/unittools.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/server/unittools.c,v
retrieving revision 1.375
diff -u -r1.375 unittools.c
--- server/unittools.c  13 Aug 2005 05:27:24 -0000      1.375
+++ server/unittools.c  20 Aug 2005 18:31:03 -0000
@@ -745,6 +745,7 @@
     if (total_activity (ptile, ACTIVITY_FORTRESS)
        >= tile_activity_time(ACTIVITY_FORTRESS, ptile)) {
       tile_set_special(ptile, S_FORTRESS);
+      map_claim_ownership(ptile, unit_owner(punit));
       unit_activity_done = TRUE;
       /* watchtower becomes effective */
       /* This could be a helper function. */