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