← Back to branch summary

~cody.smith/ubuntu/precise/freeciv/lp.202327

« back to all changes in this revision

Viewing changes to server/gotohand.c

  • Committer: Package Import Robot
  • Author(s): Clint Adams, Karl Goetz, Clint Adams
  • Date: 2011-08-28 22:40:00 UTC
  • mfrom: (17.1.3 sid)
  • Revision ID: package-import@ubuntu.com-20110828224000-itma4s7fttxl4hdq
Tags: 2.3.0-1
[ Karl Goetz ]
* New upstream version.
* Fix themes_sdl_use_system_fonts.diff to apply cleanly on 2.3.0
* Massage work_around_unity_induced_breakage.diff to get it
  applying to the new codebase (The patch assumes commits made
  after 2.3.0 was tagged upstream).

[ Clint Adams ]
* Fudge build system to think there is no libtool mismatch.

Show diffs side-by-side

added added

removed removed

Lines of Context:
server/gotohand.c
1
 
/********************************************************************** 
2
 
 Freeciv - Copyright (C) 1996 - A Kjeldberg, L Gregersen, P Unold
3
 
   This program is free software; you can redistribute it and/or modify
4
 
   it under the terms of the GNU General Public License as published by
5
 
   the Free Software Foundation; either version 2, or (at your option)
6
 
   any later version.
7
 
 
8
 
   This program is distributed in the hope that it will be useful,
9
 
   but WITHOUT ANY WARRANTY; without even the implied warranty of
10
 
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
11
 
   GNU General Public License for more details.
12
 
***********************************************************************/
13
 
 
14
 
#ifdef HAVE_CONFIG_H
15
 
#include <config.h>
16
 
#endif
17
 
 
18
 
#include <assert.h>
19
 
#include <stdio.h>
20
 
#include <stdlib.h>
21
 
#include <string.h>
22
 
 
23
 
#include "log.h"
24
 
#include "mem.h"
25
 
#include "rand.h"
26
 
 
27
 
#include "combat.h"
28
 
#include "game.h"
29
 
#include "map.h"
30
 
#include "movement.h"
31
 
#include "unitlist.h"
32
 
 
33
 
#include "maphand.h"
34
 
#include "settlers.h"
35
 
#include "unithand.h"
36
 
#include "unittools.h"
37
 
 
38
 
#include "aidata.h"
39
 
#include "aitools.h"
40
 
 
41
 
#include "gotohand.h"
42
 
 
43
 
struct move_cost_map warmap;
44
 
 
45
 
/* 
46
 
 * These settings should be either true or false.  They are used for
47
 
 * finding routes for airplanes - the airplane doesn't want to fly
48
 
 * through occupied territory, but most territory will be either
49
 
 * fogged or unknown entirely.  See airspace_looks_safe().  Note that
50
 
 * this is currently only used by the move-counting function
51
 
 * air_can_move_between(), not by the path-finding function (whatever
52
 
 * that may be).
53
 
 */
54
 
#define AIR_ASSUMES_UNKNOWN_SAFE        TRUE
55
 
#define AIR_ASSUMES_FOGGED_SAFE         TRUE
56
 
 
57
 
static bool airspace_looks_safe(struct tile *ptile, struct player *pplayer);
58
 
 
59
 
 
60
 
/* These are used for all GOTO's */
61
 
 
62
 
/* A byte must be able to hold this value i.e. is must be less than
63
 
   256. */
64
 
#define MAXCOST 255
65
 
#define MAXARRAYS 10000
66
 
#define ARRAYLENGTH 10
67
 
 
68
 
struct mappos_array {
69
 
  int first_pos;
70
 
  int last_pos;
71
 
  struct tile *tile[ARRAYLENGTH];
72
 
  struct mappos_array *next_array;
73
 
};
74
 
 
75
 
struct array_pointer {
76
 
  struct mappos_array *first_array;
77
 
  struct mappos_array *last_array;
78
 
};
79
 
 
80
 
static struct mappos_array *mappos_arrays[MAXARRAYS];
81
 
static struct array_pointer cost_lookup[MAXCOST];
82
 
static int array_count;
83
 
static int lowest_cost;
84
 
static int highest_cost;
85
 
 
86
 
 
87
 
/*************************************************************************
88
 
 Used to check if the warmap distance to a position is "finite".
89
 
*************************************************************************/
90
 
bool is_dist_finite(int dist)
91
 
