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

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

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

New patch, now with proper savegame support. This is implemented with all
new map saving code which does not use hexadecimal-transformation at all.
It is not pretty, but savegame.c never was. It adds a utility function
scanin() to utility/shared.c, which I wrote for another purpose and may be
overkill just for this, but which I think is quite neat and can have other
uses.

I think it is ready now.

  - Per

Index: utility/shared.c
===================================================================
--- utility/shared.c    (revision 11204)
+++ utility/shared.c    (working copy)
@@ -1570,3 +1570,62 @@
   return FALSE;
 }
 
+/**************************************************************************
+  Scan in a word or set of words from start to but not including
+  any of the given delimiters. The buf pointer will point past delimiter,
+  or be set to NULL if there is nothing there. Removes excess white
+  space.
+
+  This function should be safe, and dest will contain "\0" and
+  *buf == NULL on failure. We always fail gently.
+
+  Due to the way the scanning is performed, looking for a space
+  will give you the first word even if it comes before multiple
+  spaces.
+
+  Returns delimiter found.
+
+  Pass in NULL for dest and -1 for size to just skip ahead.  Note that if
+  nothing is found, dest will contain the whole string, minus leading and
+  trailing whitespace.  You can scan for "" to conveniently grab the
+  remainder of a string.
+**************************************************************************/
+char scanin(const char **buf, char *delimiters, char *dest, int size)
+{
+  char *ptr, found = '?';
+
+  if (*buf == NULL || strlen(*buf) == 0 || size == 0) {
+    if (dest) {
+      dest[0] = '\0';
+    }
+    *buf = NULL;
+    return '\0';
+  }
+
+  if (dest) {
+    strncpy(dest, *buf, size);
+    remove_leading_trailing_spaces(dest);
+    ptr = strpbrk(dest, delimiters);
+  } else {
+    /* Just skip ahead. */
+    ptr = strpbrk(*buf, delimiters);
+  }
+  if (ptr != NULL) {
+    found = *ptr;
+    if (dest) {
+      *ptr = '\0';
+    }
+    if (dest) {
+      remove_leading_trailing_spaces(dest);
+    }
+    *buf = strpbrk(*buf, delimiters);
+    if (*buf != NULL) {
+      (*buf)++; /* skip delimiter */
+    } else {
+    }
+  } else {
+    *buf = NULL;
+  }
+
+  return found;
+}
Index: utility/shared.h
===================================================================
--- utility/shared.h    (revision 11204)
+++ utility/shared.h    (working copy)
@@ -228,5 +228,7 @@
 
 bool make_dir(const char *pathname);
 bool path_is_absolute(const char *filename);
+
+char scanin(const char **buf, char *delimiters, char *dest, int size);
 #endif  /* FC__SHARED_H */
 
Index: server/srv_main.c
===================================================================
--- server/srv_main.c   (revision 11204)
+++ server/srv_main.c   (working copy)
@@ -666,6 +666,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/citytools.c
===================================================================
--- server/citytools.c  (revision 11204)
+++ server/citytools.c  (working copy)
@@ -810,11 +810,9 @@
   /* Has to follow the unfog call above. */
   city_list_unlink(pgiver->cities, pcity);
   pcity->owner = ptaker;
+  map_claim_ownership(pcity->tile, ptaker, pcity->tile);
   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);
@@ -930,6 +928,9 @@
 
   freelog(LOG_DEBUG, "Creating city %s", name);
 
