Index: server/mapgen.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/server/mapgen.c,v
retrieving revision 1.63
diff -u -r1.63 mapgen.c
--- mapgen.c	2001/01/28 22:09:44	1.63
+++ mapgen.c	2001/02/27 21:56:52
@@ -59,6 +59,7 @@
   int x,y;                        /* upper left corner of the islands */
   int goodies;
   int starters;
+  int tmp;
 };
 static struct isledata *islands;
 
@@ -970,36 +971,32 @@
 **************************************************************************/
 static void setup_isledata(void)
 {
-  int x,y;
-  int good, mingood, maxgood;
+  int goods_per_player;
   int riches;
-  int starters;
-  int isles, oldisles, goodisles;
-  int guard1=0;
+  int starters = 0;
+  int isles;
   int firstcont;
   int i;
 
-  assert(map.num_continents>0);
-  
+  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++) {
+  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;
-      }
+  whole_map_iterate(x, y) {
+    int cont = map_get_continent(x, y);
+    if (islands[cont].x == -1) {
+      islands[cont].x = x;
+      islands[cont].y = y;
     }
-  }
+  } whole_map_iterate_end;
 
   /* Add up the goodies: for useable ocean, add value to continent
      for _every_ adjacent land tile.  This is IMO not very good,
@@ -1008,33 +1005,17 @@
      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 */
-	{
-	  int goodval = is_good_tile(x, y);
-	  int x1, y1;
-	  for (x1=-1; x1<=1; x1++) {
-	    for (y1=-1; y1<=1; y1++) {
-	      int cont1 = map_get_continent(x+x1, y+y1);
-	      if (cont1>0) {  
-		islands[cont1].goodies += goodval;
-	      }
-	    }
-	  }
-	}
+  whole_map_iterate(x, y) {
+    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);
     }