{
92
 
 
93
 
  return (dist < MAXCOST);
94
 
}
95
 
 
96
 
/**************************************************************************
97
 
...
98
 
**************************************************************************/
99
 
static void init_queue(void)
100
 
{
101
 
  int i;
102
 
  static bool is_initialized = FALSE;
103
 
 
104
 
  if (!is_initialized) {
105
 
    for (i = 0; i < MAXARRAYS; i++) {
106
 
      mappos_arrays[i] = NULL;
107
 
    }
108
 
    is_initialized = TRUE;
109
 
  }
110
 
 
111
 
  for (i = 0; i < MAXCOST; i++) {
112
 
    cost_lookup[i].first_array = NULL;
113
 
    cost_lookup[i].last_array = NULL;
114
 
  }
115
 
  array_count = 0;
116
 
  lowest_cost = 0;
117
 
  highest_cost = 0;
118
 
}
119
 
 
120
 
/**************************************************************************
121
 
  Free mapqueue arrays
122
 
**************************************************************************/
123
 
void free_mapqueue(void)
124
 
{
125
 
  int i;
126
 
 
127
 
  for (i = 0; i < MAXARRAYS; i++) {
128
 
    if (mappos_arrays[i] != NULL) {
129
 
      free(mappos_arrays[i]);
130
 
      mappos_arrays[i] = NULL;
131
 
    }
132
 
  }
133
 
}
134
 
 
135
 
/**************************************************************************
136
 
...
137
 
**************************************************************************/
138
 
static struct mappos_array *get_empty_array(void)
139
 
{
140
 
  struct mappos_array *parray;
141
 
 
142
 
  if (!mappos_arrays[array_count]) {
143
 
    mappos_arrays[array_count]
144
 
      = fc_malloc(sizeof(*mappos_arrays[array_count]));
145
 
  }
146
 
  parray = mappos_arrays[array_count++];
147
 
  parray->first_pos = 0;
148
 
  parray->last_pos = -1;
149
 
  parray->next_array = NULL;
150
 
  return parray;
151
 
}
152
 
 
153
 
/**************************************************************************
154
 
...
155
 
**************************************************************************/
156
 
static void add_to_mapqueue(int cost, struct tile *ptile)
157
 
{
158
 
  struct mappos_array *our_array;
159
 
 
160
 
  assert(cost < MAXCOST && cost >= 0);
161
 
 
162
 
  our_array = cost_lookup[cost].last_array;
163
 
  if (!our_array) {
164
 
    our_array = get_empty_array();
165
 
    cost_lookup[cost].first_array = our_array;
166
 
    cost_lookup[cost].last_array = our_array;
167
 
  } else if (our_array->last_pos == ARRAYLENGTH-1) {
168
 
    our_array->next_array = get_empty_array();
169
 
    our_array = our_array->next_array;
170
 
    cost_lookup[cost].last_array = our_array;
171
 
  }
172
 
 
173
 
  our_array->tile[++(our_array->last_pos)] = ptile;
174
 
  if (cost > highest_cost)
175
 
    highest_cost = cost;
176
 
  freelog(LOG_DEBUG, "adding cost:%i at %i,%i", cost, ptile->x, ptile->y);
177
 
}
178
 
 
179
 
/**************************************************************************
180
 
...
181
 
**************************************************************************/
182
 
static struct tile *get_from_mapqueue(void)
183
 
{
184
 
  struct mappos_array *our_array;
185
 
  struct tile *ptile;
186
 
 
187
 
  freelog(LOG_DEBUG, "trying get");
188
 
  while (lowest_cost < MAXCOST) {
189
 
    if (lowest_cost > highest_cost)
190
 
      return FALSE;
191
 
    our_array = cost_lookup[lowest_cost].first_array;
192
 
    if (!our_array) {
193
 
      lowest_cost++;
194
 
      continue;
195
 
    }
196
 
    if (our_array->last_pos < our_array->first_pos) {
197
 
      if (our_array->next_array) {
198
 
        cost_lookup[lowest_cost].first_array = our_array->next_array;
199
 
        continue; /* note NOT "lowest_cost++;" */
200
 
      } else {
201
 
        cost_lookup[lowest_cost].first_array = NULL;
202
 
        lowest_cost++;
203
 
        continue;
204
 
      }
205
 
    }
206
 
    ptile = our_array->tile[our_array->first_pos];
207
 
    our_array->first_pos++;
208
 
    return ptile;
209
 
  }
210
 
  return NULL;
211
 
}
212
 
 
213
 
