[Freeciv-Dev] (PR#9774) select_random_start_pos

["Mateusz Stefek" <mstefek@xxxxxxxxx>]

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

> [jdorje - Mon Aug 23 15:24:16 2004]:
> 
> 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.
Actually I'm writing more fair starting position code, but I'm facing
some performance problems. I think this will help me later.
> 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;

starting positions aren't independent.
This would take about 5 seconds on my computer (if it was called
successively for each staring position)!

>    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);
>      }
>    }

Starting positions aren't independent. You have to maximize the distance
beetwen them

> 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.

Agreed. It may fail. (n-1/n)^n -> 1/e
But that's how the current code works. My patch lowers n, but it's 
indefferent in most cases.

Some positions are invalid if data.dist == 30 and are valid if data.dist
== 20. So filtering them isn't that easy

> jason
--
mateusz