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