/**************************************************************************
214
 
Reset the movecosts of the warmap.
215
 
**************************************************************************/
216
 
static void init_warmap(struct tile *orig_tile, enum unit_move_type move_type)
217
 
{
218
 
  if (warmap.size != MAP_INDEX_SIZE) {
219
 
    warmap.cost = fc_realloc(warmap.cost,
220
 
                             MAP_INDEX_SIZE * sizeof(*warmap.cost));
221
 
    warmap.seacost = fc_realloc(warmap.seacost,
222
 
                                MAP_INDEX_SIZE * sizeof(*warmap.seacost));
223
 
    warmap.vector = fc_realloc(warmap.vector,
224
 
                               MAP_INDEX_SIZE * sizeof(*warmap.vector));
225
 
    warmap.size = MAP_INDEX_SIZE;
226
 
  }
227
 
 
228
 
  init_queue();
229
 
 
230
 
  switch (move_type) {
231
 
  case LAND_MOVING:
232
 
  case BOTH_MOVING:
233
 
    assert(sizeof(*warmap.cost) == sizeof(char));
234
 
    memset(warmap.cost, MAXCOST, MAP_INDEX_SIZE * sizeof(char));
235
 
    warmap.cost[tile_index(orig_tile)] = 0;
236
 
    break;
237
 
  case SEA_MOVING:
238
 
    assert(sizeof(*warmap.seacost) == sizeof(char));
239
 
    memset(warmap.seacost, MAXCOST, MAP_INDEX_SIZE * sizeof(char));
240
 
    warmap.seacost[tile_index(orig_tile)] = 0;
241
 
    break;
242
 
  default:
243
 
    freelog(LOG_ERROR, "Bad move_type in init_warmap().");
244
 
  }
245
 
}  
246
 
 
247
 
 
248
 
/**************************************************************************
249
 
This creates a movecostmap (warmap), which is a two-dimentional array
250
 
corresponding to the real map. The value of a position is the number of
251
 
moves it would take to get there. If the function found no route the cost
252
 
is MAXCOST. (the value it is initialized with)
253
 
For sea units we let the map overlap onto the land one field, to allow
254
 
transporters and shore bombardment (ships can target the shore).
255
 
This map does NOT take enemy units onto account, nor ZOC.
256
 
Let generate_warmap interface to this function. Sometimes (in the AI when
257
 
using transports) this function will be called directly.
258
 
 
259
 
It is an search via Dijkstra's Algorithm
260
 
(see fx http://odin.ee.uwa.edu.au/~morris/Year2/PLDS210/dijkstra.html)
261
 
ie it piles tiles on a queue, and then use those tiles to find more tiles,
262
 
until all tiles we can reach are visited. To avoid making the warmap
263
 
potentially too big (heavy to calculate), the warmap is initialized with
264
 
a maxcost value, limiting the maximum length.
265
 
 
266
 
Note that this function is responsible for 20% of the CPU usage of freeciv...
267
 
 
268
 
This function is used by the AI in various cases when it is searching for
269
 
something to do with a unit. Maybe we could make a version that processed
270
 
the tiles in order after how many moves it took the unit to get to them,
271
 
and then gave them to the unit. This would achive 2 things:
272
 
-The unit could stop the function the instant it found what it was looking
273
 
for, or when it had already found something reasonably close and the distance
274
 
to the tiles later being searched was reasoable big. In both cases avoiding
275
 
to build the full warmap.
276
 
-The warmap would avoid examining a tile multiple times due to a series of
277
 
path with succesively smaller cost, since we would always have the smallest
278
 
possible cost the first time.
279
 
This would be done by inserting the tiles in a list after their move_cost
280
 
as they were found.
281
 
**************************************************************************/
282
 
static void really_generate_warmap(struct city *pcity, struct unit *punit,
283
 
                                   enum unit_move_type move_type)
284
 