-  }
+  } whole_map_iterate_end;
   
   /* the arctic and the antarctic are continents 1 and 2 for generator>0*/
   if (map.generator>0) {
@@ -1045,148 +1026,178 @@
   isles = map.num_continents+1;
  
   riches=0;
-  for (x=firstcont; x<isles; x++) {
-      riches+=islands[x].goodies;
+  for (i=firstcont; i<isles; i++) {
+    riches += islands[i].goodies;
   }
+
+  for (i=firstcont; i<isles; i++) {
+    freelog(LOG_VERBOSE, _("goods on isle %i : %i"), i, islands[i].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
+  */
 
-  starters= 100; oldisles= isles+1; goodisles= isles;
-  while( starters>game.nplayers && oldisles>goodisles ){
-    freelog(LOG_VERBOSE, "goodisles=%i", goodisles);
-    oldisles= goodisles;
-    maxgood= 1;
-    mingood= riches;
-    good=0; 
-    goodisles=0;
+  goods_per_player = (2*riches) / (3*game.nplayers);
+  starters = 0;
+
+  while (starters < game.nplayers) { /* not enough start positions */
     starters= 0;
 
+    for (i=firstcont; i<isles; i++) islands[i].starters=0; /* initialize */
 
-    /* goody goody */
-    for (x=firstcont;x<isles;x++) {	  
-      islands[x].starters=0;
-      if ( islands[x].goodies > (riches+oldisles-1)/oldisles ) 
-	{ 
-	  good+=islands[x].goodies; 
-	  goodisles++; 
-	  if(mingood>islands[x].goodies)
-	    mingood= islands[x].goodies;
-	  if(maxgood<islands[x].goodies)
-	    maxgood= islands[x].goodies;
-	}
-    }
-  
-    if(mingood+1<maxgood/game.nplayers)
-      mingood= maxgood/game.nplayers; 
+    for (i=firstcont; i<isles; i++) {
+      if (islands[i].goodies >= goods_per_player) { /* enough resources? */
+        assert(!islands[i].starters);
+        freelog(LOG_VERBOSE, "islands[i].goodies=%i", islands[i].goodies);
 
-    if(goodisles>game.nplayers){
-      /* bloody goodies */   
-      for (x=firstcont;x<isles;x++) {
-	if (( islands[x].goodies*4 > 3*(riches+oldisles-1)/oldisles )
-	    &&!(islands[x].goodies > (riches+oldisles-1)/oldisles)
-	    )
-	  { 
-	    good+=islands[x].goodies; 
-	    goodisles++; 
-	    if(mingood>islands[x].goodies)
-	      mingood= islands[x].goodies;
-	  }
-      }
-  
- 
-      /* starters are loosers */
-      for (x=firstcont;x<isles;x++) {
-	if (( islands[x].goodies*4 > 3*(riches+oldisles-1)/oldisles )
-	    &&!(islands[x].goodies > (riches+oldisles-1)/oldisles)) {
-	  freelog(LOG_VERBOSE, "islands[x].goodies=%i",islands[x].goodies);
-	  islands[x].starters= (islands[x].goodies+guard1)/mingood; 
-	  if(!islands[x].starters) {
-	    islands[x].starters+= 1;/* ?PS: may not be enough, guard1(tm) */
-	  }
-	  starters+= islands[x].starters;
-	}
+        /* 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[i].starters = ((4*islands[i].goodies)/goods_per_player)/5;
+        if (islands[i].starters <= 0) islands[i].starters = 1;
+        starters+= islands[i].starters;
       }
     }
 
-    /* starters are winners */
-    for (x=firstcont;x<isles;x++) {
-      if (islands[x].goodies > (riches+oldisles-1)/oldisles) {
-	assert(!islands[x].starters);
-	freelog(LOG_VERBOSE, "islands[x].goodies=%i", islands[x].goodies);
-	islands[x].starters = (islands[x].goodies+guard1)/mingood; 
-	if(!islands[x].starters) {
-	  islands[x].starters+= 1;/* ?PS: may not be enough, guard1(tm) */
-	}
-	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;
     }
 
-    riches= good;
-    if(starters<game.nplayers){
-      starters= game.nplayers+1;
-      goodisles=oldisles; 
-      oldisles= goodisles+1;
-      riches= (4*riches+3)/3;
-      if(mingood/game.nplayers>5) {
-	guard1+= mingood/game.nplayers;
-      } else {
-	guard1+=5;
-      }
-      freelog(LOG_NORMAL,
-	      _("Map generator: not enough start positions, fixing."));
+    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();
     }
   }
-  freelog(LOG_NORMAL, _("The map has %i starting positions on %i isles."),
-	  starters, goodisles);
 }
 
 /**************************************************************************
-  where do the different races start on the map? well this function tries
+  Where do the different races start on the map? well this function tries
   to spread them out on the different islands.
+
+  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
 **************************************************************************/
-#define MAXTRIES 1000000
 void create_start_positions(void)
 {
-  int nr=0;
-  int dist=40;
-  int x, y, j=0, k, sum;
-  int counter = 0;
+  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 */
+  if (islands==NULL)    /* already setup for generator>1 */
     setup_isledata();
 
-  if(dist>= map.xsize/2)
-    dist= map.xsize/2;
-  if(dist>= map.ysize/2)
-    dist= map.ysize/2;
+  /* We start with the maximum distance possible. This works more often than you
+     might think!                                                       --Frank
+  */
+  dist = map.ysize;
 
-  sum=0;
+  sum = 0;
   for (k=0; k<=map.num_continents; k++) {
     sum += islands[k].starters;
-    if (islands[k].starters!=0) {
+    if (islands[k].starters != 0) {
       freelog(LOG_VERBOSE, "starters on isle %i", k);
     }
   }
-  assert(game.nplayers<=nr+sum);
+  assert(game.nplayers <= nr+sum);
 
-  while (nr<game.nplayers) {
-    x=myrand(map.xsize);
-    y=myrand(map.ysize); 
-    if (islands[(int)map_get_continent(x, y)].starters) {
-      j++;
-      if (!is_starter_close(x, y, nr, dist)) {
-	islands[(int)map_get_continent(x, y)].starters--;
-	map.start_positions[nr].x=x;
-	map.start_positions[nr].y=y;
-	nr++;
-      }else{
-	if (j>900-dist*9) {
- 	  if(dist>1)
-	    dist--;	  	  
-	  j=0;
+  /* 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 */
+	    int grid_x = (5*x) % map.xsize;
+	    int cont = map_get_continent(grid_x, y);
+	
+            if (islands[cont].tmp) {
+              if (!is_starter_close(grid_x, y, nr, dist)) {
+                islands[cont].tmp--;
+                map.start_positions[nr].x = grid_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_DEBUG, _("dist %i, grid sizes: %i %i."), dist, inc_x, inc_y);
+      freelog(LOG_DEBUG, _("found %i start positions with distance %i."), nr, dist);
     }
-    counter++;
-    if (counter > MAXTRIES) {
+
+    /* 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"
@@ -1194,6 +1205,12 @@
       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);