diff -Nur -X/home/thue/freeciv-dev/freeciv/diff_ignore freeciv/server/gotohand.c pq/server/gotohand.c
--- freeciv/server/gotohand.c	Fri Jun 23 21:16:06 2000
+++ pq/server/gotohand.c	Sun Jun 25 23:16:34 2000
@@ -36,23 +36,6 @@
   unsigned char x, y;
 };
 
-#define WARQUEUE_DIM 16384
-static struct stack_element warqueue[WARQUEUE_DIM];
-/* WARQUEUE_DIM must be a power of 2, size of order (MAP_MAX_WIDTH*MAP_MAX_HEIGHT);
- * (Could be non-power-of-2 and then use modulus in add_to_warqueue
- * and get_from_warqueue.)
- * It is used to make the queue circular by wrapping, to awoid problems on large maps.
- * (see add_to_warqueue and get_from_warqueue).
- * Note that a single (x,y) can appear multiple
- * times in warqueue due to a sequence of paths with successively
- * smaller costs.  --dwp
- */
-
-/* warqueuesize points to the top of the queue.
-   warnodes at the buttom */
-static unsigned int warqueuesize;
-static unsigned int warnodes;
-
 /* These are used for airplane GOTOs with waypoints */
 #define MAXFUEL 100
 
@@ -74,26 +57,125 @@
 static void dealloc_refuel_stack();
 static int find_air_first_destination(struct unit *punit, int *dest_x, int *dest_y);
 
+/* These are used for all GOTO's */
+
+#define MAXCOST 255
+#define MAXARRAYS 10000
+#define ARRAYLENGTH 10
+
+struct mappos_array {
+  int first_pos;
+  int last_pos;
+  struct map_position pos[ARRAYLENGTH];
+  struct mappos_array *next_array;
+};
+
+struct array_pointer {
+  struct mappos_array *first_array;
+  struct mappos_array *last_array;
+};
+
+static struct mappos_array *mappos_arrays[MAXARRAYS];
+static struct array_pointer cost_lookup[MAXCOST];
+static int array_count;
+static int lowest_cost;
+
+/**************************************************************************
+...
+**************************************************************************/
+void init_queue(void)
+{
+  int i;
+  static int is_initialized = 0;
+  if (!is_initialized) {
+    for (i = 0; i < MAXARRAYS; i++) {
+      mappos_arrays[i] = fc_malloc(sizeof(struct mappos_array));
+    }
+    is_initialized = 1;
+  }
+
+  for (i = 0; i < MAXCOST; i++) {
+    cost_lookup[i].first_array = NULL;
+    cost_lookup[i].last_array = NULL;
+  }
+  array_count = 0;
+  lowest_cost = 0;
+  for (i = 0; i < map.xsize; i++)
+    memset(warmap.returned[i], 0, map.ysize*sizeof(char));
+}
+
 /**************************************************************************
-The "warqueuesize & (WARQUEUE_DIM-1)" make the queue wrap if too big.
+...
 **************************************************************************/
-static void add_to_warqueue(int x, int y)
+static void init_array(struct mappos_array *our_array)
 {
-  unsigned int i = warqueuesize & (WARQUEUE_DIM-1);
-  warqueue[i].x = x;
-  warqueue[i].y = y;
-  warqueuesize++;
+  our_array->first_pos = 0;
+  our_array->last_pos = -1;
+  our_array->next_array = NULL;
 }
 
 /**************************************************************************
-The "i &= (WARQUEUE_DIM-1);" make the queue wrap if too big.
+...
 **************************************************************************/