{
285
 
  int move_cost;
286
 
  struct tile *orig_tile;
287
 
  bool igter, terrain_speed;
288
 
  int maxcost = THRESHOLD * 6 + 2; /* should be big enough without being TOO big */
289
 
  struct tile *ptile;
290
 
  struct player *pplayer;
291
 
  struct unit_class *pclass = NULL;
292
 
  int unit_speed = SINGLE_MOVE;
293
 
 
294
 
  if (pcity) {
295
 
    orig_tile = pcity->tile;
296
 
    pplayer = city_owner(pcity);
297
 
  } else {
298
 
    orig_tile = punit->tile;
299
 
    pplayer = unit_owner(punit);
300
 
  }
301
 
 
302
 
  init_warmap(orig_tile, move_type);
303
 
  add_to_mapqueue(0, orig_tile);
304
 
 
305
 
  igter = FALSE;
306
 
  if (punit) {
307
 
    pclass = unit_class(punit);
308
 
 
309
 
    terrain_speed = uclass_has_flag(unit_class(punit), UCF_TERRAIN_SPEED);
310
 
    if (!terrain_speed /* Igter meaningless without terrain_speed */
311
 
        && unit_has_type_flag(punit, F_IGTER)) {
312
 
      igter = TRUE;
313
 
    }
314
 
    unit_speed = unit_move_rate(punit);
315
 
  } else {
316
 
    /* Guess - can result in bad city warmaps with custom rulesets */
317
 
    if (move_type == LAND_MOVING || move_type == SEA_MOVING) {
318
 
      terrain_speed = TRUE;
319
 
    } else {
320
 
      terrain_speed = FALSE;
321
 
    }
322
 
  }
323
 
 
324
 
  /* FIXME: Should this apply only to F_CITIES units? -- jjm */
325
 
  if (punit
326
 
      && unit_has_type_flag(punit, F_SETTLERS)
327
 
      && unit_move_rate(punit)==3)
328
 
    maxcost /= 2;
329
 
  /* (?) was unit_type(punit) == U_SETTLERS -- dwp */
330
 
 
331
 
  while ((ptile = get_from_mapqueue())) {
332
 
    /* Just look up the cost value once.  This is a minor optimization but
333
 
     * it makes a big difference since this code is called so much. */
334
 
    unsigned char cost = ((move_type == SEA_MOVING)
335
 
                          ? WARMAP_SEACOST(ptile) : WARMAP_COST(ptile));
336
 
 
337
 
    adjc_dir_iterate(ptile, tile1, dir) {
338
 
      struct terrain *pterrain1 = tile_terrain(tile1);
339
 
 
340
 
      if ((move_type == LAND_MOVING && WARMAP_COST(tile1) <= cost)
341
 
          || (move_type == SEA_MOVING && WARMAP_SEACOST(tile1) <= cost)) {
342
 
        continue; /* No need for calculations */
343
 
      }
344
 
  
345
 
      if (!terrain_speed) {
346
 
        if (punit) {
347
 
          if (!can_unit_exist_at_tile(punit, tile1)) {
348
 
 
349
 
            if (can_attack_non_native(unit_type(punit))
350
 
                && is_native_tile(unit_type(punit), ptile)) {
351
 
              /* Able to shore bombardment or similar activity,
352
 
               * but not from city in non-native terrain. */
353
 
 
354
 
              /* Attack cost is SINGLE_MOVE */
355
 
              move_cost = SINGLE_MOVE;
356
 
            } else if (unit_class_transporter_capacity(tile1, pplayer, pclass) > 0) {
357
 
              /* Enters transport */
358
 
              move_cost = SINGLE_MOVE;
359
 
            } else {
360
 
              /* Can't enter tile */
361
 
              continue;
362
 
            }
363
 
          } else {
364
 
            /* Punit can_exist_at_tile() */
365
 
            move_cost = SINGLE_MOVE;
366
 
          }
367
 
        } else {
368
 
          /* No punit. Crude guess */
369
 
          if ((move_type == SEA_MOVING && !is_ocean(pterrain1))
370
 
              || (move_type == LAND_MOVING && is_ocean(pterrain1))) {
371
 
            /* Can't enter tile */
372
 
            continue;
373
 
          }
374
 
          move_cost = SINGLE_MOVE;
375
 
        }
376
 
      } else {
377
 
  
378
 
        /* Speed determined by terrain */
379
 
        if (punit) {
380
 
          if (!can_unit_exist_at_tile(punit, tile1)) {
381
 
            if (can_attack_non_native(unit_type(punit))
382
 
                && is_native_tile(unit_type(punit), ptile)) {
383
 
              /* Shore bombardment. Impossible if already in city
384
 
               * in non-native terrain. */
385
 
              move_cost = SINGLE_MOVE;
386
 
              
387
 
            } else if (unit_class_transporter_capacity(tile1, pplayer, pclass) > 0) {
388
 
              /* Go on board */
389
 
              move_cost = SINGLE_MOVE;
390
 
            } else {
391
 
              /* Can't enter tile */
392
 
              continue;
393
 
            }
394
 
          } else if (is_native_tile(unit_type(punit), tile1)) {
395
 
            /* can_exist_at_tile() */ 
396
 
            int base_cost = map_move_cost(ptile, tile1);
397
 
  
398
 
            base_cost = base_cost > unit_speed ? unit_speed : base_cost;
399
 
            move_cost = igter ? MIN(MOVE_COST_ROAD, base_cost) : base_cost;
400
 
          } else {
401
 
            /* can_exist_at_tile(), but !is_native_tile() -> entering port */
402
 
            move_cost = SINGLE_MOVE;
403
 
          }
404
 
        } else if ((move_type == LAND_MOVING && is_ocean(pterrain1))
405
 
                   || (move_type == SEA_MOVING && !is_ocean(pterrain1))) {
406
 
          continue;     /* City warmap ignores possible transports */
407
 
        } else {
408
 
          move_cost = map_move_cost(ptile, tile1);
409
 
        }
410
 
      }
411
 
  
412
 
      move_cost += cost;
413
 
 
414
 
      if (move_type != SEA_MOVING) {
415
 
        if (WARMAP_COST(tile1) > move_cost && move_cost < maxcost) {
416
 
          warmap.cost[tile_index(tile1)] = move_cost;
417
 
          add_to_mapqueue(move_cost, tile1);
418
 
        }
419
 
      } else if (move_type == SEA_MOVING) {
420
 
        if (WARMAP_SEACOST(tile1) > move_cost && move_cost < maxcost) {
421
 
          /* by adding the move_cost to the warmap regardless if we
422
 
           * can move between we allow for shore bombardment/transport
423
 
           * to inland positions/etc. */
424
 
          warmap.seacost[tile_index(tile1)] = move_cost;
425
 
          if ((punit && can_unit_exist_at_tile(punit, tile1))
426
 
              || (!punit && (is_ocean(pterrain1) || tile_city(tile1)))) {
427
 
            /* Unit can actually move to tile */
428
 
            add_to_mapqueue(move_cost, tile1);
429
 
          }
430
 
        }
431
 
      }
432
 
    } adjc_dir_iterate_end;
433
 
  }
434
 
 
435
 
  freelog(LOG_DEBUG, "Generated warmap for (%d,%d).",
436
 
          TILE_XY(orig_tile)); 
437
 
}
438
 
 
439
 
