Fix a shipper metadata bug.
[vms-empire.git] / map.c
1 /*
2  *    Copyright (C) 1987, 1988 Chuck Simmons
3  * 
4  * See the file COPYING, distributed with empire, for restriction
5  * and warranty information.
6  */
7
8 /*
9 map.c
10
11 This file contains routines for playing around with view_maps,
12 real_maps, path_maps, and cont_maps.
13 */
14
15 #include <string.h>
16 #include "empire.h"
17 #include "extern.h"
18
19 #define SWAP(a,b) { \
20         perimeter_t *x; \
21         x = a; a = b; b = x; \
22 }
23
24 static void expand_perimeter(path_map_t *,view_map_t *,move_info_t *,
25                              perimeter_t *,int,int,int,int,
26                              perimeter_t *,perimeter_t *);
27 static void expand_prune(view_map_t *,path_map_t *,
28                          loc_t,int,perimeter_t *,int *);
29 static int objective_cost(view_map_t *,move_info_t *,loc_t,int);
30 static int terrain_type(path_map_t *,view_map_t *,move_info_t *,loc_t,loc_t);
31 static void start_perimeter(path_map_t *,perimeter_t *,loc_t,int);
32 static void add_cell(path_map_t *,loc_t,perimeter_t *,int,int,int);
33 static int vmap_count_path (path_map_t *,loc_t);
34
35 static perimeter_t p1; /* perimeter list for use as needed */
36 static perimeter_t p2;
37 static perimeter_t p3;
38 static perimeter_t p4;
39
40 static int best_cost; /* cost and location of best objective */
41 static loc_t best_loc;
42
43 /*
44 Map out a continent.  We are given a location on the continent.
45 We mark each square that is part of the continent and unexplored
46 territory adjacent to the continent.  By adjusting the value of
47 'bad_terrain', this routine can map either continents of land,
48 or lakes.
49 */
50
51 void
52 vmap_cont (int *cont_map, view_map_t *vmap, loc_t loc, char bad_terrain)
53 {
54     (void) memset ((char *)cont_map, '\0', MAP_SIZE * sizeof (int));
55     vmap_mark_up_cont (cont_map, vmap, loc, bad_terrain);
56 }
57
58 /*
59 Mark all squares of a continent and the squares that are adjacent
60 to the continent which are on the board.  Our passed location is
61 known to be either on the continent or adjacent to the continent.
62 */
63
64 void
65 vmap_mark_up_cont(int *cont_map, view_map_t *vmap, loc_t loc, char bad_terrain)
66 {
67     int i, j;
68     loc_t new_loc;
69     char this_terrain;
70     perimeter_t *from, *to;
71
72     from = &p1;
73     to = &p2;
74         
75     from->len = 1; /* init perimeter */
76     from->list[0] = loc;
77     cont_map[loc] = 1; /* loc is on continent */
78         
79     while (from->len) {
80         to->len = 0; /* nothing in new perimeter yet */
81                 
82         for (i = 0; i < from->len; i++) /* expand perimeter */
83             FOR_ADJ_ON(from->list[i], new_loc, j)
84                 if (!cont_map[new_loc]) {
85                     /* mark, but don't expand, unexplored territory */
86                     if (vmap[new_loc].contents == ' ')
87                         cont_map[new_loc] = 1;
88                     else {
89                         if (vmap[new_loc].contents == MAP_LAND)
90                             this_terrain = MAP_LAND;
91                         else if (vmap[new_loc].contents == MAP_SEA)
92                             this_terrain = MAP_SEA;
93                         else this_terrain = map[new_loc].contents;
94                                 
95                         if (this_terrain != bad_terrain) { /* on continent? */
96                             cont_map[new_loc] = 1;
97                             to->list[to->len] = new_loc;
98                             to->len += 1;
99                         }
100                     }
101                 }
102         SWAP (from, to);
103     }
104 }
105
106 /*
107 Map out a continent.  We are given a location on the continent.
108 We mark each square that is part of the continent.
109 By adjusting the value of
110 'bad_terrain', this routine can map either continents of land,
111 or lakes.
112 */
113
114 static void rmap_mark_up_cont(int *cont_map, loc_t loc, char bad_terrain);
115
116 void
117 rmap_cont(int *cont_map, loc_t loc, char bad_terrain)
118 {
119     (void) memset ((char *)cont_map, '\0', MAP_SIZE * sizeof (int));
120     rmap_mark_up_cont (cont_map, loc, bad_terrain);
121 }
122
123 /*
124 Mark all squares of a continent and the squares that are adjacent
125 to the continent which are on the board.  Our passed location is
126 known to be either on the continent or adjacent to the continent.
127
128 Someday this should be tweaked to use perimeter lists.
129 */
130
131 static void
132 rmap_mark_up_cont(int *cont_map, loc_t loc, char bad_terrain)
133 {
134     int i;
135     loc_t new_loc;
136         
137     if (!map[loc].on_board) return; /* off board */
138     if (cont_map[loc]) return; /* already marked */
139     if (map[loc].contents == bad_terrain) return; /* off continent */
140         
141     cont_map[loc] = 1; /* on continent */
142
143     FOR_ADJ (loc, new_loc, i)
144         rmap_mark_up_cont (cont_map, new_loc, bad_terrain);
145 }
146
147 /*
148 Scan a continent recording items of interest on the continent.
149
150 This could be done as we mark up the continent.
151 */
152
153 #define COUNT(c,item) case c: item += 1; break
154
155 scan_counts_t
156 vmap_cont_scan(int *cont_map, view_map_t *vmap)
157 {
158     scan_counts_t counts;
159     count_t i;
160
161     (void) memset ((char *)&counts, '\0', sizeof (scan_counts_t));
162         
163     for (i = 0; i < MAP_SIZE; i++) {
164         if (cont_map[i]) { /* cell on continent? */
165             counts.size += 1;
166                         
167             switch (vmap[i].contents) {
168                 COUNT (' ', counts.unexplored);
169                 COUNT ('O', counts.user_cities);
170                 COUNT ('A', counts.user_objects[ARMY]);
171                 COUNT ('F', counts.user_objects[FIGHTER]);
172                 COUNT ('P', counts.user_objects[PATROL]);
173                 COUNT ('D', counts.user_objects[DESTROYER]);
174                 COUNT ('S', counts.user_objects[SUBMARINE]);
175                 COUNT ('T', counts.user_objects[TRANSPORT]);
176                 COUNT ('C', counts.user_objects[CARRIER]);
177                 COUNT ('B', counts.user_objects[BATTLESHIP]);
178                 COUNT ('X', counts.comp_cities);
179                 COUNT ('a', counts.comp_objects[ARMY]);
180                 COUNT ('f', counts.comp_objects[FIGHTER]);
181                 COUNT ('p', counts.comp_objects[PATROL]);
182                 COUNT ('d', counts.comp_objects[DESTROYER]);
183                 COUNT ('s', counts.comp_objects[SUBMARINE]);
184                 COUNT ('t', counts.comp_objects[TRANSPORT]);
185                 COUNT ('c', counts.comp_objects[CARRIER]);
186                 COUNT ('b', counts.comp_objects[BATTLESHIP]);
187                 COUNT (MAP_CITY, counts.unowned_cities);
188             case MAP_LAND: break;
189             case MAP_SEA: break;
190             default: /* check for city underneath */
191                 if (map[i].contents == MAP_CITY) {
192                     switch (map[i].cityp->owner) {
193                         COUNT (USER, counts.user_cities);
194                         COUNT (COMP, counts.comp_cities);
195                         COUNT (UNOWNED, counts.unowned_cities);
196                     }
197                 }
198             }
199         }
200     }
201     return counts;
202 }
203
204 /*
205 Scan a real map as above.  Only the 'size' and 'unowned_cities'
206 fields are valid.
207 */
208
209 scan_counts_t
210 rmap_cont_scan(int *cont_map)
211 {
212     scan_counts_t counts;
213     count_t i;
214
215     (void) memset ((char *)&counts, '\0', sizeof (scan_counts_t));
216         
217     for (i = 0; i < MAP_SIZE; i++) {
218         if (cont_map[i]) { /* cell on continent? */
219             counts.size += 1;
220             if (map[i].contents == MAP_CITY)
221                 counts.unowned_cities += 1;
222         }
223     }
224     return counts;
225 }
226
227 /*
228 Return true if a location is on the edge of a continent.
229 */
230
231 bool
232 map_cont_edge(int *cont_map, loc_t loc)
233 {
234     loc_t i, j;
235
236     if (!cont_map[loc]) return false; /* not on continent */
237  
238     FOR_ADJ (loc, j, i)
239         if (!cont_map[j]) return true; /* edge of continent */
240
241     return false;
242 }
243
244 /*
245 Find the nearest objective for a piece.  This routine actually does
246 some real work.  This code represents my fourth rewrite of the
247 algorithm.  This algorithm is central to the strategy used by the
248 computer.
249
250 Given a view_map, we create a path_map.  On the path_map, we record
251 the distance from a location to the nearest objective.  We are
252 given information about what the interesting objectives are, and
253 how interesting each objective is.
254
255 We use a breadth first search to find the nearest objective.
256 We maintain something called a "perimeter list".  This list
257 initially contains a list of squares that we can reach in 'n' moves.
258 On each pass through our loop, we add all squares that are adjacent
259 to the perimeter list and which lie outside the perimeter to our
260 list.  (The loop is only slightly more complicated for armies and
261 transports.)
262
263 When our perimeter list becomes empty, or when the distance to
264 the current perimeter is at least as large as the weighted distance
265 to the best objective, we return the location of the best objective
266 found.
267
268 The 'cost' field in a path_map must be INFINITY if the cell lies
269 outside of the current perimeter.  The cost for cells that lie
270 on or within the current perimeter doesn't matter, except that
271 the information must be consistent with the needs of 'vmap_mark_path'.
272 */
273
274 /* Find an objective over a single type of terrain. */
275
276 loc_t
277 vmap_find_xobj(path_map_t path_map[], view_map_t *vmap, 
278                 loc_t loc, move_info_t *move_info, int start, int expand)
279 {
280     perimeter_t *from;
281     perimeter_t *to;
282     int cur_cost;
283
284     from = &p1;
285     to = &p2;
286         
287     start_perimeter (path_map, from, loc, start);
288     cur_cost = 0; /* cost to reach current perimeter */
289
290     for (;;) {
291         to->len = 0; /* nothing in perim yet */
292         expand_perimeter (path_map, vmap, move_info, from, expand,
293                           cur_cost, 1, 1, to, to);
294                 
295         if (trace_pmap)
296             print_pzoom ("After xobj loop:", path_map, vmap);
297
298         cur_cost += 1;
299         if (to->len == 0 || best_cost <= cur_cost)
300             return best_loc;
301
302         SWAP (from, to);
303     }
304 }
305         
306 /* Find an objective for a piece that crosses land and water. */
307
308 loc_t
309 vmap_find_aobj(path_map_t path_map[], view_map_t *vmap, 
310                 loc_t loc, move_info_t *move_info)
311 {
312     return vmap_find_xobj (path_map, vmap, loc, move_info, T_LAND, T_AIR);
313 }
314
315 /* Find an objective for a piece that crosses only water. */
316
317 loc_t
318 vmap_find_wobj(path_map_t path_map[], view_map_t *vmap, 
319                 loc_t loc, move_info_t *move_info)
320 {
321     return vmap_find_xobj (path_map, vmap, loc, move_info, T_WATER, T_WATER);
322 }
323
324 /* Find an objective for a piece that crosses only land. */
325
326 loc_t
327 vmap_find_lobj(path_map_t path_map[], view_map_t *vmap, 
328                 loc_t loc, move_info_t *move_info)
329 {
330     return vmap_find_xobj (path_map, vmap, loc, move_info, T_LAND, T_LAND);
331 }
332
333 /*
334 Find an objective moving from land to water.
335 This is mildly complicated.  It costs 2 to move on land
336 and one to move on water.  To handle this, we expand our current
337 perimeter by one cell, where land can be expanded to either
338 land or water, and water is only expanded to water.  Then
339 we expand any water one more cell.
340
341 We have different objectives depending on whether the objective
342 is being approached from the land or the water.
343 */
344
345 loc_t
346 vmap_find_lwobj(path_map_t path_map[], view_map_t *vmap, 
347                  loc_t loc, move_info_t *move_info, int beat_cost)
348 {
349     perimeter_t *cur_land;
350     perimeter_t *cur_water;
351     perimeter_t *new_land;
352     perimeter_t *new_water;
353     int cur_cost;
354
355     cur_land = &p1;
356     cur_water = &p2;
357     new_water = &p3;
358     new_land = &p4;
359         
360     start_perimeter (path_map, cur_land, loc, T_LAND);
361     cur_water->len = 0;
362     best_cost = beat_cost; /* we can do this well */
363     cur_cost = 0; /* cost to reach current perimeter */
364
365     for (;;) {
366         /* expand current perimeter one cell */
367         new_water->len = 0;
368         new_land->len = 0;
369         expand_perimeter (path_map, vmap, move_info, cur_water,
370                           T_WATER, cur_cost, 1, 1, new_water, NULL);
371
372         expand_perimeter (path_map, vmap, move_info, cur_land,
373                           T_AIR, cur_cost, 1, 2, new_water, new_land);
374                                   
375         /* expand new water one cell */
376         cur_water->len = 0;
377         expand_perimeter (path_map, vmap, move_info, new_water,
378                           T_WATER, cur_cost+1, 1, 1, cur_water, NULL);
379                                   
380         if (trace_pmap)
381             print_pzoom ("After lwobj loop:", path_map, vmap);
382                 
383         cur_cost += 2;
384         if ( (cur_water->len == 0 && new_land->len == 0) || 
385              (best_cost <= cur_cost) ) {
386             return best_loc;
387         }
388
389         SWAP (cur_land, new_land);
390     }
391 }
392
393 #ifdef __UNUSED__
394 /*
395 Return the cost to reach the adjacent cell of the correct type
396 with the lowest cost.
397 */
398
399 static int
400 best_adj(path_map_t *pmap, loc_t loc, int type)
401 {
402     int i;
403     loc_t new_loc;
404     int best;
405
406     best = INFINITY;
407
408     FOR_ADJ (loc, new_loc, i)
409         if (pmap[new_loc].terrain == type && pmap[new_loc].cost < best)
410             best = pmap[new_loc].cost;
411
412     return best;
413 }
414 #endif
415
416 /*
417 Find an objective moving from water to land.
418 Here, we expand water to either land or water.
419 We expand land only to land.
420
421 We cheat ever so slightly, but this cheating accurately reflects
422 the mechanics o moving.  The first time we expand water we can
423 expand to land or water (army moving off tt or tt moving on water),
424 but the second time, we only expand water (tt taking its second move).
425 */
426
427 loc_t
428 vmap_find_wlobj(path_map_t path_map[], view_map_t *vmap, 
429                  loc_t loc, move_info_t *move_info)
430 {
431     perimeter_t *cur_land;
432     perimeter_t *cur_water;
433     perimeter_t *new_land;
434     perimeter_t *new_water;
435     int cur_cost;
436
437     cur_land = &p1;
438     cur_water = &p2;
439     new_water = &p3;
440     new_land = &p4;
441         
442     start_perimeter (path_map, cur_water, loc, T_WATER);
443     cur_land->len = 0;
444     cur_cost = 0; /* cost to reach current perimeter */
445
446     for (;;) {
447         /* expand current perimeter one cell */
448         new_water->len = 0;
449         new_land->len = 0;
450         expand_perimeter (path_map, vmap, move_info, cur_water,
451                           T_AIR, cur_cost, 1, 2, new_water, new_land);
452
453         expand_perimeter (path_map, vmap, move_info, cur_land,
454                           T_LAND, cur_cost, 1, 2, NULL, new_land);
455                                   
456         /* expand new water one cell to water */
457         cur_water->len = 0;
458         expand_perimeter (path_map, vmap, move_info, new_water,
459                           T_WATER, cur_cost+1, 1, 1, cur_water, NULL);
460                                   
461         if (trace_pmap)
462             print_pzoom ("After wlobj loop:", path_map, vmap);
463                 
464         cur_cost += 2;
465         if ( (cur_water->len == 0 && new_land->len == 0) || 
466              (best_cost <= cur_cost) ) {
467             return best_loc;
468         }
469         SWAP (cur_land, new_land);
470     }
471 }
472
473 /*
474 Initialize the perimeter searching.
475
476 This routine was taking a significant amount of the program time (10%)
477 doing the initialization of the path map.  We now use an external
478 constant and 'memcpy'.
479 */
480
481 static path_map_t pmap_init[MAP_SIZE];
482 static bool init_done = false;
483
484 static void
485 start_perimeter(path_map_t *pmap, perimeter_t *perim, loc_t loc, int terrain)
486 {
487     /* zap the path map */
488     if (!init_done) {
489         int i;
490         
491         init_done = true;
492         for (i = 0; i < MAP_SIZE; i++) {
493             pmap_init[i].cost = INFINITY; /* everything lies outside perim */
494             pmap_init[i].terrain = T_UNKNOWN;
495         }
496     }
497     (void) memcpy ((char *)pmap, (char *)pmap_init, sizeof (pmap_init));
498         
499     /* put first location in perimeter */
500     pmap[loc].cost = 0;
501     pmap[loc].inc_cost = 0;
502     pmap[loc].terrain = terrain;
503
504     perim->len = 1;
505     perim->list[0] = loc;
506         
507     best_cost = INFINITY; /* no best yet */
508     best_loc = loc; /* if nothing found, result is current loc */
509 }
510
511 /*
512 Expand the perimeter.
513
514 Note that 'waterp' and 'landp' may be the same.
515
516 For each cell of the current perimeter, we examine each
517 cell adjacent to that cell which lies outside of the current
518 perimeter.  If the adjacent cell is an objective, we update
519 best_cost and best_loc.  If the adjacent cell is of the correct
520 type, we turn place the adjacent cell in either the new water perimeter
521 or the new land perimeter.
522
523 We set the cost to reach the current perimeter.
524 */
525
526 static void
527 expand_perimeter(path_map_t *pmap, view_map_t *vmap, move_info_t *move_info, 
528                   perimeter_t *curp, 
529                   int type, int cur_cost, int inc_wcost, int inc_lcost, 
530                   perimeter_t *waterp, perimeter_t *landp)
531 /* pmap = path map to update */
532 /* move_info = objectives and weights */
533 /* curp = perimeter to expand */
534 /* type = type of terrain to expand */
535 /* cur_cost = cost to reach cells on perimeter */
536 /* inc_wcost = cost to enter new water cells */
537 /* inc_lcost = cost to enter new land cells */
538 /* waterp = pointer to new water perimeter */
539 /* landp = pointer to new land perimeter */
540 {
541     register long i;
542     register int j;
543     loc_t new_loc;
544     int obj_cost;
545     register int new_type;
546
547     for (i = 0; i < curp->len; i++) /* for each perimeter cell... */
548         FOR_ADJ_ON (curp->list[i], new_loc, j) {/* for each adjacent cell... */
549             register path_map_t *pm = pmap + new_loc;
550
551             if (pm->cost == INFINITY) {
552                 new_type = terrain_type (pmap, vmap, move_info, curp->list[i], new_loc);
553
554                 if (new_type == T_LAND && (type & T_LAND))
555                     add_cell (pmap, new_loc, landp, new_type, cur_cost, inc_lcost);
556                 else if (new_type == T_WATER && (type & T_WATER))
557                     add_cell (pmap, new_loc, waterp, new_type, cur_cost, inc_wcost);
558                 else if (new_type == T_UNKNOWN) { /* unreachable cell? */
559                     pm->terrain = new_type;
560                     pm->cost = cur_cost + INFINITY/2;
561                     pm->inc_cost = INFINITY/2;
562                 }
563                 if (pmap[new_loc].cost != INFINITY) { /* did we expand? */
564                     obj_cost = objective_cost (vmap, move_info, new_loc, cur_cost);
565                     if (obj_cost < best_cost) {
566                         best_cost = obj_cost;
567                         best_loc = new_loc;
568                         if (new_type == T_UNKNOWN) {
569                             pm->cost=cur_cost+2;
570                             pm->inc_cost = 2;
571                         }
572                     }
573                 }
574             }
575         }
576 }
577                         
578 /* Add a cell to a perimeter list. */
579         
580 static void
581 add_cell(path_map_t *pmap, loc_t new_loc, 
582           perimeter_t *perim, int terrain, int cur_cost, int inc_cost)
583 {
584     register    path_map_t      *pm = &pmap[new_loc];
585
586     pm->terrain = terrain;
587     pm->inc_cost = inc_cost;
588     pm->cost = cur_cost + inc_cost;
589
590     perim->list[perim->len] = new_loc;
591     perim->len += 1;
592 }
593
594 /* Compute the cost to move to an objective. */
595
596 static int
597 objective_cost(view_map_t *vmap, move_info_t *move_info, 
598                 loc_t loc, int base_cost)
599 {
600     char *p;
601     int w;
602     city_info_t *cityp;
603
604     p = strchr (move_info->objectives, vmap[loc].contents);
605     if (!p) return INFINITY;
606
607     w = move_info->weights[p - move_info->objectives];
608     if (w >= 0) return w + base_cost;
609
610     switch (w) {
611     case W_TT_BUILD:
612         /* handle special case of moving to tt building city */
613         cityp = find_city (loc);
614         if (!cityp) return base_cost + 2; /* tt is already here */
615         if (cityp->prod != TRANSPORT) return base_cost + 2; /* just finished a tt */
616         
617         /* compute time to wait for tt to be built */
618         w = piece_attr[TRANSPORT].build_time - cityp->work;
619         w *= 2; /* had to cross land to get here */
620         if (w < base_cost + 2) w = base_cost + 2;
621         return w;
622
623     default:
624         ABORT;
625         /* NOTREACHED */
626         return -1;
627     }
628 }
629
630 /*
631 Return the type of terrain at a vmap location.
632 */
633
634 static int
635 terrain_type(path_map_t *pmap, view_map_t *vmap, move_info_t *move_info,
636               loc_t from_loc, loc_t to_loc)
637 {
638     if (vmap[to_loc].contents == MAP_LAND) return T_LAND;
639     if (vmap[to_loc].contents == MAP_SEA) return T_WATER;
640     if (vmap[to_loc].contents == '%') return T_UNKNOWN; /* magic objective */
641     if (vmap[to_loc].contents == ' ') return pmap[from_loc].terrain;
642         
643     switch (map[to_loc].contents) {
644     case MAP_SEA: return T_WATER;
645     case MAP_LAND: return T_LAND;
646     case MAP_CITY:
647         if (map[to_loc].cityp->owner == move_info->city_owner)
648             return T_WATER;
649         else
650             return T_UNKNOWN; /* cannot cross */
651     }
652     ABORT;
653     /*NOTREACHED*/
654     return -1;
655 }
656
657 /*
658 Prune unexplored territory.  We take a view map and we modify it
659 so that unexplored territory that is adjacent to a lot of land
660 or a lot of water is marked as being either that land or water.
661 So basically, we are making a predicition about what we expect
662 for land and water.  We iterate this algorithm until either
663 the next iteration would remove all unexplored territory, or
664 there is nothing more about which we can make an assumption.
665
666 First, we use a pathmap to save the number of adjacent land
667 and water cells for each unexplored cell.  Cells which have
668 adjacent explored territory are placed in a perimeter list.
669 We also count the number of cells that are not unexplored.
670
671 We now take this perimeter list and make high-probability
672 predictions.
673
674 Then we round things off by making one pass of medium
675 probability predictions.
676
677 Then we make multiple passes extending our predictions.
678
679 We stop if at any point all remaining unexplored cells are
680 in a perimeter list, or if no predictions were made during
681 one of the final passes.
682
683 Unlike other algorithms, here we deal with "off board" locations.
684 So be careful.
685 */
686
687 void
688 vmap_prune_explore_locs(view_map_t *vmap)
689 {
690     path_map_t pmap[MAP_SIZE];
691     perimeter_t *from, *to;
692     int explored;
693     loc_t loc, new_loc;
694     count_t i;
695     long copied;
696
697     (void) memset (pmap, '\0', sizeof (pmap));
698     from = &p1;
699     to = &p2;
700     from->len = 0;
701     explored = 0;
702         
703     /* build initial path map and perimeter list */
704     for (loc = 0; loc < MAP_SIZE; loc++) {
705         if (vmap[loc].contents != ' ')
706             explored += 1;
707         else { /* add unexplored cell to perim */
708             FOR_ADJ (loc, new_loc, i) {
709                 if (new_loc < 0 || new_loc >= MAP_SIZE); /* ignore off map */
710                 else if (vmap[new_loc].contents == ' '); /* ignore adjacent unexplored */
711                 else if (map[new_loc].contents != MAP_SEA)
712                     pmap[loc].cost += 1; /* count land */
713                 else pmap[loc].inc_cost += 1; /* count water */
714             }
715             if (pmap[loc].cost || pmap[loc].inc_cost) {
716                 from->list[from->len] = loc;
717                 from->len += 1;
718             }
719         }
720     }
721                                 
722     if (print_vmap == 'I')
723         print_xzoom (vmap);
724                 
725     for (;;) { /* do high probability predictions */
726         if (from->len + explored == MAP_SIZE) return;
727         to->len = 0;
728         copied = 0;
729                 
730         for (i = 0; i < from->len; i++) {
731             loc = from->list[i];
732             if (pmap[loc].cost >= 5)
733                 expand_prune (vmap, pmap, loc, T_LAND, to, &explored);
734             else if (pmap[loc].inc_cost >= 5)
735                 expand_prune (vmap, pmap, loc, T_WATER, to, &explored);
736             else if ((loc < MAP_WIDTH || loc >= MAP_SIZE-MAP_WIDTH) && pmap[loc].cost >= 3)
737                 expand_prune (vmap, pmap, loc, T_LAND, to, &explored);
738             else if ((loc < MAP_WIDTH || loc >= MAP_SIZE-MAP_WIDTH) && pmap[loc].inc_cost >= 3)
739                 expand_prune (vmap, pmap, loc, T_WATER, to, &explored);
740             else if ((loc == 0 || loc == MAP_SIZE-1) && pmap[loc].cost >= 2)
741                 expand_prune (vmap, pmap, loc, T_LAND, to, &explored);
742             else if ((loc == 0 || loc == MAP_SIZE-1) && pmap[loc].inc_cost >= 2)
743                 expand_prune (vmap, pmap, loc, T_WATER, to, &explored);
744             else { /* copy perimeter cell */
745                 to->list[to->len] = loc;
746                 to->len += 1;
747                 copied += 1;
748             }
749         }
750         if (copied == from->len) break; /* nothing expanded */
751         SWAP (from, to);
752     }
753         
754     if (print_vmap == 'I')
755         print_xzoom (vmap);
756                 
757     /* one pass for medium probability predictions */
758     if (from->len + explored == MAP_SIZE)
759         return;
760     to->len = 0;
761         
762     for (i = 0; i < from->len; i++) {
763         loc = from->list[i];
764         if (pmap[loc].cost > pmap[loc].inc_cost)
765             expand_prune (vmap, pmap, loc, T_LAND, to, &explored);
766         else if (pmap[loc].cost < pmap[loc].inc_cost)
767             expand_prune (vmap, pmap, loc, T_WATER, to, &explored);
768         else { /* copy perimeter cell */
769             to->list[to->len] = loc;
770             to->len += 1;
771         }
772     }
773     SWAP (from, to);
774
775     if (print_vmap == 'I') print_xzoom (vmap);
776                 
777     /* multiple low probability passes */
778     for (;;) {
779         /* return if very little left to explore */
780         if (from->len + explored >= MAP_SIZE - MAP_HEIGHT) {
781             if (print_vmap == 'I') print_xzoom (vmap);
782             return;
783         }
784         to->len = 0;
785         copied = 0;
786                 
787         for (i = 0; i < from->len; i++) {
788             loc = from->list[i];
789             if (pmap[loc].cost >= 4 && pmap[loc].inc_cost < 4)
790                 expand_prune (vmap, pmap, loc, T_LAND, to, &explored);
791             else if (pmap[loc].inc_cost >= 4 && pmap[loc].cost < 4)
792                 expand_prune (vmap, pmap, loc, T_WATER, to, &explored);
793             else if ((loc < MAP_WIDTH || loc >= MAP_SIZE-MAP_WIDTH) && pmap[loc].cost > pmap[loc].inc_cost)
794                 expand_prune (vmap, pmap, loc, T_LAND, to, &explored);
795             else if ((loc < MAP_WIDTH || loc >= MAP_SIZE-MAP_WIDTH) && pmap[loc].inc_cost > pmap[loc].cost)
796                 expand_prune (vmap, pmap, loc, T_WATER, to, &explored);
797             else { /* copy perimeter cell */
798                 to->list[to->len] = loc;
799                 to->len += 1;
800                 copied += 1;
801             }
802         }
803         if (copied == from->len) break; /* nothing expanded */
804         SWAP (from, to);
805     }
806     if (print_vmap == 'I') print_xzoom (vmap);
807 }
808
809 /*
810 Expand an unexplored cell.  We increment the land or water count
811 of each neighbor.  Any neighbor that acquires a non-zero count
812 is added to the 'to' perimiter list.  The count of explored
813 territory is incremented.
814
815 Careful:  'loc' may be "off board".
816 */
817
818 static void
819 expand_prune(view_map_t *vmap, path_map_t *pmap,
820               loc_t loc, int type, perimeter_t *to, int *explored)
821 {
822     int i;
823     loc_t new_loc;
824         
825     *explored += 1;
826         
827     if (type == T_LAND)
828         vmap[loc].contents = MAP_LAND;
829     else
830         vmap[loc].contents = MAP_SEA;
831         
832     FOR_ADJ (loc, new_loc, i)
833         if (new_loc >= 0 && new_loc < MAP_SIZE && vmap[new_loc].contents == ' ') {
834             if (!pmap[new_loc].cost && !pmap[new_loc].inc_cost) {
835                 to->list[to->len] = new_loc;
836                 to->len += 1;
837             }
838             if (type == T_LAND)
839                 pmap[new_loc].cost += 1;
840             else pmap[new_loc].inc_cost += 1;
841         }
842 }
843         
844 /*
845 Find the shortest path from the current location to the
846 destination which passes over valid terrain.  We return
847 the destination if a path exists.  Otherwise we return the
848 origin.
849
850 This is similar to 'find_objective' except that we know our destination.
851 */
852
853 loc_t
854 vmap_find_dest(path_map_t path_map[], view_map_t vmap[], 
855                 loc_t cur_loc, loc_t dest_loc, int owner, int terrain)
856 /* cur_loc = current location of piece */
857 /* dest_loc = destination of piece */
858 /* owner = owner of piece being moved */
859 /* terrain = terrain we can cross */
860 {
861     perimeter_t *from;
862     perimeter_t *to;
863     int cur_cost;
864     int start_terrain;
865     move_info_t move_info;
866     char old_contents;
867
868     old_contents = vmap[dest_loc].contents;
869     vmap[dest_loc].contents = '%'; /* mark objective */
870     move_info.city_owner = owner;
871     move_info.objectives = "%";
872     move_info.weights[0] = 1;
873
874     from = &p1;
875     to = &p2;
876         
877     if (terrain == T_AIR) start_terrain = T_LAND;
878     else start_terrain = terrain;
879         
880     start_perimeter (path_map, from, cur_loc, start_terrain);
881     cur_cost = 0; /* cost to reach current perimeter */
882
883     for (;;) {
884         to->len = 0; /* nothing in perim yet */
885         expand_perimeter (path_map, vmap, &move_info, from,
886                           terrain, cur_cost, 1, 1, to, to);
887         cur_cost += 1;
888         if (to->len == 0 || best_cost <= cur_cost) {
889             vmap[dest_loc].contents = old_contents;
890             return best_loc;
891         }
892         SWAP (from, to);
893     }
894 }
895
896 /*
897 Starting with the destination, we recursively back track toward the source
898 marking all cells which are on a shortest path between the start and the
899 destination.  To do this, we know the distance from the destination to
900 the start.  The destination is on a path.  We then find the cells adjacent
901 to the destination and nearest to the source and place them on the path.
902
903 If we know square P is on the path, then S is on the path if S is
904 adjacent to P, the cost to reach S is less than the cost to reach P,
905 and the cost to move from S to P is the difference in cost between
906 S and P.
907
908 Someday, this routine should probably use perimeter lists as well.
909 */
910
911 void
912 vmap_mark_path(path_map_t *path_map, view_map_t *vmap, loc_t dest)
913 {
914     int n;
915     loc_t new_dest;
916
917     if (path_map[dest].cost == 0) return; /* reached end of path */
918     if (path_map[dest].terrain == T_PATH) return; /* already marked */
919
920     path_map[dest].terrain = T_PATH; /* this square is on path */
921
922     /* loop to mark adjacent squares on shortest path */
923     FOR_ADJ (dest, new_dest, n)
924         if (path_map[new_dest].cost == path_map[dest].cost - path_map[dest].inc_cost)
925             vmap_mark_path (path_map, vmap, new_dest);
926
927 }
928
929 /*
930 Create a marked path map.  We mark those squares adjacent to the
931 starting location which are on the board.  'find_dir' must be
932 invoked to decide which squares are actually valid.
933 */
934
935 void
936 vmap_mark_adjacent(path_map_t path_map[], loc_t loc)
937 {
938     int i;
939     loc_t new_loc;
940
941     FOR_ADJ_ON (loc, new_loc, i)
942         path_map[new_loc].terrain = T_PATH;
943 }
944
945 /*
946 Modify a marked path map.  We mark those squares adjacent to the
947 starting location which are on the board and which are adjacent
948 to a location on the existing shortest path.
949 */
950
951 void
952 vmap_mark_near_path(path_map_t path_map[], loc_t loc)
953 {
954     int i, j;
955     loc_t new_loc, xloc;
956     int hit_loc[8];
957
958     (void) memset ((char *)hit_loc, '\0', sizeof(int)*8);
959         
960     FOR_ADJ_ON (loc, new_loc, i) {
961         FOR_ADJ_ON (new_loc, xloc, j)
962             if (xloc != loc && path_map[xloc].terrain == T_PATH) {
963                 hit_loc[i] = 1;
964                 break;
965             }
966     }
967     for (i = 0; i < 8; i++)
968         if (hit_loc[i])
969             path_map[loc + dir_offset[i]].terrain = T_PATH;
970 }
971
972 /*
973 Look at each neighbor of 'loc'.  Select the first marked cell which
974 is on a short path to the desired destination, and which holds a valid
975 terrain.  Note that while this terrain is matched against a 'vmap',
976 it differs slightly from terrains used above.  This terrain is the
977 terrain to which we can move immediately, and does not include terrain
978 for which we would have to wait for another piece to move off of.
979
980 We prefer diagonal moves, and we try to have as many squares
981 as possible containing something in 'adj_char'.
982
983 For tie-breaking, we prefer moving to cells that are adjacent to
984 as many other squares on the path.  This should have a few benefits:
985
986 1)  Fighters are less likely to be blocked from reaching a city
987 because they stay in the center of the path and increase the number
988 of options for subsequent moves.
989
990 2)  Transports will approach a city so that as many armies
991 as possible can hop off the tt on one turn to take a valid
992 path toward the city.
993
994 3)  User pieces will move more intuitively by staying in the
995 center of the best path.
996 */
997
998 static int order[] = {NORTHWEST, NORTHEAST, SOUTHWEST, SOUTHEAST, 
999                         WEST, EAST, NORTH, SOUTH};
1000
1001 loc_t
1002 vmap_find_dir(path_map_t path_map[], view_map_t *vmap,
1003               loc_t loc, char *terrain, char *adj_char)
1004 {
1005     int i, count, bestcount;
1006     loc_t bestloc, new_loc;
1007     int path_count, bestpath;
1008     char *p;
1009         
1010     if (trace_pmap)
1011         print_pzoom ("Before vmap_find_dir:", path_map, vmap);
1012                 
1013     bestcount = -INFINITY; /* no best yet */
1014     bestpath = -1;
1015     bestloc = loc;
1016         
1017     for (i = 0; i < 8; i++) { /* for each adjacent square */
1018         new_loc = loc + dir_offset[order[i]];
1019         if (path_map[new_loc].terrain == T_PATH) { /* which is on path */
1020             p = strchr (terrain, vmap[new_loc].contents);
1021                         
1022             if (p != NULL) { /* desirable square? */
1023                 count = vmap_count_adjacent (vmap, new_loc, adj_char);
1024                 path_count = vmap_count_path (path_map, new_loc);
1025                                 
1026                 /* remember best location */
1027                 if (count > bestcount
1028                     || (count == bestcount && path_count > bestpath) ) {
1029                     bestcount = count;
1030                     bestpath = path_count;
1031                     bestloc = new_loc;
1032                 }
1033             }
1034         }
1035     }
1036     return (bestloc);
1037 }
1038         
1039 /*
1040 Count the number of adjacent squares of interest.
1041 Squares are weighted so that the first in the list
1042 is the most interesting.
1043 */
1044
1045 int
1046 vmap_count_adjacent(view_map_t *vmap, loc_t loc, char *adj_char)
1047 {
1048     int i, count;
1049     loc_t new_loc;
1050     char *p;
1051     int len;
1052
1053     len = strlen (adj_char);
1054
1055     count = 0;
1056         
1057     FOR_ADJ_ON (loc, new_loc, i) {
1058         p = strchr (adj_char, vmap[new_loc].contents);
1059         if (p) count += 8 * (len - (p - adj_char));
1060     }
1061     return (count);
1062 }
1063
1064 /*
1065 Count the number of adjacent cells that are on the path.
1066 */
1067
1068 int
1069 vmap_count_path(path_map_t *pmap, loc_t loc)
1070 {
1071     int i, count;
1072     loc_t new_loc;
1073
1074     count = 0;
1075         
1076     FOR_ADJ_ON (loc, new_loc, i)
1077         if (pmap[new_loc].terrain == T_PATH)
1078             count += 1;
1079
1080     return (count);
1081 }
1082
1083 /*
1084 See if a location is on the shore.  We return true if a surrounding
1085 cell contains water and is on the board.
1086 */
1087
1088 bool
1089 rmap_shore(loc_t loc)
1090 {
1091     loc_t i, j;
1092
1093     FOR_ADJ_ON (loc, j, i)
1094         if (map[j].contents == MAP_SEA)
1095             return (true);
1096
1097     return (false);
1098 }
1099
1100 bool
1101 vmap_shore(view_map_t *vmap, loc_t loc)
1102 {
1103     loc_t i, j;
1104
1105     FOR_ADJ_ON (loc, j, i)
1106         if (vmap[j].contents != ' ' &&
1107             vmap[j].contents != MAP_LAND &&
1108             map[j].contents == MAP_SEA)
1109             return (true);
1110
1111     return (false);
1112 }
1113
1114 /*
1115 Return true if a location is surrounded by ocean.  Off board locations
1116 which cannot be moved to are treated as ocean.
1117 */
1118
1119 bool
1120 vmap_at_sea(view_map_t *vmap, loc_t loc)
1121 {
1122     loc_t i, j;
1123
1124     if (map[loc].contents != MAP_SEA)
1125         return (false);
1126     FOR_ADJ_ON (loc, j, i)
1127         if (vmap[j].contents == ' '
1128             || vmap[j].contents == MAP_LAND
1129             || map[j].contents != MAP_SEA)
1130             return (false);
1131
1132     return (true);
1133 }
1134
1135 bool
1136 rmap_at_sea (loc_t loc)
1137 {
1138     loc_t i, j;
1139
1140     if (map[loc].contents != MAP_SEA)
1141         return (false);
1142     FOR_ADJ_ON (loc, j, i) {
1143         if (map[j].contents != MAP_SEA)
1144             return (false);
1145     }
1146     return (true);
1147 }
1148
1149 /* end */