+  /* Ensure that we claim the ground we stand on */
+  map_claim_ownership(ptile, pplayer, ptile);
+
   if (terrain_control.may_road) {
     tile_set_special(ptile, S_ROAD);
     if (player_knows_techs_with_flag(pplayer, TF_RAILROAD)) {
@@ -987,10 +988,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. */
@@ -1139,7 +1136,6 @@
   old_vision = pcity->server.vision;
   pcity->server.vision = NULL;
   game_remove_city(pcity);
-  map_update_borders_city_destroyed(ptile);
 
   players_iterate(other_player) {
     if (map_is_known_and_seen(ptile, other_player, V_MAIN)) {
Index: server/maphand.c
===================================================================
--- server/maphand.c    (revision 11204)
+++ server/maphand.c    (working copy)
@@ -1013,6 +1013,8 @@
 
   Note this only checks for changing of the terrain or special for the
   tile, since these are the only values held in the playermap.
+
+  A tile's owner always can see terrain changes in his or her territory.
 ****************************************************************************/
 void update_tile_knowledge(struct tile *ptile)
 {
@@ -1407,71 +1409,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;
@@ -1479,48 +1454,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.
 
@@ -1537,146 +1470,177 @@
 }
 
 /*************************************************************************
-  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;
+  /* Update happiness */
+ unit_list_iterate(tile1->units, unit) {
+   struct city* homecity = find_city_by_id(unit->homecity);
+   bool already_listed = FALSE;
 
-      if (new_owner != tile_get_owner(tile1)) {
-       tile_set_owner(tile1, new_owner);
-       /* Note we call send_tile_info, not update_tile_knowledge here.
-        * Borders information is sent to everyone who has seen the tile
-        * before; it's not stored in the playermap. */
-       send_tile_info(NULL, 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;
-           
-           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);
+      if (!already_listed) {
+        city_list_prepend(cities_to_refresh, homecity);
+      }
     } city_list_iterate_end;
-    
-    city_list_unlink_all(cities_to_refresh);
-    city_list_free(cities_to_refresh);
-  }
+  } unit_list_iterate_end;
 }
 
 /*************************************************************************
-  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.
+  Claim ownership of a single tile.  This does no checks.
 *************************************************************************/
-void map_update_borders_city_destroyed(struct tile *ptile)
+void map_claim_ownership(struct tile *ptile, struct player *owner,
+                         struct tile *source)
 {
-  map_update_borders_recalculate_position(ptile);
+  ptile->owner_source = source;
+  tile_set_owner(ptile, owner);
+  send_tile_info(NULL, ptile);
+  tile_update_owner(ptile);
 }
 
 /*************************************************************************
-  Modify national territories resulting from a change of landmass.
-  Tile worker states are updated as necessary, but not sync'd with client.
+  Establish range of a city's borders.
 *************************************************************************/
-void map_update_borders_landmass_change(struct tile *ptile)
+static inline int tile_border_range(struct tile *ptile)
 {
-  map_update_borders_recalculate_position(ptile);
-}
+  int range;
 
-/*************************************************************************
-  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);
+  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;
+  }
+  return range;
 }
 
 /*************************************************************************
-  Delete the territorial claims to all tiles.
+  Update borders for all sources.  Call this on turn end.
+
+  We will remove claim to land whose source is gone, and claim
+  more land to 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 transfer remove undue ownership.  We transfer ownership from
+   * a removed source to another source if we find another source within
+   * range owned by the same player. */
   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, 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();
+  /* Now claim ownership of unclaimed tiles for all sources; we
+   * grab one circle each turn as long as we have range left
+   * to better visually displaying expansion hurdles. */
+  whole_map_iterate(ptile) {
+#ifdef DEBUG
+    if (ptile->owner == NULL
+        && (ptile->city || tile_has_special(ptile, S_FORTRESS))) {
+      /* Sanity problem */
+      freelog(LOG_ERROR, "city or fortress at (%d, %d) has no owner",
+              ptile->x, ptile->y);
+      assert(FALSE);
+      continue;
+    }
+#endif
+    if (ptile->owner
+        && (ptile->city || tile_has_special(ptile, S_FORTRESS))) {
+      /* We have an ownership source */
+      int expand_range = 99;
+      int found_unclaimed = 99;
+      int range = tile_border_range(ptile);
 
-  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);
+      freelog(LOG_DEBUG, "source at %d,%d", ptile->x, ptile->y);
+      range *= range; /* due to sq dist */
+      freelog(LOG_DEBUG, "borders range for source is %d", range);
 
-       if (pccity) {
-         tile_set_owner(ptile, pccity->owner);
-       }
-      } iterate_outward_end;
-    } cities_iterate_end;
-  }
-}
+      circle_dxyr_iterate(ptile, range, atile, dx, dy, dist) {
+        if (expand_range > dist) {
+          unit_list_iterate(atile->units, punit) {
+            if (!pplayers_allied(unit_owner(punit), ptile->owner)) {
+              /* We cannot expand borders further when enemy units are
+               * standing in the way. */
+              expand_range = dist - 1;
+            }
+          } unit_list_iterate_end;
+        }
+        if (found_unclaimed > dist
+            && atile->owner == NULL
+            && map_is_known(atile, ptile->owner)
+            && (!is_ocean(atile->terrain)
+                || is_claimable_ocean(atile, ptile))) {
+          found_unclaimed = dist;
+        }
+      } circle_dxyr_iterate_end;
+      freelog(LOG_DEBUG, "expand_range=%d found_unclaimed=%d", expand_range,
+              found_unclaimed);
 