/**************************************************************************
440
 
This is a wrapper for really_generate_warmap that checks if the warmap we
441
 
want is allready in existence. Also calls correctly depending on whether
442
 
pcity and/or punit is nun-NULL.
443
 
FIXME: Why is the movetype not used initialized on the warmap? Leaving it
444
 
for now.
445
 
**************************************************************************/
446
 
void generate_warmap(struct city *pcity, struct unit *punit)
447
 
{
448
 
  freelog(LOG_DEBUG, "Generating warmap, pcity = %s, punit = %s",
449
 
          (pcity ? city_name(pcity) : "NULL"),
450
 
          (punit ? unit_rule_name(punit) : "NULL"));
451
 
 
452
 
  if (punit) {
453
 
    /* 
454
 
     * If the previous warmap was for the same unit and it's still
455
 
     * correct (warmap.(sea)cost[x][y] == 0), reuse it.
456
 
     */
457
 
    if (warmap.warunit == punit &&
458
 
        (is_sailing_unit(punit) ? (WARMAP_SEACOST(punit->tile) == 0)
459
 
         : (WARMAP_COST(punit->tile) == 0))) {
460
 
      return;
461
 
    }
462
 
 
463
 
    pcity = NULL;
464
 
  }
465
 
 
466
 
  warmap.warcity = pcity;
467
 
  warmap.warunit = punit;
468
 
 
469
 
  warmap.invalid = FALSE;
470
 
 
471
 
  if (punit) {
472
 
    if (is_sailing_unit(punit)) {
473
 
      really_generate_warmap(pcity, punit, SEA_MOVING);
474
 
    } else {
475
 
      really_generate_warmap(pcity, punit, LAND_MOVING);
476
 
    }
477
 
    warmap.orig_tile = punit->tile;
478
 
  } else {
479
 
    really_generate_warmap(pcity, punit, LAND_MOVING);
480
 
    really_generate_warmap(pcity, punit, SEA_MOVING);
481
 
    warmap.orig_tile = pcity->tile;
482
 
  }
483
 
}
484
 
 
485
 