-static void get_from_warqueue(unsigned int i, int *x, int *y)
+static void add_to_mapqueue(int cost, int x, int y)
 {
-  assert(i<warqueuesize && warqueuesize-i<WARQUEUE_DIM);
-  i &= (WARQUEUE_DIM-1);
-  *x = warqueue[i].x;
-  *y = warqueue[i].y;
+  struct mappos_array *our_array;
+
+  assert(cost < MAXCOST && cost >= 0);
+
+  our_array = cost_lookup[cost].last_array;
+  if (our_array == NULL) {
+    our_array = mappos_arrays[array_count++];
+    cost_lookup[cost].first_array = our_array;
+    cost_lookup[cost].last_array = our_array;
+    init_array(our_array);
+  } else if (our_array->last_pos == ARRAYLENGTH-1) {
+    our_array->next_array = mappos_arrays[array_count++];
+    our_array = our_array->next_array;
+    init_array(our_array);
+    cost_lookup[cost].last_array = our_array;
+  }
+
+  our_array->pos[++(our_array->last_pos)].x = x;
+  our_array->pos[our_array->last_pos].y = y;
+  freelog(LOG_DEBUG, "adding cost:%i at %i,%i", cost, x, y);
+}
+
+/**************************************************************************
+...
+**************************************************************************/
+static int get_from_mapqueue(int *x, int *y)
+{
+  struct mappos_array *our_array;
+  freelog(LOG_DEBUG, "trying get");
+  while (lowest_cost < MAXCOST) {
+    our_array = cost_lookup[lowest_cost].first_array;
+    if (our_array == NULL) {
+      lowest_cost++;
+      continue;
+    }
+    if (our_array->last_pos < our_array->first_pos) {
+      if (our_array->next_array) {
+	cost_lookup[lowest_cost].first_array = our_array->next_array;
+	continue; /* note NOT "lowest_cost++;" */
+      } else {
+	cost_lookup[lowest_cost].first_array = NULL;
+	lowest_cost++;
+	continue;
+      }
+    }
+    *x = our_array->pos[our_array->first_pos].x;
+    *y = our_array->pos[our_array->first_pos].y;
+    our_array->first_pos++;
+    if (warmap.returned[*x][*y]) {
+      freelog(LOG_DEBUG, "returned before. getting next");
+      return get_from_mapqueue(x, y);
+    } else {
+      freelog(LOG_DEBUG, "got %i,%i, at cost %i", *x, *y, warmap.cost[*x][*y]);
+      return 1;
+    }
+  }
+  return 0;
 }
 
 /**************************************************************************
@@ -108,9 +190,12 @@
       warmap.cost[x]=fc_malloc(map.ysize*sizeof(unsigned char));
       warmap.seacost[x]=fc_malloc(map.ysize*sizeof(unsigned char));
       warmap.vector[x]=fc_malloc(map.ysize*sizeof(unsigned char));
+      warmap.returned[x]=fc_malloc(map.ysize*sizeof(char));
     }
   }
 
+  init_queue();
+
   switch (move_type) {
   case LAND_MOVING:
     for (x = 0; x < map.xsize; x++)
@@ -184,10 +269,7 @@
   }
 
   init_warmap(orig_x, orig_y, move_type);
-  warqueuesize = 0;
-  warnodes = 0;
-
-  add_to_warqueue(orig_x, orig_y);
+  add_to_mapqueue(0, orig_x, orig_y);
 
   if (punit && unit_flag(punit->type, F_IGTER))
     igter = 1;
@@ -201,9 +283,7 @@
     maxcost /= 2;
   /* (?) was punit->type == U_SETTLERS -- dwp */
 
-  do {
-    get_from_warqueue(warnodes, &x, &y);
-    warnodes++;
+  while (get_from_mapqueue(&x, &y)) {
     ptile = map_get_tile(x, y);
     for (dir = 0; dir < 8; dir++) {
       x1 = x + ii[dir];
@@ -236,23 +316,23 @@
 		       (ptile->move_cost[dir] > tmp ? 1 : 0))/2;
         }
 
-        move_cost = warmap.cost[x][y] + move_cost;
+        move_cost += warmap.cost[x][y];
         if (warmap.cost[x1][y1] > move_cost && move_cost < maxcost) {
           warmap.cost[x1][y1] = move_cost;
-          add_to_warqueue(x1, y1);
+          add_to_mapqueue(move_cost, x1, y1);
         }
 	break;
 
 
       case SEA_MOVING:
         move_cost = 3;
-        move_cost = warmap.seacost[x][y] + move_cost;
+        move_cost += warmap.seacost[x][y];
         if (warmap.seacost[x1][y1] > move_cost && move_cost < maxcost) {
 	  /* by adding the move_cost to the warmap regardless if we can move between
 	     we allow for shore bombardment/transport to inland positions/etc. */
           warmap.seacost[x1][y1] = move_cost;
           if (ptile->move_cost[dir] == -3) /* -3 means ships can move between */
-	    add_to_warqueue(x1, y1);
+	    add_to_mapqueue(move_cost, x1, y1);
 	}
 	break;
       default:
@@ -261,16 +341,10 @@
 	abort();
       }
     } /* end for */
-  } while (warqueuesize > warnodes);
-
-  if (warnodes > WARQUEUE_DIM) {
-    freelog(LOG_VERBOSE, "Warning: %u nodes in map #%d for (%d, %d)",
-	 warnodes, move_type, orig_x, orig_y);
   }
 
