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