[Freeciv-Dev] Re: (PR#6183) barbarians on the poles

["Jason Short" <jdorje@xxxxxxxxxxxxxxxxxxxxx>]

Gregory Berkolaiko wrote:
> On Fri, 19 Sep 2003, Jason Short wrote:
> 
> 
>>On Fri, 19 Sep 2003, Mike Kaufman wrote:
>>
>>>I don't like special checks like this because maybe I want to play with an
>>>all arctic/tundra map. Are barbarians then screwed?
>>
>>It should be ruleset-controlled.  But unless you change the ruleset, not
>>only will barbarians be screwed but unless the code deals with the special
>>case you will be too.

> If you are talking about finding starting positions, you are right, the 
> present code won't find any, but there is a patch by Karen which fixes 
> that.  I am awaiting the next edition of the patch, but she disappeared as 
> usual.  The ref is 5438.

Code for finding starting positions (IIRC), placing huts, and placing 
barbarians is all similar.  Currently it relies on repetitive loops to 
pick a random place repeatedly until it finds an acceptable one. 
Usually there's an upper limit on the number of tries.

This should be replaced by code to check every position then pick one of 
the acceptable ones.  A new function rand_map_pos_filtered would be 
helpful.  The function would return FALSE if no positions are 
acceptable.  The disadvantages of this are:

- You can't/shouldn't use any randomness in the filter function.

- It changes the logic slightly.  For instance with barbarians 
try_summon_barbarian is called a vast number of times each turn, but 
usually (randomly) fails.  Doing it the above way try_summon_barbarian 
would always succeed when a barbarian can be summoned, so the randomness 
needs to be introduced in some other way.

All of these are minor compared to the robustness given by this method, 
however.

Note the new method needn't be any slower.

jason

Index: common/map.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/map.c,v
retrieving revision 1.143
diff -u -r1.143 map.c
--- common/map.c        2003/09/19 13:17:12     1.143
+++ common/map.c        2003/09/22 05:04:22
@@ -1462,6 +1462,51 @@
 }
 
 /**************************************************************************
+ Random square anywhere on the map for which the 'filter' function
+ returns true.  return FALSE if none can be found.
+**************************************************************************/
+bool rand_map_pos_filtered(int *x, int *y, bool (*filter)(int x, int y))
+{
+  int tries = 0, count = 0;
+  const int max_tries = map.xsize * map.ysize / 10;
+
+  /* First do a few quick checks to find a spot. */
+  do {
+    index_to_map_pos(x, y, myrand(map.xsize * map.ysize));
+  } while (!filter(*x, *y) && ++tries < max_tries);
+  if (tries < max_tries) {
+    return TRUE;
+  }
+
+  /* If that fails, count all available spots and pick one.
+   * Slow but reliable. */
+  whole_map_iterate(x1, y1) {
+    if (filter(x1, y1)) {
+      count++;
+    }
+  } whole_map_iterate_end;
+
+  if (count == 0) {
+    return FALSE;
+  }
+
+  count = myrand(count);
+  whole_map_iterate(x1, y1) {
+    if (filter(x1, y1)) {
+      if (count == 0) {
+       *x = x1;
+       *y = y1;
+       return TRUE;
+      }
+      count--;
+    }
+  } whole_map_iterate_end;
+
+  assert(0);
+  return FALSE;
+}
+
+/**************************************************************************
 Return the debugging name of the direction.
 **************************************************************************/
 const char *dir_get_name(enum direction8 dir)
Index: common/map.h
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/map.h,v
retrieving revision 1.153
diff -u -r1.153 map.h
--- common/map.h        2003/09/19 13:17:12     1.153
+++ common/map.h        2003/09/22 05:04:22
@@ -315,6 +315,7 @@
 
 void rand_neighbour(int x0, int y0, int *x, int *y);
 void rand_map_pos(int *x, int *y);
+bool rand_map_pos_filtered(int *x, int *y, bool (*filter)(int x, int y));
 
 bool is_water_adjacent_to_tile(int x, int y);
 bool is_tiles_adjacent(int x0, int y0, int x1, int y1);