Freeciv-3.3: /fast/freeciv/nightly/main/server/advisors/autoexplorer.c Source File

Freeciv-3.3

Loading...
Searching...
No Matches
autoexplorer.c
Go to the documentation of this file.
1/***********************************************************************
2 Freeciv - Copyright (C) 2004 - The Freeciv Project
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 <fc_config.h>
16#endif
17
18#include <math.h> /* log */
19
20/* utility */
21#include "bitvector.h"
22#include "log.h"
23
24/* common */
25#include "ai.h"
26#include "map.h"
27#include "movement.h"
28#include "player.h"
29#include "unit.h"
30
31/* common/aicore */
32#include "path_finding.h"
33#include "pf_tools.h"
34
35/* server */
36#include "maphand.h"
37#include "srv_log.h"
38
39/* server/advisors */
40#include "advgoto.h"
41
42/* ai */
43#include "handicaps.h"
44
45#include "autoexplorer.h"
46
47
48/**********************************************************************/
53 static int likely_native(struct tile *ptile,
54 struct player *pplayer,
55 struct unit_class *pclass)
56{
57 int native = 0;
58 int foreign = 0;
59
60 /* We do not check H_MAP here, it should be done by map_is_known() */
61 if (map_is_known(ptile, pplayer)) {
62 /* we've seen the tile already. */
63 return (is_native_tile_to_class(pclass, ptile) ? 100 : 0);
64 }
65
66 /* The central tile is likely to be the same as the
67 * nearby tiles. */
68 adjc_dir_iterate(&(wld.map), ptile, ptile1, dir) {
69 if (map_is_known(ptile1, pplayer)) {
70 if (is_native_tile_to_class(pclass, ptile)) {
71 native++;
72 } else {
73 foreign++;
74 }
75 }
76 } adjc_dir_iterate_end;
77
78 return 50 + (50 / MAP_NUM_VALID_DIRS * (native - foreign));
79}
80
81/**********************************************************************/
86 static bool player_may_explore(const struct tile *ptile,
87 const struct player *pplayer,
88 const struct unit_type *punittype)
89{
90 struct city *pcity;
91
92 /* Don't allow military units to cross borders. */
93 if (!utype_has_flag(punittype, UTYF_CIVILIAN)
94 && !player_can_invade_tile(pplayer, ptile)) {
95 return FALSE;
96 }
97
98 /* Can't visit tiles with non-allied units. */
99 if (is_non_allied_unit_tile(ptile, pplayer,
100 utype_has_flag(punittype, UTYF_FLAGLESS))) {
101 return FALSE;
102 }
103
104 /* Non-allied cities are taboo even if no units are inside. */
105 pcity = tile_city(ptile);
106 if (pcity != NULL
107 && !pplayers_allied(city_owner(pcity), pplayer)) {
108 return FALSE;
109 }
110
111 return TRUE;
112}
113
114/**********************************************************************/
117 static enum tile_behavior explorer_tb(const struct tile *ptile,
118 enum known_type k,
119 const struct pf_parameter *param)
120{
121 if (!player_may_explore(ptile, param->owner, param->utype)) {
122 return TB_IGNORE;
123 }
124 return TB_NORMAL;
125}
126
127/**********************************************************************/
130 static bool explorer_goto(struct unit *punit, struct tile *ptile)
131{
132 struct pf_parameter parameter;
133 struct adv_risk_cost risk_cost;
134 bool alive = TRUE;
135 struct pf_map *pfm;
136 struct pf_path *path;
137 struct player *pplayer = unit_owner(punit);
138 const struct civ_map *nmap = &(wld.map);
139
140 pft_fill_unit_parameter(&parameter, nmap, punit);
141 parameter.omniscience = !has_handicap(pplayer, H_MAP);
142 parameter.get_TB = explorer_tb;
143 adv_avoid_risks(&parameter, &risk_cost, punit, NORMAL_STACKING_FEARFULNESS);
144
145 /* Show the destination in the client */
146 punit->goto_tile = ptile;
147
148 UNIT_LOG(LOG_DEBUG, punit, "explorer_goto to %d,%d", TILE_XY(ptile));
149
150 pfm = pf_map_new(&parameter);
151 path = pf_map_path(pfm, ptile);
152
153 if (path != NULL) {
154 alive = adv_follow_path(punit, path, ptile);
155 pf_path_destroy(path);
156 }
157
158 pf_map_destroy(pfm);
159
160 return alive;
161}
162
163/**********************************************************************/
173#define SAME_TER_SCORE 21
174#define DIFF_TER_SCORE 81
175#define KNOWN_SAME_TER_SCORE 0
176#define KNOWN_DIFF_TER_SCORE 51
177
178/* The maximum number of tiles that the unit might uncover in a move.
179 * #define MAX_NEW_TILES (1 + 4 * (unit_type_get(punit)->vision_range))
180 * The previous line would be ideal, but we'd like these to be constants
181 * for efficiency, so pretend vision_range == 1 */
182#define MAX_NEW_TILES 5
183
184/* The number of tiles that the unit can see. =(1 + 2r)^2
185 * #define VISION_TILES (1 + 2 * unit_type_get(punit)->vision_range)*\
186 * (1 + 2 * unit_type_get(punit)->vision_range)
187 * As above, set vision_range == 1 */
188#define VISION_TILES 9
189
190/* The desirability of the best tile possible without cities or huts.
191 * TER_SCORE is given per 1% of certainty about the terrain, so
192 * muliply by 100 to compensate. */
193#define BEST_NORMAL_TILE \
194 (100 * MAX_NEW_TILES * DIFF_TER_SCORE +\
195 100 * (VISION_TILES - MAX_NEW_TILES) * KNOWN_DIFF_TER_SCORE)
196
197/* We value exploring around our cities just slightly more than exploring
198 * tiles fully surrounded by different terrain. */
199#define OWN_CITY_SCORE (BEST_NORMAL_TILE + 1)
200
201/* And we value exploring huts even more than our own cities.
202 * FIXME: different desirability of entering different huts
203 * in different circumstates must be specifiable by a ruleset. */
204#define HUT_SCORE (OWN_CITY_SCORE + 1)
205
206#define BEST_POSSIBLE_SCORE (HUT_SCORE + BEST_NORMAL_TILE)
207
208 static int explorer_desirable(struct tile *ptile, struct player *pplayer,
209 struct unit *punit)
210{
211 int radius_sq = unit_type_get(punit)->vision_radius_sq;
212 int desirable = 0;
213 int unknown = 0;
214
215 /* First do some checks that would make a tile completely non-desirable.
216 * If we're a barbarian and the tile has a hut, don't go there. */
217 /* FIXME: Would be ok for a unit that does not enter or frighten hut */
218 if (is_barbarian(pplayer) && hut_on_tile(ptile)) {
219 return 0;
220 }
221
222 /* Do no try to cross borders and break a treaty, etc. */
223 if (!player_may_explore(ptile, punit->owner, unit_type_get(punit))) {
224 return 0;
225 }
226
227 circle_iterate(&(wld.map), ptile, radius_sq, ptile1) {
228 int native = likely_native(ptile1, pplayer, unit_class_get(punit));
229
230 if (!map_is_known(ptile1, pplayer)) {
231 unknown++;
232
233 /* FIXME: we should add OWN_CITY_SCORE to desirable if the tile
234 * can be harvested by a city of ours. Just calculating this each
235 * time becomes rather expensive. Jason Short suggests:
236 * It should be easy to generate this information once, for
237 * the entire world. It can be used by everyone and only
238 * sometimes needs to be recalculated (actually all changes
239 * only require local recalculation, but that could be unstable). */
240
241 desirable += (native * SAME_TER_SCORE + (100 - native) * DIFF_TER_SCORE);
242 } else {
243 if (is_tiles_adjacent(ptile, ptile1)) {
244 /* we don't value staying offshore from land,
245 * only adjacent. Otherwise destroyers do the wrong thing. */
246 desirable += (native * KNOWN_SAME_TER_SCORE
247 + (100 - native) * KNOWN_DIFF_TER_SCORE);
248 }
249 }
250 } circle_iterate_end;
251
252 if (unknown <= 0) {
253 /* We make sure we'll uncover at least one unexplored tile. */
254 desirable = 0;
255 }
256
257 if ((!is_ai(pplayer) || !has_handicap(pplayer, H_HUTS))
258 && map_is_known(ptile, pplayer)
259 && unit_can_enter_hut(punit, ptile)) {
260 /* we want to explore huts whenever we can,
261 * even if doing so will not uncover any tiles. */
262 desirable += HUT_SCORE;
263 }
264
265 return desirable;
266}
267
268/**********************************************************************/
277 enum unit_move_result manage_auto_explorer(struct unit *punit)
278{
279 struct player *pplayer = unit_owner(punit);
280 /* Loop prevention */
281 const struct tile *init_tile = unit_tile(punit);
282
283 /* The log of the want of the most desirable tile,
284 * given nearby water, cities, etc. */
285 double log_most_desirable = -FC_INFINITY;
286
287 /* The maximum distance we are willing to search. It decreases depending
288 * on the want of already discovered targets. It is defined as the distance
289 * at which a tile with BEST_POSSIBLE_SCORE would have to be found in
290 * order to be better than the current most_desirable tile. */
291 int max_dist = FC_INFINITY;
292
293 /* Coordinates of most desirable tile. Initialized to make
294 * compiler happy. Also MC to the best tile. */
295 struct tile *best_tile = NULL;
296 int best_MC = FC_INFINITY;
297
298 /* Path-finding stuff */
299 struct pf_map *pfm;
300 struct pf_parameter parameter;
301
302 const struct civ_map *nmap = &(wld.map);
303
304#define DIST_FACTOR 0.6
305
306 double logDF = log(DIST_FACTOR);
307 double logBPS = log(BEST_POSSIBLE_SCORE);
308
309 UNIT_LOG(LOG_DEBUG, punit, "auto-exploring.");
310
311 if (!is_human(pplayer) && unit_has_type_flag(punit, UTYF_GAMELOSS)) {
312 UNIT_LOG(LOG_DEBUG, punit, "exploration too dangerous!");
313
314 return MR_BAD_ACTIVITY; /* too dangerous */
315 }
316
317 TIMING_LOG(AIT_EXPLORER, TIMER_START);
318
319 pft_fill_unit_parameter(&parameter, nmap, punit);
320 parameter.get_TB = no_fights_or_unknown;
321 /* When exploring, even AI should pretend to not cheat. */
322 parameter.omniscience = FALSE;
323
324 pfm = pf_map_new(&parameter);
325 pf_map_move_costs_iterate(pfm, ptile, move_cost, FALSE) {
326 int desirable;
327 double log_desirable;
328
329 /* Our callback should insure this. */
330 fc_assert_action(map_is_known(ptile, pplayer), continue);
331
332 desirable = explorer_desirable(ptile, pplayer, punit);
333
334 if (desirable <= 0) {
335 /* Totally non-desirable tile. No need to continue. */
336 continue;
337 }
338
339 /* take the natural log */
340 log_desirable = log(desirable);
341
342 /* Ok, the way we calculate goodness is taking the base tile
343 * desirability amortized by the time it takes to get there:
344 *
345 * goodness = desirability * DIST_FACTOR^total_MC
346 *
347 * TODO: JDS notes that we should really make our exponential
348 * term dimensionless by dividing by move_rate.
349 *
350 * We want to truncate our search, so we calculate a maximum distance
351 * that we would move to find the tile with the most possible desirability
352 * (BEST_POSSIBLE_SCORE) that gives us the same goodness as the current
353 * tile position we're looking at. Therefore we have:
354 *
355 * desirability * DIST_FACTOR^total_MC =
356 * BEST_POSSIBLE_SCORE * DIST_FACTOR^(max distance) (1)
357 *
358 * and then solve for max_dist. We only want to change max_dist when
359 * we find a tile that has better goodness than we've found so far; hence
360 * the conditional below. It looks cryptic, but all it is is testing which
361 * of two goodnesses is bigger after taking the natural log of both sides.
362 */
363 if (log_desirable + move_cost * logDF
364 > log_most_desirable + best_MC * logDF) {
365
366 log_most_desirable = log_desirable;
367 best_tile = ptile;
368 best_MC = move_cost;
369
370 /* take the natural log and solve equation (1) above. We round
371 * max_dist down (is this correct?). */
372 max_dist = best_MC + (log_most_desirable - logBPS)/logDF;
373 }
374
375 /* let's not go further than this */
376 if (move_cost > max_dist) {
377 break;
378 }
379 } pf_map_move_costs_iterate_end;
380 pf_map_destroy(pfm);
381
382 TIMING_LOG(AIT_EXPLORER, TIMER_STOP);
383
384 /* Go to the best tile found. */
385 if (best_tile != NULL) {
386 /* TODO: read the path off the map we made. Then we can make a path
387 * which goes beside the unknown, with a good EC callback... */
388 enum override_bool allow = NO_OVERRIDE;
389
390 if (is_ai(pplayer)) {
391 CALL_PLR_AI_FUNC(want_to_explore, pplayer, punit, best_tile, &allow);
392 }
393 if (allow == OVERRIDE_FALSE) {
394 UNIT_LOG(LOG_DEBUG, punit, "not allowed to explore");
395 return MR_NOT_ALLOWED;
396 }
397 if (!explorer_goto(punit, best_tile)) {
398 /* Died? Strange... */
399 return MR_DEATH;
400 }
401 UNIT_LOG(LOG_DEBUG, punit, "exploration GOTO succeeded");
402 if (punit->moves_left > 0) {
403 /* We can still move on... */
404 if (!same_pos(init_tile, unit_tile(punit))) {
405 /* At least we moved (and maybe even got to where we wanted).
406 * Let's do more exploring.
407 * (Checking only whether our position changed is unsafe: can allow
408 * yoyoing on a RR) */
409 UNIT_LOG(LOG_DEBUG, punit, "recursively exploring...");
410 return manage_auto_explorer(punit);
411 } else {
412 UNIT_LOG(LOG_DEBUG, punit, "done exploring (all finished)...");
413 return MR_PAUSE;
414 }
415 }
416 UNIT_LOG(LOG_DEBUG, punit, "done exploring (but more go go)...");
417 return MR_OK;
418 } else {
419 /* Didn't find anything. */
420 UNIT_LOG(LOG_DEBUG, punit, "failed to explore more");
421 return MR_BAD_MAP_POSITION;
422 }
423#undef DIST_FACTOR
424}
425
426#undef SAME_TER_SCORE
427#undef DIFF_TER_SCORE
428#undef KNOWN_SAME_TER_SCORE
429#undef KNOWN_DIFF_TER_SCORE
430#undef OWN_CITY_SCORE
431#undef HUT_SCORE
adv_follow_path
bool adv_follow_path(struct unit *punit, struct pf_path *path, struct tile *ptile)
Definition advgoto.c:47
adv_avoid_risks
void adv_avoid_risks(struct pf_parameter *parameter, struct adv_risk_cost *risk_cost, struct unit *punit, const double fearfulness)
Definition advgoto.c:595
advgoto.h
NORMAL_STACKING_FEARFULNESS
#define NORMAL_STACKING_FEARFULNESS
Definition advgoto.h:23
ai.h
CALL_PLR_AI_FUNC
#define CALL_PLR_AI_FUNC(_func, _player,...)
Definition ai.h:377
SAME_TER_SCORE
#define SAME_TER_SCORE
Definition autoexplorer.c:173
explorer_desirable
static int explorer_desirable(struct tile *ptile, struct player *pplayer, struct unit *punit)
Definition autoexplorer.c:208
explorer_tb
static enum tile_behavior explorer_tb(const struct tile *ptile, enum known_type k, const struct pf_parameter *param)
Definition autoexplorer.c:117
manage_auto_explorer
enum unit_move_result manage_auto_explorer(struct unit *punit)
Definition autoexplorer.c:277
HUT_SCORE
#define HUT_SCORE
Definition autoexplorer.c:204
DIFF_TER_SCORE
#define DIFF_TER_SCORE
Definition autoexplorer.c:174
explorer_goto
static bool explorer_goto(struct unit *punit, struct tile *ptile)
Definition autoexplorer.c:130
KNOWN_DIFF_TER_SCORE
#define KNOWN_DIFF_TER_SCORE
Definition autoexplorer.c:176
KNOWN_SAME_TER_SCORE
#define KNOWN_SAME_TER_SCORE
Definition autoexplorer.c:175
likely_native
static int likely_native(struct tile *ptile, struct player *pplayer, struct unit_class *pclass)
Definition autoexplorer.c:53
DIST_FACTOR
#define DIST_FACTOR
BEST_POSSIBLE_SCORE
#define BEST_POSSIBLE_SCORE
Definition autoexplorer.c:206
player_may_explore
static bool player_may_explore(const struct tile *ptile, const struct player *pplayer, const struct unit_type *punittype)
Definition autoexplorer.c:86
autoexplorer.h
bitvector.h
city_owner
#define city_owner(_pcity_)
Definition city.h:563
incite_cost
char * incite_cost
Definition comments.c:74
punit
struct unit struct city struct unit struct tile struct extra_type const struct act_prob *act_probs int actor_unit_id struct unit struct unit * punit
Definition dialogs_g.h:74
unit_can_enter_hut
bool unit_can_enter_hut(const struct unit *punit, const struct tile *ptile)
Definition extras.c:720
hut_on_tile
bool hut_on_tile(const struct tile *ptile)
Definition extras.c:705
override_bool
override_bool
Definition fc_types.h:94
NO_OVERRIDE
@ NO_OVERRIDE
Definition fc_types.h:94
OVERRIDE_FALSE
@ OVERRIDE_FALSE
Definition fc_types.h:94
wld
struct world wld
Definition game.c:62
has_handicap
bool has_handicap(const struct player *pplayer, enum handicap_type htype)
Definition handicaps.c:66
handicaps.h
H_MAP
@ H_MAP
Definition handicaps.h:28
H_HUTS
@ H_HUTS
Definition handicaps.h:25
log.h
fc_assert_action
#define fc_assert_action(condition, action)
Definition log.h:187
LOG_DEBUG
@ LOG_DEBUG
Definition log.h:34
is_tiles_adjacent
bool is_tiles_adjacent(const struct tile *tile0, const struct tile *tile1)
Definition map.c:941
same_pos
bool same_pos(const struct tile *tile1, const struct tile *tile2)
Definition map.c:950
map.h
adjc_dir_iterate
#define adjc_dir_iterate(nmap, center_tile, itr_tile, dir_itr)
Definition map.h:424
circle_iterate
#define circle_iterate(nmap, center_tile, sq_radius, tile_itr)
Definition map.h:387
adjc_dir_iterate_end
#define adjc_dir_iterate_end
Definition map.h:428
circle_iterate_end
#define circle_iterate_end
Definition map.h:390
map_is_known
bool map_is_known(const struct tile *ptile, const struct player *pplayer)
Definition maphand.c:901
maphand.h
movement.h
is_native_tile_to_class
static bool is_native_tile_to_class(const struct unit_class *punitclass, const struct tile *ptile)
Definition movement.h:84
unit_move_result
unit_move_result
Definition movement.h:34
MR_OK
@ MR_OK
Definition movement.h:35
MR_BAD_MAP_POSITION
@ MR_BAD_MAP_POSITION
Definition movement.h:43
MR_BAD_ACTIVITY
@ MR_BAD_ACTIVITY
Definition movement.h:41
MR_NOT_ALLOWED
@ MR_NOT_ALLOWED
Definition movement.h:53
MR_DEATH
@ MR_DEATH
Definition movement.h:36
MR_PAUSE
@ MR_PAUSE
Definition movement.h:37
pf_path_destroy
void pf_path_destroy(struct pf_path *path)
Definition path_finding.c:3411
pf_map_new
struct pf_map * pf_map_new(const struct pf_parameter *parameter)
Definition path_finding.c:3182
pf_map_path
struct pf_path * pf_map_path(struct pf_map *pfm, struct tile *ptile)
Definition path_finding.c:3235
pf_map_destroy
void pf_map_destroy(struct pf_map *pfm)
Definition path_finding.c:3206
path_finding.h
pf_map_move_costs_iterate_end
#define pf_map_move_costs_iterate_end
Definition path_finding.h:592
pf_map_move_costs_iterate
#define pf_map_move_costs_iterate(ARG_pfm, NAME_tile, NAME_cost, COND_from_start)
Definition path_finding.h:582
tile_behavior
tile_behavior
Definition path_finding.h:308
TB_NORMAL
@ TB_NORMAL
Definition path_finding.h:309
TB_IGNORE
@ TB_IGNORE
Definition path_finding.h:310
pft_fill_unit_parameter
void pft_fill_unit_parameter(struct pf_parameter *parameter, const struct civ_map *nmap, const struct unit *punit)
Definition pf_tools.c:843
no_fights_or_unknown
enum tile_behavior no_fights_or_unknown(const struct tile *ptile, enum known_type known, const struct pf_parameter *param)
Definition pf_tools.c:493
pf_tools.h
player_can_invade_tile
bool player_can_invade_tile(const struct player *pplayer, const struct tile *ptile)
Definition player.c:270
pplayers_allied
bool pplayers_allied(const struct player *pplayer, const struct player *pplayer2)
Definition player.c:1409
player.h
is_barbarian
static bool is_barbarian(const struct player *pplayer)
Definition player.h:491
is_ai
#define is_ai(plr)
Definition player.h:232
is_human
#define is_human(plr)
Definition player.h:231
FC_INFINITY
#define FC_INFINITY
Definition shared.h:36
srv_log.h
UNIT_LOG
#define UNIT_LOG(loglevel, punit, msg,...)
Definition srv_log.h:98
AIT_EXPLORER
@ AIT_EXPLORER
Definition srv_log.h:61
TIMER_STOP
@ TIMER_STOP
Definition srv_log.h:76
TIMER_START
@ TIMER_START
Definition srv_log.h:76
TIMING_LOG
#define TIMING_LOG(timer, activity)
Definition srv_log.h:125
adv_risk_cost
Definition advgoto.h:26
city
Definition city.h:320
civ_map
Definition map_types.h:71
pf_map
Definition path_finding.c:78
pf_parameter
Definition path_finding.h:357
pf_parameter::get_TB
enum tile_behavior(* get_TB)(const struct tile *ptile, enum known_type known, const struct pf_parameter *param)
Definition path_finding.h:398
pf_parameter::owner
const struct player * owner
Definition path_finding.h:374
pf_parameter::utype
const struct unit_type * utype
Definition path_finding.h:373
pf_parameter::omniscience
bool omniscience
Definition path_finding.h:376
pf_path
Definition path_finding.h:344
player
Definition player.h:249
tile
Definition tile.h:50
unit_class
Definition unittype.h:149
unit_type
Definition unittype.h:507
unit_type::vision_radius_sq
int vision_radius_sq
Definition unittype.h:529
unit
Definition unit.h:140
unit::moves_left
int moves_left
Definition unit.h:152
unit::goto_tile
struct tile * goto_tile
Definition unit.h:157
unit::owner
struct player * owner
Definition unit.h:145
world::map
struct civ_map map
Definition world_object.h:38
TRUE
#define TRUE
Definition support.h:46
FALSE
#define FALSE
Definition support.h:47
tile_city
struct city * tile_city(const struct tile *ptile)
Definition tile.c:83
known_type
known_type
Definition tile.h:35
TILE_XY
#define TILE_XY(ptile)
Definition tile.h:43
unit.h
unit_tile
#define unit_tile(_pu)
Definition unit.h:397
unit_owner
#define unit_owner(_pu)
Definition unit.h:396
is_non_allied_unit_tile
static bool is_non_allied_unit_tile(const struct tile *ptile, const struct player *pplayer, bool everyone_non_allied)
Definition unit.h:433
unit_type_get
const struct unit_type * unit_type_get(const struct unit *punit)
Definition unittype.c:123
unit_class_get
struct unit_class * unit_class_get(const struct unit *punit)
Definition unittype.c:2498
unit_has_type_flag
bool unit_has_type_flag(const struct unit *punit, enum unit_type_flag_id flag)
Definition unittype.c:190
utype_has_flag
static bool utype_has_flag(const struct unit_type *punittype, int flag)
Definition unittype.h:624
MAP_NUM_VALID_DIRS
#define MAP_NUM_VALID_DIRS
Definition world_object.h:65