-/*************************************************************************
-  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();
+      circle_dxyr_iterate(ptile, range, atile, dx, dy, dist) {
+        if (dist > expand_range || dist > found_unclaimed) {
+          continue; /* only expand one extra circle radius each turn */
+        }
+        if (map_is_known(atile, ptile->owner)) {
+          if (atile->owner == NULL) {
+            if (!is_ocean(atile->terrain)
+                || is_claimable_ocean(atile, ptile)) {
+              map_claim_ownership(atile, ptile->owner, ptile);
+              atile->owner_source = ptile;
+              if (game.info.happyborders > 0) {
+                add_unique_homecities(cities_to_refresh, atile);
+              }
+            }
+          } else if (atile->owner == ptile->owner
+                     && sq_map_distance(ptile, atile) 
+                        < sq_map_distance(atile->owner_source, atile)) {
+            /* Steal tiles from your own cities when they are closer
+             * to this source than to its current source. This makes
+             * sure that when a source is lost, borders close to
+             * other sources will not go lost as well. */
+            atile->owner_source = ptile;
+          }
+        }
+      } circle_dxyr_iterate_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
===================================================================
--- server/maphand.h    (revision 11204)
+++ server/maphand.h    (working copy)
@@ -91,10 +91,9 @@
 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,
+                         struct tile *source);
 
 void check_terrain_change(struct tile *ptile, struct terrain *oldter);
 int get_continent_size(Continent_id id);
Index: server/unittools.c
===================================================================
--- server/unittools.c  (revision 11204)
+++ server/unittools.c  (working copy)
@@ -693,6 +693,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), ptile);
       unit_activity_done = TRUE;
 
       /* watchtower becomes effective
@@ -2702,6 +2703,12 @@
                        get_unit_vision_at(punit, pdesttile, v));
   } vision_layer_iterate_end;
 
+  /* Claim ownership of fortress? */
+  if (tile_has_special(pdesttile, S_FORTRESS)
+      && pplayers_at_war(pdesttile->owner, pplayer)) {
+    map_claim_ownership(pdesttile, pplayer, pdesttile);
+  }
+
   unit_list_unlink(psrctile->units, punit);
   punit->tile = pdesttile;
   punit->moved = TRUE;
Index: server/sanitycheck.c
===================================================================
--- server/sanitycheck.c        (revision 11204)
+++ server/sanitycheck.c        (working copy)
@@ -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;
 }
 
@@ -144,6 +148,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/savegame.c
===================================================================
--- server/savegame.c   (revision 11204)
+++ server/savegame.c   (working copy)
@@ -62,6 +62,8 @@
 #include "techtools.h"
 #include "unittools.h"
 
