[Freeciv-Dev] (PR#10308) PATCH: New startpos option and rational control of generators

["Marcelo Burda" <mburda@xxxxxxxxx>]

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

Now the there is a workeable code for start_pos, any coment is welcome 
 
 

? server/.kdbgrc.civserver
Index: common/map.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/map.c,v
retrieving revision 1.198
diff -u -r1.198 map.c
--- common/map.c        29 Sep 2004 02:24:23 -0000      1.198
+++ common/map.c        1 Oct 2004 16:56:53 -0000
@@ -196,6 +196,7 @@
   map.wetness               = MAP_DEFAULT_WETNESS;
   map.steepness             = MAP_DEFAULT_STEEPNESS;
   map.generator             = MAP_DEFAULT_GENERATOR;
+  map.startpos              = MAP_DEFAULT_STARTPOS;
   map.tinyisles             = MAP_DEFAULT_TINYISLES;
   map.separatepoles         = MAP_DEFAULT_SEPARATE_POLES;
   map.alltemperate          = MAP_DEFAULT_ALLTEMPERATE;
Index: common/map.h
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/map.h,v
retrieving revision 1.218
diff -u -r1.218 map.h
--- common/map.h        29 Sep 2004 02:24:23 -0000      1.218
+++ common/map.h        1 Oct 2004 16:56:53 -0000
@@ -172,6 +172,7 @@
   int huts;
   int landpercent;
   int generator;
+  int startpos;
   bool tinyisles;
   bool separatepoles;
   bool alltemperate;
@@ -651,7 +652,11 @@
 
 #define MAP_DEFAULT_GENERATOR    1
 #define MAP_MIN_GENERATOR        1
-#define MAP_MAX_GENERATOR        5
+#define MAP_MAX_GENERATOR        3
+
+#define MAP_DEFAULT_STARTPOS     0
+#define MAP_MIN_STARTPOS         0
+#define MAP_MAX_STARTPOS         4
 
 #define MAP_DEFAULT_TINYISLES    FALSE
 #define MAP_MIN_TINYISLES        FALSE
Index: server/maphand.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/server/maphand.c,v
retrieving revision 1.149
diff -u -r1.149 maphand.c
--- server/maphand.c    29 Sep 2004 02:24:24 -0000      1.149
+++ server/maphand.c    1 Oct 2004 16:56:55 -0000
@@ -1712,6 +1712,14 @@
 }
 
 /*************************************************************************
+  setn size in tiles of the given continent(not ocean)
+*************************************************************************/
+void set_continent_size(Continent_id id, int size) {
+  assert(id > 0);
+  continent_sizes[id] = size;
+}
+
+/*************************************************************************
   Return size in tiles of the given ocean. You should use positive ocean
   number.
 *************************************************************************/
Index: server/maphand.h
===================================================================
RCS file: /home/freeciv/CVS/freeciv/server/maphand.h,v
retrieving revision 1.48
diff -u -r1.48 maphand.h
--- server/maphand.h    29 Sep 2004 02:24:24 -0000      1.48
+++ server/maphand.h    1 Oct 2004 16:56:55 -0000
@@ -106,4 +106,5 @@
                                               Terrain_type_id oldter);
 int get_continent_size(Continent_id id);
 int get_ocean_size(Continent_id id);
+void set_continent_size(Continent_id id, int size);
 #endif  /* FC__MAPHAND_H */
