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)
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
***********************************************************************/
28
/* These are used for airplane GOTOs with waypoints */
30
/* Only used in the priority function for the queue */
31
#define MAX_FLIGHT 256
33
/* Type of refuel point */
35
FUEL_START = 0, FUEL_GOAL, FUEL_CITY, FUEL_AIRBASE
38
/* Is this refuel point listed in the queue? */
39
enum refuel_list_status {
40
RLS_NOT_YET, RLS_YES, RLS_ALREADY_NOT
44
enum refuel_type type;
45
enum refuel_list_status listed;
49
struct refuel *coming_from;
53
static struct player_refuel_list {
54
struct refuel *points;
55
/* Size of the actual list */
56
unsigned int list_size;
57
/* Size of the allocated memory in points */
58
unsigned int alloc_size;
59
/* It is convenient to hold additional info here */
60
struct player *pplayer;
66
static void make_list_of_refuel_points(struct player *pplayer,
68
int moves_per_turn, int max_moves);
71
/*---------------- Refuel Points C/D and access --------------------------*/
72
/******************************************************************
73
* Access function for struct refuel
74
*****************************************************************/
75
struct tile *get_refuel_tile(struct refuel *point)
80
/******************************************************************
81
* Access function for struct refuel
82
*****************************************************************/
83
unsigned int get_turns_to_refuel(struct refuel *point)
88
/*------------------- End of Refuel Point C/D and Access ---------------*/
91
/*------------------- Refuel Point List Handling -----------------------*/
92
/******************************************************************
93
* Add new refuel point to the (static) refuel point list.
94
* If the last argument start is TRUE, the point will be written at
95
* the head of the list.
96
*****************************************************************/
97
static void add_refuel_point(struct tile *ptile,
98
enum refuel_type type, int turns,
99
int moves_left, bool start)
106
pos = refuels.list_size;
110
if (pos +1 > refuels.alloc_size) {
111
refuels.alloc_size += ALLOC_STEP;
112
/* If refuels.alloc_size was zero (on the first call),
113
* then refuels.points is NULL and realloc will actually malloc */
114
refuels.points = fc_realloc(refuels.points,
115
refuels.alloc_size * sizeof(*refuels.points));
116
/* This memory, because refuels is static, is never freed.
117
* It is just reused. */
120
/* Fill the new point in */
121
refuels.points[pos].tile = ptile;
122
refuels.points[pos].type = type;
123
refuels.points[pos].listed = RLS_NOT_YET;
124
refuels.points[pos].turns = turns;
125
refuels.points[pos].moves_left = moves_left;
126
refuels.points[pos].coming_from = NULL;
131
/******************************************************************
132
* Wrapper to refuel point access. Checks range too.
133
******************************************************************/
134
static struct refuel *get_refuel_by_index(int i)
136
if (i < 0 || i >= refuels.list_size) {
140
return &refuels.points[i];
143
/*************************************************************************
144
This list should probably be made by having a list of airbase and then
145
adding the players cities. It takes a little time to iterate over the map
146
as it is now, but as it is only used in the players turn that does not
148
Can probably do some caching...
149
*************************************************************************/
150
static void make_list_of_refuel_points(struct player *pplayer,
155
refuels.list_size = 1;
156
refuels.pplayer = pplayer;
157
refuels.moves_per_turn = moves_per_turn;
158
refuels.max_moves = max_moves;
160
whole_map_iterate(ptile) {
161
if (is_allied_city_tile(ptile, pplayer)
162
&& !is_non_allied_unit_tile(ptile, pplayer) ) {
163
add_refuel_point(ptile, FUEL_CITY,
164
MAP_MAX_HEIGHT + MAP_MAX_WIDTH, 0, FALSE);
165
} else if (tile_has_special(ptile, S_AIRBASE)
166
&& !is_non_allied_unit_tile(ptile, pplayer)
168
add_refuel_point(ptile, FUEL_AIRBASE,
169
MAP_MAX_HEIGHT + MAP_MAX_WIDTH, 0, FALSE);
171
} whole_map_iterate_end;
174
/*************************************************************************
175
* Priority function for refuel points --- on the basis of their
176
* turn-distance from the starting point
177
************************************************************************/
178
static int queue_priority_function(const void *value)
180
const struct refuel *point = (const struct refuel *) value;
182
return -(MAX_FLIGHT * point->turns - point->moves_left);
185
/*----------------- End of Refuel Point List Handling -----------------*/
188
/*----------------- Refuel Point List Iterators -----------------------*/
190
/*************************************************************************
191
* initialize air-map iterate
192
* Args: (x,y) -- starting point
193
* (dest_x, dest_y) -- proposed destination ( or repeat x,y if none)
194
* cities_only -- will not consider airbases outside cities
195
* moves_left -- moves left
196
* moves_per_turn -- max moves per turn
197
* max_fuel -- max fuel
198
************************************************************************/
199
struct pqueue *refuel_iterate_init(struct player *pplayer,
201
struct tile *dest_tile,
202
bool cities_only, int moves_left,
203
int moves_per_turn, int max_fuel)
206
struct pqueue *rp_queue = pq_create(MAP_MAX_WIDTH);
209
/* List of all refuel points of the player!
210
* TODO: Should cache the results */
211
make_list_of_refuel_points(pplayer, cities_only,
212
moves_per_turn, moves_per_turn * max_fuel);
213
/* Add the starting point: we keep it for later backtracking */
214
add_refuel_point(ptile, FUEL_START, 0, moves_left, TRUE);
216
if (!same_pos(ptile, dest_tile)) {
217
add_refuel_point(dest_tile, FUEL_GOAL,
218
MAP_MAX_HEIGHT + MAP_MAX_WIDTH, 0, FALSE);
221
/* Process the starting point, no need to queue it
222
* Note: starting position is in the head of refuels list */
223
refuel_iterate_process(rp_queue, get_refuel_by_index(0));
226
(void) pq_peek(rp_queue, &index);
227
tmp = get_refuel_by_index(index);
229
if (tmp && same_pos(ptile, tmp->tile)) {
230
/* We should get the starting point twice
231
* in case we start on less than full fuel */
232
pq_remove(rp_queue, NULL);
233
refuel_iterate_process(rp_queue, tmp);
239
/*************************************************************************
240
* Get the next refuel point (wrt the turn-distance from the starting
241
* point). Sort out the points that are already processed.
242
************************************************************************/
243
struct refuel *refuel_iterate_next(struct pqueue *rp_list)
245
struct refuel *next_point;
247
/* Get the next nearest point from the queue
248
* (ignoring already processed ones) */
250
short int index = -1;
252
(void) pq_remove(rp_list, &index);
254
next_point = get_refuel_by_index(index);
255
} while(next_point != NULL && next_point->listed == RLS_ALREADY_NOT);
258
if (next_point != NULL) {
259
/* Mark as processed */
260
next_point->listed = RLS_ALREADY_NOT;
266
/*************************************************************************
267
* Process next refuel point: find all points we can reach from pfrom,
268
* see if the new path is better than already existing one, add new
269
* reachable points to the priority queue.
270
************************************************************************/
271
void refuel_iterate_process(struct pqueue *rp_list, struct refuel *pfrom)
275
= (pfrom->type == FUEL_START ? pfrom->moves_left : refuels.max_moves);
277
/* Iteration starts from 1, since 0 is occupied by the start point */
278
for (k = 1; k < refuels.list_size; k++) {
279
struct refuel *pto = get_refuel_by_index(k);
281
= air_can_move_between(max_moves,
282
pfrom->tile, pto->tile,
284
if (moves_left != -1) {
285
int moves_used = max_moves - moves_left;
286
/* Turns used on this flight (for units with fuel > 1) */
288
= 1 + ((moves_used == 0 ? 0 : moves_used - 1)
289
/ refuels.moves_per_turn);
290
/* Total turns to get from the start to the pto refuelling point */
291
int total_turns = pfrom->turns + turns_used;
293
freelog(LOG_DEBUG, "Considering: (%i,%i)->(%i,%i), in (%d %d)",
294
pfrom->tile->x, pfrom->tile->y, pto->tile->x, pto->tile->y,
295
total_turns, moves_left);
296
freelog(LOG_DEBUG, "\t\t compared to (%d %d)",
297
pto->turns, pto->moves_left);
299
if ( (pto->turns > total_turns)
300
|| ((pto->turns == total_turns)
301
&& (moves_left > pto->moves_left)) ) {
302
/* Found a new refuelling point or at least a new route */
303
if (pto->listed == RLS_ALREADY_NOT) {
304
freelog(LOG_ERROR, "Found a shorter route to a node: (%i,%i)",
305
pto->tile->x, pto->tile->y);
308
/* Update the info on pto */
309
pto->coming_from = pfrom;
310
pto->moves_left = moves_left;
311
pto->turns = total_turns;
313
/* Insert it into the queue. No problem if it's already there */
314
pq_insert(rp_list, k, queue_priority_function(pto));
315
pto->listed = RLS_YES;
317
freelog(LOG_DEBUG, "Recorded (%i,%i) from (%i,%i) in (%d %d)",
318
pto->tile->x, pto->tile->y, pfrom->tile->x, pfrom->tile->y,
319
total_turns, moves_left);
325
/*************************************************************************
327
************************************************************************/
328
void refuel_iterate_end(struct pqueue *rp_list)
330
/* No need to free memory allocated for the refuels list
331
* -- it will be reused */
333
/* Just destroy the queue */
337
/*----------------- End of Refuel Point List Iterators -------------------*/
340
/*----------------- Air Goto Standard Functions --------------------------*/
342
/************************************************************************
343
* We need to find a route that our airplane can use without crashing. The
344
* first waypoint of this route is returned inside the arguments dest_x and
345
* dest_y. This can be the point where we start, fx when a plane with few
346
* moves left need to stay in a city to refuel.
348
* This is achieved by a simple use of refuel_iterate and then backtracking.
350
* The path chosen will be such that upon arrival the unit will have maximal
351
* moves left (among the paths that get to dest in minimal number of moves).
354
* We might also make sure that fx a fighter will have enough fuel to fly back
355
* to a base after reaching it's destination. This could be done by making a
356
* list of goal from which the last jump on the route could be done
357
* satisfactory. We should also make sure that bombers given an order to
358
* attack a unit will not make the attack on it's last fuel point etc. etc.
359
***********************************************************************/
360
bool find_air_first_destination(struct unit *punit, struct tile **dest_tile)
362
unsigned int fullmoves = unit_move_rate(punit) / SINGLE_MOVE;
363
unsigned int fullfuel = unit_type(punit)->fuel;
364
unsigned int moves_and_fuel_left
365
= punit->moves_left / SINGLE_MOVE + fullmoves * (punit->fuel - 1);
366
struct pqueue *my_list
367
= refuel_iterate_init(unit_owner(punit), punit->tile,
369
moves_and_fuel_left, fullmoves, fullfuel);
370
struct refuel *next_point;
371
bool reached_goal = FALSE;
373
while((next_point = refuel_iterate_next(my_list)) != NULL) {
374
freelog(LOG_DEBUG, "Next point (%d, %d), priority %d",
375
next_point->tile->x, next_point->tile->y,
376
queue_priority_function(next_point));
377
if (next_point -> type == FUEL_GOAL) {
382
refuel_iterate_process(my_list, next_point);
386
struct refuel *backtrack = next_point;
387
while (backtrack->coming_from->type != FUEL_START) {
388
backtrack = backtrack->coming_from;
389
freelog(LOG_DEBUG, "(%i,%i) ->",
390
backtrack->tile->x, backtrack->tile->y);
392
freelog(LOG_DEBUG, "Found a route!");
393
*dest_tile = backtrack->tile;
395
freelog(LOG_DEBUG, "Didn't find a route...");
397
refuel_iterate_end(my_list);
403
/*----------------- End of Air Goto Standard Functions ------------------*/
added
removed
server/airgoto.c