/**************************************************************************
486
 
Return the direction that takes us most directly to dest_x,dest_y.
487
 
The direction is a value for use in DIR_DX[] and DIR_DY[] arrays.
488
 
 
489
 
FIXME: This is a bit crude; this only gives one correct path, but sometimes
490
 
       there can be more than one straight path (fx going NW then W is the
491
 
       same as going W then NW)
492
 
**************************************************************************/
493
 
static int straightest_direction(struct tile *src_tile,
494
 
                                 struct tile *dst_tile)
495
 
{
496
 
  int best_dir;
497
 
  int diff_x, diff_y;
498
 
 
499
 
  /* Should we go up or down, east or west: diff_x/y is the "step" in x/y. */
500
 
  map_distance_vector(&diff_x, &diff_y, src_tile, dst_tile);
501
 
 
502
 
  if (diff_x == 0) {
503
 
    best_dir = (diff_y > 0) ? DIR8_SOUTH : DIR8_NORTH;
504
 
  } else if (diff_y == 0) {
505
 
    best_dir = (diff_x > 0) ? DIR8_EAST : DIR8_WEST;
506
 
  } else if (diff_x > 0) {
507
 
    best_dir = (diff_y > 0) ? DIR8_SOUTHEAST : DIR8_NORTHEAST;
508
 
  } else if (diff_x < 0) {
509
 
    best_dir = (diff_y > 0) ? DIR8_SOUTHWEST : DIR8_NORTHWEST;
510
 
  } else {
511
 
    assert(0);
512
 
    best_dir = 0;
513
 
  }
514
 
 
515
 
  return (best_dir);
516
 
}
517
 
 
518
 
/**************************************************************************
519
 
  Basic checks as to whether a GOTO is possible. The target (x,y) should
520
 
  be on the same continent as punit is, up to embarkation/disembarkation.
521
 
**************************************************************************/
522
 
bool goto_is_sane(struct unit *punit, struct tile *ptile, bool omni)
523
 
{  
524
 
  struct player *pplayer = unit_owner(punit);
525
 
  struct city *pcity = tile_city(ptile);
526
 
  Continent_id my_cont = tile_continent(punit->tile);
527
 
  Continent_id target_cont = tile_continent(ptile);
528
 
 
529
 
  if (same_pos(punit->tile, ptile)) {
530
 
    return TRUE;
531
 
  }
532
 
 
533
 
  if (!(omni || map_is_known_and_seen(ptile, pplayer, V_MAIN))) {
534
 
    /* The destination is in unknown -- assume sane */
535
 
    return TRUE;
536
 
  }
537
 
 
538
 
  switch (uclass_move_type(unit_class(punit))) {
539
 
 
540
 
  case LAND_MOVING:
541
 
    if (is_ocean_tile(ptile)) {
542
 
      /* Going to a sea tile, the target should be next to our continent 
543
 
       * and with a boat */
544
 
      if (unit_class_transporter_capacity(ptile, pplayer,
545
 
                                          unit_class(punit)) > 0) {
546
 
        adjc_iterate(ptile, tmp_tile) {
547
 
          if (tile_continent(tmp_tile) == my_cont) {
548
 
            /* The target is adjacent to our continent! */
549
 
            return TRUE;
550
 
          }
551
 
        } adjc_iterate_end;
552
 
      }
553
 
    } else {
554
 
      /* Going to a land tile: better be our continent */
555
 
      if (my_cont == target_cont) {
556
 
        return TRUE;
557
 
      } else {
558
 
        /* Well, it's not our continent, but maybe we are on a boat
559
 
         * adjacent to the target continent? */
560
 
        adjc_iterate(punit->tile, tmp_tile) {
561
 
          if (tile_continent(tmp_tile) == target_cont) {
562
 
            return TRUE;
563
 
          }
564
 
        } adjc_iterate_end;
565
 
      }
566
 
    }
567
 
      
568
 
    return FALSE;
569
 
 
570
 
  case SEA_MOVING:
571
 
    if (!is_ocean_tile(punit->tile)) {
572
 
      /* Oops, we are not in the open waters.  Pick an ocean that we have
573
 
       * access to.  We can assume we are in a city, and any oceans adjacent
574
 
       * are connected, so it does not matter which one we pick. */
575
 
      adjc_iterate(punit->tile, tmp_tile) {
576
 
        if (is_ocean_tile(tmp_tile)) {
577
 
          my_cont = tile_continent(tmp_tile);
578
 
          break;
579
 
        }
580
 
      } adjc_iterate_end;
581
 
    }
582
 
    if (is_ocean_tile(ptile)) {
583
 
      if (ai_channel(pplayer, target_cont, my_cont)) {
584
 
        return TRUE; /* Ocean -> Ocean travel ok. */
585
 
      }
586
 
    } else if ((pcity && pplayers_allied(city_owner(pcity), pplayer))
587
 
               || !unit_has_type_flag(punit, F_NO_LAND_ATTACK)) {
588
 
      /* Not ocean, but allied city or can bombard, checking if there is
589
 
       * good ocean adjacent */
590
 
      adjc_iterate(ptile, tmp_tile) {
591
 
        if (is_ocean_tile(tmp_tile)
592
 
            && ai_channel(pplayer, my_cont, tile_continent(tmp_tile))) {
593
 
          return TRUE;
594
 
        }
595
 
      } adjc_iterate_end;
596
 
    }
597
 
    return FALSE; /* Not ok. */
598
 
 
599
 
  default:
600
 
    return TRUE;
601
 
  }
602
 
}
603
 
 
604
 
