[Freeciv-Dev] Re: (PR#9774) select_random_start_pos

["Jason Short" <jdorje@xxxxxxxxxxxxxxxxxxxxx>]

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

Mateusz Stefek wrote:
> <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

This adds a lot of code and for what?  It cuts down mapgen time but by 
less than a second in these examples.  And it doesn't make the code any 
less likely to fail.

What would be better is something that had a definite termination point. 
  Create a list of tiles at the start, and make this list smaller

   struct map_position tiles[MAX_MAP_INDEX];
   int num_tiles = 0;

   whole_map_iterate(x, y) {
     if (!is_valid_start_pos(x, y)) {
       tiles[num_tiles].x = x;
       tiles[num_tiles].y = y;
       num_tiles++;
     }
   } whole_map_iterate_end;

   while (start_positions_needed > 0 && num_tiles > 0) {
     int index = myrand(num_tiles);
     struct map_position pos = tiles[index];

     num_tiles--;
     tiles[index] = tiles[num_tiles]

     if (is_valid_start_pos(pos.x, pos.y)) {
       add_start_pos(pos.x, pos.y);
     }
   }

This could be adjusted to search per-island if you like.

The following code:

+  /* 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;
+    }
+  }

in particular has no guarantee of succeeding I think.  If there's just 1 
valid position left on the island there's a good chance this loop won't 
find it.  However if you remove invalid start positions from the list as 
you find them the results will be much better I think.

jason