Reindent the code.
[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 bool
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     /* zap the path map */
490     if (!init_done) {
491         int i;
492         
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 != ' ')
707             explored += 1;
708         else { /* add unexplored cell to perim */
709             FOR_ADJ (loc, new_loc, i) {
710                 if (new_loc < 0 || new_loc >= MAP_SIZE); /* ignore off map */
711                 else if (vmap[new_loc].contents == ' '); /* ignore adjacent unexplored */
712                 else if (map[new_loc].contents != '.')
713                     pmap[loc].cost += 1; /* count land */
714                 else pmap[loc].inc_cost += 1; /* count water */
715             }
716             if (pmap[loc].cost || pmap[loc].inc_cost) {
717                 from->list[from->len] = loc;
718                 from->len += 1;
719             }
720         }
721     }
722                                 
723     if (print_vmap == 'I')
724         print_xzoom (vmap);
725                 
726     for (;;) { /* do high probability predictions */
727         if (from->len + explored == MAP_SIZE) return;
728         to->len = 0;
729         copied = 0;
730                 
731         for (i = 0; i < from->len; i++) {
732             loc = from->list[i];
733             if (pmap[loc].cost >= 5)
734                 expand_prune (vmap, pmap, loc, T_LAND, to, &explored);
735             else if (pmap[loc].inc_cost >= 5)
736                 expand_prune (vmap, pmap, loc, T_WATER, to, &explored);
737             else if ((loc < MAP_WIDTH || loc >= MAP_SIZE-MAP_WIDTH) && pmap[loc].cost >= 3)
738                 expand_prune (vmap, pmap, loc, T_LAND, to, &explored);
739             else if ((loc < MAP_WIDTH || loc >= MAP_SIZE-MAP_WIDTH) && pmap[loc].inc_cost >= 3)
740                 expand_prune (vmap, pmap, loc, T_WATER, to, &explored);
741             else if ((loc == 0 || loc == MAP_SIZE-1) && pmap[loc].cost >= 2)
742                 expand_prune (vmap, pmap, loc, T_LAND, to, &explored);
743             else if ((loc == 0 || loc == MAP_SIZE-1) && pmap[loc].inc_cost >= 2)
744                 expand_prune (vmap, pmap, loc, T_WATER, to, &explored);
745             else { /* copy perimeter cell */
746                 to->list[to->len] = loc;
747                 to->len += 1;
748                 copied += 1;
749             }
750         }
751         if (copied == from->len) break; /* nothing expanded */
752         SWAP (from, to);
753     }
754         
755     if (print_vmap == 'I')
756         print_xzoom (vmap);
757                 
758     /* one pass for medium probability predictions */
759     if (from->len + explored == MAP_SIZE)
760         return;
761     to->len = 0;
762         
763     for (i = 0; i < from->len; i++) {
764         loc = from->list[i];
765         if (pmap[loc].cost > pmap[loc].inc_cost)
766             expand_prune (vmap, pmap, loc, T_LAND, to, &explored);
767         else if (pmap[loc].cost < pmap[loc].inc_cost)
768             expand_prune (vmap, pmap, loc, T_WATER, to, &explored);
769         else { /* copy perimeter cell */
770             to->list[to->len] = loc;
771             to->len += 1;
772         }
773     }
774     SWAP (from, to);
775
776     if (print_vmap == 'I') print_xzoom (vmap);
777                 
778     /* multiple low probability passes */
779     for (;;) {
780         /* return if very little left to explore */
781         if (from->len + explored >= MAP_SIZE - MAP_HEIGHT) {
782             if (print_vmap == 'I') print_xzoom (vmap);
783             return;
784         }
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 >= 4 && pmap[loc].inc_cost < 4)
791                 expand_prune (vmap, pmap, loc, T_LAND, to, &explored);
792             else if (pmap[loc].inc_cost >= 4 && pmap[loc].cost < 4)
793                 expand_prune (vmap, pmap, loc, T_WATER, to, &explored);
794             else if ((loc < MAP_WIDTH || loc >= MAP_SIZE-MAP_WIDTH) && pmap[loc].cost > pmap[loc].inc_cost)
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 > pmap[loc].cost)
797                 expand_prune (vmap, pmap, loc, T_WATER, to, &explored);
798             else { /* copy perimeter cell */
799                 to->list[to->len] = loc;
800                 to->len += 1;
801                 copied += 1;
802             }
803         }
804         if (copied == from->len) break; /* nothing expanded */
805         SWAP (from, to);
806     }
807     if (print_vmap == 'I') print_xzoom (vmap);
808 }
809
810 /*
811 Expand an unexplored cell.  We increment the land or water count
812 of each neighbor.  Any neighbor that acquires a non-zero count
813 is added to the 'to' perimiter list.  The count of explored
814 territory is incremented.
815
816 Careful:  'loc' may be "off board".
817 */
818
819 STATIC void
820 expand_prune(view_map_t *vmap, path_map_t *pmap,
821               loc_t loc, int type, perimeter_t *to, int *explored)
822 {
823     int i;
824     loc_t new_loc;
825         
826     *explored += 1;
827         
828     if (type == T_LAND) vmap[loc].contents = '+';
829     else vmap[loc].contents = '.';
830         
831     FOR_ADJ (loc, new_loc, i)
832         if (new_loc >= 0 && new_loc < MAP_SIZE && vmap[new_loc].contents == ' ') {
833             if (!pmap[new_loc].cost && !pmap[new_loc].inc_cost) {
834                 to->list[to->len] = new_loc;
835                 to->len += 1;
836             }
837             if (type == T_LAND)
838                 pmap[new_loc].cost += 1;
839             else pmap[new_loc].inc_cost += 1;
840         }
841 }
842         
843 /*
844 Find the shortest path from the current location to the
845 destination which passes over valid terrain.  We return
846 the destination if a path exists.  Otherwise we return the
847 origin.
848
849 This is similar to 'find_objective' except that we know our destination.
850 */
851
852 loc_t
853 vmap_find_dest(path_map_t path_map[], view_map_t vmap[], 
854                 loc_t cur_loc, loc_t dest_loc, int owner, int terrain)
855 /* cur_loc = current location of piece */
856 /* dest_loc = destination of piece */
857 /* owner = owner of piece being moved */
858 /* terrain = terrain we can cross */
859 {
860     perimeter_t *from;
861     perimeter_t *to;
862     int cur_cost;
863     int start_terrain;
864     move_info_t move_info;
865     char old_contents;
866
867     old_contents = vmap[dest_loc].contents;
868     vmap[dest_loc].contents = '%'; /* mark objective */
869     move_info.city_owner = owner;
870     move_info.objectives = "%";
871     move_info.weights[0] = 1;
872
873     from = &p1;
874     to = &p2;
875         
876     if (terrain == T_AIR) start_terrain = T_LAND;
877     else start_terrain = terrain;
878         
879     start_perimeter (path_map, from, cur_loc, start_terrain);
880     cur_cost = 0; /* cost to reach current perimeter */
881
882     for (;;) {
883         to->len = 0; /* nothing in perim yet */
884         expand_perimeter (path_map, vmap, &move_info, from,
885                           terrain, cur_cost, 1, 1, to, to);
886         cur_cost += 1;
887         if (to->len == 0 || best_cost <= cur_cost) {
888             vmap[dest_loc].contents = old_contents;
889             return best_loc;
890         }
891         SWAP (from, to);
892     }
893 }
894
895 /*
896 Starting with the destination, we recursively back track toward the source
897 marking all cells which are on a shortest path between the start and the
898 destination.  To do this, we know the distance from the destination to
899 the start.  The destination is on a path.  We then find the cells adjacent
900 to the destination and nearest to the source and place them on the path.
901
902 If we know square P is on the path, then S is on the path if S is
903 adjacent to P, the cost to reach S is less than the cost to reach P,
904 and the cost to move from S to P is the difference in cost between
905 S and P.
906
907 Someday, this routine should probably use perimeter lists as well.
908 */
909
910 void
911 vmap_mark_path(path_map_t *path_map, view_map_t *vmap, loc_t dest)
912 {
913     int n;
914     loc_t new_dest;
915
916     if (path_map[dest].cost == 0) return; /* reached end of path */
917     if (path_map[dest].terrain == T_PATH) return; /* already marked */
918
919     path_map[dest].terrain = T_PATH; /* this square is on path */
920
921     /* loop to mark adjacent squares on shortest path */
922     FOR_ADJ (dest, new_dest, n)
923         if (path_map[new_dest].cost == path_map[dest].cost - path_map[dest].inc_cost)
924             vmap_mark_path (path_map, vmap, new_dest);
925
926 }
927
928 /*
929 Create a marked path map.  We mark those squares adjacent to the
930 starting location which are on the board.  'find_dir' must be
931 invoked to decide which squares are actually valid.
932 */
933
934 void
935 vmap_mark_adjacent(path_map_t path_map[], loc_t loc)
936 {
937     int i;
938     loc_t new_loc;
939
940     FOR_ADJ_ON (loc, new_loc, i)
941         path_map[new_loc].terrain = T_PATH;
942 }
943
944 /*
945 Modify a marked path map.  We mark those squares adjacent to the
946 starting location which are on the board and which are adjacent
947 to a location on the existing shortest path.
948 */
949
950 void
951 vmap_mark_near_path(path_map_t path_map[], loc_t loc)
952 {
953     int i, j;
954     loc_t new_loc, xloc;
955     int hit_loc[8];
956
957     (void) bzero ((char *)hit_loc, sizeof(int)*8);
958         
959     FOR_ADJ_ON (loc, new_loc, i) {
960         FOR_ADJ_ON (new_loc, xloc, j)
961             if (xloc != loc && path_map[xloc].terrain == T_PATH) {
962                 hit_loc[i] = 1;
963                 break;
964             }
965     }
966     for (i = 0; i < 8; i++)
967         if (hit_loc[i])
968             path_map[loc + dir_offset[i]].terrain = T_PATH;
969 }
970
971 /*
972 Look at each neighbor of 'loc'.  Select the first marked cell which
973 is on a short path to the desired destination, and which holds a valid
974 terrain.  Note that while this terrain is matched against a 'vmap',
975 it differs slightly from terrains used above.  This terrain is the
976 terrain to which we can move immediately, and does not include terrain
977 for which we would have to wait for another piece to move off of.
978
979 We prefer diagonal moves, and we try to have as many squares
980 as possible containing something in 'adj_char'.
981
982 For tie-breaking, we prefer moving to cells that are adjacent to
983 as many other squares on the path.  This should have a few benefits:
984
985 1)  Fighters are less likely to be blocked from reaching a city
986 because they stay in the center of the path and increase the number
987 of options for subsequent moves.
988
989 2)  Transports will approach a city so that as many armies
990 as possible can hop off the tt on one turn to take a valid
991 path toward the city.
992
993 3)  User pieces will move more intuitively by staying in the
994 center of the best path.
995 */
996
997 static int order[] = {NORTHWEST, NORTHEAST, SOUTHWEST, SOUTHEAST, 
998                         WEST, EAST, NORTH, SOUTH};
999
1000 loc_t
1001 vmap_find_dir(path_map_t path_map[], view_map_t *vmap,
1002               loc_t loc, char *terrain, 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(view_map_t *vmap, loc_t loc, char *adj_char)
1046 {
1047     int i, count;
1048     loc_t new_loc;
1049     char *p;
1050     int len;
1051
1052     len = strlen (adj_char);
1053
1054     count = 0;
1055         
1056     FOR_ADJ_ON (loc, new_loc, i) {
1057         p = strchr (adj_char, vmap[new_loc].contents);
1058         if (p) count += 8 * (len - (p - adj_char));
1059     }
1060     return (count);
1061 }
1062
1063 /*
1064 Count the number of adjacent cells that are on the path.
1065 */
1066
1067 int
1068 vmap_count_path(path_map_t *pmap, loc_t loc)
1069 {
1070     int i, count;
1071     loc_t new_loc;
1072
1073     count = 0;
1074         
1075     FOR_ADJ_ON (loc, new_loc, i)
1076         if (pmap[new_loc].terrain == T_PATH)
1077             count += 1;
1078
1079     return (count);
1080 }
1081
1082 /*
1083 See if a location is on the shore.  We return true if a surrounding
1084 cell contains water and is on the board.
1085 */
1086
1087 bool
1088 rmap_shore(loc_t loc)
1089 {
1090     loc_t i, j;
1091
1092     FOR_ADJ_ON (loc, j, i)
1093         if (map[j].contents == '.') return (true);
1094
1095     return (false);
1096 }
1097
1098 bool
1099 vmap_shore(view_map_t *vmap, loc_t loc)
1100 {
1101     loc_t i, j;
1102
1103     FOR_ADJ_ON (loc, j, i)
1104         if (vmap[j].contents != ' ' && vmap[j].contents != '+' && map[j].contents == '.')
1105             return (true);
1106
1107     return (false);
1108 }
1109
1110 /*
1111 Return true if a location is surrounded by ocean.  Off board locations
1112 which cannot be moved to are treated as ocean.
1113 */
1114
1115 bool
1116 vmap_at_sea(view_map_t *vmap, loc_t loc)
1117 {
1118     loc_t i, j;
1119
1120     if (map[loc].contents != '.') return (false);
1121     FOR_ADJ_ON (loc, j, i)
1122         if (vmap[j].contents == ' ' || vmap[j].contents == '+' || map[j].contents != '.')
1123             return (false);
1124
1125     return (true);
1126 }
1127
1128 bool
1129 rmap_at_sea (loc_t loc)
1130 {
1131     loc_t i, j;
1132
1133     if (map[loc].contents != '.') return (false);
1134     FOR_ADJ_ON (loc, j, i) {
1135         if (map[j].contents != '.') return (false);
1136     }
1137     return (true);
1138 }
1139
1140 /* end */