/**************************************************************************
605
 
 Returns true if the airspace at given map position _looks_ safe to
606
 
 the given player. The airspace is unsafe if the player believes
607
 
 there is an enemy unit on it. This is tricky, since we have to
608
 
 consider what the player knows/doesn't know about the tile.
609
 
**************************************************************************/
610
 
static bool airspace_looks_safe(struct tile *ptile, struct player *pplayer)
611
 
{
612
 
  /* 
613
 
   * We do handicap checks for the player with ai_handicap(). This
614
 
   * function returns true if the player is handicapped. For human
615
 
   * players they'll always return true. This is the desired behavior.
616
 
   */
617
 
 
618
 
  /* If the tile's unknown, we (may) assume it's safe. */
619
 
  if (ai_handicap(pplayer, H_MAP) && !map_is_known(ptile, pplayer)) {
620
 
    return AIR_ASSUMES_UNKNOWN_SAFE;
621
 
  }
622
 
 
623
 
  /* This is bad: there could be a city there that the player doesn't
624
 
      know about.  How can we check that? */
625
 
  if (is_non_allied_city_tile(ptile, pplayer)) {
626
 
    return FALSE;
627
 
  }
628
 
 
629
 
  /* If the tile's fogged we again (may) assume it's safe. */
630
 
  if (ai_handicap(pplayer, H_FOG) &&
631
 
      !map_is_known_and_seen(ptile, pplayer, V_MAIN)) {
632
 
    return AIR_ASSUMES_FOGGED_SAFE;
633
 
  }
634
 
 
635
 
  /* The tile is unfogged so we can check for enemy units on the
636
 
     tile. */
637
 
  return !is_non_allied_unit_tile(ptile, pplayer);
638
 
}
639
 
 
640
 
/**************************************************************************
641
 
 An air unit starts (src_x,src_y) with moves moves and want to go to
642
 
 (dest_x,dest_y). It returns the number of moves left if this is
643
 
 possible without running out of moves. It returns -1 if it is
644
 
 impossible.
645
 
 
646
 
  Note that the 'moves' passed to this function should be the number of
647
 
  steps the air unit has left.  The caller should *already* have
648
 
  divided by SINGLE_MOVE.
649
 
 
650
 
The function has 3 stages:
651
 
Try to rule out the possibility in O(1) time              else
652
 
Try to quickly verify in O(moves) time                    else
653
 
Do an A* search using the warmap to completely search for the path.
654
 
**************************************************************************/
655
 
int air_can_move_between(int moves, struct tile *src_tile,
656
 
                         struct tile *dest_tile, struct player *pplayer)
657
 
