[Freeciv-Dev] (PR#9774) select_random_start_pos

["Mateusz Stefek" <mstefek@xxxxxxxxx>]

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

The method which is used to search for a starting position is too
inefective. It is based on the algorithm "lets pick a tile randomly and
check if it is valid. Try many times". 70% of choices are lost in ocean
and if game.numplayers is high it is very hard to hit the correct island
especially in gen2.
This solution adds an array of all tiles for every island. (into
islands[] array). When a starting position is chosen we select an island
first and select random tile on the island. This also means that the
probability of generator's failure is lower.

Here are some speed measures. (time consumed by create_start_positions)
I tested each settings 5 times with aifill = 30.
size/gen:old method in miliseconds,new method in miliseconds
4/1:240,120
4/2:4,10
29/2:0,20
4/4:110,10
10/5:680,310
--
mateusz



? core.27627
Index: mapgen.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/server/mapgen.c,v
retrieving revision 1.144
diff -u -r1.144 mapgen.c
--- mapgen.c    19 Aug 2004 07:34:25 -0000      1.144
+++ mapgen.c    23 Aug 2004 12:22:36 -0000
@@ -81,6 +81,12 @@
 struct isledata {
   int goodies;
   int starters;
+  int num_tiles;
+  /* list of all tiles */
+  struct coordinate {
+    unsigned char x;
+    unsigned char y;
+  }* tiles;
 };
 static struct isledata *islands;
 
@@ -1303,6 +1309,19 @@
 }
 
 /**************************************************************************
+ Free islands array and all data used by it.
+**************************************************************************/
+static void free_isledata(void)
+{
+  int i;
+  for (i = 1; i <= map.num_continents; i++) {
+    free(islands[i].tiles);
+  }
+  free(islands);
+  islands = NULL;
+}
+
+/**************************************************************************
  Allocate islands array and fill in values.
  Note this is only used for map.generator <= 1 or >= 5, since others
  setups islands and starters explicitly.
@@ -1409,6 +1428,42 @@
   }
 }
 
+/**************************************************************************
+  For each island create an array of all tiles it consist of
+**************************************************************************/
+static void setup_island_tiles()
+{
+  int counter[map.num_continents + 1];
+  int i;
+  
+  /* For each island count it's tiles */
+  whole_map_iterate(x, y) {
+    Continent_id cont;
+    cont = map_get_continent(x, y);
+    if (cont >= 1) {
+      islands[cont].num_tiles++;
+    }
+  } whole_map_iterate_end;
+  
+  /* Allocate memory */
+  for (i = 1; i <= map.num_continents; i++) {
+    islands[i].tiles = 
+      fc_malloc(islands[i].num_tiles * sizeof(struct coordinate));
+    counter[i] = 0;
+  }
+  
+  /* Fill arrays */
+  whole_map_iterate(x, y) {
+    Continent_id cont;
+    cont = map_get_continent(x, y);
+    if (cont >= 1) {
+      int index = counter[cont]++;
+      islands[cont].tiles[index].x = x;
+      islands[cont].tiles[index].y = y;
+    }
+  } whole_map_iterate_end;
+}
+
 struct start_filter_data {
   int count; /* Number of existing start positions. */
   int dist; /* Minimum distance between starting positions. */
@@ -1418,28 +1473,21 @@
   Return TRUE if (x,y) is a good starting position.
 
   Bad places:
-  - Islands with no room.
   - Non-suitable terrain;
   - On a hut;
   - Too close to another starter on the same continent:
     'dist' is too close (real_map_distance)
     'nr' is the number of other start positions in
     map.start_positions to check for too closeness.
+    
+  This function assumes that (x, y) is not an ocean and that the island
+  has got enough starting positions.
 **************************************************************************/
-static bool is_valid_start_pos(int x, int y, void *dataptr)
+static bool is_valid_start_pos(int x, int y, struct start_filter_data* data)
 {
-  struct start_filter_data *data = dataptr;
   int i;
   enum tile_terrain_type t = map_get_terrain(x, y);
 
-  if (is_ocean(map_get_terrain(x, y))) {
-    return FALSE;
-  }
-
-  if (islands[(int)map_get_continent(x, y)].starters == 0) {
-    return FALSE;
-  }
-
   /* Only start on certain terrain types. */
   if (!terrain_has_flag(t, TER_STARTER)) {
     return FALSE;
@@ -1467,6 +1515,41 @@
 }
 
 /**************************************************************************
+  Search for a good starting position. If the position is found store
+  it in (*x, *y) and return TRUE.
+  starters_left is the number of free starting positions left on the map.
+**************************************************************************/
+static bool select_random_start_pos(int* x, int* y, int starters_left,
+                                    struct start_filter_data* data)
+{
+  int i;
+  Continent_id cont;
+  
+  /* Select an island with starting position */
+  for (cont = 1; cont <= map.num_continents; cont++) {
+    if (islands[cont].starters > 0 && 
+        myrand(starters_left) <= islands[cont].starters - 1) {
+      break;
+    }
+    starters_left -= islands[cont].starters;
+  }
+  
+  assert(cont <= map.num_continents);
+  
+  /* Search for a good tile on the island */
+  for (i = 0; i < islands[cont].num_tiles; i++) {
+    int k = myrand(islands[cont].num_tiles);
+  
+    *x = islands[cont].tiles[k].x;
+    *y = islands[cont].tiles[k].y;
+    if (is_valid_start_pos(*x, *y, data)) {
+      return TRUE;
+    }
+  }
+  return FALSE;
+}
+
+/**************************************************************************
   where do the different races start on the map? well this function tries
   to spread them out on the different islands.
 **************************************************************************/
@@ -1479,6 +1562,8 @@
     /* Isle data is already setup for generators 2, 3, and 4. */
     setup_isledata();
   }
+  
+  setup_island_tiles();
 
   data.dist = MIN(40, MIN(map.xsize / 2, map.ysize / 2));
 
@@ -1496,7 +1581,7 @@
                                   game.nplayers
                                   * sizeof(*map.start_positions));
   while (data.count < game.nplayers) {
-    if (rand_map_pos_filtered(&x, &y, &data, is_valid_start_pos)) {
+    if (select_random_start_pos(&x, &y, sum - data.count, &data)) {
       islands[(int)map_get_continent(x, y)].starters--;
       map.start_positions[data.count].x = x;
       map.start_positions[data.count].y = y;
@@ -1517,8 +1602,7 @@
   }
   map.num_start_positions = game.nplayers;
 
-  free(islands);
-  islands = NULL;
+  free_isledata();
 }
 
 /****************************************************************************
@@ -2336,7 +2420,7 @@
 {
   int i;
   height_map = fc_malloc(sizeof(int) * map.ysize * map.xsize);
-  islands = fc_malloc((MAP_NCONT+1)*sizeof(struct isledata));
+  islands = fc_calloc((MAP_NCONT+1), sizeof(struct isledata));
 
   whole_map_iterate(x, y) {
     map_set_terrain(x, y, T_OCEAN);