Freeciv-3.1: /fast/freeciv/nightly/S3_1/server/advisors/autoexplorer.c Source File

Freeciv-3.1

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