+#define TOKEN_SIZE 10
+
 /* 
  * This loops over the entire map to save data. It collects all the data of
  * a line using GET_XY_CHAR and then executes the macro SECFILE_INSERT_LINE.
@@ -86,8 +88,8 @@
                                                                             \
   for (_nat_y = 0; _nat_y < map.ysize; _nat_y++) {                         \
     for (_nat_x = 0; _nat_x < map.xsize; _nat_x++) {                       \
-      struct tile *ptile = native_pos_to_tile(_nat_x, _nat_y);             \
-                                                                           \
+      struct tile *ptile = native_pos_to_tile(_nat_x, _nat_y);                 
  \
+      assert(ptile != NULL);                                                \
       line[_nat_x] = (GET_XY_CHAR);                                         \
       if (!my_isprint(line[_nat_x] & 0x7f)) {                               \
           die("Trying to write invalid map "                                \
@@ -184,8 +186,9 @@
    and rulesets */
 #define SAVEFILE_OPTIONS "startoptions spacerace2 rulesets" \
 " diplchance_percent map_editor known32fix turn " \
-"attributes rulesetdir client_worklists orders " \
-"startunits turn_last_built improvement_order technology_order embassies"
+"attributes watchtower rulesetdir client_worklists orders " \
+"startunits turn_last_built improvement_order technology_order embassies " \
+"new_owner_map"
 
 static const char hex_chars[] = "0123456789abcdef";
 
@@ -726,6 +729,70 @@
                secfile_lookup_str_default(file, NULL, "map.f%03d", nat_y),
                set_savegame_special(&ptile->special, ch, 3));
 
