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