Index: server/settings.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/server/settings.c,v
retrieving revision 1.5
diff -u -r1.5 settings.c
--- server/settings.c   20 Sep 2004 16:42:31 -0000      1.5
+++ server/settings.c   1 Oct 2004 16:56:55 -0000
@@ -259,21 +259,26 @@
   GEN_INT("generator", map.generator,
          SSET_MAP_GEN, SSET_GEOLOGY, SSET_VITAL,  SSET_TO_CLIENT,
          N_("Method used to generate map"),
-         N_("1 = standard, with random continents;\n\n"
-            "2 = equally sized large islands with one player each, and "
-            "twice that many smaller islands;\n\n"
-            "3 = equally sized large islands with one player each, and "
-            "a number of other islands of similar size;\n\n"
-            "4 = equally sized large islands with two players on every "
-            "island (or one with three players for an odd number of "
-            "players), and additional smaller islands;\n\n"
-            "5 = one or more large earthlike continents with some "
-            "scatter.\n\n"
-            "Note: values 2,3 and 4 generate \"fairer\" (but more boring) "
+         N_("1 = Full random height map based generator    (old gen1)  \n"
+            "2 = Pseudo-fractal height map based generator (old gen5)  \n"
+            "3 = Deprecated islands based map generator    (old gen2-4)\n"
+            "Note: generator 3 generate \"fairer\" (but more boring) "
             "maps.\n"
             "(Zero indicates a scenario map.)"), NULL,
          MAP_MIN_GENERATOR, MAP_MAX_GENERATOR, MAP_DEFAULT_GENERATOR)
 
+  GEN_INT("startpos", map.startpos,
+         SSET_MAP_GEN, SSET_GEOLOGY, SSET_VITAL,  SSET_TO_CLIENT,
+         N_("Method used to chice starts pos"),
+         N_("0 = Developper choice, default of the generator;\nn"
+            "1 = try to place one player per isle\n"
+            "2 = try to place 2 players per isle;\n"
+            "3 = try to place all player in some isle\n"
+            "4 = place 2 player per isle or more\n"
+          "Note: generators try to be optimzed for the choice of start pos \n"
+          "and to the number of players"), NULL,
+         MAP_MIN_STARTPOS, MAP_MAX_STARTPOS, MAP_DEFAULT_STARTPOS)
+
   GEN_BOOL("tinyisles", map.tinyisles,
           SSET_MAP_GEN, SSET_GEOLOGY, SSET_RARE, SSET_TO_CLIENT,
           N_("Presence of 1x1 islands"),
Index: server/srv_main.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/server/srv_main.c,v
retrieving revision 1.200
diff -u -r1.200 srv_main.c
--- server/srv_main.c   30 Sep 2004 12:31:26 -0000      1.200
+++ server/srv_main.c   1 Oct 2004 16:56:56 -0000
@@ -103,7 +103,6 @@
 #include "citymap.h"
 
 #include "mapgen.h"
-#include "startpos.h"
 
 #include "srv_main.h"
 
@@ -1775,17 +1774,11 @@
   }
    
   /* if we have a tile map, and map.generator==0, call map_fractal_generate
-     anyway, to make the specials and huts */
+     anyway, to make the specials, huts and assign_continent_numbers */
   if (map_is_empty() || (map.generator == 0 && game.is_new_game)) {
     map_fractal_generate(TRUE);
   }
 
-  /*
-   * Don't assign continent numbers here. We have to do it later,
-   * because generators 2-4 use their own continent numbering
-   * in create_start_positions(). For other generators continent numbers
-   * are already assigned.
-   */
   gamelog_map();
   /* start the game */
 
@@ -1810,18 +1803,8 @@
        * we don't want to change it. */
       game.max_players = game.nplayers;
     }
-
-    /* we don't want random start positions in a scenario which already
-       provides them. -- Gudy */
-    if(map.num_start_positions == 0) {
-      create_start_positions();
-    }
-
   }
 
