[Freeciv-Dev] Re: (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 >

Le ven 01/10/2004 à 19:26, Jason Short a écrit :
> <URL: http://rt.freeciv.org/Ticket/Display.html?id=10308 >
> 
> Marcelo Burda wrote:
> > <URL: http://rt.freeciv.org/Ticket/Display.html?id=10308 >
> > 
> > Now the there is a workeable code for start_pos, any coment is welcome 
> 
> How will generators 1 and 5 handle this?
> 
generaterato can do more isle when we ask for one isle per player, this
is partially done in this code.

random generator (1, old 1) do more smooth if we want less number of
islands.
pseudo-fractal generator (2 old 5) do more divicions to do more islands.

then start_pos code do that it can, if number of isles in not good, or
size, symply do aithing else, but this work ok, we try to get one isle
per player but there is not garanted a this point!

i am ideas to garanted it, but this is a lot of fine work.


there is a little patch ato do a minor fix in generator 5
now startpos = 0 and startpos = 3 is really the some thing in
pseudo-fractal generator (do a big continent with all civilizationes in)
> jason
> 
> 

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 18:49:29 -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 18:49:30 -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 18:49:31 -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 18:49:31 -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 18:49:32 -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 18:49:33 -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 18:49:33 -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 18:49:33 -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 18:49:34 -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,31 @@
     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 == 0 || map.startpos == 3)  ? 0 : game.nplayers));
     }
+
     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 +1048,6 @@
     if (!map.tinyisles) {
       remove_tiny_islands();
     }
-  } else {
-    assign_continent_numbers();
   }
 
   if (!temperature_is_initialized()) {
@@ -1061,6 +1066,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 +1158,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 +1616,6 @@
     if (i <= 0) {
       return FALSE;
     }
-    islands[pstate->isleindex].starters = starters;
     assert(starters >= 0);
     freelog(LOG_VERBOSE, "island %i", pstate->isleindex);
 
@@ -1648,9 +1676,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 +1695,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 18:49:34 -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 18:49:34 -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 18:49:34 -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 18:49:34 -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*/