{
658
 
  struct tile *ptile;
659
 
  int dist, total_distance = real_map_distance(src_tile, dest_tile);
660
 
 
661
 
  freelog(LOG_DEBUG,
662
 
          "air_can_move_between(moves=%d, src=(%i,%i), "
663
 
          "dest=(%i,%i), player=%s)", moves, TILE_XY(src_tile),
664
 
          TILE_XY(dest_tile), player_name(pplayer));
665
 
 
666
 
  /* First we do some very simple O(1) checks. */
667
 
  if (total_distance > moves) {
668
 
    return -1;
669
 
  }
670
 
  if (total_distance == 0) {
671
 
    assert(moves >= 0);
672
 
    return moves;
673
 
  }
674
 
 
675
 
  /* 
676
 
   * Then we do a fast O(n) straight-line check.  It'll work so long
677
 
   * as the straight-line doesn't cross any unreal tiles, unknown
678
 
   * tiles, or enemy-controlled tiles.  So, it should work most of the
679
 
   * time. 
680
 
   */
681
 
  ptile = src_tile;
682
 
  
683
 
  /* 
684
 
   * We don't check the endpoint of the goto, since it is possible
685
 
   * that the endpoint is a tile which has an enemy which should be
686
 
   * attacked. But we do check that all points in between are safe.
687
 
   */
688
 
  for (dist = total_distance; dist > 1; dist--) {
689
 
    /* Warning: straightest_direction may not actually follow the
690
 
       straight line. */
691
 
    int dir = straightest_direction(ptile, dest_tile);
692
 
    struct tile *new_tile;
693
 
 
694
 
    if (!(new_tile = mapstep(ptile, dir))
695
 
        || !airspace_looks_safe(new_tile, pplayer)) {
696
 
      break;
697
 
    }
698
 
    ptile = new_tile;
699
 
  }
700
 
  if (dist == 1) {
701
 
    /* Looks like the O(n) quicksearch worked. */
702
 
    assert(real_map_distance(ptile, dest_tile) == 1);
703
 
    assert(moves - total_distance >= 0);
704
 
    return moves - total_distance;
705
 
  }
706
 
 
707
 
  /* 
708
 
   * Finally, we do a full A* search if this isn't one of the specical
709
 
   * cases from above. This is copied from find_the_shortest_path but
710
 
   * we use real_map_distance as a minimum distance estimator for the
711
 
   * A* search. This distance estimator is used for the cost value in
712
 
   * the queue, but is not stored in the warmap itself.
713
 
   *
714
 
   * Note, A* is possible here but not in a normal FreeCiv path
715
 
   * finding because planes always take 1 movement unit to move -
716
 
   * which is not true of land units.
717
 
   */
718
 
  freelog(LOG_DEBUG,
719
 
          "air_can_move_between: quick search didn't work. Lets try full.");
720
 
 
721
 
  warmap.warunit = NULL;
722
 
  warmap.warcity = NULL;
723
 
 
724
 
  init_warmap(src_tile, BOTH_MOVING);
725
 
 
726
 
  /* The 0 is inaccurate under A*, but it doesn't matter. */
727
 
  add_to_mapqueue(0, src_tile);
728
 
 
729
 
  while ((ptile = get_from_mapqueue())) {
730
 
    adjc_dir_iterate(ptile, tile1, dir) {
731
 
      if (WARMAP_COST(tile1) != MAXCOST) {
732
 
        continue;
733
 
      }
734
 
 
735
 
      /*
736
 
       * This comes before the airspace_looks_safe check because it's
737
 
       * okay to goto into an enemy. 
738
 
       */
739
 
      if (same_pos(tile1, dest_tile)) {
740
 
        /* We're there! */
741
 
        freelog(LOG_DEBUG, "air_can_move_between: movecost: %i",
742
 
                WARMAP_COST(ptile) + 1);
743
 
        /* The -1 is because we haven't taken the final
744
 
           step yet. */
745
 
        assert(moves - WARMAP_COST(ptile) - 1 >= 0);
746
 
        return moves - WARMAP_COST(ptile) - 1;
747
 
      }
748
 
 
749
 
      /* We refuse to goto through unsafe airspace. */
750
 
      if (airspace_looks_safe(tile1, pplayer)) {
751
 
        int cost = WARMAP_COST(ptile) + 1;
752
 
 
753
 
        warmap.cost[tile_index(tile1)] = cost;
754
 
 
755
 
        /* Now for A* we find the minimum total cost. */
756
 
        cost += real_map_distance(tile1, dest_tile);
757
 
        if (cost <= moves) {
758
 
          add_to_mapqueue(cost, tile1);
759
 
        }
760
 
      }
761
 
    } adjc_dir_iterate_end;
762
 
  }
763
 
 
764
 
  freelog(LOG_DEBUG, "air_can_move_between: no route found");
765
 
  return -1;
766
 
}