-  freelog(LOG_DEBUG, "Generated warmap for (%d,%d) with %u nodes checked.",
-	  orig_x, orig_y, warnodes); 
-  /* warnodes is often as much as 2x the size of the continent -- Syela */
+  freelog(LOG_DEBUG, "Generated warmap for (%d,%d).",
+	  orig_x, orig_y); 
 }
 
 /**************************************************************************
@@ -322,8 +396,6 @@
 **************************************************************************/
 static void init_gotomap(int orig_x, int orig_y, enum unit_move_type move_type)
 {
-  int x;
-
   switch (move_type) {
   case LAND_MOVING:
   case HELI_MOVING:
@@ -335,10 +407,6 @@
     break;
   }
 
-  for (x = 0; x < map.xsize; x++) {
-    memset(warmap.vector[x], 0, map.ysize*sizeof(unsigned char));
-  }
-
   return;
 }
 
@@ -564,10 +632,7 @@
   local_vector[orig_x][orig_y] = 0;
 
   init_gotomap(punit->x, punit->y, move_type);
-  warqueuesize = 0;
-  warnodes = 0;
-
-  add_to_warqueue(orig_x, orig_y);
+  add_to_mapqueue(0, orig_x, orig_y);
 
   if (punit && unit_flag(punit->type, F_IGTER))
     igter = 1;
@@ -591,9 +656,7 @@
     pcargo = NULL;
 
   /* until we have found the shortest paths */
