[Freeciv-Dev] (PR#6965) civilwar_nations as alternative to misc_cities.ruleset

["Jason Short" <jdorje@xxxxxxxxxxxxxxxxxxxxx>]

<URL: http://rt.freeciv.org/Ticket/Display.html?id=6965 >

> [morgan - Fri Nov 28 05:35:24 2003]:

> Now that we have civilwar_nations I thought that this mechanism might
>    be a better way to supplement a nations citylist when it is
>    exhausted.
> 
> Eg:
> 
> A player is the Dutch.  He/she has built every city listed in the
>    dutch.ruleset and normally further names would be selected from the
>    misc_cities.ruleset (which currently seems to be a catalogue of
>    small-town America).
> 
> The Boer (amongst others) would be listed as a split off nation should
>    the Dutch nation ever have a civil war.
> 
> Further city names for the Dutch could be selected from the
>    Boer.ruleset, therefore providing much better consistancy.
> 
> Of course if the Boer are already in play then another alternative
>    could be considered from the list, with misc_cities.ruleset
>    remaining the ultimate backup.
> 
> Freeciv already handles duplicate city names so if the Boer suddenly
>    came into existence during play it shouldn't be a problem.

Well, here's a patch.

The patch adds the concept of "parent nations".  A parent nation is the
opposite of a civilwar nation.  It is included so that we can use both
parent and civilwar nations to choose cities from.

For instance, if the Dutch are out of city names, a Boer name may be
chosen.  If the Boer are out of city names, a Dutch name may be chosen.

This is recursive.  So a parent nation of a civilwar nation may be used
for its city names, if you have enough cities.

If we run out of parent and civilwar nations, we just use any nation. 
Thus misc.cities is no longer needed and is removed (a "cvs rm" should
be done on this file).

See the documentation in the patch for a more detailed explanation.  IMO
it is quite cool - the only drawback being that it takes about 50 extra
lines of code.

jason

P.S. Filipino should not be a civilwar_nation of America.

? diff
Index: common/nation.h
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/nation.h,v
retrieving revision 1.26
diff -u -r1.26 nation.h
--- common/nation.h     2003/09/21 14:02:14     1.26
+++ common/nation.h     2004/01/26 04:25:44
@@ -77,9 +77,11 @@
   char *class;                         /* may be empty */
   char *legend;                                /* may be empty */
 
-  /* NO_NATION_SELECTED-terminated list of index of the nations that can fork
-   * from this one.  Server only. */
-  Nation_Type_id *civilwar_nations;                
+  /* civilwar_nations is a NO_NATION_SELECTED-terminated list of index of
+   * the nations that can fork from this one.  parent_nations is the inverse
+   * of this array.  Server only. */
+  Nation_Type_id *civilwar_nations;
+  Nation_Type_id *parent_nations;
 
   /* untranslated copies: */
   char name_orig[MAX_LEN_NAME];
Index: data/civ1/nations.ruleset
===================================================================
RCS file: /home/freeciv/CVS/freeciv/data/civ1/nations.ruleset,v
retrieving revision 1.2
diff -u -r1.2 nations.ruleset
--- data/civ1/nations.ruleset   2002/03/30 02:43:51     1.2
+++ data/civ1/nations.ruleset   2004/01/26 04:25:44
@@ -65,5 +65,3 @@
 ; barbarians MUST go last
 ;
 *include "nation/barbarian.ruleset"
-
-*include "nation/misc_cities.ruleset"
Index: data/default/nations.ruleset
===================================================================
RCS file: /home/freeciv/CVS/freeciv/data/default/nations.ruleset,v
retrieving revision 1.63
diff -u -r1.63 nations.ruleset
--- data/default/nations.ruleset        2003/09/21 14:02:14     1.63
+++ data/default/nations.ruleset        2004/01/26 04:25:44
@@ -103,5 +103,3 @@
 ; barbarians MUST go last
 ;
 *include "nation/barbarian.ruleset"
-
-*include "nation/misc_cities.ruleset"
Index: server/citytools.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/server/citytools.c,v
retrieving revision 1.247
diff -u -r1.247 citytools.c
--- server/citytools.c  2004/01/17 04:29:14     1.247
+++ server/citytools.c  2004/01/26 04:25:45
@@ -63,8 +63,6 @@
 static bool update_city_tile_status(struct city *pcity, int city_x,
                                    int city_y);
 
-struct city_name *misc_city_names;
-
 /****************************************************************
 Returns the priority of the city name at the given position,
 using its own internal algorithm.  Lower priority values are
@@ -277,27 +275,99 @@
 *****************************************************************/
 char *city_name_suggestion(struct player *pplayer, int x, int y)
 {
-  char *name;
-  int i;
-  struct nation_type *nation = get_nation_by_plr(pplayer);
+  int i = 0, j;
   /* tempname must be static because it's returned below. */
   static char tempname[MAX_LEN_NAME];
+  bool nations_selected[game.nation_count];
+  Nation_Type_id nation_list[game.nation_count], n;
+  int queue_size;
 
   static const int num_tiles = MAP_MAX_WIDTH * MAP_MAX_HEIGHT; 
 
+  /* This function follows a straightforward algorithm to look through
+   * nations to find a city name.
+   *
+   * We start by adding the player's nation to the queue.  Then we proceed:
+   * - Pick a random nation from the queue.
+   * - If it has a valid city name, use that.
+   * - Otherwise, add all parent and child nations to the queue.
+   * - If the queue is empty, add all remaining nations to it and continue.
+   *
+   * Variables used:
+   * - nation_list is a queue of nations to look through.
+   * - nations_selected tells whether each nation is in the queue already
+   * - queue_size gives the size of the queue (number of nations in it).
+   * - i is the current position in the queue.
+   * Note that nations aren't removed from the queue after they're processed.
+   * New nations are just added onto the end.
+   */
+
   freelog(LOG_VERBOSE, "Suggesting city name for %s at (%d,%d)",
          pplayer->name, x, y);
   
   CHECK_MAP_POS(x,y);
 
-  name = search_for_city_name(x, y, nation->city_names, pplayer);
-  if (name) {
-    return name;
-  }
+  memset(nations_selected, 0, sizeof(nations_selected));
+
+  queue_size = 1;
+  nation_list[0] = pplayer->nation;
+  nations_selected[pplayer->nation] = TRUE;
+
+  while (i < game.nation_count) {
+    for (; i < queue_size; i++) {
+      struct nation_type *nation;
+      char *name;
+
+      {
+       /* Pick a random nation from the queue. */
+       const int which = i + myrand(queue_size - i);
+       const Nation_Type_id tmp = nation_list[i];
+
+       nation_list[i] = nation_list[which];
+       nation_list[which] = tmp;
+      }
+
+      nation = get_nation_by_idx(nation_list[i]);
+      name = search_for_city_name(x, y, nation->city_names, pplayer);
 
-  name = search_for_city_name(x, y, misc_city_names, pplayer);
-  if (name) {
-    return name;
+      freelog(LOG_NORMAL, "Looking through %s.", nation->name);
+
+      if (name) {
+       return name;
+      }
+
+      /* Append the nation's parent nations into the search tree. */
+      for (j = 0; nation->parent_nations[j] != NO_NATION_SELECTED; j++) {
+       n = nation->parent_nations[j];
+       if (!nations_selected[n]) {
+         nation_list[queue_size] = n;
+         nations_selected[n] = TRUE;
+         queue_size++;
+         freelog(LOG_NORMAL, "Parent %s.", get_nation_by_idx(n)->name);
+       }
+      }
+
+      /* Append the nation's civil war nations into the search tree. */
+      for (j = 0; nation->civilwar_nations[j] != NO_NATION_SELECTED; j++) {
+       n = nation->civilwar_nations[j];
+       if (!nations_selected[n]) {
+         nation_list[queue_size] = n;
+         nations_selected[n] = TRUE;
+         queue_size++;
+         freelog(LOG_NORMAL, "Child %s.", get_nation_by_idx(n)->name);
+       }
+      }
+    }
+
+    /* Append all remaining nations. */
+    for (n = 0; n < game.nation_count; n++) {
+      if (!nations_selected[n]) {
+       nation_list[queue_size] = n;
+       nations_selected[n] = TRUE;
+       queue_size++;
+       freelog(LOG_NORMAL, "Misc nation %s.", get_nation_by_idx(n)->name);
+      }
+    }
   }
 
   for (i = 1; i <= num_tiles; i++ ) {
Index: server/citytools.h
===================================================================
RCS file: /home/freeciv/CVS/freeciv/server/citytools.h,v
retrieving revision 1.49
diff -u -r1.49 citytools.h
--- server/citytools.h  2004/01/11 17:45:05     1.49
+++ server/citytools.h  2004/01/26 04:25:45
@@ -86,7 +86,6 @@
 bool is_allowed_city_name(struct player *pplayer, const char *city_name,
                          int x, int y, bool notify_player);
 char *city_name_suggestion(struct player *pplayer, int x, int y);
-extern struct city_name *misc_city_names;
 
 
 bool city_can_work_tile(struct city *pcity, int city_x, int city_y);
Index: server/ruleset.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/server/ruleset.c,v
retrieving revision 1.160
diff -u -r1.160 ruleset.c
--- server/ruleset.c    2004/01/11 17:45:05     1.160
+++ server/ruleset.c    2004/01/26 04:25:45
@@ -2427,8 +2427,28 @@
     }
   }
 
-  /* read miscellaneous city names */
-  misc_city_names = load_city_name_list(file, "misc.cities", "");
+  /* Calculate parent nations.  O(n^2) algorithm. */
+  for (i = 0; i < game.nation_count; i++) {
+    Nation_Type_id parents[game.nation_count];
+    int count = 0;
+
+    pl = get_nation_by_idx(i);
+    for (j = 0; j < game.nation_count; j++) {
+      struct nation_type *p2 = get_nation_by_idx(j);
+
+      for (k = 0; p2->civilwar_nations[k] != NO_NATION_SELECTED; k++) {
+       if (p2->civilwar_nations[k] == i) {
+         parents[count] = j;
+         count++;
+       }
+      }
+    }
+
+    assert(sizeof(parents[0]) == sizeof(*pl->parent_nations));
+    pl->parent_nations = fc_malloc((count + 1) * sizeof(parents[0]));
+    memcpy(pl->parent_nations, parents, count * sizeof(parents[0]));
+    pl->parent_nations[count] = NO_NATION_SELECTED;
+  }
 
   free(sec);
   section_file_check_unused(file, filename);
Index: server/srv_main.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/server/srv_main.c,v
retrieving revision 1.151
diff -u -r1.151 srv_main.c
--- server/srv_main.c   2004/01/23 03:14:45     1.151
+++ server/srv_main.c   2004/01/26 04:25:46
@@ -1710,7 +1710,5 @@
     player_map_free(pplayer);
   } players_iterate_end;
 
-  nation_city_names_free(misc_city_names);
-  misc_city_names = NULL;
   game_free();
 }