-  /* start positions are created, now we can do this safely */
-  assign_continent_numbers();
-
   /* Set up alliances based on team selections */
   if (game.is_new_game) {
    players_iterate(pplayer) {
Index: server/generator/height_map.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/server/generator/height_map.c,v
retrieving revision 1.5
diff -u -r1.5 height_map.c
--- server/generator/height_map.c       29 Sep 2004 02:24:24 -0000      1.5
+++ server/generator/height_map.c       1 Oct 2004 16:56:56 -0000
@@ -157,7 +157,7 @@
 
   All X and Y values used in this function are in native coordinates.
 **************************************************************************/
-void make_pseudofractal1_hmap(void)
+void make_pseudofractal1_hmap(int extra_div)
 {
   const bool xnowrap = !topo_has_flag(TF_WRAPX);
   const bool ynowrap = !topo_has_flag(TF_WRAPY);
@@ -166,8 +166,8 @@
    * How many blocks should the x and y directions be divided into
    * initially. 
    */
-  const int xdiv = 6;          
-  const int ydiv = 5;
+  const int xdiv = 5 + extra_div;              
+  const int ydiv = 5 + extra_div;
 
   int xdiv2 = xdiv + (xnowrap ? 1 : 0);
   int ydiv2 = ydiv + (ynowrap ? 1 : 0);
Index: server/generator/height_map.h
===================================================================
RCS file: /home/freeciv/CVS/freeciv/server/generator/height_map.h,v
retrieving revision 1.3
diff -u -r1.3 height_map.h
--- server/generator/height_map.h       29 Sep 2004 02:24:24 -0000      1.3
+++ server/generator/height_map.h       1 Oct 2004 16:56:56 -0000
@@ -37,6 +37,6 @@
 void normalize_hmap_poles(void);
 void renormalize_hmap_poles(void);
 void make_random_hmap(int smooth);
-void make_pseudofractal1_hmap(void);
+void make_pseudofractal1_hmap(int div);
 
 #endif  /* FC__HEIGHT__MAP_H */
Index: server/generator/mapgen.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/server/generator/mapgen.c,v
retrieving revision 1.11
diff -u -r1.11 mapgen.c
--- server/generator/mapgen.c   29 Sep 2004 02:24:24 -0000      1.11
+++ server/generator/mapgen.c   1 Oct 2004 16:56:57 -0000
@@ -31,9 +31,9 @@
 #include "shared.h"
 #include "srv_main.h"
 
-#include "mapgen.h"
 
 #include "height_map.h"
+#include "mapgen.h"
 #include "mapgen_topology.h"
 #include "startpos.h"
 #include "temperature_map.h"
@@ -1016,24 +1016,29 @@
     adjust_terrain_param();
     /* if one mapgenerator fails, it will choose another mapgenerator */
     /* with a lower number to try again */
-    if (map.generator == 5 ) {
-      make_pseudofractal1_hmap();
-    }
-    if (map.generator == 4) {
-      mapgenerator4();
-    }
+    
     if (map.generator == 3) {
-      mapgenerator3();
+      if (map.startpos >= 2 ) { /* any else 2 or 3 player per isle*/
+       mapgenerator4();
+      }
+      if (map.startpos == 1 ) { /* single player per isle */
+       mapgenerator3();
+      }
+      if (map.startpos == 0 ) { /* developer choice */
+       mapgenerator2();
+      }
     }
-    if (map.generator == 2) {
-      mapgenerator2();
+
+    if (map.generator == 2 ) {
+      make_pseudofractal1_hmap(1 + (map.startpos ? game.nplayers: 0));
     }
+
     if (map.generator == 1 ) {
-      make_random_hmap(1 + SQSIZE);
+      make_random_hmap(MAX(1, 1 + SQSIZE - (map.startpos ? game.nplayers / 4: 
0)));
     }
 
     /* if hmap only generator make anything else */
-    if (map.generator == 1 || map.generator == 5) {
+    if (map.generator == 1 || map.generator == 2) {
       make_land();
       free(height_map);
       height_map = NULL;
@@ -1041,8 +1046,6 @@
     if (!map.tinyisles) {
       remove_tiny_islands();
     }
-  } else {
-    assign_continent_numbers();
   }
 
   if (!temperature_is_initialized()) {
@@ -1061,6 +1064,33 @@
   /* restore previous random state: */
   set_myrand_state(rstate);
   destroy_tmap();
+
+  /* we don't want random start positions in a scenario which already
+       provides them. */
+  if (map.num_start_positions == 0) {
+    switch (map.generator) {
+    case 0:
+    case 1:
+      create_start_positions(map.startpos);
+      break;
+    case 2:
+      if (map.startpos == 0) {
+       create_start_positions(MT_ALL);
+      } else {
+       create_start_positions(map.startpos);
+      };
+      break;
+    case 3:
+      if (map.startpos <= 1) {
+       create_start_positions(MT_SINGLE);
+      } else {
+       create_start_positions(MT_2or3);
+      };
+      break;
+    }
+  }
+
+  assign_continent_numbers();
 }
 
 /**************************************************************************
@@ -1126,9 +1156,6 @@
        number--;
        map_set_special(ptile, S_HUT);
        set_placed_near_pos(ptile, 3);
-           /* Don't add to islands[].goodies because islands[] not
-              setup at this point, except for generator>1, but they
-              have pre-set starters anyway. */
       }
     }
   }
@@ -1587,7 +1614,6 @@
     if (i <= 0) {
       return FALSE;
     }
-    islands[pstate->isleindex].starters = starters;
     assert(starters >= 0);
     freelog(LOG_VERBOSE, "island %i", pstate->isleindex);
 
@@ -1648,9 +1674,7 @@
 **************************************************************************/
 static void initworld(struct gen234_state *pstate)
 {
-  int i;
   height_map = fc_malloc(sizeof(int) * map.ysize * map.xsize);
-  islands = fc_malloc((MAP_NCONT+1)*sizeof(struct isledata));
   create_placed_map(); /* land tiles which aren't placed yet */
   create_tmap(FALSE);
   
@@ -1669,11 +1693,7 @@
   /* Set poles numbers.  After the map is generated continents will 
    * be renumbered. */
   assign_continent_numbers(); 
-
   make_island(0, 0, pstate, 0);
-  for(i = 0; i <= map.num_continents; i++ ) {
-      islands[i].starters = 0;
-  }
 }  
 
 /* This variable is the Default Minimum Specific Island Size, 
Index: server/generator/startpos.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/server/generator/startpos.c,v
retrieving revision 1.3
diff -u -r1.3 startpos.c
--- server/generator/startpos.c 29 Sep 2004 02:24:24 -0000      1.3
+++ server/generator/startpos.c 1 Oct 2004 16:56:57 -0000
@@ -1,5 +1,5 @@
 /********************************************************************** 
- Freeciv - Copyright (C) 1996 - A Kjeldberg, L Gregersen, P Unold
+ Freeciv - Copyright (C) 1996 - 2004 The Freeciv Project Team 
    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2, or (at your option)
@@ -23,8 +23,92 @@
 
 #include "mapgen_topology.h"
 #include "startpos.h"
+#include "utilities.h"
 
-struct isledata *islands;
+typedef struct {
+  Continent_id id;
+  int size;
+  int goodies;
+  int starters;
+  int total;
+} islands_data_type;
+islands_data_type *islands;
+int *islands_index;
+
+#define notgood(ptile) (is_ocean(map_get_terrain(ptile)) \
+           || terrain_has_flag(map_get_terrain(ptile), TER_UNSAFE))
+/**************************************************************************
+  Number this tile and nearby tiles (recursively) with the specified
+  continent number, using a flood-fill algorithm.
+  
+  dangerous terrains get 0 value
+
+  is_land tells us whether we are assigning continent numbers or ocean 
+  numbers.
+**************************************************************************/
+static void assign_continent_flood2(struct tile *ptile, int nr)
+{
+  if (map_get_continent(ptile) != 0 || notgood(ptile)) {
+    return;
+  }
+
+  map_set_continent(ptile, nr);
+
+  /* count the tile */
+  set_continent_size(nr, get_continent_size(nr) + 1);
+
+  adjc_iterate(ptile, tile1) {
+    assign_continent_flood2(tile1, nr);
+  } adjc_iterate_end;
+}
+
+/**************************************************************************
+  Spetial Assign continent and ocean numbers to all tiles, and set
+  map.num_continents,
+
+  the dangerous land tiles get nr 0 and can separate continents
+  
+  Recalculate continent and ocean sizes
+
+  Continents have numbers 1 to map.num_continents _inclusive_.
+  Oceans have (negative) numbers -1 to -map.num_oceans _inclusive_.
+  
+  Also recalculate lake_surrounders[] arrays
+**************************************************************************/
+static void spetial_assign_continent_numbers(void)
+{
+  int i;
+  
+  /* reset ocean/continent counters */
+  for (i = 1; i < MAP_NCONT; i++) {
+    set_continent_size(i, 0);
+  }
+  
+  /* Initialize */
+  map.num_continents = 0;
+
+  whole_map_iterate(ptile) {
+    if(!is_ocean(map_get_terrain(ptile))) {
+       map_set_continent(ptile, 0);
+    }
+  } whole_map_iterate_end;
+
+  /* Assign new numbers */
+  whole_map_iterate(ptile) {
+    if (map_get_continent(ptile) != 0) {
+      /* Already assigned. */
+      continue;
+    }
+    if (!notgood(ptile)) {
+      map.num_continents++;
+      assert(map.num_continents < MAP_NCONT);
+      assign_continent_flood2(ptile, map.num_continents);
+    } 
+  } whole_map_iterate_end;
+
+  freelog(LOG_VERBOSE, "Map has %d continents and %d oceans", 
+         map.num_continents, map.num_oceans);
+}
 
 /****************************************************************************
   Return an approximation of the goodness of a tile to a civilization.
@@ -54,8 +138,8 @@
   map_set_special(ptile, S_ROAD);
   map_mine_tile(ptile);
   mine_bonus = (get_food_tile(ptile)
-                + get_shields_tile(ptile)
-                + get_trade_tile(ptile)) - value;
+               + get_shields_tile(ptile)
+               + get_trade_tile(ptile)) - value;
 
   ptile->terrain = old_terrain;
   ptile->special = old_special;
@@ -65,118 +149,13 @@
   return value;
 }
 
-/**************************************************************************
- 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.
-**************************************************************************/
-static void setup_isledata(void)
-{
-  int starters = 0;
-  int min,  i;
-  
-  assert(map.num_continents > 0);
-  
-  /* allocate + 1 so can use continent number as index */
-  islands = fc_calloc((map.num_continents + 1), sizeof(struct isledata));
-
-  /* add up all the resources of the map */
-  whole_map_iterate(ptile) {
-    /* number of different continents seen from (x,y) */
-    int seen_conts = 0;
-    /* list of seen continents */
-    Continent_id conts[CITY_TILES]; 
-    int j;
-    
-    /* add tile's value to each continent that is within city 
-     * radius distance */
-    map_city_radius_iterate(ptile, tile1) {
-      /* (x1,y1) is possible location of a future city which will
-       * be able to get benefit of the tile (x,y) */
-      if (is_ocean(map_get_terrain(tile1)) 
-         || map_colatitude(tile1) <= 2 * ICE_BASE_LEVEL) { 
-       /* Not land, or too cold. */
-        continue;
-      }
-      for (j = 0; j < seen_conts; j++) {
-       if (map_get_continent(tile1) == conts[j]) {
-          /* Continent of (x1,y1) is already in the list */
-         break;
-        }
-      }
-      if (j >= seen_conts) { 
-       /* we have not seen this continent yet */
-       assert(seen_conts < CITY_TILES);
-       conts[seen_conts] = map_get_continent(tile1);
-       seen_conts++;
-      }
-    } map_city_radius_iterate_end;
-    
-    /* Now actually add the tile's value to all these continents */
-    for (j = 0; j < seen_conts; j++) {
-      islands[conts[j]].goodies += get_tile_value(ptile);
-    }
-  } whole_map_iterate_end;
-  
-  /* now divide the number of desired starting positions among
-   * the continents so that the minimum number of resources per starting 
-   * position is as large as possible */
-  
-  /* set minimum number of resources per starting position to be value of
-   * the best continent */
-  min = 0;
-  for (i = 1; i <= map.num_continents; i++) {
-    if (min < islands[i].goodies) {
-      min = islands[i].goodies;
-    }
-  }
-  
-  /* place as many starting positions as possible with the current minumum
-   * number of resources, if not enough are placed, decrease the minimum */
-  while ((starters < game.nplayers) && (min > 0)) {
-    int nextmin = 0;
-    
-    starters = 0;
-    for (i = 1; i <= map.num_continents; i++) {
-      int value = islands[i].goodies;
-      
-      starters += value / min;
-      if (nextmin < (value / (value / min + 1))) {
-        nextmin = value / (value / min + 1);
-      }
-    }
-    
-    freelog(LOG_VERBOSE,
-           "%d starting positions allocated with\n"
-            "at least %d resouces per starting position; \n",
-            starters, min);
-
-    assert(nextmin < min);
-    /* This choice of next min guarantees that there will be at least 
-     * one more starter on one of the continents */
-    min = nextmin;
-  }
-  
-  if (min == 0) {
-    freelog(LOG_VERBOSE,
-            "If we continue some starting positions will have to have "
-            "access to zero resources (as defined in get_tile_value). \n");
-    freelog(LOG_FATAL,
-            "Cannot create enough starting position and will abort.\n"
-            "Please report this bug at " WEBSITE_URL);
-    abort();
-  } else {
-    for (i = 1; i <= map.num_continents; i++) {
-      islands[i].starters = islands[i].goodies / min;
-    }
-  }
-}
-
 struct start_filter_data {
-  int count; /* Number of existing start positions. */
-  int dist; /* Minimum distance between starting positions. */
+  int count;                   /* Number of existing start positions. */
+  int min_value;
+  int *value;
 };
 
+
 /**************************************************************************
   Return TRUE if (x,y) is a good starting position.
 
@@ -189,78 +168,214 @@
     'nr' is the number of other start positions in
     map.start_positions to check for too closeness.
 **************************************************************************/
-static bool is_valid_start_pos(const struct tile *ptile, const void *dataptr)
+static bool is_valid_start_pos(const struct tile *ptile,
+                              const void *dataptr)
 {
-  const struct start_filter_data *data = dataptr;
+  const struct start_filter_data *pdata = dataptr;
   int i;
-  Terrain_type_id t = map_get_terrain(ptile);
 
-  if (is_ocean(map_get_terrain(ptile))) {
-    return FALSE;
-  }
+  /* Only start on certain terrain types. */  
+  if (pdata->value[ptile->index] < pdata->min_value) {
+      return FALSE;
+  } 
 
-  if (islands[(int)map_get_continent(ptile)].starters == 0) {
+  if (islands[islands_index[(int) map_get_continent(ptile)]].starters == 0) {
     return FALSE;
   }
 
-  /* Only start on certain terrain types. */
-  if (!terrain_has_flag(t, TER_STARTER)) {
-    return FALSE;
-  }
-  
   /* Don't start on a hut. */
   if (map_has_special(ptile, S_HUT)) {
     return FALSE;
   }
-  
-  /* Nobody will start on the poles since they aren't valid terrain. */
 
   /* Don't start too close to someone else. */
-  for (i = 0; i < data->count; i++) {
+  for (i = 0; i < pdata->count; i++) {
     struct tile *tile1 = map.start_positions[i].tile;
 
-    if (map_get_continent(ptile) == map_get_continent(tile1)
-       && real_map_distance(ptile, tile1) < data->dist) {
+    if ((map_get_continent(ptile) == map_get_continent(tile1)
+        && (real_map_distance(ptile, tile1) * 1000 / pdata->min_value
+            <= (sqrt(get_continent_size(map_get_continent(ptile))
+                    /
+                    islands[islands_index
+                            [(int) map_get_continent(ptile)]].total)
+               )))
+       || (real_map_distance(ptile, tile1) * 1000 / pdata->min_value < 5)) {
       return FALSE;
     }
   }
-
   return TRUE;
 }
 
+/*************************************************************************
+ help function for qsort
+ *************************************************************************/
+static int compare_islands(const void *A, const void *B)
+{
+  return -(((islands_data_type *) A)->goodies
+          - ((islands_data_type *) B)->goodies);
+}
+/*********************************************
+ initialize with some 0 values, call malloc, etc
+********************************************/
+static void initialize_isle_data(void)
+{
+  int nr;
+  islands =
+      fc_malloc((map.num_continents + 1) * sizeof(islands_data_type));
+  islands_index = fc_malloc((map.num_continents + 1) * sizeof(int));
+
+  for (nr = 1; nr <= map.num_continents; nr++) {
+    islands[nr].id = nr;
+    islands[nr].size = get_continent_size(nr);
+    islands[nr].goodies = 0;
+    islands[nr].starters = 0;
+    islands[nr].total = 0;
+  }
+}
+
+static bool filter(const struct tile *ptile, const void *data)
+{
+  return terrain_has_flag(map_get_terrain(ptile), TER_STARTER);
+}
+
 /**************************************************************************
-  where do the different races start on the map? well this function tries
+  where do the different nations start on the map? well this function tries
   to spread them out on the different islands.
+  MT_SIGLE one player per isle
+  MT_2or3 2 player per isle if number of players is even
+  MT_ALL  all player in single isle
+  MT_VARIABLE at last 2 player per isle
 **************************************************************************/
-void create_start_positions(void)
+void create_start_positions(mode_type mode)
 {
   struct tile *ptile;
   int k, sum;
   struct start_filter_data data;
-  
-  if (!islands) {
-    /* Isle data is already setup for generators 2, 3, and 4. */
-    setup_isledata();
+  int tile_value_aux[MAX_MAP_INDEX], tile_value[MAX_MAP_INDEX];
+  int min_size_per_player = 25;
+
+  assign_continent_numbers();
+  /* unsafe terrains separate continents for this task
+     else littles green isles near poles can be populated by
+     a civilization if pole touch a big one! */
+  spetial_assign_continent_numbers();
+
+  /* create_start_positions not known what is the right default,
+     then use MT_VARIABLE */
+  if(mode == MT_DEFAULT) {
+      mode = MT_VARIABLE;
   }
 
-  data.dist = MIN(40, MIN(map.xsize / 2, map.ysize / 2));
+  /* get the tile value */
+  whole_map_iterate(ptile) {
+    tile_value_aux[ptile->index] = get_tile_value(ptile);
+  } whole_map_iterate_end;
+
+  /* select the best tiles */
+  whole_map_iterate(ptile) {
+    int this_tile_value = tile_value_aux[ptile->index];
+    int lcount = 0, bcount = 0;
+    map_city_radius_iterate(ptile, ptile1) {
+      if (this_tile_value > tile_value_aux[ptile1->index]) {
+       lcount++;
+      } else if (this_tile_value < tile_value_aux[ptile1->index]) {
+       bcount++;
+      }
+    }
+    map_city_radius_iterate_end;
+    if (lcount <= bcount) {
+      this_tile_value = 0;
+    }
+    tile_value[ptile->index] = 100 * this_tile_value;
+  } whole_map_iterate_end;
+  /* get a average value */
+  smooth_int_map(tile_value, TRUE);
+
+  initialize_isle_data();
+
+  /* oceans are not good for start, discard its */
+  whole_map_iterate(ptile) {
+    if (!filter(ptile, NULL)) {
+      tile_value[ptile->index] = 0;
+    } else {
+      islands[map_get_continent(ptile)].goodies
+         += tile_value[ptile->index];
+    }
+  } whole_map_iterate_end;
+
+  /* evaluate the best places on the map */
+  adjust_int_map_filtered(tile_value, 1000, NULL, filter);
+ 
+  /* best islands first */
+  qsort(islands + 1, (map.num_continents),
+       sizeof(islands_data_type), compare_islands);
+
+  /* some times we can't place start pos as wanted then choixe the best way */
+  if (mode == MT_SINGLE && map.num_continents < game.nplayers + 3) {
+    mode = MT_2or3;
+  }
+
+  if (mode == MT_2or3 && map.num_continents < game.nplayers / 2 + 4) {
+    mode = MT_VARIABLE;
+  }
+
+  if (mode == MT_ALL 
+       && (islands[1].size < game.nplayers * min_size_per_player
+          || (islands[1].size < map.landpercent * MAX_MAP_INDEX / 300))) {
+    mode = MT_VARIABLE;
+  }
+
+  /* the variable way is the last posibility */
+  if (mode == MT_VARIABLE) {
+    min_size_per_player = map.landpercent * MAX_MAP_INDEX * 0.65  
+       / (100 * game.nplayers);
+  }
+
+ 
+  {  /* set starters per isle */
+    int nr, to_place = game.nplayers;
+    for (nr = 1; nr <= map.num_continents; nr++) {
+      islands_index[islands[nr].id] = nr;
+      if (mode == MT_ALL && (to_place > 0)) {
+       islands[nr].starters = to_place;
+       to_place -= islands[nr].total = islands[nr].starters;
+      }
+      if (mode == MT_SINGLE && (to_place > 0)) {
+       islands[nr].starters = 1;
+       islands[nr].total = 1;
+       to_place--;
+      }
+      if (mode == MT_2or3 && (to_place > 0)) {
+       islands[nr].starters = 2 + (nr == 1 ? (game.nplayers % 2) : 0);
+       to_place -= islands[nr].total = islands[nr].starters;
+      }
+      if (mode == MT_VARIABLE && (to_place > 0)) {
+       islands[nr].starters = MAX(1, islands[nr].size / min_size_per_player);
+       to_place -= islands[nr].total = islands[nr].starters;
+      }
+    }
+  }
 
   data.count = 0;
+  data.value = tile_value;
+  data.min_value = 900;
   sum = 0;
   for (k = 1; k <= map.num_continents; k++) {
-    sum += islands[k].starters;
-    if (islands[k].starters != 0) {
+    sum += islands[islands_index[k]].starters;
+    if (islands[islands_index[k]].starters != 0) {
       freelog(LOG_VERBOSE, "starters on isle %i", k);
     }
   }
   assert(game.nplayers <= data.count + sum);
 
+
+  /* now search the best place and set start_positions */
   map.start_positions = fc_realloc(map.start_positions,
                                   game.nplayers
                                   * sizeof(*map.start_positions));
   while (data.count < game.nplayers) {
     if ((ptile = rand_map_pos_filtered(&data, is_valid_start_pos))) {
-      islands[(int)map_get_continent(ptile)].starters--;
+      islands[islands_index[(int) map_get_continent(ptile)]].starters--;
       map.start_positions[data.count].tile = ptile;
       map.start_positions[data.count].nation = NO_NATION_SELECTED;
       freelog(LOG_DEBUG, "Adding %d,%d as starting position %d.",
@@ -268,9 +383,8 @@
       data.count++;
 
     } else {
-      
-      data.dist--;
-      if (data.dist == 0) {
+      data.min_value *= 0.9;
+      if (data.min_value <= 10) {
        die(_("The server appears to have gotten into an infinite loop "
              "in the allocation of starting positions, and will abort.\n"
              "Maybe the numbers of players/ia is too much for this map.\n"
@@ -280,6 +394,11 @@
   }
   map.num_start_positions = game.nplayers;
 
+  /* assign standard continent numbers */
+  assign_continent_numbers();
+
   free(islands);
+  free(islands_index);
   islands = NULL;
+  islands_index = NULL;
 }
Index: server/generator/startpos.h
===================================================================
RCS file: /home/freeciv/CVS/freeciv/server/generator/startpos.h,v
retrieving revision 1.1
diff -u -r1.1 startpos.h
--- server/generator/startpos.h 16 Sep 2004 09:53:11 -0000      1.1
+++ server/generator/startpos.h 1 Oct 2004 16:56:57 -0000
@@ -13,12 +13,9 @@
 #ifndef FC__STARTING_POSITIONS
 #define FC__STARTING_POSITIONS
 
-void create_start_positions(void);
-/* This is manipulated directly by gen234 */
-struct isledata {
-  int goodies;
-  int starters;
-};
-extern struct isledata *islands;
+typedef  enum {MT_DEFAULT = 0, MT_SINGLE, MT_2or3, MT_ALL, MT_VARIABLE}
+         mode_type;
+
+void create_start_positions(mode_type mode);
 
 #endif
Index: server/generator/utilities.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/server/generator/utilities.c,v
retrieving revision 1.7
diff -u -r1.7 utilities.c
--- server/generator/utilities.c        29 Sep 2004 02:24:24 -0000      1.7
+++ server/generator/utilities.c        1 Oct 2004 16:56:57 -0000
@@ -101,15 +101,18 @@
   The lowest 20% of tiles will have values lower than 0.2 * int_map_max.
 
 **************************************************************************/
-void adjust_int_map(int *int_map, int int_map_max)
+void adjust_int_map_filtered(int *int_map, int int_map_max, void *data,
+                                  bool (*filter)(const struct tile *ptile,
+                                                 const void *data))
 {
-  int minval = *int_map, maxval = minval;
+  int minval = +(int)HUGE_VAL, maxval = -(int)HUGE_VAL, total = 0;
 
   /* Determine minimum and maximum value. */
-  whole_map_iterate(ptile) {
+  whole_map_iterate_filtered(ptile, data, filter) {
     maxval = MAX(maxval, int_map[ptile->index]);
     minval = MIN(minval, int_map[ptile->index]);
-  } whole_map_iterate_end;
+    total++;
+  } whole_map_iterate_filtered_end;
 
   {
     int const size = 1 + maxval - minval;
@@ -120,23 +123,24 @@
     /* Translate value so the minimum value is 0
        and count the number of occurencies of all values to initialize the 
        frequencies[] */
-    whole_map_iterate(ptile) {
+    whole_map_iterate_filtered(ptile, data, filter) {
       int_map[ptile->index] = (int_map[ptile->index] - minval);
       frequencies[int_map[ptile->index]]++;
-    } whole_map_iterate_end;
+    } whole_map_iterate_filtered_end;
 
     /* create the linearize function as "incremental" frequencies */
     for(i =  0; i < size; i++) {
       count += frequencies[i]; 
-      frequencies[i] = (count * int_map_max) / MAX_MAP_INDEX;
+      frequencies[i] = (count * int_map_max) / total;
     }
 
     /* apply the linearize function */
-    whole_map_iterate(ptile) {
+    whole_map_iterate_filtered(ptile, data, filter) {
       int_map[ptile->index] = frequencies[int_map[ptile->index]];
-    } whole_map_iterate_end;
+    } whole_map_iterate_filtered_end;
   }
 }
+
 bool normalize_nat_pos(int *x, int  *y) 
 {
     int map_x, map_y;
Index: server/generator/utilities.h
===================================================================
RCS file: /home/freeciv/CVS/freeciv/server/generator/utilities.h,v
retrieving revision 1.3
diff -u -r1.3 utilities.h
--- server/generator/utilities.h        29 Sep 2004 02:24:24 -0000      1.3
+++ server/generator/utilities.h        1 Oct 2004 16:56:57 -0000
@@ -57,11 +57,24 @@
     } \
 } 
 
+#define whole_map_iterate_filtered(ptile, pdata, pfilter)               \
+  whole_map_iterate(ptile) {                                            \
+    if((pfilter) != NULL && !(pfilter)(ptile, (pdata))) {               \
+      continue;                                                         \
+    }
+
+#define whole_map_iterate_filtered_end } whole_map_iterate_end
+
 bool normalize_nat_pos(int *x, int  *y);
 bool is_normal_nat_pos(int x, int y);
 
 /* int maps tools */
-void adjust_int_map(int *int_map, int int_map_max);
+void adjust_int_map_filtered(int *int_map, int int_map_max, void *data,
+                                  bool (*filter)(const struct tile *ptile,
+                                                 const void *data));
+#define adjust_int_map(int_map, int_map_max) \
+  adjust_int_map_filtered(int_map, int_map_max, (void *)NULL, \
+            (bool (*)(const struct tile *ptile, const void *data) )NULL)
 void smooth_int_map(int *int_map, bool zeroes_at_edges);
 
 /* placed_map tool*/