-  do {
-    get_from_warqueue(warnodes, &x, &y);
-    warnodes++; /* points to bottom of queue */
+  while (get_from_mapqueue(&x, &y)) {
     psrctile = map_get_tile(x, y);
 
     if (restriction == GOTO_MOVE_STRAIGHTEST)
@@ -669,7 +732,7 @@
 	if (total_cost < maxcost) {
           if (warmap.cost[x1][y1] > total_cost) {
             warmap.cost[x1][y1] = total_cost;
-            add_to_warqueue(x1, y1);
+            add_to_mapqueue(total_cost, x1, y1);
             local_vector[x1][y1] = 128>>dir;
 	    freelog(LOG_DEBUG,
 		    "Candidate: %s from (%d, %d) to (%d, %d), cost %d",
@@ -734,7 +797,7 @@
 	if (total_cost < maxcost) {
 	  if (warmap.seacost[x1][y1] > total_cost) {
 	    warmap.seacost[x1][y1] = total_cost;
-	    add_to_warqueue(x1, y1);
+	    add_to_mapqueue(total_cost, x1, y1);
 	    local_vector[x1][y1] = 128>>dir;
 	    freelog(LOG_DEBUG,
 		    "Candidate: %s from (%d, %d) to (%d, %d), cost %d",
@@ -777,7 +840,7 @@
 	if (total_cost < maxcost) {
 	  if (warmap.cost[x1][y1] > total_cost) {
 	    warmap.cost[x1][y1] = total_cost;
-	    add_to_warqueue(x1, y1);
+	    add_to_mapqueue(total_cost, x1, y1);
 	    local_vector[x1][y1] = 128>>dir;
 	    freelog(LOG_DEBUG,
 		    "Candidate: %s from (%d, %d) to (%d, %d), cost %d",
@@ -804,23 +867,25 @@
         maxcost = total_cost + 1;
       }
     } /* end  for (dir = 0; dir < 8; dir++) */
-  } while (warqueuesize > warnodes);
+  }
 
-  freelog(LOG_DEBUG, "GOTO: (%d, %d) -> (%d, %d), %u nodes, cost = %d", 
-	  orig_x, orig_y, dest_x, dest_y, warnodes, maxcost - 1);
+  freelog(LOG_DEBUG, "GOTO: (%d, %d) -> (%d, %d), cost = %d", 
+	  orig_x, orig_y, dest_x, dest_y, maxcost - 1);
 
   if (maxcost == 255)
     return 0; /* No route */
 
   /*** Succeeded. The vector at the destination indicates which way we get there.
      Now backtrack to remove all the blind paths ***/
-  warnodes = 0;
-  warqueuesize = 0;
-  add_to_warqueue(dest_x, dest_y);
+  for (x = 0; x < map.xsize; x++)
+    memset(warmap.vector[x], 0, map.ysize*sizeof(unsigned char));
 
-  do {
-    get_from_warqueue(warnodes, &x, &y);
-    warnodes++;
+  init_queue();
+  add_to_mapqueue(0, dest_x, dest_y);
+
+  while (1) {
+    if (!get_from_mapqueue(&x, &y))
+      break;
 
     for (dir = 0; dir < 8; dir++) {
       if ((restriction == GOTO_MOVE_CARDINAL_ONLY) && d[dir][1])
@@ -831,18 +896,16 @@
 	y1 = y + jj[dir];
 	if (!normalize_map_pos(&x1, &y1))
 	  continue;
+	move_cost = (move_type == SEA_MOVING) ? warmap.seacost[x1][y1] : warmap.cost[x1][y1];
 
-	if (move_type == LAND_MOVING)
-	  assert(warmap.cost[x1][y1] != 255);
-        add_to_warqueue(x1, y1);
+        add_to_mapqueue(MAXCOST-1 - move_cost, x1, y1);
         warmap.vector[x1][y1] |= 128>>dir; /* Mark it on the warmap */
         local_vector[x][y] -= 1<<dir; /* avoid repetition */
 	freelog(LOG_DEBUG, "PATH-SEGMENT: %s from (%d, %d) to (%d, %d)",
 		d[7-dir], x1, y1, x, y);
       }
     }
-  } while (warqueuesize > warnodes);
-  freelog(LOG_DEBUG, "BACKTRACE: %u nodes", warnodes);
+  }
 
   return 1;
 }
@@ -876,18 +939,6 @@
     passenger = other_passengers(punit);
   else passenger = NULL;
 
-  /* If we can get to the destination rigth away there is nothing to be gained
-     from going round in little circles to move across desirable squares */
-  for (k = 0; k < 8; k++) {
-    if (warmap.vector[punit->x][punit->y]&(1<<k)
-	&& !(restriction == GOTO_MOVE_CARDINAL_ONLY && dir[k][1])) {
-      x = map_adjust_x(punit->x + ii[k]);
-      y = map_adjust_y(punit->y + jj[k]);
-      if (x == dest_x && y == dest_y)
-	return k;
-    }
-  }
-
   for (k = 0; k < 8; k++) {
     if ((restriction == GOTO_MOVE_CARDINAL_ONLY) && dir[k][1]) continue;
     if (!(warmap.vector[punit->x][punit->y]&(1<<k))) d[k] = 0;
@@ -1539,17 +1590,16 @@
   {
     static const int ii[8] = { -1, 0, 1, -1, 1, -1, 0, 1 };
     static const int jj[8] = { -1, -1, -1, 0, 0, 1, 1, 1 };
-    int x1, y1, dir;
+    int x1, y1, dir, cost;
     struct unit *penemy;
 
     init_gotomap(src_x, src_y, AIR_MOVING);
-    warqueuesize = 0;
-    warnodes = 0;
-    add_to_warqueue(src_x, src_y);
+    add_to_mapqueue(0, src_x, src_y);
 
-    do {
-      get_from_warqueue(warnodes, &x, &y);
-      warnodes++;
+    while (get_from_mapqueue(&x, &y)) {
+      if (warmap.cost[x][y] > moves /* no chance */
+	  || warmap.cost[dest_x][dest_y] == 255) /* found route */
+	break;
 
       for (dir = 0; dir < 8; dir++) {
 	y1 = y + jj[dir];
@@ -1564,14 +1614,12 @@
 	  penemy = is_non_allied_unit_tile(ptile, playerid);
 	  if (penemy
 	      || (x1 == dest_x && y1 == dest_y)) { /* allow attack goto's */
-	    warmap.cost[x1][y1] = warmap.cost[x][y] + 1;
-	    add_to_warqueue(x1, y1);
+	    cost = warmap.cost[x1][y1] = warmap.cost[x][y] + 1;
+	    add_to_mapqueue(cost, x1, y1);
 	  }
 	}
       } /* end for */
-    } while (warmap.cost[x][y] <= moves
-	     && warmap.cost[dest_x][dest_y] == 255
-	     && warnodes < warqueuesize);
+    }
 
     freelog(LOG_DEBUG, "movecost: %i", warmap.cost[dest_x][dest_y]);
   }
diff -Nur -X/home/thue/freeciv-dev/freeciv/diff_ignore freeciv/server/gotohand.h pq/server/gotohand.h
--- freeciv/server/gotohand.h	Sun Jun 18 20:31:34 2000
+++ pq/server/gotohand.h	Sun Jun 25 23:08:20 2000
@@ -40,6 +40,8 @@
   unsigned char *cost[MAP_MAX_WIDTH];
   unsigned char *seacost[MAP_MAX_WIDTH];
   unsigned char *vector[MAP_MAX_WIDTH];
+  char *returned[MAP_MAX_WIDTH]; /* boolean used to indicate if the goto algoritm
+				    has processed this tile */
   struct city *warcity; /* so we know what we're dealing with here */
   struct unit *warunit; /* so we know what we're dealing with here */
   int orig_x, orig_y;