[Freeciv-Dev] new function create_start_positions

[Schilder <Frank.Schilder@xxxxxxxxxxxxxxxxxxxxxxxx>]

----------
X-Sun-Data-Type: text
X-Sun-Data-Description: text
X-Sun-Data-Name: text
X-Sun-Charset: us-ascii
X-Sun-Content-Lines: 12

I did rewrite the algorithms for setting up the start positions
because the default created unfaif and therefore boring games.

I did not create a diff because the changes are too simple,
I submit the new functions as an attachment.

The changes affect the file mapgen.c only so they should be easy
to incorporate. The attached file contains detailed comments.

I would like to hear about the success. God luck.

Frank
----------
X-Sun-Data-Type: c-source
X-Sun-Data-Name: mapgen.c
X-Sun-Charset: us-ascii
X-Sun-Content-Lines: 317

### replace this new definition of isledata:

/*
This struct has been extended with the field tmp. --Frank
*/

struct isledata {
  int x,y;                        /* upper left corner of the islands */
  int goodies;
  int starters;
  int tmp;
};

### replace the two functions setup_isledata and create_start_positions
### with the following code:

/**************************************************************************
 Allocate islands array and fill in values.
 Note this is only use for map.generator<=1, since others
 setups islands and starters explicitly.
**************************************************************************/
static void setup_isledata(void)
{
  int x,y;
  int goods_per_player;
  int riches;
  int starters = 0;
  int isles;
  int firstcont;
  int i;

  assert(map.num_continents>0);
  
  /* allocate + 1 so can use continent number as index */
  islands = fc_malloc((map.num_continents+1)*sizeof(struct isledata));

  /* initialize: */
  for(i=0; i<=map.num_continents; i++) {
    islands[i].x = islands[i].y = -1;             /* flag */
    islands[i].goodies = islands[i].starters = 0;
  }

  /* get x and y positions: (top left) */
  for (y=0; y<map.ysize; y++) {
    for (x=0; x<map.xsize; x++) {
      int cont = map_get_continent(x, y);
      if (islands[cont].x == -1) {
  islands[cont].x = x;
  islands[cont].y = y;
      }
    }
  }

  /* Add up the goodies: for useable ocean, add value to continent
     for _every_ adjacent land tile.  This is IMO not very good,
     because it adds potentially many times, and usable sea of
     distance 2 from land is ignored, but this re-produces the
     results of the previous method which used flood_fill().  --dwp
     This is also the correct place to add S_HUT bonus.
  */
  for (y=0; y<map.ysize; y++) {
    for (x=0; x<map.xsize; x++) {
      int cont = map_get_continent(x, y);
      if (cont) {
  islands[cont].goodies += is_good_tile(x, y);
  if (map_get_special(x,y) & S_HUT) {
    islands[cont].goodies += 0; /* 3; */   /* regression testing */
  }
      } else {
  assert(map_get_terrain(x, y)==T_OCEAN);
  /* no need to check is_sea_usable(x,y), because will
     only use for adjacent land (cont1>0) below */
/*
This part has been removed because for small islands it generated a too
high value. The effect of ocean is accounted indirectly, see below. --Frank
*/
      }
    }
  }
  
  /* the arctic and the antarctic are continents 1 and 2 for generator>0*/
  if (map.generator>0) {
    firstcont = 3;
  } else {
    firstcont = 1;
  }
  isles = map.num_continents+1;
 
  riches=0;
  for (x=firstcont; x<isles; x++) {
      riches+=islands[x].goodies;
  }

  for (x=firstcont;x<isles;x++) {
      freelog(LOG_VERBOSE, _("goods on isle %i : %i"), x, islands[x].goodies);
    }

/*
Calculate the number of starting positions for each island. We try to allocate
(2/3) of the average goods for each player. If this fails we successively retry
with a value decremented by 1. We stop if we get at least game.nplayers 
positions.
This algorithm will always succeed. --Frank
*/

  goods_per_player = (2*riches) / (3*game.nplayers);
  starters = 0;

  while( starters<game.nplayers ) /* not enough start positions */
    {
    starters= 0;

    for (x=firstcont;x<isles;x++) islands[x].starters=0; /* initialize */

    for (x=firstcont; x<isles; x++)
      {
      if (islands[x].goodies >= goods_per_player) /* enough resources? */
        {
        assert(!islands[x].starters);
        freelog(LOG_VERBOSE, "islands[x].goodies=%i", islands[x].goodies);

        /*
        If an island can support at least one player we calculate the maximum
        number of players that can be supported. We give 20% more land for
        isles with at least two players. This takes into account the strategic
        advantage of being alone on an island. It also accounts fairly for
        usable ocean tiles - smaller islands have a comparatively larger
        number of usable ocean tiles. The value 20% gave very fair results
        in tests - especially for the critical start of the game. --Frank
        */
        
        islands[x].starters = ((4*islands[x].goodies)/goods_per_player)/5;
        if(islands[x].starters <= 0) islands[x].starters = 1;
        starters+= islands[x].starters;
        }
      }

    if(starters<game.nplayers)
      {
      /*
      We did not get enough start positions and retry with one less resource
      per player. Although this may seem slow - it is fast enough. --Frank
      */
      
      --goods_per_player;
      starters = 0;
      }
    
    if(goods_per_player <= 0)
      {
      /*
      The algorithm is guaranteed to terminate. This is only for the case ...
                                                                      --Frank
      */
      
      freelog(LOG_FATAL, "could not find start positions.");
      abort();
      }
    
    }
}

