1 /* Worlds and areas in Xconq.
2    Copyright (C) 1987-1989, 1991-2000 Stanley T. Shebs.
3 
4 Xconq is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation; either version 2, or (at your option)
7 any later version.  See the file COPYING.  */
8 
9 #include "conq.h"
10 #include "kernel.h"
11 
12 #include <math.h>
13 
14 /* The main world structure. */
15 
16 World world;
17 
18 /* The current area of the world. */
19 
20 Area area;
21 
22 /* This is the head and tail of the list of features. */
23 
24 Feature *featurelist = NULL;
25 
26 Feature *last_feature = NULL;
27 
28 /* Feature id 0 means no geographical feature defined. */
29 
30 int nextfid = 1;
31 
32 int numfeatures;
33 
34 int minelev;
35 int maxelev;
36 
37 /* This is true if the elevation may ever vary in a game. */
38 
39 int any_elev_variation = FALSE;
40 
41 int mintemp;
42 int maxtemp;
43 
44 /* This is true if the temperature ever changes during a game. */
45 
46 int any_temp_variation = FALSE;
47 
48 /* This is true if the temperatures in a layer can have different values in
49    different cells. */
50 
51 int any_temp_variation_in_layer = FALSE;
52 
53 int minwindforce;
54 int maxwindforce;
55 
56 int any_wind_variation = FALSE;
57 
58 /* This is true if the winds in a layer can have different values in
59    different cells. */
60 
61 int any_wind_variation_in_layer = FALSE;
62 
63 /* This is true if clouds can ever exist. */
64 
65 int any_clouds = FALSE;
66 
67 int minclouds;
68 int maxclouds;
69 
70 /* This is true if it is ever possible to have quantities of material
71    in cells. */
72 
73 int any_materials_in_terrain = FALSE;
74 
75 static Feature *tmpfeature;
76 
77 static int tmpint, tmpint2, tmpint3;
78 
79 TRegion *terrain_region_list;
80 TRegion *landsea_region_list;
81 
82 int num_terrain_regions;
83 int num_landsea_regions;
84 
85 /* Clean out all the world and area data. */
86 
87 void
init_world(void)88 init_world(void)
89 {
90     memset(&world, 0, sizeof(World));
91     /* These default values effectively disable day and year effects. */
92     world.daylength = 1;
93     world.yearlength = 1;
94     world.daylight_fraction = 50;
95     world.twilight_fraction = 60;
96     /* Init the current (default) area. */
97     memset(&area, 0, sizeof(Area));
98     /* Note especially that area width and height dimensions are now zero. */
99     area.sunx = area.suny = -1;
100     area.temp_year = lispnil;
101 }
102 
103 int
set_world_circumference(int circum,int warn)104 set_world_circumference(int circum, int warn)
105 {
106 
107     /* All world circumferences are valid, no checks necessary. */
108     /* (circumference < area width means that the "world" is not part
109        of a sphere, such as for space games; meridian display should be
110        disabled, etc) */
111     world.circumference = circum;
112     world.daylight_width =
113       ((world.daylight_fraction * world.circumference) / 100) / 2;
114     world.twilight_width =
115       ((world.twilight_fraction * world.circumference) / 100) / 2;
116     area.xwrap = (world.circumference == area.width);
117     return TRUE;
118 }
119 
120 int
set_area_shape(int width,int height,int warn)121 set_area_shape(int width, int height, int warn)
122 {
123     int changed = FALSE;
124     if (!valid_area_shape(width, height, warn))
125       return FALSE;
126     if (area.width != width || area.height != height) {
127       changed = TRUE;
128     }
129     area.width = width;  area.height = height;
130     area.halfwidth = area.width / 2;  area.halfheight = area.height / 2;
131     area.maxdim = max(area.width, area.height);
132     area.xwrap = (world.circumference == area.width);
133     area.numcells = area.width * area.height;
134     if (!area.xwrap)
135       area.numcells = (area.numcells * 3) / 4;
136 
137     /* We don't have code to resize the units table once allocated. */
138     if (changed && area.units != NULL) {
139       run_error("attempt to resize world");
140     }
141     return TRUE;
142 }
143 
144 int
valid_area_shape(int width,int height,int warn)145 valid_area_shape(int width, int height, int warn)
146 {
147     if (width < MINWIDTH || height < MINHEIGHT) {
148 	if (warn)
149 	  init_warning("area is %dx%d, too small", width, height);
150     	return FALSE;
151     }
152     if (width != world.circumference && width * 2 < height) {
153 	if (warn)
154 	  init_warning("hexagon area is %dx%d, impossible dimensions",
155 		       width, height);
156     	return FALSE;
157     }
158     return TRUE;
159 }
160 
161 void
check_area_shape(void)162 check_area_shape(void)
163 {
164     if (area.width == 0 || area.height == 0)
165       run_error("0x0 area");
166     if (!valid_area_shape(area.width, area.height, TRUE))
167       run_error("sorry, this is a fatal error here");
168 }
169 
170 /* Calculate globals that we can use later to decide if particular
171    classes of calculations need to be done, such as weather changes. */
172 
173 void
calculate_world_globals(void)174 calculate_world_globals(void)
175 {
176     int t, m;
177 
178     /* This is a last chance to set a default world size.
179        Will usually be set already, by players or by module. */
180     if (area.width <= 0 && area.height <= 0)
181       set_area_shape(DEFAULTWIDTH, DEFAULTHEIGHT, 0);
182 
183     /* Also assign a reasonable circumference if still undefined. Use default circumference
184     for all those real-earth games in which it is undefined (zero). However, don't allow the
185     circumference to be less than the area width.  To force a flat world (space games etc.) the
186     circumference should be set to -1. */
187     if (world.circumference == 0)
188 	world.circumference = max(area.width, DEFAULTCIRCUMFERENCE);
189 
190     /* Set uninitialized sun position to something reasonable. */
191     if (area.sunx < 0)
192       area.sunx = area.width / 2;
193     if (area.suny < 0)
194       area.suny = area.halfheight;
195     minelev = t_elev_min(0);
196     maxelev = t_elev_max(0);
197     mintemp = t_temp_min(0);
198     maxtemp = t_temp_max(0);
199     minwindforce = t_wind_force_min(0);
200     maxwindforce = t_wind_force_max(0);
201     minclouds = t_clouds_min(0);
202     maxclouds = t_clouds_max(0);
203     for_all_terrain_types(t) {
204 	if (t_elev_min(t) < minelev)
205 	  minelev = t_elev_min(t);
206 	if (t_elev_max(t) > maxelev)
207 	  maxelev = t_elev_max(t);
208 	if (t_temp_min(t) < mintemp)
209 	  mintemp = t_temp_min(t);
210 	if (t_temp_max(t) > maxtemp)
211 	  maxtemp = t_temp_max(t);
212 	if (t_wind_force_min(t) < maxwindforce)
213 	  minwindforce = t_wind_force_min(t);
214 	if (t_wind_force_max(t) > maxwindforce)
215 	  maxwindforce = t_wind_force_max(t);
216 	if (t_clouds_min(t) < minclouds)
217 	  minclouds = t_clouds_min(t);
218 	if (t_clouds_max(t) > maxclouds)
219 	  maxclouds = t_clouds_max(t);
220 	/* Decide if materials can ever be accumulated in cells. */
221 	for_all_material_types(m) {
222 	    if (tm_storage_x(t, m) > 0)
223 	      any_materials_in_terrain = TRUE;
224 	}
225     }
226     if (minelev != maxelev)
227       any_elev_variation = TRUE;
228     if (mintemp != maxtemp)
229       any_temp_variation = TRUE;
230     if (minwindforce != maxwindforce)
231       any_wind_variation = TRUE;
232     if (minwindforce != maxwindforce)
233       any_wind_variation_in_layer = TRUE;
234     if (minclouds != maxclouds)
235       any_clouds = TRUE;
236 }
237 
238 /* Do the final setup that the world needs. */
239 
240 void
final_init_world(void)241 final_init_world(void)
242 {
243     int u;
244 
245     /* Calculate extent and position of geographical features. */
246     compute_all_feature_centroids();
247     /* These area layers must be allocated already here since the tcltk
248     Weather menu needs to know if temps etc. exist when init_display
249     is run. */
250     if (any_temp_variation && !temperatures_defined()) {
251         allocate_area_temperatures();
252         allocate_area_scratch(3);
253     }
254     if (any_clouds && !clouds_defined()) {
255         allocate_area_clouds();
256         allocate_area_scratch(3);
257     }
258     if (any_wind_variation_in_layer && !winds_defined()) {
259         allocate_area_winds();
260         allocate_area_scratch(2);
261     }
262     if (any_elev_variation && !elevations_defined()) {
263     	allocate_area_elevations();
264     }
265     /* Allocate the user layer if there are any advanced units. */
266     for_all_unit_types(u) {
267 	if (u_advanced(u)){
268 		allocate_area_users();
269 		break;
270 	}
271     }
272     /* Calculate the landsea layer if not already done. */
273     if (area.landsea_regions == NULL) {
274 	area.landsea_regions = malloc_area_layer(TRegion *);
275 	divide_into_regions(area.terrain, area.landsea_regions, TRUE);
276     }
277     compute_elevation_bounds();
278 }
279 
280 void
compute_elevation_bounds(void)281 compute_elevation_bounds(void)
282 {
283     int x, y, el, count, sum, rowcount, rowsum, rowavg;
284 
285     area.minelev = area.maxelev = area.avgelev = 0;
286     if (elevations_defined()) {
287 	area.maxelev = area.minelev = elev_at(area.width / 2, area.height / 2);
288 	/* In order to avoid overflowing by summing all elevations at
289 	   once, we average along a row, then average the row averages. */
290 	count = sum = 0;
291 	for (y = 0; y < area.height; y++) {
292 	    rowcount = rowsum = 0;
293 	    for (x = 0; x < area.width; x++) {
294 		if (in_area(x, y)) {
295 		    el = elev_at(x, y);
296 		    if (el < area.minelev)
297 		      area.minelev = el;
298 		    if (el > area.maxelev)
299 		      area.maxelev = el;
300 		    ++rowcount;
301 		    rowsum += el;
302 		}
303 	    }
304 	    rowavg = rowsum / rowcount;
305 	    ++count;
306 	    sum += rowavg;
307 	}
308 	area.avgelev = sum / count;
309 	Dprintf("Area elevations range %d to %d, averaging %d\n",
310 		area.minelev, area.maxelev, area.avgelev);
311     }
312 }
313 
314 /* Make space for an area's terrain, and for the unit cache. */
315 
316 /* This can be postponed until it is actually needed. */
317 
318 void
allocate_area_terrain(void)319 allocate_area_terrain(void)
320 {
321     check_area_shape();
322     /* Get rid of old stuff maybe. (is this desirable?) */
323     if (area.terrain != NULL) {
324 	free((char *) area.terrain);
325 	free((char *) area.units);
326     }
327     /* Allocate the basic terrain layer. */
328     /* It doesn't matter what ttype 0 is, we're guaranteed that it
329        will be defined eventually. */
330     area.terrain = malloc_area_layer(char);
331     /* Allocate and null out the unit cache. */
332     area.units = malloc_area_layer(Unit *);
333 }
334 
335 /* Set up the auxiliary terrain layer of the area. */
336 
337 void
allocate_area_aux_terrain(int t)338 allocate_area_aux_terrain(int t)
339 {
340     if (!any_aux_terrain_defined()) {
341 	area.auxterrain = (char **) xmalloc(numttypes * sizeof(char *));
342     }
343     if (!aux_terrain_defined(t)) {
344 	area.auxterrain[t] = malloc_area_layer(char);
345     }
346 }
347 
348 /* Allocate some number of scratch layers.  These are used as temporaries
349    in calculations, etc. */
350 
351 void
allocate_area_scratch(int n)352 allocate_area_scratch(int n)
353 {
354     check_area_shape();
355     if (n >= 1 && !area.tmp1) {
356 	area.tmp1 = malloc_area_layer(short);
357     }
358     if (n >= 2 && !area.tmp2) {
359 	area.tmp2 = malloc_area_layer(short);
360     }
361     if (n >= 3 && !area.tmp3) {
362 	area.tmp3 = malloc_area_layer(short);
363     }
364     if (n >= 4) {
365 	run_error("can't allocate more than 3 scratch layers");
366     }
367 }
368 
369 /* Should have something to free scratch layers up also maybe. */
370 
371 /* Allocate and init the elevation layer. */
372 
373 void
allocate_area_elevations(void)374 allocate_area_elevations(void)
375 {
376     int x, y;
377 
378     if (!elevations_defined()) {
379 	check_area_shape();
380 	area.elevations = malloc_area_layer(short);
381 	/* If we have terrain, make the initial elevations fall into
382 	   the correct ranges for the types of terrain present. */
383 	if (terrain_defined()) {
384 	    for_all_cells(x, y) {
385 		set_elev_at(x, y, t_elev_min(terrain_at(x, y)));
386 	    }
387 	}
388     }
389 }
390 
391 /* Allocate and init the temperature layer. */
392 
393 void
allocate_area_temperatures(void)394 allocate_area_temperatures(void)
395 {
396     if (!temperatures_defined()) {
397 	check_area_shape();
398 	area.temperature = malloc_area_layer(short);
399     }
400     /* We'll need one scratch layer too. */
401     allocate_area_scratch(1);
402 }
403 
404 /* Allocate a layer indicating the side of the people living in each cell. */
405 
406 void
allocate_area_people_sides(void)407 allocate_area_people_sides(void)
408 {
409     if (!people_sides_defined()) {
410 	check_area_shape();
411 	area.peopleside = malloc_area_layer(char);
412 	/* NOBODY != 0, so need to blast it over the layer. */
413 	memset(area.peopleside, NOBODY, area.width * area.height);
414 	memset(area.peopleside, NOBODY, area.width * area.height);
415     }
416 }
417 
418 /* Allocate a layer indicating the side in control of each cell. */
419 
420 void
allocate_area_control_sides(void)421 allocate_area_control_sides(void)
422 {
423     if (!control_sides_defined()) {
424 	check_area_shape();
425 	area.controlside = malloc_area_layer(char);
426 	/* NOCONTROL != 0, so need to blast it over the layer. */
427 	memset(area.controlside, NOCONTROL, area.width * area.height);
428     }
429 }
430 
431 /* Set up a cell material layer of the area. */
432 
433 void
allocate_area_material(int m)434 allocate_area_material(int m)
435 {
436     check_area_shape();
437     if (!any_cell_materials_defined()) {
438 	area.materials = (long **) xmalloc(nummtypes * sizeof(long *));
439     }
440     if (!cell_material_defined(m)) {
441 	area.materials[m] = malloc_area_layer(long);
442     }
443 }
444 
445 void
allocate_area_clouds(void)446 allocate_area_clouds(void)
447 {
448     if (!clouds_defined()) {
449 	check_area_shape();
450 	area.clouds = malloc_area_layer(short);
451     }
452 }
453 
454 void
allocate_area_cloud_altitudes(void)455 allocate_area_cloud_altitudes(void)
456 {
457     allocate_area_cloud_bottoms();
458     allocate_area_cloud_heights();
459 }
460 
461 void
allocate_area_cloud_bottoms(void)462 allocate_area_cloud_bottoms(void)
463 {
464     if (!cloud_bottoms_defined()) {
465 	check_area_shape();
466 	area.cloudbottoms = malloc_area_layer(short);
467     }
468 }
469 
470 void
allocate_area_cloud_heights(void)471 allocate_area_cloud_heights(void)
472 {
473     if (!cloud_heights_defined()) {
474 	check_area_shape();
475 	area.cloudheights = malloc_area_layer(short);
476     }
477 }
478 
479 void
allocate_area_winds(void)480 allocate_area_winds(void)
481 {
482     if (!winds_defined()) {
483 	check_area_shape();
484 	area.winds = malloc_area_layer(short);
485     }
486 }
487 
488 void
allocate_area_users(void)489 allocate_area_users(void)
490 {
491     if (!user_defined()) {
492 	check_area_shape();
493 	area.user = malloc_area_layer(short);
494     }
495 }
496 
497 int
fn_terrain_at(int x,int y)498 fn_terrain_at(int x, int y)
499 {
500     return terrain_at(x, y);
501 }
502 
503 int
fn_aux_terrain_at(int x,int y)504 fn_aux_terrain_at(int x, int y)
505 {
506     return aux_terrain_at(x, y, tmpttype);
507 }
508 
509 int
fn_feature_at(int x,int y)510 fn_feature_at(int x, int y)
511 {
512     return raw_feature_at(x, y);
513 }
514 
515 int
fn_elevation_at(int x,int y)516 fn_elevation_at(int x, int y)
517 {
518     return elev_at(x, y);
519 }
520 
521 int
fn_people_side_at(int x,int y)522 fn_people_side_at(int x, int y)
523 {
524     return people_side_at(x, y);
525 }
526 
527 int
fn_control_side_at(int x,int y)528 fn_control_side_at(int x, int y)
529 {
530     return control_side_at(x, y);
531 }
532 
533 int
fn_user_at(int x,int y)534 fn_user_at(int x, int y)
535 {
536     return user_at(x, y);
537 }
538 
539 int
fn_material_at(int x,int y)540 fn_material_at(int x, int y)
541 {
542     return material_at(x, y, tmpmtype);
543 }
544 
545 int
fn_temperature_at(int x,int y)546 fn_temperature_at(int x, int y)
547 {
548     return temperature_at(x, y);
549 }
550 
551 int
fn_raw_cloud_at(int x,int y)552 fn_raw_cloud_at(int x, int y)
553 {
554     return raw_cloud_at(x, y);
555 }
556 
557 int
fn_raw_cloud_bottom_at(int x,int y)558 fn_raw_cloud_bottom_at(int x, int y)
559 {
560     return raw_cloud_bottom_at(x, y);
561 }
562 
563 int
fn_raw_cloud_height_at(int x,int y)564 fn_raw_cloud_height_at(int x, int y)
565 {
566     return raw_cloud_height_at(x, y);
567 }
568 
569 int
fn_raw_wind_at(int x,int y)570 fn_raw_wind_at(int x, int y)
571 {
572     return raw_wind_at(x, y);
573 }
574 
575 void
fn_set_terrain_at(int x,int y,int val)576 fn_set_terrain_at(int x, int y, int val)
577 {
578     extern int warnbadterrain, numbadterrain;
579 
580     /* It's important not to put bad values into the terrain layer. */
581     if (!is_terrain_type(val)) {
582     	/* Only warn the first few times, just count thereafter. */
583     	if (warnbadterrain && numbadterrain < 10) {
584 	    read_warning("Unknown terrain type (%d) at %d,%d; substituting %s",
585 			 val, x, y, t_type_name(0));
586 	}
587 	val = 0;
588 	++numbadterrain;
589     }
590     set_terrain_at(x, y, val);
591 }
592 
593 void
fn_set_aux_terrain_at(int x,int y,int val)594 fn_set_aux_terrain_at(int x, int y, int val)
595 {
596     /* Filter anything but the basic six bits. */
597     val &= 0x3f;
598     set_aux_terrain_at(x, y, tmpttype, val);
599 }
600 
601 void
fn_set_people_side_at(int x,int y,int val)602 fn_set_people_side_at(int x, int y, int val)
603 {
604     set_people_side_at(x, y, val);
605 }
606 
607 void
fn_set_control_side_at(int x,int y,int val)608 fn_set_control_side_at(int x, int y, int val)
609 {
610     set_control_side_at(x, y, val);
611 }
612 
613 void
fn_set_user_at(int x,int y,int val)614 fn_set_user_at(int x, int y, int val)
615 {
616     set_user_at(x, y, val);
617 }
618 
619 void
fn_set_raw_feature_at(int x,int y,int val)620 fn_set_raw_feature_at(int x, int y, int val)
621 {
622     set_raw_feature_at(x, y, val);
623 }
624 
625 void
fn_set_elevation_at(int x,int y,int val)626 fn_set_elevation_at(int x, int y, int val)
627 {
628     set_elev_at(x, y, val);
629 }
630 
631 void
fn_set_material_at(int x,int y,int val)632 fn_set_material_at(int x, int y, int val)
633 {
634     set_material_at(x, y, tmpmtype, val);
635 }
636 
637 void
fn_set_temperature_at(int x,int y,int val)638 fn_set_temperature_at(int x, int y, int val)
639 {
640     set_temperature_at(x, y, val);
641 }
642 
643 void
fn_set_raw_wind_at(int x,int y,int val)644 fn_set_raw_wind_at(int x, int y, int val)
645 {
646     set_raw_wind_at(x, y, val);
647 }
648 
649 void
fn_set_raw_cloud_at(int x,int y,int val)650 fn_set_raw_cloud_at(int x, int y, int val)
651 {
652     set_raw_cloud_at(x, y, val);
653 }
654 
655 void
fn_set_raw_cloud_bottom_at(int x,int y,int val)656 fn_set_raw_cloud_bottom_at(int x, int y, int val)
657 {
658     set_raw_cloud_bottom_at(x, y, val);
659 }
660 
661 void
fn_set_raw_cloud_height_at(int x,int y,int val)662 fn_set_raw_cloud_height_at(int x, int y, int val)
663 {
664     set_raw_cloud_height_at(x, y, val);
665 }
666 
667 /* Change the terrain of the cell at the given location to the given
668    type of terrain, and update everything affected by the change. */
669 
670 void
change_terrain_type(int x,int y,int t2)671 change_terrain_type(int x, int y, int t2)
672 {
673     int t, m, curview, newview, update, u2;
674     HistEventType hevttype;
675     Unit *unit2;
676     Side *side;
677 
678     t = terrain_at(x, y);
679     set_terrain_at(x, y, t2);
680     for_all_material_types(m) {
681 	if (tm_initial(t, m) > 0) {
682 	    if (!(any_cell_materials_defined() && cell_material_defined(m)))
683 	      allocate_area_material(m);
684 	    set_material_at(x, y, m, min(tm_storage_x(t, m), tm_initial(t, m)));
685 	} else {
686 	    if (any_cell_materials_defined() && cell_material_defined(m))
687 	      set_material_at(x, y, m, 0);
688 	}
689     }
690     /* Let everybody see this change. */
691     for_all_sides(side) {
692 	update = FALSE;
693 	if (side->see_all) {
694 	    update = TRUE;
695 	} else if (cover(side, x, y) > 0) {
696 	    /* Always update our knowledge of the terrain. */
697 	    curview = terrain_view(side, x, y);
698 	    newview = buildtview(t2);
699 	    set_terrain_view(side, x, y, newview);
700 	    if (!g_see_terrain_always())
701 	      set_terrain_view_date(side, x, y, g_turn());
702 	    if (newview != curview)
703 	      update = TRUE;
704 	}
705 	if (update) {
706 	    update_cell_display(side, x, y, UPDATE_ALWAYS | UPDATE_ADJ);
707 	}
708     }
709     /* There might be catastrophic consequences for any units here. */
710     for_all_stack(x, y, unit2) {
711 	u2 = unit2->type;
712 	if (ut_vanishes_on(u2, t2)
713 	    /* The unit may be rescued by a connection. */
714 	    && !type_survives_in_cell(unit2->type, unit2->x, unit2->y)) {
715 	    hevttype = H_UNIT_VANISHED;
716 	    kill_unit(unit2, hevttype);
717 	} else if (ut_wrecks_on(u2, t2)
718 	    	   /* The unit may be rescued by a connection. */
719 		   && !type_survives_in_cell(unit2->type, unit2->x, unit2->y)) {
720 	    if (u_wrecked_type(u2) == NONUTYPE) {
721 		/* Occupants always die if the wrecked unit disappears. */
722 		hevttype = H_UNIT_WRECKED;
723 		kill_unit(unit2, hevttype);
724 	    } else {
725 		/* Change the unit's type. */
726 		hevttype = H_UNIT_WRECKED;
727 		wreck_unit(unit2, hevttype, WRECK_TYPE_TERRAIN, t2, NULL);
728 		/* Maybe make it go away, taking remaining unlucky
729                    occupants with. */
730 		if (ut_vanishes_on(unit2->type, t2)) {
731 		    hevttype = H_UNIT_VANISHED;
732 		    kill_unit(unit2, hevttype);
733 		}
734 	    }
735 	}
736 	if (active_display(unit2->side)) {
737 	    if (hevttype == H_UNIT_VANISHED) {
738 		notify(unit2->side, "Terrain change from %s to %s causes %s to vanish",
739 		       t_type_name(t), t_type_name(t2),
740 		       unit_handle(unit2->side, unit2));
741 	    } else if (hevttype == H_UNIT_WRECKED) {
742 		notify(unit2->side, "Terrain change from %s to %s wrecks %s",
743 		       t_type_name(t), t_type_name(t2),
744 		       unit_handle(unit2->side, unit2));
745 	    }
746 	}
747     }
748 }
749 
750 /* Generalized area search routine.  It starts in the immediately adjacent
751    cells and expands outwards.  The basic structure is to examine successive
752    "rings" out to the max distance; within each ring, we must scan each of
753    six faces (picking a random one to start with) by iterating along that
754    face, in a direction 120 degrees from the direction out to one corner of
755    the face.  Draw a picture if you want to understand it... */
756 
757 /* Incr is normally one.  It is set to area_size to search on areas
758    instead of cells. */
759 
760 /* Note that points far outside the map may be generated, but the predicate
761    will not be called on them.  It may be applied to the same point several
762    times, however, if the distance is enough to wrap around the area. */
763 
764 /* This needs to be changed to understand different world shapes. */
765 
766 /* Predicate can manipulate a counter and a parameter box for returning
767    compound results. A result limit can terminate the search if counter
768    exceeds it. */
769 
770 int
limited_search_around(int x0,int y0,int range,int (* pred)(int,int,int *,ParamBox *),int incr,int * counter,int rsltlimit,ParamBox * parambox)771 limited_search_around(int x0, int y0, int range,
772 		      int (*pred)(int, int, int *, ParamBox *),
773 		      int incr, int *counter, int rsltlimit,
774 		      ParamBox *parambox)
775 {
776     int clockwise, dist, dd, d, dir, x1, y1, i, dir2, x, y, xw;
777 
778     range = max(min(range, area.width), min(range, area.height));
779     clockwise = (flip_coin() ? 1 : -1);
780     for (dist = 1; dist <= range; dist += incr) {
781 	dd = random_dir();
782 	for_all_directions(d) {
783 	    dir = (d + dd) % NUMDIRS;
784 	    x1 = x0 + dist * dirx[dir];
785 	    y1 = y0 + dist * diry[dir];
786 	    for (i = 0; i < dist; ++i) {
787 		dir2 = opposite_dir(dir + clockwise);
788 		x = x1 + i * dirx[dir2] * incr;
789 		y = y1 + i * diry[dir2] * incr;
790 		xw = wrapx(x);
791 		if (inside_area(x, y) && (*pred)(xw, y, counter, parambox))
792 		  return TRUE;
793                 if (counter && (*counter >= rsltlimit))
794                   return FALSE;
795 	    }
796 	}
797     }
798     return FALSE;
799 }
800 
801 /* Search around without any result limits. */
802 
803 int
search_around(int x0,int y0,int range,int (* pred)(int,int,int *,ParamBox *),int incr,ParamBox * parambox)804 search_around(int x0, int y0, int range,
805 		      int (*pred)(int, int, int *, ParamBox *),
806 		      int incr, ParamBox *parambox)
807 {
808     return limited_search_around(x0, y0, range, pred, incr,
809 				 NULL, INT_MAX, parambox);
810 }
811 
812 /* Original version of 'search_around'. */
813 /* (NOTE: This is part of the gradual evolution of 'search_around' to
814     resemble 'search_under_arc' in terms of predicate function parameters.
815     This should eventually be phased out to eliminate code duplication.) */
816 
817 int
search_around(int x0,int y0,int maxdist,int (* pred)(int,int),int * rxp,int * ryp,int incr)818 search_around(int x0, int y0, int maxdist, int (*pred)(int, int),
819 	      int *rxp, int *ryp, int incr)
820 {
821     int clockwise, dist, dd, d, dir, x1, y1, i, dir2, x, y, xw;
822 
823     maxdist = max(min(maxdist, area.width), min(maxdist, area.height));
824     clockwise = (flip_coin() ? 1 : -1);
825     for (dist = 1; dist <= maxdist; dist += incr) {
826 	dd = random_dir();
827 	for_all_directions(d) {
828 	    dir = (d + dd) % NUMDIRS;
829 	    x1 = x0 + dist * dirx[dir];
830 	    y1 = y0 + dist * diry[dir];
831 	    for (i = 0; i < dist; ++i) {
832 		dir2 = opposite_dir(dir + clockwise);
833 		x = x1 + i * dirx[dir2] * incr;
834 		y = y1 + i * diry[dir2] * incr;
835 		xw = wrapx(x);
836 		if (inside_area(x, y) && (*pred)(xw, y)) {
837 		    *rxp = xw;  *ryp = y;
838 		    return TRUE;
839 		}
840 	    }
841 	}
842     }
843     return FALSE;
844 }
845 
846 /* Limited version of search_around for optimizing performance by
847    restricting the number of query results. The address of the result
848    counter must be given to the predicate function so that it can
849    increment it as deemed fit. */
850 /* (NOTE: This is part of the gradual evolution of 'search_around' to
851     resemble 'search_under_arc' in terms of predicate function parameters.
852     This should eventually be phased out to eliminate code duplication.) */
853 
854 int
limited_search_around(int x0,int y0,int maxdist,int (* pred)(int,int,int *),int * rxp,int * ryp,int incr,int rsltlimit)855 limited_search_around(int x0, int y0, int maxdist, int (*pred)(int, int, int *),
856 	      int *rxp, int *ryp, int incr, int rsltlimit)
857 {
858     int clockwise, dist, dd, d, dir, x1, y1, i, dir2, x, y, xw, rsltcount = 0;
859 
860     maxdist = max(min(maxdist, area.width), min(maxdist, area.height));
861     clockwise = (flip_coin() ? 1 : -1);
862     for (dist = 1; dist <= maxdist; dist += incr) {
863 	dd = random_dir();
864 	for_all_directions(d) {
865 	    dir = (d + dd) % NUMDIRS;
866 	    x1 = x0 + dist * dirx[dir];
867 	    y1 = y0 + dist * diry[dir];
868 	    for (i = 0; i < dist; ++i) {
869 		dir2 = opposite_dir(dir + clockwise);
870 		x = x1 + i * dirx[dir2] * incr;
871 		y = y1 + i * diry[dir2] * incr;
872 		xw = wrapx(x);
873 		if (inside_area(x, y) && (*pred)(xw, y, &rsltcount)) {
874 		    *rxp = xw;  *ryp = y;
875 		    return TRUE;
876 		}
877                 if (rsltcount >= rsltlimit)
878                   return FALSE;
879 	    }
880 	}
881     }
882     return FALSE;
883 }
884 
885 int
search_and_apply(int x0,int y0,int maxdist,int (* pred)(int,int),int * rxp,int * ryp,int incr,void (* fn)(int,int),int num)886 search_and_apply(int x0, int y0, int maxdist, int (*pred)(int, int),
887 		 int *rxp, int *ryp, int incr, void (*fn)(int, int), int num)
888 {
889     int clockwise, dist, x0w, dd, d, dir, x1, y1, i, dir2, x, y, xw;
890 
891     maxdist = max(min(maxdist, area.width), min(maxdist, area.height));
892     clockwise = (flip_coin() ? 1 : -1);
893     if (maxdist >= 0) {
894 	x0w = wrapx(x0);
895 	if (inside_area(x0w, y0)) {
896 	    if ((*pred)(x0w, y0)) {
897 		*rxp = x0w;  *ryp = y0;
898 		(*fn)(x0w, y0);
899 	    } else {
900 		return 0;
901 	    }
902 	}
903     }
904     for (dist = 1; dist <= maxdist; dist += incr) {
905 	dd = random_dir();
906 	for_all_directions(d) {
907 	    dir = (d + dd) % NUMDIRS;
908 	    x1 = x0 + dist * dirx[dir];
909 	    y1 = y0 + dist * diry[dir];
910 	    for (i = 0; i < dist; ++i) {
911 		dir2 = opposite_dir(dir + clockwise);
912 		x = x1 + i * dirx[dir2] * incr;
913 		y = y1 + i * diry[dir2] * incr;
914 		if (between(0, y, area.height-1)) {
915 		    xw = wrapx(x);
916 		    if (inside_area(x, y)) {
917 			if ((*pred)(xw, y)) {
918 			    *rxp = xw;  *ryp = y;
919 			    (*fn)(xw, y);
920 			} else {
921 			    return 0;
922 			}
923 		    }
924 		}
925 	    }
926 	}
927     }
928     return 0;
929 }
930 
931 /* Apply a function to every cell within the given radius, being
932    careful (for both safety and efficiency reasons) not to go past
933    edges.  Note that the distance is inclusive, and that distance of 0
934    means x0,y0 only.  Also, if the distance is greater than either map
935    dimension, this routine still operates on a correct intersection
936    with the area.  */
937 
938 int stop_apply;
939 
940 void
apply_to_area(int x0,int y0,int dist,void (* fn)(int,int))941 apply_to_area(int x0, int y0, int dist, void (*fn)(int, int))
942 {
943     int x, y, x1, y1, x2, y2;
944 
945     dist = min(dist, area.maxdim);
946     y1 = y0 - dist;
947     y2 = y0 + dist;
948     stop_apply = FALSE;
949     for (y = y1; y <= y2; ++y) {
950 	if (between(1, y, area.height-2)) {
951 	    /* Compute endpoints of row, but don't wrap or loop will confuse */
952 	    x1 = x0 - (y < y0 ? (y - y1) : dist);
953 	    x2 = x0 + (y > y0 ? (y2 - y) : dist);
954 	    for (x = x1; x <= x2; ++x) {
955 		/* not real efficient, sigh... */
956 		if (in_area(x, y)) {
957 		    ((*fn)(wrapx(x), y));
958 		    /* Backdoor for early termination. */
959 		    if (stop_apply)
960 		      return;
961 		}
962 	    }
963 	}
964     }
965 }
966 
967 /* Similarly, but operating on edge cells as well. */
968 
969 void
apply_to_area_plus_edge(int x0,int y0,int dist,void (* fn)(int,int))970 apply_to_area_plus_edge(int x0, int y0, int dist, void (*fn)(int, int))
971 {
972     int x, y, x1, y1, x2, y2;
973 
974     dist = min(dist, area.maxdim);
975     y1 = y0 - dist;
976     y2 = y0 + dist;
977     for (y = y1; y <= y2; ++y) {
978 	if (between(0, y, area.height-1)) {
979 	    /* Compute endpoints of row, but don't wrap or loop will confuse */
980 	    x1 = x0 - (y < y0 ? (y - y1) : dist);
981 	    x2 = x0 + (y > y0 ? (y2 - y) : dist);
982 	    for (x = x1; x <= x2; ++x) {
983 		/* not real efficient, sigh... */
984 		if (in_area(x, y)) {
985 		    ((*fn)(wrapx(x), y));
986 		}
987 	    }
988 	}
989     }
990 }
991 
992 void
apply_to_ring(int x0,int y0,int distmin,int distmax,void (* fn)(int,int))993 apply_to_ring(int x0, int y0, int distmin, int distmax, void (*fn)(int, int))
994 {
995     int dist, x, y, x1, y1, x2, y2;
996 
997     dist = min(distmax, area.maxdim);
998     y1 = y0 - dist;
999     y2 = y0 + dist;
1000     for (y = y1; y <= y2; ++y) {
1001 	if (between(1, y, area.height-2)) {
1002 	    /* Compute endpoints of row, but don't wrap or loop will confuse */
1003 	    x1 = x0 - (y < y0 ? (y - y1) : dist);
1004 	    x2 = x0 + (y > y0 ? (y2 - y) : dist);
1005 	    for (x = x1; x <= x2; ++x) {
1006 		/* not real efficient, sigh... */
1007 		if (in_area(x, y) && distance(x, y, x0, y0) >= distmin) {
1008 		    ((*fn)(wrapx(x), y));
1009 		}
1010 	    }
1011 	}
1012     }
1013 }
1014 
1015 /* Apply the function to the hexagon bounded by w,h. */
1016 
1017 void
apply_to_hexagon(int x0,int y0,int w2,int h2,void (* fn)(int,int))1018 apply_to_hexagon(int x0, int y0, int w2, int h2, void (*fn)(int, int))
1019 {
1020     int x, y, x1, y1, x2, y2;
1021 
1022     y1 = limity(y0 - h2);
1023     y2 = limity(y0 + h2);
1024     for (y = y1; y <= y2; ++y) {
1025 	if (between(0, y, area.height-1)) {  /* always true? */
1026 	    /* Compute endpoints of row, but don't wrap or loop will confuse */
1027 	    x1 = x0 - w2 + (y < y0 ? (y0 - y) : 0);
1028 	    x2 = x0 + w2 - (y > y0 ? (y - y0) : 0);
1029 	    for (x = x1; x <= x2; ++x) {
1030 		/* not real efficient, sigh... */
1031 		if (in_area(x, y)) {
1032 		    ((*fn)(wrapx(x), y));
1033 		}
1034 	    }
1035 	}
1036     }
1037 }
1038 
1039 /* Search cells under an arc between one directional ray and a neighboring
1040    directional ray until rlstlimit results have been accumulated. */
1041 /* Note that larger arcs may searched by decomposing them into the size of
1042    arcs used in this search. It is harder to efficiently search wider arcs
1043    without overlaps. */
1044 /* If dirbias is set to 0, then only a radial line segment will be searched. */
1045 /* (May be useful for implementing some LOS stuff.) */
1046 int
limited_search_under_arc(int x,int y,int dir,int range,int dirbias,int (* pred)(int x,int y,int * counter,ParamBox * parambox),int * counter,int rsltlimit,ParamBox * parambox)1047 limited_search_under_arc(int x, int y, int dir, int range,
1048                          int dirbias,
1049                          int (*pred)(int x, int y, int *counter,
1050                                      ParamBox *parambox),
1051                          int *counter, int rsltlimit, ParamBox *parambox)
1052 {
1053     int nextdir = NODIR;
1054     int nx = -1, ny = -1;
1055 
1056     /* Sanity checks. */
1057     if ((dir < 0) || (dir >= NUMDIRS))
1058       return FALSE;
1059     if (range < 0)
1060       return FALSE;
1061     /* Apply predicate function to this cell. */
1062     if (pred(x, y, counter, parambox))
1063       return TRUE;
1064     if (counter && (*counter >= rsltlimit))
1065       return FALSE;
1066     /* Decrement the remaining range to search. */
1067     --range;
1068     /* Recurse into next cells, if they exist and we still have range left. */
1069     if (range >= 0) {
1070         nextdir = dir;
1071         if (!point_in_dir(x, y, nextdir, &nx, &ny))
1072           nextdir = NODIR;
1073         if ((nextdir != NODIR)
1074             && limited_search_under_arc(nx, ny, dir, range, 0, pred,
1075                                         counter, rsltlimit, parambox))
1076           return TRUE;
1077         if (counter && (*counter >= rsltlimit))
1078           return FALSE;
1079         if (dirbias < 0)
1080           nextdir = left_dir(dir);
1081         else if (dirbias > 0)
1082           nextdir = right_dir(dir);
1083         else
1084           nextdir = NODIR;
1085         if (nextdir != NODIR) {
1086             if (!point_in_dir(x, y, nextdir, &nx, &ny))
1087               nextdir = NODIR;
1088             if ((nextdir != NODIR)
1089                 && limited_search_under_arc(nx, ny, dir, range, dirbias, pred,
1090                                             counter, rsltlimit, parambox))
1091               return TRUE;
1092             if (counter && (*counter >= rsltlimit))
1093               return FALSE;
1094         }
1095     }
1096     return FALSE;
1097 }
1098 
1099 /* Search under an arc between one directional ray and a neighboring
1100    directional ray. */
1101 int
search_under_arc(int x,int y,int dir,int range,int dirbias,int (* pred)(int x,int y,int * counter,ParamBox * parambox),ParamBox * parambox)1102 search_under_arc(int x, int y, int dir, int range, int dirbias,
1103                  int (*pred)(int x, int y, int *counter, ParamBox *parambox),
1104                  ParamBox *parambox)
1105 {
1106     return limited_search_under_arc(x, y, dir, range, dirbias, pred, NULL,
1107                                     INT_MAX, parambox);
1108 }
1109 
1110 /* Apply a function all along a path. */
1111 
1112 void
apply_to_path(int fx,int fy,int tx,int ty,int (* dirtest)(int x,int y,int dir),int (* dirsort)(int x,int y,int * dirchoices,int numchoices),int (* fn)(int x,int y,int dir,int j,int numchoices),int shortest)1113 apply_to_path(int fx, int fy, int tx, int ty,
1114 	      int (*dirtest)(int x, int y, int dir),
1115 	      int (*dirsort)(int x, int y, int *dirchoices, int numchoices),
1116 	      int (*fn)(int x, int y, int dir, int j, int numchoices),
1117 	      int shortest)
1118 {
1119     int i = 500, j, x = fx, y = fy, moved;
1120     int dx, dxa, dy, dirchoices[NUMDIRS], axis, hextant, sig;
1121     int d1, d2, d3, d4;
1122     int numchoices, shortestnumchoices;
1123 
1124     while (!(x == tx && y == ty) && i-- > 0 /* safety */) {
1125 	dx = tx - x;  dy = ty - y;
1126 	/* If in a wrapping world, choose the shortest of directions. */
1127 	if (area.xwrap) {
1128 	    dxa = (tx + area.width) - fx;
1129 	    if (ABS(dx) > ABS(dxa))
1130 	      dx = dxa;
1131 	    dxa = (tx - area.width) - fx;
1132 	    if (ABS(dx) > ABS(dxa))
1133 	      dx = dxa;
1134 	}
1135 	/* Figure out the axis or hextant of this delta. */
1136 	axis = hextant = -1;
1137 	/* Decode the delta values. */
1138 	if (dx == 0) {
1139 	    axis = (dy > 0 ? NORTHEAST : SOUTHWEST);
1140 	} else if (dy == 0) {
1141 	    axis = (dx > 0 ? EAST : WEST);
1142 	} else if (dx == (0 - dy)) {
1143 	    axis = (dy > 0 ? NORTHWEST : SOUTHEAST);
1144 	} else if (dx > 0) {
1145 	    hextant = (dy > 0 ? EAST :
1146 		       (ABS(dx) > ABS(dy) ? SOUTHEAST : SOUTHWEST));
1147 	} else {
1148 	    hextant = (dy < 0 ? WEST :
1149 		       (ABS(dx) > ABS(dy) ? NORTHWEST : NORTHEAST));
1150 	}
1151 	numchoices = 0;
1152 	/* On an axis, there's no choice. */
1153 	if (axis >= 0) {
1154 	    d1 = d2 = axis;
1155 	    if (dirtest == NULL || (*dirtest)(x, y, d1))
1156 	      dirchoices[numchoices++] = axis;
1157 	}
1158 	/* Two choices in the middle of a hextant. */
1159 	if (hextant >= 0) {
1160 	    d1 = left_dir(hextant);
1161 	    d2 = hextant;
1162 	    if (dirtest == NULL || (*dirtest)(x, y, d1))
1163 	      dirchoices[numchoices++] = d1;
1164 	    if (dirtest == NULL || (*dirtest)(x, y, d2))
1165 	      dirchoices[numchoices++] = d2;
1166 	}
1167 	/* Sort the choices if requested. */
1168 	if (numchoices > 1 && dirsort != NULL)
1169 	  numchoices = (*dirsort)(x, y, dirchoices, numchoices);
1170 	/* Try each of the directions. */
1171 	if (!inside_area(x, y))
1172 	  return;
1173 	moved = FALSE;
1174 	for (j = 0; j < numchoices; ++j) {
1175 	    sig = (*fn)(x, y, dirchoices[j], j, numchoices);
1176 	    if (sig > 0) {
1177 		/* It's cool - go with this dir. */
1178 		/* Jump along to the new spot on the path. */
1179 		x += dirx[dirchoices[j]];  y += diry[dirchoices[j]];
1180 		moved = TRUE;
1181 		/* Out of the loop. */
1182 		break;
1183 	    } else if (sig < 0) {
1184 		/* Stop applying to the path right now. */
1185 		return;
1186 	    } else {
1187 		/* Try another. */
1188 	    }
1189 	}
1190 	/* If we don't have to pick a shortest path, we have two more
1191 	   directions to try if we need to. */
1192 	if (!moved && !shortest) {
1193 	    shortestnumchoices = numchoices;
1194 	    d3 = left_dir(d1);
1195 	    d4 = right_dir(d2);
1196 	    if (dirtest == NULL || (*dirtest)(x, y, d3))
1197 	      dirchoices[numchoices++] = d3;
1198 	    if (dirtest == NULL || (*dirtest)(x, y, d4))
1199 	      dirchoices[numchoices++] = d4;
1200 	    if (numchoices > shortestnumchoices + 1 && dirsort != NULL)
1201 	      (*dirsort)(x, y, dirchoices + shortestnumchoices, numchoices - shortestnumchoices);
1202 	    /* Try each of the directions. */
1203 	    for (j = shortestnumchoices; j < numchoices; ++j) {
1204 		sig = (*fn)(x, y, dirchoices[j], j, numchoices - shortestnumchoices);
1205 		if (sig > 0) {
1206 		    /* It's cool - go with this dir. */
1207 		    /* Jump along to the new spot on the path. */
1208 		    x += dirx[dirchoices[j]];  y += diry[dirchoices[j]];
1209 		    /* Out of the loop. */
1210 		    break;
1211 		} else if (sig < 0) {
1212 		    /* Stop applying to the path right now. */
1213 		    return;
1214 		} else {
1215 		    /* Try another. */
1216 		}
1217 	    }
1218 	}
1219     }
1220 }
1221 
1222 #if 0 /* currently unused */
1223 /* Find a path between the two given points. */
1224 
1225 /* The chooser function gets passed an small array for directions;
1226    it is expected to fill it with directions sorted in order of
1227    preference, and to return the number of directions it found. */
1228 
1229 /* (the chooser also needs to respect already-marked cells) */
1230 /* (marking should account for all directions in?) */
1231 /* (should return a "figure of merit" sometimes) */
1232 /* (main prog should test vicinity of dest, might not be reachable
1233    anyway, but maybe should have "reach within n cells") */
1234 
1235 int
1236 find_path(fx, fy, tx, ty, chooser, maxwps, waypoints, numwpsp)
1237 int fx, fy, tx, ty, maxwps, *numwpsp;
1238 int (*chooser)(int, int, int, int, int *);
1239 Waypoint *waypoints;
1240 {
1241     int ndirs, trythese[NUMDIRS], i;
1242     int x1, y1, x2, y2;
1243 
1244     if (fx == fy && tx == ty) {
1245 	return TRUE;
1246     }
1247     ndirs = (*chooser)(x1, y1, x2, y2, trythese);
1248     if (ndirs == 0) {
1249 	/* We're totally blocked. */
1250 	return FALSE;
1251     } else {
1252 	for (i = 0; i < ndirs; ++i) {
1253 	    /* try this direction with find_path_aux */
1254 	}
1255     }
1256     return FALSE;
1257 }
1258 #endif
1259 
1260 int
search_straight_line(int x0,int y0,int x1,int y1,int (* pred)(int,int),int * rxp,int * ryp)1261 search_straight_line(int x0, int y0, int x1, int y1, int (*pred)(int, int),
1262 		     int *rxp, int *ryp)
1263 {
1264     int i, dist, x, y, xw;
1265 
1266     dist = distance(x0, y0, x1, y1);
1267     if (dist <= 1)
1268       return FALSE;
1269     for (i = 1; i < dist; ++i) {
1270 	/* Interpolate to get an x,y */
1271 	if (x0 == x1)
1272 	  x = x0;
1273 	else
1274 	  x = x0 + (i * (x1 - x0)) / dist;
1275 	if (y0 == y1)
1276 	  y = y0;
1277 	else
1278 	  y = y0 + (i * (y1 - y0)) / dist;
1279 	xw = wrapx(x);
1280 	if (inside_area(x, y) && (*pred)(xw, y)) {
1281 	    *rxp = xw;  *ryp = y;
1282 	    return TRUE;
1283 	}
1284     }
1285     return FALSE;
1286 }
1287 
1288 /* For now, set a bit on both sides of a border. */
1289 
1290 void
set_border_at(int x,int y,int dir,int t,int onoff)1291 set_border_at(int x, int y, int dir, int t, int onoff)
1292 {
1293     int ox, oy, bord, obord;
1294     int odir = opposite_dir(dir);
1295 
1296     if (!t_is_border(t))
1297       return;
1298     if (!point_in_dir(x, y, dir, &ox, &oy)) {
1299 	run_warning("border on outside of world at %d,%d, can't set", x, y);
1300 	return;
1301     }
1302     allocate_area_aux_terrain(t);
1303     onoff = (onoff ? 1 : 0);  /* make sure it's one bit */
1304     bord = aux_terrain_at(x, y, t);
1305     bord = ((onoff << dir) | (bord & ~(1 << dir)));
1306     set_aux_terrain_at(x, y, t, bord);
1307     /* Go to the other cell and tweak its border bits. */
1308     obord = aux_terrain_at(ox, oy, t);
1309     obord = ((onoff << odir) | (obord & ~(1 << odir)));
1310     set_aux_terrain_at(ox, oy, t, obord);
1311 }
1312 
1313 /* For now, set a bit on both sides of a connection. */
1314 
1315 void
set_connection_at(int x,int y,int dir,int t,int onoff)1316 set_connection_at(int x, int y, int dir, int t, int onoff)
1317 {
1318     int ox, oy, conn, oconn;
1319     int odir = opposite_dir(dir);
1320 
1321     if (!t_is_connection(t))
1322       return;
1323     if (!point_in_dir(x, y, dir, &ox, &oy)) {
1324 	run_warning("connection to outside of world at %d,%d, can't set",
1325 		    x, y);
1326 	return;
1327     }
1328     allocate_area_aux_terrain(t);
1329     onoff = (onoff ? 1 : 0);  /* make sure it's one bit */
1330     conn = aux_terrain_at(x, y, t);
1331     conn = ((onoff << dir) | (conn & ~(1 << dir)));
1332     set_aux_terrain_at(x, y, t, conn);
1333     /* Go to the other cell and tweak its connection bits. */
1334     oconn = aux_terrain_at(ox, oy, t);
1335     oconn = ((onoff << odir) | (oconn & ~(1 << odir)));
1336     set_aux_terrain_at(ox, oy, t, oconn);
1337 }
1338 
1339 /* If there might be any inconsistencies in borders or connections,
1340    this fixes them.  Basically this just detects if a bit is set on
1341    either side, and sets the bits on both sides if so. */
1342 
1343 void
patch_linear_terrain(int t)1344 patch_linear_terrain(int t)
1345 {
1346     int x, y, dir, x1, y1;
1347 
1348     if (t_is_border(t)) {
1349 	for_all_cells(x, y) {
1350 	    /* This test is a hack to save some time.  If a cell has
1351 	       no border flags in any direction, then either it has no
1352 	       borders or else it will be fixed up later on, when an
1353 	       adjacent cell is patched. */
1354 	    if (aux_terrain_at(x, y, t) != 0) {
1355 		for_all_directions(dir) {
1356 		    if (border_at(x, y, dir, t)
1357 			&& point_in_dir(x, y, dir, &x1, &y1)
1358 			&& !border_at(x1, y1, opposite_dir(dir), t))
1359 		      set_border_at(x, y, dir, t, TRUE);
1360 		}
1361 	    }
1362 	}
1363     } else if (t_is_connection(t)) {
1364 	for_all_cells(x, y) {
1365 	    if (aux_terrain_at(x, y, t) != 0) {
1366 		for_all_directions(dir) {
1367 		    if (connection_at(x, y, dir, t)
1368 			&& point_in_dir(x, y, dir, &x1, &y1)
1369 			&& !connection_at(x1, y1, opposite_dir(dir), t))
1370 		      set_connection_at(x, y, dir, t, TRUE);
1371 		}
1372 	    }
1373 	}
1374     }
1375 }
1376 
1377 /* Make space to record named features. */
1378 
1379 void
init_features(void)1380 init_features(void)
1381 {
1382     if (features_defined())
1383       return;
1384     featurelist = last_feature = NULL;
1385     numfeatures = 0;
1386     area.features = malloc_area_layer(short);
1387     /* No need to fill layer with default value, as long as feature 0
1388        means "no feature". */
1389 }
1390 
1391 Feature *
create_feature(char * feattype,char * name)1392 create_feature(char *feattype, char *name)
1393 {
1394     Feature *newfeature = (Feature *) xmalloc(sizeof(Feature));
1395 
1396     /* If we're going to have a feature, we need to have the layer
1397        too.  init_features clears other data, which is why we do it at
1398        the beginning of this function. */
1399     if (!features_defined())
1400       init_features();
1401     newfeature->id = nextfid++;
1402     newfeature->feattype = feattype;
1403     newfeature->name = name;
1404     /* Add to the end of the feature list. */
1405     if (last_feature != NULL) {
1406     	last_feature->next = newfeature;
1407     } else {
1408     	featurelist = newfeature;
1409     }
1410     last_feature = newfeature;
1411     ++numfeatures;
1412     return newfeature;
1413 }
1414 
1415 /* Given a feature id, find the corresponding object. */
1416 
1417 Feature *
find_feature(int fid)1418 find_feature(int fid)
1419 {
1420     Feature *feature;
1421 
1422     /* Feature id of 0 is always a non-feature. */
1423     if (fid == 0)
1424       return NULL;
1425     for_all_features(feature) {
1426 	if (feature->id == fid)
1427 	  return feature;
1428     }
1429     return NULL;
1430 }
1431 
1432 /* Return the feature object at the given location. */
1433 
1434 Feature *
feature_at(int x,int y)1435 feature_at(int x, int y)
1436 {
1437     int fid;
1438 
1439     if (!features_defined())
1440       return NULL;
1441 
1442     fid = raw_feature_at(x, y);
1443     return find_feature(fid);
1444 }
1445 
1446 /* Set the type name of the feature. */
1447 
1448 void
set_feature_type_name(Feature * feature,char * feattype)1449 set_feature_type_name(Feature *feature, char *feattype)
1450 {
1451     if (feature == NULL)
1452       return;
1453     feature->feattype = copy_string(feattype);
1454     /* (should ping all displays) */
1455 }
1456 
1457 /* Set the name of the feature. */
1458 
1459 void
set_feature_name(Feature * feature,char * name)1460 set_feature_name(Feature *feature, char *name)
1461 {
1462     if (feature == NULL)
1463       return;
1464     feature->name = copy_string(name);
1465     /* (should ping all displays) */
1466 }
1467 
1468 /* Given a feature object, make it go away. */
1469 
1470 void
destroy_feature(Feature * feature)1471 destroy_feature(Feature *feature)
1472 {
1473     int x, y, oldfid, fid;
1474     Feature *tmp, *prev;
1475 
1476     if (feature == NULL)
1477       return; /* (should be error?) */
1478     oldfid = feature->id;
1479     if (feature == featurelist) {
1480 	featurelist = feature->next;
1481 	if (feature == last_feature)
1482 	  last_feature = NULL;
1483     } else {
1484 	prev = NULL;
1485 	for_all_features(tmp) {
1486     	    if (tmp == feature) {
1487 		if (prev != NULL)
1488 		  prev->next = tmp->next;
1489 		break;
1490 	    }
1491 	    prev = tmp;
1492 	}
1493 	if (feature == last_feature)
1494 	  last_feature = prev;
1495     }
1496     --numfeatures;
1497     /* Clear out any uses in the features layer. */
1498     for_all_cells(x, y) {
1499 	fid = raw_feature_at(x, y);
1500 	if (fid == oldfid)
1501 	  set_raw_feature_at(x, y, 0);
1502     }
1503     /* (should dealloc also?) */
1504 }
1505 
1506 /* Renumber everything in the layer according to the order in which
1507    it appears in the list of features. */
1508 /* (should be able to call this from designer tools) */
1509 
1510 void
renumber_features(void)1511 renumber_features(void)
1512 {
1513     int newfid = 1, maxoldfid = 0, x, y;
1514     short *newlabels;
1515     Feature *feature;
1516 
1517     if (!features_defined())
1518       return;
1519     for_all_features(feature) {
1520     	maxoldfid = max(maxoldfid, feature->id);
1521     	feature->relabel = newfid++;
1522     }
1523     if (maxoldfid > 1000)
1524       return; /* don't risk it */
1525     newlabels = (short *) xmalloc((maxoldfid + 1) * sizeof(short));
1526     for_all_features(feature) {
1527     	newlabels[feature->id] = feature->relabel;
1528     }
1529     /* Apply the new labels to everything in the layer. */
1530     for_all_cells(x, y) {
1531     	set_raw_feature_at(x, y, newlabels[raw_feature_at(x, y)]);
1532     }
1533     for_all_features(feature) {
1534     	feature->id = feature->relabel;
1535     }
1536     free(newlabels);
1537 }
1538 
1539 /* A feature's centroid is the closest it has to an actual center;
1540    this function computes for all features. */
1541 
1542 void
compute_all_feature_centroids(void)1543 compute_all_feature_centroids(void)
1544 {
1545     compute_feature_centroid(NULL);
1546 }
1547 
1548 /* The same, but for a single feature.  This would be very inefficient
1549    to call repeatedly for each feature in the world. */
1550 
1551 void
compute_feature_centroid(Feature * feature)1552 compute_feature_centroid(Feature *feature)
1553 {
1554     int x, y;
1555     Feature *tmpfeature;
1556 
1557     /* Only do this if features and a feature layer to work with. */
1558     if (featurelist == NULL || !features_defined())
1559       return;
1560     /* Either clear all features or just the one passed in. */
1561     for_all_features(tmpfeature) {
1562 	if (feature == NULL || tmpfeature == feature) {
1563 	    tmpfeature->size = 0;
1564 	    tmpfeature->x = tmpfeature->y = 0;
1565 	    tmpfeature->xmin = tmpfeature->ymin = area.maxdim + 1;
1566 	    tmpfeature->xmax = tmpfeature->ymax = -1;
1567 	}
1568     }
1569     /* Iterate over all cells. */
1570     for_all_cells(x, y) {
1571 	if (feature) {
1572 	    if (feature->id == raw_feature_at(x, y))
1573 	      tmpfeature = feature;
1574 	    else
1575 	      tmpfeature = NULL;
1576 	} else {
1577 	    tmpfeature = feature_at(x, y);
1578 	}
1579 	if (tmpfeature != NULL) {
1580 	    ++(tmpfeature->size);
1581 	    tmpfeature->x += x;
1582 	    tmpfeature->y += y;
1583 	    tmpfeature->xmin = min(x, tmpfeature->xmin);
1584 	    tmpfeature->ymin = min(y, tmpfeature->ymin);
1585 	    tmpfeature->xmax = max(x, tmpfeature->xmax);
1586 	    tmpfeature->ymax = max(y, tmpfeature->ymax);
1587 	}
1588     }
1589     for_all_features(tmpfeature) {
1590 	if (feature == NULL || tmpfeature == feature) {
1591 	    if (tmpfeature->size > 0) {
1592 		tmpfeature->x = tmpfeature->x / tmpfeature->size;
1593 		tmpfeature->y = tmpfeature->y / tmpfeature->size;
1594 	    }
1595 	}
1596     }
1597 }
1598 
1599 int
num_people_at(int x,int y)1600 num_people_at(int x, int y)
1601 {
1602     int m, num;
1603 
1604     num = 0;
1605     for_all_material_types(m) {
1606 	if (cell_material_defined(m)) {
1607 	    num += material_at(x, y, m) * m_people(m);
1608 	}
1609     }
1610     return num;
1611 }
1612 
1613 /* Compute the coords of a point in the given direction. */
1614 
1615 int
point_in_dir(int x,int y,int dir,int * xp,int * yp)1616 point_in_dir(int x, int y, int dir, int *xp, int *yp)
1617 {
1618     *xp = wrapx(x + dirx[dir]);  *yp = y + diry[dir];
1619     return (in_area(*xp, *yp));
1620 }
1621 
1622 /* Compute the coords of a point in the given direction, but flag
1623    points not inside the area. */
1624 
1625 int
interior_point_in_dir(int x,int y,int dir,int * xp,int * yp)1626 interior_point_in_dir(int x, int y, int dir, int *xp, int *yp)
1627 {
1628     *xp = wrapx(x + dirx[dir]);  *yp = y + diry[dir];
1629     return (inside_area(*xp, *yp));
1630 }
1631 
1632 /* Compute the point in a direction, n cells away. */
1633 
1634 int
point_in_dir_n(int x,int y,int dir,int n,int * xp,int * yp)1635 point_in_dir_n(int x, int y, int dir, int n, int *xp, int *yp)
1636 {
1637     *xp = wrapx(x + n * dirx[dir]);  *yp = y + n * diry[dir];
1638     return (in_area(*xp, *yp));
1639 }
1640 
1641 int
interior_point_in_dir_n(int x,int y,int dir,int n,int * xp,int * yp)1642 interior_point_in_dir_n(int x, int y, int dir, int n, int *xp, int *yp)
1643 {
1644     *xp = wrapx(x + n * dirx[dir]);  *yp = y + n * diry[dir];
1645     return (inside_area(*xp, *yp));
1646 }
1647 
1648 /* Return a random point guaranteed inside the area. */
1649 
1650 int
random_point(int * xp,int * yp)1651 random_point(int *xp, int *yp)
1652 {
1653     int tries = 500;
1654 
1655     while (tries-- > 0) {
1656 	*xp = xrandom(area.width);  *yp = xrandom(area.height - 2) + 1;
1657 	if (inside_area(*xp, *yp))
1658 	  return TRUE;
1659     }
1660     return FALSE;
1661 }
1662 
1663 /* Return a random point guaranteed on the edge of the area. */
1664 
1665 int
random_edge_point(int * xp,int * yp)1666 random_edge_point(int *xp, int *yp)
1667 {
1668     int tries = 500, adjustedwidth, ratio, val;
1669 
1670     while (tries-- > 0) {
1671 	if (area.xwrap) {
1672 	    *xp = xrandom(area.width);
1673 	    *yp = (flip_coin() ? 0 : area.height - 1);
1674 	} else {
1675 	    adjustedwidth = area.width - area.halfheight;
1676 	    ratio = (adjustedwidth * 100) / (area.width + area.halfheight);
1677 	    if (probability(ratio)) {
1678 		/* Pick along top or bottom edge. */
1679 		if (flip_coin()) {
1680 		    /* Pick along bottom edge. */
1681 		    *xp = xrandom(adjustedwidth) + area.halfheight;
1682 		    *yp = 0;
1683 		} else {
1684 		    /* Pick along top edge. */
1685 		    *xp = xrandom(adjustedwidth);
1686 		    *yp = area.height - 1;
1687 		}
1688 	    } else {
1689 		/* Pick along right or left side. */
1690 		if (flip_coin()) {
1691 		    /* Pick along right side. */
1692 		    if (flip_coin()) {
1693 			/* Pick along upper right side. */
1694 			val = xrandom(area.halfheight);
1695 			*xp = area.width - val;
1696 			*yp = area.halfheight + val;
1697 		    } else {
1698 			/* Pick along lower right side. */
1699 			*xp = area.width;
1700 			*yp = xrandom(area.halfheight);
1701 		    }
1702 		} else {
1703 		    /* Pick along left side. */
1704 		    if (flip_coin()) {
1705 			/* Pick along upper left side. */
1706 			*xp = 0;
1707 			*yp = area.halfheight + xrandom(area.halfheight);
1708 		    } else {
1709 			/* Pick along lower left side. */
1710 			val = xrandom(area.halfheight);
1711 			*xp = val;
1712 			*yp = area.halfheight - val;
1713 		    }
1714 		}
1715 	    }
1716 	}
1717 	if (in_area(*xp, *yp) && !inside_area(*xp, *yp))
1718 	  return TRUE;
1719     }
1720     return FALSE;
1721 }
1722 
1723 /* Return a random point guaranteed to be within a given radius of
1724    a given point. */
1725 
1726 int
random_point_near(int cx,int cy,int radius,int * xp,int * yp)1727 random_point_near(int cx, int cy, int radius, int *xp, int *yp)
1728 {
1729     int tries = 500;
1730 
1731     if (radius <= 0)
1732       return FALSE;
1733     while (tries-- > 0) {
1734 	*xp = cx + xrandom(2 * radius + 1) - radius;
1735 	*yp = cy + xrandom(2 * radius + 1) - radius;
1736 	if (inside_area(*xp, *yp)
1737 	    && distance(cx, cy, *xp, *yp) <= radius)
1738 	      return TRUE;
1739     }
1740     return FALSE;
1741 }
1742 
1743 /* Return a random point guaranteed to be within a given radius of
1744    a given point. */
1745 
1746 int
random_point_in_area(int cx,int cy,int rx,int ry,int * xp,int * yp)1747 random_point_in_area(int cx, int cy, int rx, int ry, int *xp, int *yp)
1748 {
1749     int tries = 500;
1750 
1751     if (rx < 0)
1752       rx = 0;
1753     if (ry < 0)
1754       ry = 0;
1755     /* If no variation allowed, just return the center directly. */
1756     if (rx == 0 && ry == 0) {
1757 	*xp = cx;
1758 	*yp = cy;
1759 	return inside_area(*xp, *yp);
1760     }
1761     while (tries-- > 0) {
1762 	*xp = cx + xrandom(2 * rx + 1) - rx;
1763 	*yp = cy + xrandom(2 * ry + 1) - ry;
1764 	if (inside_area(*xp, *yp)
1765 	    && distance(cx, cy, *xp, *yp) <= max(rx - ry, ry - rx))
1766 	  return TRUE;  /* (should fix test?) */
1767     }
1768     return FALSE;
1769 }
1770 
1771 /* Generic warning that a terrain subtype is incorrect. */
1772 
1773 void
terrain_subtype_warning(char * context,int t)1774 terrain_subtype_warning(char *context, int t)
1775 {
1776     run_warning("In %s: Garbage t%d (%s) subtype %d",
1777 		context, t, t_type_name(t), t_subtype(t));
1778 }
1779 
1780 /* Given a vector, return the direction that best approximates it. */
1781 
1782 int
approx_dir(int dx,int dy)1783 approx_dir(int dx, int dy)
1784 {
1785     if (dx == 0) {
1786 	if (dy == 0)
1787 	  return -1; /* should flag so can use special cursor */
1788 	if (dy > 0)
1789 	  return NORTHEAST;
1790 	return SOUTHWEST;
1791     } else if (dx > 0) {
1792     	/* Check for the axes first. */
1793 	if (dy == 0)
1794 	  return EAST;
1795 	if (dy == (-dx))
1796 	  return SOUTHEAST;
1797 	if (dy > dx)
1798 	  return NORTHEAST;
1799 	if ((-dy) <= dx / 2)
1800 	  return EAST;
1801 	if ((-dy) < dx * 2)
1802 	  return SOUTHEAST;
1803 	return SOUTHWEST;
1804     } else {
1805     	/* Check for the axes first. */
1806 	if (dy == 0)
1807 	  return WEST;
1808     	if (dy == (-dx))
1809     	  return NORTHWEST;
1810 	if (dy > (-dx) * 2)
1811 	  return NORTHEAST;
1812 	if (dy >= (-dx) / 2)
1813 	  return NORTHWEST;
1814 	if (dy > dx)
1815 	  return WEST;
1816 	return SOUTHWEST;
1817     }
1818 }
1819 
1820 /* Computing distance in a hexagonal system is a little peculiar,
1821    since it's sometimes just delta x or y, and other times is the sum.
1822    Basically there are six formulas to compute distance, depending on
1823    the direction between the two points.  If the area wraps, this
1824    routine reports the shortest distance. */
1825 
1826 int
distance(int x1,int y1,int x2,int y2)1827 distance(int x1, int y1, int x2, int y2)
1828 {
1829     int dx = x2 - x1, dy = y2 - y1;
1830 
1831     if (area.xwrap) {
1832     	/* Choose the shortest way around a cylinder. */
1833     	dx = (dx < 0 ? (dx < 0 - area.width / 2 ? area.width + dx : dx)
1834 	        	 : (dx > area.width / 2 ? dx - area.width : dx));
1835     }
1836     if (dx >= 0) {
1837 	if (dy >= 0) {
1838 	    return (dx + dy);
1839 	} else if ((0 - dy) <= dx) {
1840 	    return dx;
1841 	} else {
1842 	    return (0 - dy);
1843 	}
1844     } else {
1845 	if (dy <= 0) {
1846 	    return (0 - (dx + dy));
1847 	} else if (dy <= (0 - dx)) {
1848 	    return (0 - dx);
1849 	} else {
1850 	    return dy;
1851 	}
1852     }
1853 }
1854 
1855 /* Compute distance in the world, irrespective of area size.  The
1856    result of this function is undefined if the world circumference
1857    is 0. (why?) */
1858 
1859 int
world_distance(int x1,int y1,int x2,int y2)1860 world_distance(int x1, int y1, int x2, int y2)
1861 {
1862     int circumf, dx = x2 - x1, dy = y2 - y1;
1863 
1864     circumf = world.circumference;
1865     /* Choose the shortest way around the world. */
1866     dx = (dx < 0 ? (dx < 0 - circumf / 2 ? circumf + dx : dx)
1867 	         : (dx > 0 + circumf / 2 ? dx - circumf : dx));
1868     if (dx >= 0) {
1869 	if (dy >= 0) {
1870 	    return (dx + dy);
1871 	} else if ((0 - dy) <= dx) {
1872 	    return dx;
1873 	} else {
1874 	    return (0 - dy);
1875 	}
1876     } else {
1877 	if (dy <= 0) {
1878 	    return (0 - (dx + dy));
1879 	} else if (dy <= (0 - dx)) {
1880 	    return (0 - dx);
1881 	} else {
1882 	    return dy;
1883 	}
1884     }
1885 }
1886 
1887 /* Find the direction matching the given x and y, return -1 if no
1888    match.  Callers should be careful to test for this! */
1889 
1890 int
closest_dir(int x,int y)1891 closest_dir(int x, int y)
1892 {
1893     int dir;
1894 
1895     for_all_directions(dir) {
1896 	if (dirx[dir] == x && diry[dir] == y)
1897 	  return dir;
1898     }
1899     return -1;
1900 }
1901 
1902 /* 360 degrees * 60 minutes */
1903 
1904 #define MINUTES (21600)
1905 
1906 /* Given an x,y and position within a cell, compute the latitude and
1907    longitude in arc minutes. */
1908 
1909 void
xy_to_latlong(int x,int y,int xf,int yf,int * latp,int * lonp)1910 xy_to_latlong(int x, int y, int xf, int yf, int *latp, int *lonp)
1911 {
1912     int lat, lon, center;
1913     float fx1, fy1, ratio;
1914 
1915     /* The world must be considered to be spherical. */
1916     if (world.circumference <= 0) {
1917 	*latp = *lonp = 0;
1918 	return;
1919     }
1920     fy1 = y + area.latitude - area.halfheight + ((float) yf) / 1000;
1921     /* Convert to arc minutes. */
1922     lat = (int)(fy1 * MINUTES) / world.circumference;
1923     center = (1000 * (area.width + area.halfheight - y)) / 2 - 500;
1924     fx1 = 1000 * x + xf;
1925     fx1 -= center;
1926     if (area.projection == 1) {
1927 	/* Compute compression ratio due to latitude. */
1928 	/* The magic value is 2 pi / MINUTES. */
1929 	ratio = cos(abs(lat) * 0.000290888);
1930 	fx1 = fx1 / ratio;
1931     }
1932     /* Offset by the longitude. */
1933     fx1 += 1000 * area.longitude;
1934     /* Convert to arc minutes. */
1935     lon = (int)(fx1 * MINUTES) / world.circumference;
1936     lon /= 1000;
1937     /* Push the longitude into the range -180 to 180 degrees. */
1938     if (lon > MINUTES / 2)
1939       lon -= MINUTES;
1940     if (lon <= (- MINUTES / 2))
1941       lon += MINUTES;
1942     *latp = lat;  *lonp = lon;
1943 }
1944 
1945 /* Given latitude/longitude in arc minutes, compute the cell and position
1946    within the cell, in 1/1000ths of the cell. */
1947 
1948 int
latlong_to_xy(int lat,int lon,int * xp,int * yp,int * xfp,int * yfp)1949 latlong_to_xy(int lat, int lon, int *xp, int *yp, int *xfp, int *yfp)
1950 {
1951     int x1, y1, center;
1952     float fx1, fy1, ratio;
1953 
1954     /* The world must be considered to be spherical. */
1955     if (world.circumference <= 0) {
1956 	return FALSE;
1957     }
1958     /* Convert latitude to 1000ths of a cell. */
1959     fy1 = (((float) lat) * world.circumference) / MINUTES;
1960     y1 = (int)(fy1 * 1000);
1961     /* Latitude of 0 passes through the center of the area. */
1962     *yp = y1 / 1000 - area.latitude + area.halfheight;
1963     *yfp = y1 % 1000;
1964 
1965     /* Convert longitude to cell. */
1966     /* Only do this for wrapped areas, or it will prevent drawing of
1967     the Western hemisphere meridians on the Mac. */
1968     if (lon <= 0 && area.xwrap)
1969       lon += MINUTES;
1970     fx1 = (((float) lon) * world.circumference) / MINUTES;
1971     fx1 -= area.longitude;
1972     if (area.projection == 1) {
1973 	/* Compute compression ratio due to latitude. */
1974 	/* The magic value is 2 pi / MINUTES. */
1975 	ratio = cos(abs(lat) * 0.000290888);
1976 	/* Compute x by compressing longitude towards center of the area. */
1977 	fx1 = fx1 * ratio;
1978     }
1979     x1 = (int)(fx1 * 1000);
1980     /* Compute the effect of obliqueness on x. */
1981     center = (1000 * (area.width + area.halfheight - *yp)) / 2 - 500;
1982     x1 += center;
1983     /* Convert to cell and cell fraction. */
1984     *xp = x1 / 1000;
1985     *xfp = x1 % 1000;
1986     if (*xp < 0)
1987       *xp += world.circumference;
1988     return TRUE;
1989 }
1990 
1991 void add_neighbor(TRegion *reg1, TRegion *reg2);
1992 
1993 int region_value(int x, int y, int landsea);
1994 
1995 /* The landsea flag tells us that we only want to consider if terrain
1996 is liquid or not when making regions. */
1997 
1998 int
region_value(int x,int y,int landsea)1999 region_value(int x, int y, int landsea)
2000 {
2001  	if (landsea) {
2002 		return (t_liquid(terrain_at(x, y)) ? 0 : 1);
2003 	} else {
2004 		return (terrain_at(x, y));
2005 	}
2006 }
2007 
2008 void
divide_into_regions(char * tlayer,TRegion ** rlayer,int landsea)2009 divide_into_regions(char *tlayer, TRegion **rlayer, int landsea)
2010 {
2011     int x, y, dir, x1, y1, i;
2012     TRegion *region, *reg1, *reg2;
2013 
2014     if (landsea) {
2015 	    landsea_region_list = NULL;
2016 	    num_landsea_regions = 0;
2017     } else {
2018 	    terrain_region_list = NULL;
2019 	    num_terrain_regions = 0;
2020     }
2021     /* We need to know the exact order of scanning, so can't use standard
2022        iteration macro. */
2023     for (y = 1; y < area.height - 1; ++y) {
2024 	for (x = 0; x < area.width; ++x) {
2025 	    if (inside_area(x, y)) {
2026 		if (interior_point_in_dir(x, y, WEST, &x1, &y1)
2027 		    && region_value(x, y, landsea) == region_value(x1, y1, landsea)) {
2028 		    region = aref(rlayer, x1, y1);
2029 		} else if (interior_point_in_dir(x, y, SOUTHWEST, &x1, &y1)
2030 			   && region_value(x, y, landsea) == region_value(x1, y1, landsea)) {
2031 		    region = aref(rlayer, x1, y1);
2032 		} else if (interior_point_in_dir(x, y, SOUTHEAST, &x1, &y1)
2033 			   && region_value(x, y, landsea) == region_value(x1, y1, landsea)) {
2034 		    region = aref(rlayer, x1, y1);
2035 		} else {
2036 		    region = NULL;
2037 		}
2038 		/* Create a new region if no matches found. */
2039 		if (region == NULL) {
2040 		    region = (TRegion *) xmalloc(sizeof(TRegion));
2041 		    region->ttype = region_value(x, y, landsea);
2042 		    region->xmin = region->ymin = 10000;
2043 		    region->xmax = region->ymax = -1;
2044 		    if (landsea) {
2045 			    region->next = landsea_region_list;
2046 			    landsea_region_list = region;
2047 			    ++num_landsea_regions;
2048 		    } else {
2049 			    region->next = terrain_region_list;
2050 			    terrain_region_list = region;
2051 			    ++num_terrain_regions;
2052 		    }
2053 		}
2054 		/* Add the point to the region. */
2055 		aset(rlayer, x, y, region);
2056 		++(region->size);
2057 		region->xmin = min(x, region->xmin);
2058 		region->ymin = min(y, region->ymin);
2059 		region->xmax = max(x, region->xmax);
2060 		region->ymax = max(y, region->ymax);
2061 	    }
2062 	}
2063     }
2064     /* We need to iterate the process several times in order to make sure
2065     that all regions that should be merged really are merged. A region of
2066     type 1 may border on second region of type 1 which borders on a third
2067     region of type 1. Only the first two regions will then get merged in the
2068     first pass. */
2069     for (i = 0; i < 10; i++) {
2070 	    for_all_interior_cells(x, y) {
2071 		for_all_directions(dir) {
2072 		    if (interior_point_in_dir(x, y, dir, &x1, &y1)) {
2073 			if (region_value(x, y, landsea) == region_value(x1, y1, landsea)) {
2074 			    reg1 = aref(rlayer, x, y);
2075 			    reg2 = aref(rlayer, x1, y1);
2076 			    if (reg1 != reg2) {
2077 				if (reg1->size > reg2->size)
2078 				  reg2->merge = reg1;
2079 				else if (reg1->size > reg2->size)
2080 				  reg1->merge = reg2;
2081 			    }
2082 			}
2083 		    }
2084 		}
2085 	    }
2086 	    for_all_interior_cells(x, y) {
2087 		reg1 = aref(rlayer, x, y);
2088 		reg2 = reg1->merge;
2089 		if (reg2 != NULL) {
2090 		    aset(rlayer, x, y, reg2);
2091 		    ++(reg2->size);
2092 		    reg2->xmin = min(x, reg2->xmin);  reg2->ymin = min(y, reg2->ymin);
2093 		    reg2->xmax = max(x, reg2->xmax);  reg2->ymax = max(y, reg2->ymax);
2094 		    --(reg1->size);
2095 		}
2096 	    }
2097     }
2098     for_all_interior_cells(x, y) {
2099 	reg1 = aref(rlayer, x, y);
2100 	for_all_directions(dir) {
2101 	    if (interior_point_in_dir(x, y, dir, &x1, &y1)) {
2102 		reg2 = aref(rlayer, x1, y1);
2103 		if (reg1 != reg2) {
2104 		    add_neighbor(reg1, reg2);
2105 		    add_neighbor(reg2, reg1);
2106 		}
2107 	    }
2108 	}
2109     }
2110 }
2111 
2112 void
add_neighbor(TRegion * reg1,TRegion * reg2)2113 add_neighbor(TRegion *reg1, TRegion *reg2)
2114 {
2115     TRegionLink *link;
2116 
2117     for (link = reg1->neighbors; link != NULL; link = link->next) {
2118 	/* If already listed as neighbor, we're done. */
2119 	if (reg2 == link->neighbor)
2120 	  return;
2121     }
2122     link = (TRegionLink *) xmalloc(sizeof(TRegionLink));
2123     link->neighbor = reg2;
2124     link->next = reg1->neighbors;
2125     reg1->neighbors = link;
2126 }
2127 
2128 /* (should put internal date-handling code here) */
2129 
2130 #ifdef DESIGNERS
2131 
2132 static void paint_cell_1(int x, int y);
2133 static void paint_coating_1(int x, int y);
2134 static void paint_people_1(int x, int y);
2135 static void paint_control_1(int x, int y);
2136 static void paint_feature_1(int x, int y);
2137 static void paint_elevation_1(int x, int y);
2138 static void paint_temperature_1(int x, int y);
2139 static void paint_material_1(int x, int y);
2140 static void paint_clouds_1(int x, int y);
2141 static void paint_winds_1(int x, int y);
2142 
2143 extern void fix_elevations(void);
2144 
2145 /* Cell painting. */
2146 
2147 void
paint_cell(Side * side,int x,int y,int r,int t)2148 paint_cell(Side *side, int x, int y, int r, int t)
2149 {
2150     tmpside = side;
2151     tmpttype = t;
2152     apply_to_area_plus_edge(x, y, r, paint_cell_1);
2153 }
2154 
2155 static void
paint_cell_1(int x,int y)2156 paint_cell_1(int x, int y)
2157 {
2158     /* Only do anything if we're actually changing to a different type. */
2159     if (terrain_at(x, y) != tmpttype) {
2160 	set_terrain_at(x, y, tmpttype);
2161 	update_cell_display(tmpside, x, y, UPDATE_ALWAYS | UPDATE_ADJ);
2162     }
2163 }
2164 
2165 /* Border/connection painting. */
2166 
2167 void
paint_border(Side * side,int x,int y,int dir,int t,int mode)2168 paint_border(Side *side, int x, int y, int dir, int t, int mode)
2169 {
2170     int oldbord, x1, y1;
2171 
2172     if (!inside_area(x, y))
2173       return;
2174     allocate_area_aux_terrain(t);
2175     oldbord = border_at(x, y, dir, t);
2176     set_border_at(x, y, dir, t, (mode < 0 ? !oldbord : mode));
2177     if (oldbord != border_at(x, y, dir, t)) {
2178 	update_cell_display(side, x, y, UPDATE_ALWAYS | UPDATE_ADJ);
2179 	/* We need to do this because UPDATE_ADJ is a hint, not a
2180 	   requirement to redraw adjacent cells. */
2181 	if (point_in_dir(x, y, dir, &x1, &y1))
2182 	  update_cell_display(side, x1, y1, UPDATE_ALWAYS | UPDATE_ADJ);
2183     }
2184 }
2185 
2186 void
paint_connection(Side * side,int x,int y,int dir,int t,int mode)2187 paint_connection(Side *side, int x, int y, int dir, int t, int mode)
2188 {
2189     int oldconn, x1, y1;
2190 
2191     if (!inside_area(x, y))
2192       return;
2193     allocate_area_aux_terrain(t);
2194     oldconn = connection_at(x, y, dir, t);
2195     set_connection_at(x, y, dir, t, (mode < 0 ? !oldconn : mode));
2196     if (oldconn != connection_at(x, y, dir, t)) {
2197 	update_cell_display(side, x, y, UPDATE_ALWAYS | UPDATE_ADJ);
2198 	/* We need to do this because UPDATE_ADJ is a hint, not a
2199 	   requirement to redraw adjacent cells. */
2200 	if (point_in_dir(x, y, dir, &x1, &y1))
2201 	  update_cell_display(side, x1, y1, UPDATE_ALWAYS | UPDATE_ADJ);
2202     }
2203 }
2204 
2205 /* Coating painting. */
2206 
2207 void
paint_coating(Side * side,int x,int y,int r,int t,int depth)2208 paint_coating(Side *side, int x, int y, int r, int t, int depth)
2209 {
2210     allocate_area_aux_terrain(t);
2211     tmpside = side;
2212     tmpttype = t;
2213     tmpint = depth;
2214     apply_to_area_plus_edge(x, y, r, paint_coating_1);
2215 }
2216 
2217 static void
paint_coating_1(int x,int y)2218 paint_coating_1(int x, int y)
2219 {
2220     int olddepth = aux_terrain_at(x, y, tmpttype);
2221 
2222     if (olddepth != tmpint) {
2223 	set_aux_terrain_at(x, y, tmpttype, tmpint);
2224 	update_cell_display(tmpside, x, y, UPDATE_ALWAYS | UPDATE_ADJ);
2225     }
2226 }
2227 
2228 /* Painting of people sides. */
2229 
2230 void
paint_people(Side * side,int x,int y,int r,int s)2231 paint_people(Side *side, int x, int y, int r, int s)
2232 {
2233     allocate_area_people_sides();
2234     tmpside = side;
2235     tmpint = s;
2236     apply_to_area(x, y, r, paint_people_1);
2237 }
2238 
2239 static void
paint_people_1(int x,int y)2240 paint_people_1(int x, int y)
2241 {
2242     int oldpeop = people_side_at(x, y);
2243 
2244     if (oldpeop != tmpint) {
2245 	set_people_side_at(x, y, tmpint);
2246 	/* Appearance of adjacent cells may change also. */
2247 	update_cell_display(tmpside, x, y, UPDATE_ALWAYS | UPDATE_ADJ);
2248 
2249     }
2250 }
2251 
2252 /* Painting of controlling side. */
2253 
2254 void
paint_control(Side * side,int x,int y,int r,int s)2255 paint_control(Side *side, int x, int y, int r, int s)
2256 {
2257     allocate_area_control_sides();
2258     tmpside = side;
2259     tmpint = s;
2260     apply_to_area(x, y, r, paint_control_1);
2261 }
2262 
2263 static void
paint_control_1(int x,int y)2264 paint_control_1(int x, int y)
2265 {
2266     int oldpeop = control_side_at(x, y);
2267 
2268     if (oldpeop != tmpint) {
2269 	set_control_side_at(x, y, tmpint);
2270 	/* Appearance of adjacent cells may change also. */
2271 	update_cell_display(tmpside, x, y, UPDATE_ALWAYS | UPDATE_ADJ);
2272     }
2273 }
2274 
2275 /* Painting of geographical features.  A feature id of 0 directs feature
2276    removal from the given area. */
2277 
2278 void
paint_feature(Side * side,int x,int y,int r,int f)2279 paint_feature(Side *side, int x, int y, int r, int f)
2280 {
2281     init_features();
2282     tmpside = side;
2283     tmpint = f;
2284     tmpfeature = find_feature(f);
2285     apply_to_area(x, y, r, paint_feature_1);
2286 }
2287 
2288 static void
paint_feature_1(int x,int y)2289 paint_feature_1(int x, int y)
2290 {
2291     int oldfid = raw_feature_at(x, y);
2292     Feature *oldfeature;
2293 
2294     if (oldfid != tmpint) {
2295 	set_raw_feature_at(x, y, tmpint);
2296 	if (tmpfeature != NULL) {
2297 	    ++(tmpfeature->size);
2298 	    /* too expensive while painting */
2299 	    /* compute_feature_centroid(tmpfeature); */
2300 	}
2301     	if (oldfid != 0) {
2302 	    oldfeature = find_feature(oldfid);
2303 	    if (oldfeature != NULL) {
2304 		--(oldfeature->size);
2305 		/* compute_feature_centroid(oldfeature); */
2306 	    }
2307 	}
2308 	/* Might need to redraw feature borders in adjacent cells. */
2309 	update_cell_display(tmpside, x, y, UPDATE_ALWAYS | UPDATE_ADJ);
2310     }
2311 }
2312 
2313 /* Painting of terrain elevations. */
2314 
2315 void
paint_elevation(Side * side,int x,int y,int r,int code,int elev,int vary)2316 paint_elevation(Side *side, int x, int y, int r, int code, int elev, int vary)
2317 {
2318     allocate_area_elevations();
2319     tmpside = side;
2320     tmpint = code;
2321     tmpint2 = elev;
2322     tmpint3 = vary;
2323     apply_to_area_plus_edge(x, y, r, paint_elevation_1);
2324 }
2325 
2326 static void
paint_elevation_1(int x,int y)2327 paint_elevation_1(int x, int y)
2328 {
2329     int oldelev = elev_at(x, y), newelev;
2330 
2331     /* Decide whether we're setting or adjusting the elevation. */
2332     switch (tmpint) {
2333       case 0:
2334 	newelev = tmpint2;
2335 	break;
2336       case 1:
2337 	newelev = oldelev + tmpint2;
2338 	break;
2339       default:
2340 	run_warning("bogus elevation paint code");
2341 	newelev = 0;
2342 	break;
2343     }
2344     /* Add an optional random variation if desired. */
2345     if (tmpint3 > 0)
2346       newelev += xrandom(tmpint3 * 2 + 1) - tmpint3;
2347     if (newelev != oldelev) {
2348 	set_elev_at(x, y, newelev);
2349 	if (newelev < area.minelev)
2350 	  area.minelev = newelev;
2351 	if (newelev > area.maxelev)
2352 	  area.maxelev = newelev;
2353 	/* Note that the contour intervals may now no longer be
2354 	   reasonable, but since redoing them will probably require a
2355 	   full map update, don't adjust them automatically here. */
2356 	update_cell_display(tmpside, x, y, UPDATE_ALWAYS | UPDATE_ADJ);
2357     }
2358 }
2359 
2360 void
paint_temperature(Side * side,int x,int y,int r,int temp)2361 paint_temperature(Side *side, int x, int y, int r, int temp)
2362 {
2363     allocate_area_temperatures();
2364     tmpside = side;
2365     tmpint = temp;
2366     apply_to_area_plus_edge(x, y, r, paint_temperature_1);
2367 }
2368 
2369 static void
paint_temperature_1(int x,int y)2370 paint_temperature_1(int x, int y)
2371 {
2372     int n, t = terrain_at(x, y), oldtemp = temperature_at(x, y);
2373 
2374     n = max(t_temp_min(t), min(tmpint, t_temp_max(t)));
2375     if (n != oldtemp) {
2376 	set_temperature_at(x, y, n);
2377 	update_cell_display(tmpside, x, y, UPDATE_ALWAYS);
2378     }
2379 }
2380 
2381 /* Material layer painting. */
2382 
2383 void
paint_material(Side * side,int x,int y,int r,int m,int amt)2384 paint_material(Side *side, int x, int y, int r, int m, int amt)
2385 {
2386     allocate_area_material(m);
2387     tmpside = side;
2388     tmpmtype = m;
2389     tmpint = amt;
2390     apply_to_area_plus_edge(x, y, r, paint_material_1);
2391 }
2392 
2393 static void
paint_material_1(int x,int y)2394 paint_material_1(int x, int y)
2395 {
2396     int oldm = material_at(x, y, tmpmtype);
2397 
2398     if (oldm != tmpint) {
2399 	set_material_at(x, y, tmpmtype, tmpint);
2400 	update_cell_display(tmpside, x, y, UPDATE_ALWAYS);
2401     }
2402 }
2403 
2404 /* Cloud painting is more complicated because up to three separate
2405    layers are involved. */
2406 
2407 void
paint_clouds(Side * side,int x,int y,int r,int cloudtype,int bot,int hgt)2408 paint_clouds(Side *side, int x, int y, int r, int cloudtype, int bot, int hgt)
2409 {
2410     allocate_area_clouds();
2411     /* (should not always do altitudes) */
2412     allocate_area_cloud_altitudes();
2413     tmpside = side;
2414     tmpint = cloudtype;
2415     tmpint2 = bot;
2416     tmpint3 = hgt;
2417     apply_to_area_plus_edge(x, y, r, paint_clouds_1);
2418 }
2419 
2420 static void
paint_clouds_1(int x,int y)2421 paint_clouds_1(int x, int y)
2422 {
2423     int oldcl = raw_cloud_at(x, y);
2424     int oldbot = raw_cloud_bottom_at(x, y);
2425     int oldhgt = raw_cloud_height_at(x, y);
2426     int changed = FALSE;
2427 
2428     if (oldcl != tmpint) {
2429 	set_raw_cloud_at(x, y, tmpint);
2430 	changed = TRUE;
2431     }
2432     if (oldbot != tmpint2) {
2433 	set_raw_cloud_bottom_at(x, y, tmpint2);
2434 	changed = TRUE;
2435     }
2436     if (oldhgt != tmpint3) {
2437 	set_raw_cloud_height_at(x, y, tmpint3);
2438 	changed = TRUE;
2439     }
2440     if (changed)
2441       update_cell_display(tmpside, x, y, UPDATE_ALWAYS | UPDATE_ADJ);
2442 }
2443 
2444 /* Winds painting. */
2445 
2446 void
paint_winds(Side * side,int x,int y,int r,int dir,int force)2447 paint_winds(Side *side, int x, int y, int r, int dir, int force)
2448 {
2449     allocate_area_winds();
2450     tmpside = side;
2451     tmpint = force << 3 | dir;
2452     apply_to_area_plus_edge(x, y, r, paint_winds_1);
2453 }
2454 
2455 static void
paint_winds_1(int x,int y)2456 paint_winds_1(int x, int y)
2457 {
2458     int oldw = raw_wind_at(x, y);
2459 
2460     if (oldw != tmpint) {
2461 	set_raw_wind_at(x, y, tmpint);
2462 	update_cell_display(tmpside, x, y, UPDATE_ALWAYS);
2463     }
2464 }
2465 
2466 /* Scan the elevation layer, putting all values into the ranges
2467    required by terrain types. */
2468 
2469 void
fix_elevations(void)2470 fix_elevations(void)
2471 {
2472     int x, y, t, oldelev, newelev, numfixed;
2473     Side *side;
2474 
2475     if (!elevations_defined())
2476       return;
2477     numfixed = 0;
2478     area.maxelev = area.minelev = elev_at(area.width / 2, area.height / 2);
2479     for_all_interior_cells(x, y) {
2480 	t = terrain_at(x, y);
2481 	oldelev = elev_at(x, y);
2482 	/* Clip desired elevation to what's allowed for the terrain here. */
2483 	newelev = max(t_elev_min(t), min(oldelev, t_elev_max(t)));
2484 	set_elev_at(x, y, newelev);
2485 	/* (should try to share with final_init_world?) */
2486 	if (newelev < area.minelev)
2487 	  area.minelev = newelev;
2488 	if (newelev > area.maxelev)
2489 	  area.maxelev = newelev;
2490 	if (newelev != oldelev)
2491 	  ++numfixed;
2492     }
2493     /* Set edge elevations to be averages of adjacent interior
2494        cells. */
2495     set_edge_terrain(FALSE);
2496     /* Let everybody know what we did. */
2497     notify_all("Fixed %d elevations, range from %d to %d.",
2498 	       numfixed, area.minelev, area.maxelev);
2499     if (numfixed > 0)
2500       for_all_sides(side)
2501 	update_area_display(side);
2502 }
2503 
2504 #endif /* DESIGNERS */
2505 
2506 /* For an advanced unit, toggle its use of the given cell. */
2507 
2508 void
toggle_user_at(Unit * unit,int x,int y)2509 toggle_user_at(Unit *unit, int x, int y)
2510 {
2511     Unit *unit2;
2512     Side *side2;
2513 
2514     /* Return if landuse is undefined. */
2515     if (!user_defined())
2516       return;
2517     /* Return if the cell is not visible to this side. */
2518     if (!terrain_visible(unit->side, x, y))
2519       return;
2520     /* Return if the cell is used by another unit. */
2521     if (user_at(x, y) != NOUSER && user_at(x, y) != unit->id) {
2522 	/* (could be more helpful) */
2523 	notify(unit->side, "Cell at %d,%d is already in use", x, y);
2524 	return;
2525     }
2526     /* Return if using maxcells and we are trying to add one more. */
2527     if (unit->usedcells >= unit->maxcells && user_at(x, y) != unit->id) {
2528 	notify(unit->side, "Cannot use any more cells");
2529 	return;
2530     }
2531     /* Return if independents or untrusted side has a unit in the cell. */
2532     if (unit_at(x, y) != NULL) {
2533 	for_all_stack(x, y, unit2) {
2534 	    if (!trusted_side(unit->side, unit2->side))
2535 	      return;
2536 	}
2537     }
2538     /* Toggle landuse by unit either on or off for the cell. */
2539     if (user_at(x, y) == NOUSER) {
2540 	set_user_at(x, y, unit->id);
2541 	unit->usedcells += 1;
2542     } else if (user_at(x, y) == unit->id) {
2543 	set_user_at(x, y, NOUSER);
2544 	unit->usedcells -= 1;
2545     }
2546     for_all_sides(side2) {
2547 	if (side2->see_all
2548 	    || side_sees_unit(side2, unit)
2549 	    || side_tracking_unit(side2, unit)) {
2550 	    update_cell_display(side2, x, y, UPDATE_ALWAYS);
2551 	}
2552     }
2553 }
2554