+  /* Owner and ownership source are stored as plain numbers */
+  if (has_capability("new_owner_map", savefile_options)) {
+    int x, y;
+
+    for (y = 0; y < map.ysize; y++) {
+      char *buffer = 
+            secfile_lookup_str_default(file, NULL, "map.owner%03d", y);
+      const char *ptr = buffer;
+
+      if (buffer == NULL) {
+        die("Savegame corrupt - map line %d not found.", y);
+      }
+      for (x = 0; x < map.xsize; x++) {
+        char token[TOKEN_SIZE];
+        int number;
+        struct tile *ptile = native_pos_to_tile(x, y);
+
+        scanin(&ptr, ",", token, sizeof(token));
+        if (token[0] == '\0') {
+          die("Savegame corrupt - map size not correct.");
+        }
+        if (strcmp(token, "-") == 0) {
+          ptile->owner = NULL;
+        } else {
+          if (sscanf(token, "%d", &number)) {
+            ptile->owner = get_player(number);
+          } else {
+            die("Savegame corrupt - got map owner %s in (%d, %d).", 
+                token, x, y);
+          }
+        }
+      }
+    }
+    for (y = 0; y < map.ysize; y++) {
+      char *buffer2 = 
+            secfile_lookup_str_default(file, NULL, "map.source%03d", y);
+      const char *ptr2 = buffer2;
+
+      if (buffer2 == NULL) {
+        die("Savegame corrupt - map line %d not found.", y);
+      }
+      for (x = 0; x < map.xsize; x++) {
+        char token2[TOKEN_SIZE];
+        int number;
+        struct tile *ptile = native_pos_to_tile(x, y);
+
+        scanin(&ptr2, ",", token2, sizeof(token2));
+        if (token2[0] == '\0') {
+          die("Savegame corrupt - map size not correct.");
+        }
+        if (strcmp(token2, "-") == 0) {
+          ptile->owner_source = NULL;
+        } else {
+          if (sscanf(token2, "%d", &number)) {
+            ptile->owner_source = index_to_tile(number);
+          } else {
+            die("Savegame corrupt - got map source %s in (%d, %d).", 
+                token2, x, y);
+          }
+        }
+      }
+    }
+  }
+
   if (secfile_lookup_bool_default(file, TRUE, "game.save_known")) {
     int known[MAP_INDEX_SIZE];
 
@@ -840,6 +907,52 @@
   SAVE_NORMAL_MAP_DATA(ptile, file, "map.n%03d",
                       get_savegame_special(ptile->special, 2));
 
+  /* Store owner and ownership source as plain numbers */
+  {
+    int x, y;
+
+    for (y = 0; y < map.ysize; y++) {
+      char line[map.xsize * TOKEN_SIZE];
+
+      line[0] = '\0';
+      for (x = 0; x < map.xsize; x++) {
+        char token[TOKEN_SIZE];
+        struct tile *ptile = native_pos_to_tile(x, y);
+
+        if (ptile->owner == NULL) {
+          strcpy(token, "-");
+        } else {
+          snprintf(token, sizeof(token), "%d", ptile->owner->player_no);
+        }
+        strcat(line, token);
+        if (x + 1 < map.xsize) {
+          strcat(line, ",");
+        }
+      }
+      secfile_insert_str(file, line, "map.owner%03d", y);
+    }
+    for (y = 0; y < map.ysize; y++) {
+      char line[map.xsize * TOKEN_SIZE];
+
+      line[0] = '\0';
+      for (x = 0; x < map.xsize; x++) {
+        char token[TOKEN_SIZE];
+        struct tile *ptile = native_pos_to_tile(x, y);
+
+        if (ptile->owner_source == NULL) {
+          strcpy(token, "-");
+        } else {
+          snprintf(token, sizeof(token), "%d", ptile->index);
+        }
+        strcat(line, token);
+        if (x + 1 < map.xsize) {
+          strcat(line, ",");
+        }
+      }
+      secfile_insert_str(file, line, "map.source%03d", y);
+    }
+  }
+
   secfile_insert_bool(file, game.save_options.save_known, "game.save_known");
   if (game.save_options.save_known) {
     int known[MAP_INDEX_SIZE];
@@ -1971,6 +2084,7 @@
 
     pcity = create_city_virtual(plr, ptile,
                       secfile_lookup_str(file, "player%d.c%d.name", plrno, i));
+    map_claim_ownership(ptile, plr, ptile);
 
     pcity->id=secfile_lookup_int(file, "player%d.c%d.id", plrno, i);
     alloc_id(pcity->id);
@@ -3607,9 +3721,6 @@
     initialize_globals();
     apply_unit_ordering();
 
-    /* Rebuild national borders. */
-    map_calculate_borders();
-
     /* Make sure everything is consistent. */
     players_iterate(pplayer) {
       unit_list_iterate(pplayer->units, punit) {
Index: common/city.c
===================================================================
--- common/city.c       (revision 11204)
+++ common/city.c       (working copy)
@@ -753,6 +753,12 @@
     return FALSE;
   }
 
+  if (ptile->owner && ptile->owner != punit->owner) {
+    /* Cannot steal borders by settling. This has to be settled by
+     * force of arms. */
+    return FALSE;
+  }
+
   /* game.info.min_dist_bw_cities minimum is 1, meaning adjacent is okay */
   citymindist = game.info.citymindist;
   if (citymindist == 0) {
Index: common/tile.h
===================================================================
--- common/tile.h       (revision 11204)
+++ common/tile.h       (working copy)
@@ -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: common/map.c
===================================================================
--- common/map.c        (revision 11204)
+++ common/map.c        (working copy)
@@ -278,6 +278,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/game.h
===================================================================
--- common/game.h       (revision 11204)
+++ common/game.h       (working copy)
@@ -205,11 +205,10 @@
 
 #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         4
 #define GAME_MIN_BORDERS             0
-#define GAME_MAX_BORDERS             24
+#define GAME_MAX_BORDERS             12
 
 #define GAME_DEFAULT_HAPPYBORDERS    TRUE
 
Index: common/map.h
===================================================================
--- common/map.h        (revision 11204)
+++ common/map.h        (working copy)
@@ -337,6 +337,8 @@
 #define circle_iterate_end                                                  \
   circle_dxyr_iterate_end
 
+/* dx, dy, dr are distance from center to tile in x, y and square distance;
+ * do not rely on x, y distance, since they do not work for hex topologies */
 #define circle_dxyr_iterate(center_tile, sq_radius,                        \
                            tile_itr, dx, dy, dr)                           \
 {                                                                          \