/**************************************************************************
  where do the different races start on the map? well this function tries
  to spread them out on the different islands.
**************************************************************************/

/*
This help function maps an arbitrary x-value into a world-coordinate.
It is called from within create_start_positions. --Frank
*/

static int get_map_coord(int x)
  {
  while(x>=map.xsize) x-=map.xsize;
  return x;
  }

/*
This function calculates the start positions for each player. It tries to
create start positions with maximum distance. The algorithm is probably
far from being optimal but gives very fair results. But this seems almost
better than to restart a game often to get a fair start.

The algorithm is more or less simple. Instead of using random positions
we seek positions on a grid with a mesh size equal or larger than 1. On this
grid we seek start positions that have a distance greater or equal to dist.
If the meshsize is larger than 1 we try any position for the top left point
of our grid. This takes much time but gives excellent results.

The algorithm is fast if each player has its own island and slows down
otherwise.                                                  --Frank
*/

void create_start_positions(void)
{
  int nr=0;
  int dist=40;
  int x, xb, y, k, sum, inc_x=1, inc_y=1, xs, ys;

  if (islands==NULL)    /* already setup for generator>1 */
    setup_isledata();

  /*
  We start with the maximum distance possible. This works more often than you
  might think!                                                       --Frank
  */
  dist  = map.ysize;

  sum=0;
  for (k=0; k<=map.num_continents; k++) {
    sum += islands[k].starters;
    if (islands[k].starters!=0) {
      freelog(LOG_VERBOSE, "starters on isle %i", k);
    }
  }
  assert(game.nplayers<=nr+sum);

  /*
  Try until we have our start positions.
  The algorithm is guaranteed to terminate. --Frank
  */
  
  while (nr<game.nplayers)
    {
    /*
    Calculate the mesh size. The given initial values seem to be good
    start values. There is in general no solution with a larger mesh-size. 
--Frank
    */
    
    inc_x = map.xsize/(game.nplayers+1);
    inc_y = map.ysize/(game.nplayers+1);
    if(inc_x == 0) inc_x=1;
    if(inc_y == 0) inc_y=1;

    /* Try as long as we have a valid grid. */
    
    while(inc_x+inc_y >= 2)
      {
      for(xs=0; xs<=inc_x; xs++) for(ys=0; ys<=inc_y; ys++)
        {
        /*
        This is the part where the time goes. We want to get valid start 
positions
        on the same grid So we forget the previous result. This is also the part
        where the high quality comes from.                                
--Frank
        */
        
        for (k=0; k<=map.num_continents; k++) islands[k].tmp = 
islands[k].starters;
        nr = 0;

        for(xb=xs; xb<map.xsize; xb+=inc_x)
          for(x=xb, y=ys; y<map.ysize; x+=inc_x, y+=inc_y)
          
          /* We step trough our grid and are happy about every hit. --Frank */
          
            if( islands[(int)map_get_continent(get_map_coord(5*x), y)].tmp )
              {
              if (!is_starter_close(get_map_coord(5*x), y, nr, dist))
                {
                islands[(int)map_get_continent(get_map_coord(5*x), y)].tmp--;
                map.start_positions[nr].x=get_map_coord(5*x);
                map.start_positions[nr].y=y;
                nr++;

                /* Puh, we are finished. Quick escape.   --Frank*/

                if(nr >= game.nplayers) goto finish;
                }
              }
        }

      /*
      If we are here we did not get a result. Reduce the larger mesh-size and
      hope for the best.                                           --Frank
      */
      
      if(inc_x < inc_y)
        --inc_y;
      else 
        --inc_x;

/*      freelog(LOG_NORMAL, _("dist %i, grid sizes: %i %i."), dist, inc_x, 
inc_y);
      freelog(LOG_NORMAL, _("found %i start positions with distance %i."), nr, 
dist); */
      
      }

    /*
    If all our effort did not give a result, we try a smaller distance and start
    working again.                                                       --Frank
    */
    
    dist--;

    if (dist == 0 )
      {
      /*
      As I said before - the algorithm will never fail ...         --Frank
      */
      
       freelog(LOG_FATAL,
        "The server appears to have gotten into an infinite loop "
        "in the allocation of starting positions, and will abort.\n"
        "Please report this bug at " WEBSITE_URL);
       abort();
       }
    }

  finish:
  
  freelog(LOG_VERBOSE, _("found %i start positions with distance %i, grid size: 
%i,%i."),
    nr, dist, inc_x, inc_y);

  map.num_start_positions = game.nplayers;

  free(islands);
  islands = NULL;
}