1 /* $Id: wildmap.c,v 5.2 2001/05/28 17:47:16 bertg Exp $
2 *
3 * Wildmap, a random map generator for XPilot. Copyright (C) 1993-2001 by
4 *
5 * Bj�rn Stabell <bjoern@xpilot.org>
6 * Ken Ronny Schouten <ken@xpilot.org>
7 * Bert Gijsbers <bert@xpilot.org>
8 *
9 * This program is free software; you can redistribute it and/or modify
10 * it under the terms of the GNU General Public License as published by
11 * the Free Software Foundation; either version 2 of the License, or
12 * (at your option) any later version.
13 *
14 * This program is distributed in the hope that it will be useful,
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 * GNU General Public License for more details.
18 *
19 * You should have received a copy of the GNU General Public License
20 * along with this program; if not, write to the Free Software
21 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
22 */
23
24 #include <stdlib.h>
25 #include <stdio.h>
26 #include <errno.h>
27 #include <limits.h>
28 #include <time.h>
29 #include <string.h>
30
31 #ifndef _WINDOWS
32 # include <unistd.h>
33 #endif
34
35
36
37 #define NELEM(a) (sizeof(a) / sizeof(a[0]))
38
39 #define FUZZ_MASK 0xFFFFFFFFU
40 #define MAX_FUZZ FUZZ_MASK
41
42 #define MAPOFFLEFT(i) (((i) >= 1) ? (i) - 1 : map.datasize - 1)
43 #define MAPOFFRIGHT(i) (((i) + 1 < map.datasize) ? (i) + 1 : 0)
44 #define MAPOFFUP(i) (((i) >= map.linewidth) \
45 ? (i) - map.linewidth \
46 : (i) - map.linewidth + map.datasize)
47 #define MAPOFFDOWN(i) (((i) + map.linewidth < map.datasize) \
48 ? (i) + map.linewidth \
49 : (i) + map.linewidth - map.datasize)
50 #define MAPLEFT(i) map.data[MAPOFFLEFT(i)]
51 #define MAPRIGHT(i) map.data[MAPOFFRIGHT(i)]
52 #define MAPUP(i) map.data[MAPOFFUP(i)]
53 #define MAPDOWN(i) map.data[MAPOFFDOWN(i)]
54
55 #ifndef MAX_MAP_SIZE
56 #define MAX_MAP_SIZE 900
57 #endif
58
59 #define BLOCK_SPACE ' '
60 #define BLOCK_SOLID 'x'
61 #define BLOCK_UP_RIGHT 'a'
62 #define BLOCK_UP_LEFT 's'
63 #define BLOCK_DOWN_LEFT 'w'
64 #define BLOCK_DOWN_RIGHT 'q'
65 #define BLOCK_CANNON_RIGHT 'd'
66 #define BLOCK_CANNON_DOWN 'r'
67 #define BLOCK_CANNON_LEFT 'f'
68 #define BLOCK_CANNON_UP 'c'
69 #define BLOCK_FUEL '#'
70 #define BLOCK_GRAV_POS '+'
71 #define BLOCK_GRAV_NEG '-'
72 #define BLOCK_GRAV_CLOCK '>'
73 #define BLOCK_GRAV_ANTI_CLOCK '<'
74 #define BLOCK_WORM_BOTH '@'
75 #define BLOCK_WORM_IN '('
76 #define BLOCK_WORM_OUT ')'
77
78 struct map {
79 unsigned seed,
80 fuzz_word;
81 char *data;
82 double fill_ratio,
83 seed_ratio,
84 cannon_ratio,
85 fuel_ratio,
86 grav_ratio,
87 worm_ratio;
88 int width,
89 height,
90 linewidth,
91 datasize,
92 num_bases,
93 num_teams,
94 flood_marker,
95 flood_trigger,
96 flood_count[256];
97 };
98
99 static struct map map;
100
fuzz(void)101 static unsigned fuzz(void)
102 {
103 /*
104 * Implement a private pseudo-random generator to be able
105 * to regenerate the same map from the same seed on
106 * different architectures.
107 * It assumes an unsigned int with at least 32 bits (as I do always).
108 * The magic constant used below is from Sedgewick's Algorithms.
109 * Note that the low order digits are not random at all :(.
110 */
111 map.fuzz_word = (map.fuzz_word * 31415821 + 1) & FUZZ_MASK;
112
113 return map.fuzz_word;
114 }
115
fuzz_bound(unsigned max)116 static unsigned fuzz_bound(unsigned max)
117 {
118 /*
119 * Return a pseudo-random unsigned integer
120 * in the range: [0-max] inclusive.
121 */
122 return (unsigned)(((double) fuzz() * (double) max) / (double) MAX_FUZZ);
123 }
124
Default_map(void)125 static void Default_map(void)
126 {
127 map.width = 100;
128 map.height = 100;
129 map.seed = (unsigned)getpid() ^ (unsigned)time(NULL) * (unsigned)getppid();
130 map.seed_ratio = 0.16;
131 map.fill_ratio = 0.20;
132 map.num_bases = 26;
133 map.num_teams = 3;
134 map.cannon_ratio = 0.0020;
135 map.fuel_ratio = 0.0006;
136 map.grav_ratio = 0.0006;
137 map.worm_ratio = 0.0004;
138 }
139
Option_map(int argc,char ** argv)140 static void Option_map(int argc, char **argv)
141 {
142 struct map_opt {
143 char *name;
144 int *intp;
145 unsigned *unsp;
146 double *dblp;
147 double min;
148 double max;
149 };
150 static struct map_opt mapopts[] = {
151 { "mapWidth", &map.width, 0, 0, 90, MAX_MAP_SIZE },
152 { "mapHeight", &map.height, 0, 0, 90, MAX_MAP_SIZE },
153 { "seed", 0, &map.seed, 0, 0, MAX_FUZZ },
154 { "seedRatio", 0, 0, &map.seed_ratio, 0.02, 0.22 },
155 { "fillRatio", 0, 0, &map.fill_ratio, 0.02, 0.80 },
156 { "numBases", &map.num_bases, 0, 0, 2, 50 },
157 { "numTeams", &map.num_teams, 0, 0, 3, 10 },
158 { "cannonRatio", 0, 0, &map.cannon_ratio, 0.0, 0.2 },
159 { "fuelRatio", 0, 0, &map.fuel_ratio, 0.0, 0.1 },
160 { "gravRatio", 0, 0, &map.grav_ratio, 0.0, 0.1 },
161 { "wormRatio", 0, 0, &map.worm_ratio, 0.0, 0.1 }
162 };
163 int i,
164 j,
165 intval;
166 unsigned unsval;
167 char *opt,
168 *arg = NULL;
169 double dblval;
170
171 for (i = 1; i < argc; i += 2) {
172 opt = argv[i];
173 arg = NULL;
174 if (*opt != '-') {
175 break;
176 }
177 for (j = 0; j < NELEM(mapopts); j++) {
178 if (strcmp(&opt[1], mapopts[j].name) == 0) {
179 break;
180 }
181 }
182 if (j == NELEM(mapopts)) {
183 break;
184 }
185 if (i + 1 == argc) {
186 break;
187 }
188 arg = argv[i + 1];
189 if (mapopts[j].intp) {
190 if (sscanf(arg, "%d", &intval) != 1) {
191 break;
192 }
193 if (intval < mapopts[j].min || intval > mapopts[j].max) {
194 break;
195 }
196 *mapopts[j].intp = intval;
197 }
198 else if (mapopts[j].unsp) {
199 if (sscanf(arg, "%u", &unsval) != 1) {
200 break;
201 }
202 if (unsval < mapopts[j].min || unsval > mapopts[j].max) {
203 break;
204 }
205 *mapopts[j].unsp = unsval;
206 }
207 else if (mapopts[j].dblp) {
208 if (sscanf(arg, "%lf", &dblval) != 1) {
209 break;
210 }
211 if (dblval < mapopts[j].min || dblval > mapopts[j].max) {
212 break;
213 }
214 *mapopts[j].dblp = dblval;
215 }
216 }
217 if (i < argc) {
218 if (strcmp(opt, "-help")) {
219 fprintf(stderr, "Invalid option: %s %s\n", opt, arg ? arg : "");
220 }
221 fprintf(stderr, "Usage: %s [-option value] ...\n", *argv);
222 fprintf(stderr, "Where options include:\n");
223 for (i = 0; i < NELEM(mapopts); i++) {
224 fprintf(stderr, " -%-11s <value>\t", mapopts[i].name);
225 if (mapopts[i].intp) {
226 fprintf(stderr, "(= %d, min: %d, max: %d)",
227 (int)*mapopts[i].intp,
228 (int)mapopts[i].min, (int)mapopts[i].max);
229 }
230 else if (mapopts[i].unsp) {
231 fprintf(stderr, "(= %u, min: %u, max: %u)",
232 (unsigned)*mapopts[i].unsp,
233 (unsigned)mapopts[i].min, (unsigned)mapopts[i].max);
234 } else {
235 fprintf(stderr, "(= %-6.4f, min: %-6.4f, max: %-6.4f)",
236 (double)*mapopts[i].dblp,
237 (double)mapopts[i].min, (double)mapopts[i].max);
238 }
239 fprintf(stderr, "\n");
240 }
241 fprintf(stderr,
242 "SeedRatio is the chance that a map object starts as solid instead of empty.\n"
243 "FillRatio is the amount of wall space divided by the total map size.\n"
244 "Seed is the seed for the random number generator and determines the map\n"
245 "layout uniquely given the values for seedRatio, fillRatio and the map size.\n"
246 "To get thick walls increase seedRatio.\n"
247 "For maps with lots of space to fly in decrease fillRatio.\n"
248 "\n");
249 exit(1);
250 }
251 }
252
Alloc_map(void)253 static void Alloc_map(void)
254 {
255 /*
256 * Allocate the map data.
257 * The (0, 0) coordinate is in the top left corner.
258 * An extra column is appended at the far right, which
259 * will later be turned into newlines for easy printing.
260 */
261 map.fuzz_word = map.seed;
262 map.linewidth = map.width + 1;
263 map.datasize = map.linewidth * map.height;
264 map.data = (char *) malloc(map.datasize + 1);
265 if (!map.data) {
266 printf("no mem\n");
267 exit(1);
268 }
269 }
270
Flood_map(int i)271 static void Flood_map(int i)
272 {
273 /*
274 * Connect all adjacent (up, down, left, right) map objects,
275 * which have the same type as map.flood_trigger.
276 * The map objects will be marked with value map.flood_marker,
277 * to distinguish them from map objects which already have
278 * been processed.
279 */
280
281 #define INTARR_SIZE 1024
282
283 struct int_arr {
284 struct int_arr *next;
285 int n;
286 int arr[INTARR_SIZE];
287 };
288
289 struct int_arr intarr, *putp = &intarr, *getp, *tmpp;
290 int k, j;
291
292 if (map.data[i] != map.flood_trigger) {
293 return;
294 }
295 map.data[i] = map.flood_marker;
296 putp->next = NULL;
297 putp->n = 1;
298 putp->arr[0] = i;
299
300 for (getp = &intarr; getp != NULL; getp = tmpp) {
301
302 while (getp->n > 0) {
303 k = getp->arr[--getp->n];
304 if (putp->n + 4 > INTARR_SIZE) {
305 if ((putp->next = (struct int_arr *)
306 malloc(sizeof(struct int_arr))) == NULL) {
307 fprintf(stderr, "No mem\n");
308 exit(1);
309 }
310 putp = putp->next;
311 putp->next = NULL;
312 putp->n = 0;
313 }
314 j = MAPOFFUP(k);
315 if (map.data[j] == map.flood_trigger) {
316 map.data[j] = map.flood_marker;
317 putp->arr[putp->n++] = j;
318 }
319 j = MAPOFFLEFT(k);
320 if (map.data[j] == map.flood_trigger) {
321 map.data[j] = map.flood_marker;
322 putp->arr[putp->n++] = j;
323 }
324 j = MAPOFFDOWN(k);
325 if (map.data[j] == map.flood_trigger) {
326 map.data[j] = map.flood_marker;
327 putp->arr[putp->n++] = j;
328 }
329 j = MAPOFFRIGHT(k);
330 if (map.data[j] == map.flood_trigger) {
331 map.data[j] = map.flood_marker;
332 putp->arr[putp->n++] = j;
333 }
334 }
335 tmpp = getp->next;
336 if (getp != &intarr) {
337 free(getp);
338 }
339 }
340 }
341
Generate_map(void)342 static void Generate_map(void)
343 {
344 /*
345 * Initialize the map with noise.
346 * Later the noise is either removed or connected,
347 * depending upon the outcome of a randomizer.
348 */
349
350 int todo, i;
351 unsigned edge;
352
353 map.flood_trigger = 1;
354 map.flood_marker = 2;
355
356 edge = MAX_FUZZ * map.seed_ratio;
357 for (todo = map.datasize; todo--; ) {
358 map.data[todo] = (fuzz() < edge);
359 }
360
361 edge = (MAX_FUZZ / map.datasize);
362 for (todo = map.datasize; todo--; ) {
363 i = fuzz_bound(map.datasize - 1);
364 if (map.data[i] == 0) {
365 if (MAPUP(i) == 1) MAPUP(i) = 0;
366 if (MAPLEFT(i) == 1) MAPLEFT(i) = 0;
367 if (MAPDOWN(i) == 1) MAPDOWN(i) = 0;
368 if (MAPRIGHT(i) == 1) MAPRIGHT(i) = 0;
369 }
370 else {
371 if (map.data[i] == 0) {
372 map.data[i] = 1;
373 Flood_map(i);
374 map.data[i] = 1;
375 }
376 else if (map.data[i] == 1) {
377 Flood_map(i);
378 if (MAPUP(i) == 0) {
379 MAPUP(i) = 1;
380 Flood_map(MAPOFFUP(i));
381 MAPUP(i) = 1;
382 }
383 if (MAPLEFT(i) == 0) {
384 MAPLEFT(i) = 1;
385 Flood_map(MAPOFFLEFT(i));
386 MAPLEFT(i) = 1;
387 }
388 if (MAPDOWN(i) == 0) {
389 MAPDOWN(i) = 1;
390 Flood_map(MAPOFFDOWN(i));
391 MAPDOWN(i) = 1;
392 }
393 if (MAPRIGHT(i) == 0) {
394 MAPRIGHT(i) = 1;
395 Flood_map(MAPOFFRIGHT(i));
396 MAPRIGHT(i) = 1;
397 }
398 }
399 }
400 }
401 }
402
Connect_map(void)403 static void Connect_map(void)
404 {
405 /*
406 * Connect small constructs to another if they are very close
407 * to one another (1 or only 2 blocks apart).
408 */
409
410 char *p0, *p1, *p2, *p3, *p4, *p5, *p6, *p7, *p8, *p9, *pa;
411 char *maxp;
412 int n;
413
414 maxp = &map.data[map.datasize];
415
416 do {
417 n = 0;
418
419 p0 = &map.data[map.datasize];
420 p1 = p0 - 1;
421 p2 = p0 - 2;
422 p3 = p0 - 3;
423 p4 = p0 - map.linewidth;
424 p5 = p4 - 1;
425 p6 = p4 - 2;
426 p7 = p4 - map.linewidth;
427 p8 = p7 - 1;
428 p9 = p7 - 2;
429 pa = p7 - map.linewidth;
430 p0 = map.data;
431
432 while (p0 < maxp) {
433 if (*p0) {
434 if (!*p1) {
435 if (*p2) {
436 *p1 = *p0;
437 n++;
438 }
439 else if (*p3) {
440 *p2 = *p1 = *p0;
441 n++;
442 }
443 }
444 if (!*p4) {
445 if (*p7) {
446 *p4 = *p0;
447 n++;
448 }
449 else if (*pa) {
450 *p7 = *p4 = *p0;
451 n++;
452 }
453 }
454 if (*p5) {
455 if (!*p1 && !*p4) {
456 *p4 = *p1 = *p0;
457 n++;
458 }
459 }
460 } else {
461 if (!*p5 && *p1 && *p4) {
462 *p0 = *p5 = *p1;
463 n++;
464 }
465 }
466 if (!*p5) {
467 if ((*p0 || (*p1 && *p4)) && *p9) {
468 *p5 = *p0;
469 n++;
470 }
471 else if (*p6 && *p8 && *p0) {
472 *p5 = *p0;
473 n++;
474 }
475 else if (*p2 && (*p7 || (*p4 && *p8))) {
476 *p5 = *p2;
477 n++;
478 }
479 else if (*p7 && *p1 && *p6) {
480 *p5 = *p7;
481 n++;
482 }
483 else if (!*p0 && !*p1 && *p2
484 && !*p4 && *p6
485 && *p7 && *p8 && *p9) {
486 *p5 = *p9;
487 n++;
488 }
489 else if (*p0 && !*p1 && !*p2
490 && *p4 && !*p6
491 && *p7 && *p8 && *p9) {
492 *p5 = *p7;
493 n++;
494 }
495 else if (*p0 && *p1 && *p2
496 && *p4 && !*p6
497 && *p7 && !*p8 && !*p9) {
498 *p5 = *p0;
499 n++;
500 }
501 else if (*p0 && *p1 && *p2
502 && !*p4 && *p6
503 && !*p7 && !*p8 && *p9) {
504 *p5 = *p0;
505 n++;
506 }
507 else if (*p0 && !*p1 && !*p2
508 && !*p4 && !*p6
509 && !*p7 && *p8 && !*p9) {
510 *p5 = *p8;
511 n++;
512 }
513 else if (!*p0 && !*p1 && *p2
514 && !*p4 && !*p6
515 && !*p7 && *p8 && !*p9) {
516 *p5 = *p8;
517 n++;
518 }
519 else if (*p0 && !*p1 && !*p2
520 && !*p4 && *p6
521 && !*p7 && !*p8 && !*p9) {
522 *p5 = *p6;
523 n++;
524 }
525 else if (!*p0 && !*p1 && !*p2
526 && !*p4 && *p6
527 && *p7 && !*p8 && !*p9) {
528 *p5 = *p6;
529 n++;
530 }
531 else if (!*p0 && *p1 && !*p2
532 && !*p4 && !*p6
533 && !*p7 && !*p8 && *p9) {
534 *p5 = *p1;
535 n++;
536 }
537 else if (!*p0 && *p1 && !*p2
538 && !*p4 && !*p6
539 && *p7 && !*p8 && !*p9) {
540 *p5 = *p1;
541 n++;
542 }
543 else if (!*p0 && !*p1 && !*p2
544 && *p4 && !*p6
545 && !*p7 && !*p8 && *p9) {
546 *p5 = *p4;
547 n++;
548 }
549 else if (!*p0 && !*p1 && *p2
550 && *p4 && !*p6
551 && !*p7 && !*p8 && !*p9) {
552 *p5 = *p4;
553 n++;
554 }
555 }
556 p3 = p2;
557 p2 = p1;
558 p1 = p0;
559 p0++;
560 p6 = p5;
561 p5 = p4;
562 if (++p4 >= maxp) {
563 p4 = map.data;
564 }
565 p9 = p8;
566 p8 = p7;
567 if (++p7 >= maxp) {
568 p7 = map.data;
569 }
570 if (++pa >= maxp) {
571 pa = map.data;
572 }
573 }
574
575 } while (n > 0);
576 }
577
Count_labels(void)578 static void Count_labels(void)
579 {
580 /*
581 * For each possible map value count the number of occurences.
582 */
583
584 int todo;
585
586 memset(map.flood_count, 0, sizeof map.flood_count);
587
588 for (todo = map.datasize; todo--; ) {
589 map.flood_count[(unsigned char) map.data[todo]]++;
590 }
591 }
592
Sort_labels(int tbl[256])593 static void Sort_labels(int tbl[256])
594 {
595 /*
596 * Sort the map to have big map constructs with low map values
597 * close to zero and small map constructs with high map values.
598 */
599
600 int i, j, n;
601
602 Count_labels();
603
604 memset(tbl, 0, sizeof(int *) * 256);
605
606 tbl[0] = 0;
607 tbl[1] = 1;
608 n = 2;
609 for (i = 2; i < 256; i++) {
610 for (j = n; j > 2; j--) {
611 if (map.flood_count[i] > map.flood_count[tbl[j - 1]]) {
612 tbl[j] = tbl[j - 1];
613 } else {
614 break;
615 }
616 }
617 tbl[j] = i;
618 n++;
619 }
620 }
621
Label_map(int label)622 static void Label_map(int label)
623 {
624 /*
625 * Give each map construct an unique value depending on how
626 * big it is. It is OK to delete small constructs if we are
627 * running out of label values.
628 */
629
630 int todo,
631 i,
632 tbl[256],
633 del[256];
634
635 memset(tbl, 0, sizeof tbl);
636 tbl[label] = 1;
637 for (todo = map.datasize; todo--; ) {
638 map.data[todo] = tbl[(unsigned char)map.data[todo]];
639 }
640
641 map.flood_trigger = 1;
642 map.flood_marker = 2;
643
644 for (todo = map.datasize; todo--; ) {
645 if (map.data[todo] == map.flood_trigger) {
646 if (map.flood_marker >= 256) {
647 Sort_labels(tbl);
648 for (i = 0; i < 224; i++) {
649 del[tbl[i]] = i;
650 }
651 for (i = 224; i < 256; i++) {
652 del[tbl[i]] = 0;
653 }
654 for (i = map.datasize; i--; ) {
655 map.data[i] = del[(unsigned char)map.data[i]];
656 }
657 map.flood_marker = 224;
658 }
659 Flood_map(todo);
660 map.flood_marker++;
661 }
662 }
663 }
664
Partition_map(void)665 static void Partition_map(void)
666 {
667 /*
668 * Remove all the inaccessible holes from the map.
669 * And remove enough small map constructs to meet our fillRatio.
670 */
671
672 int todo,
673 i,
674 j,
675 marker,
676 count,
677 excess,
678 tbl[256],
679 del[256];
680
681 Label_map(0);
682 Count_labels();
683 marker = 0;
684 for (i = 2; i < 256; i++) {
685 if (map.flood_count[i] > map.flood_count[marker]) {
686 marker = i;
687 }
688 }
689 memset(tbl, 0, sizeof tbl);
690 tbl[marker] = 1;
691 for (todo = map.datasize; todo--; ) {
692 map.data[todo] = tbl[(unsigned char)map.data[todo]];
693 }
694
695 Label_map(0);
696 Sort_labels(tbl);
697 for (i = 0; i < 256; i++) {
698 del[tbl[i]] = tbl[i];
699 }
700 count = 0;
701 excess = map.datasize - map.flood_count[0]
702 - (int)(map.fill_ratio * map.datasize + 0.5);
703 for (i = 256; i-- > 2; ) {
704 if (excess < count) {
705 break;
706 }
707 count += map.flood_count[tbl[i]];
708 }
709 if (++i < 256) {
710 for (j = i + 1; j < 256; j++) {
711 if (count - map.flood_count[tbl[j]] > excess) {
712 if (2 * map.flood_count[tbl[j]] >= map.flood_count[tbl[i]]) {
713 continue;
714 }
715 }
716 del[tbl[j]] = 0;
717 }
718 del[tbl[i]] = 0;
719 for (todo = map.datasize; todo--; ) {
720 map.data[todo] = del[(unsigned char)map.data[todo]];
721 }
722 }
723 }
724
Smooth_map(void)725 static void Smooth_map(void)
726 {
727 /*
728 * Round all sharp edges and corners.
729 */
730
731 char *p0, *p1, *p2, *p3, *p4, *p5, *p6, *p7, *p8;
732 char *maxp;
733 int todo, n;
734
735 for (todo = map.datasize; todo--; ) {
736 map.data[todo] = (map.data[todo] ? BLOCK_SOLID : BLOCK_SPACE);
737 }
738
739 maxp = &map.data[map.datasize];
740
741 do {
742 n = 0;
743
744 p0 = &map.data[map.datasize];
745 p1 = p0 - 1;
746 p2 = p0 - 2;
747 p3 = p0 - map.linewidth;
748 p4 = p3 - 1;
749 p5 = p4 - 2;
750 p6 = p3 - map.linewidth;
751 p7 = p6 - 1;
752 p8 = p7 - 2;
753 p0 = map.data;
754
755 while (p0 < maxp) {
756
757 if (*p4 == BLOCK_SPACE || *p4 == BLOCK_SOLID) {
758 if (*p0 == BLOCK_SOLID && *p1 == BLOCK_SOLID
759 && *p3 == BLOCK_SOLID && *p5 == BLOCK_SPACE
760 && *p7 == BLOCK_SPACE && *p8 == BLOCK_SPACE) {
761 *p4 = BLOCK_DOWN_RIGHT;
762 n++;
763 }
764 else if (*p1 == BLOCK_SOLID && *p2 == BLOCK_SOLID
765 && *p3 == BLOCK_SPACE && *p5 == BLOCK_SOLID
766 && *p6 == BLOCK_SPACE && *p7 == BLOCK_SPACE) {
767 *p4 = BLOCK_DOWN_LEFT;
768 n++;
769 }
770 else if (*p0 == BLOCK_SPACE && *p1 == BLOCK_SPACE
771 && *p3 == BLOCK_SPACE && *p5 == BLOCK_SOLID
772 && *p7 == BLOCK_SOLID && *p8 == BLOCK_SOLID) {
773 *p4 = BLOCK_UP_LEFT;
774 n++;
775 }
776 else if (*p1 == BLOCK_SPACE && *p2 == BLOCK_SPACE
777 && *p3 == BLOCK_SOLID && *p5 == BLOCK_SPACE
778 && *p6 == BLOCK_SOLID && *p7 == BLOCK_SOLID) {
779 *p4 = BLOCK_UP_RIGHT;
780 n++;
781 }
782 else if (*p4 == BLOCK_SOLID) {
783 if (*p5 == BLOCK_SPACE && *p8 == BLOCK_SPACE
784 && *p7 == BLOCK_SPACE
785 && *p6 == BLOCK_SPACE && *p3 == BLOCK_SPACE) {
786 if (*p2 != BLOCK_SOLID && *p0 != BLOCK_SOLID) {
787 *p4 = BLOCK_SPACE;
788 n++;
789 }
790 }
791 else if (*p7 == BLOCK_SPACE && *p6 == BLOCK_SPACE
792 && *p3 == BLOCK_SPACE
793 && *p0 == BLOCK_SPACE && *p1 == BLOCK_SPACE) {
794 if (*p8 != BLOCK_SOLID && *p2 != BLOCK_SOLID) {
795 *p4 = BLOCK_SPACE;
796 n++;
797 }
798 }
799 else if (*p3 == BLOCK_SPACE && *p0 == BLOCK_SPACE
800 && *p1 == BLOCK_SPACE
801 && *p2 == BLOCK_SPACE && *p5 == BLOCK_SPACE) {
802 if (*p6 != BLOCK_SOLID && *p8 != BLOCK_SOLID) {
803 *p4 = BLOCK_SPACE;
804 n++;
805 }
806 }
807 else if (*p1 == BLOCK_SPACE && *p2 == BLOCK_SPACE
808 && *p5 == BLOCK_SPACE
809 && *p8 == BLOCK_SPACE && *p7 == BLOCK_SPACE) {
810 if (*p0 != BLOCK_SOLID && *p6 != BLOCK_SOLID) {
811 *p4 = BLOCK_SPACE;
812 n++;
813 }
814 }
815 }
816 }
817
818 p2 = p1;
819 p1 = p0;
820 p0++;
821 p5 = p4;
822 p4 = p3;
823 if (++p3 >= maxp) {
824 p3 = map.data;
825 }
826 p8 = p7;
827 p7 = p6;
828 if (++p6 >= maxp) {
829 p6 = map.data;
830 }
831 }
832
833 } while (n > 0);
834 }
835
Decorate_map(void)836 static void Decorate_map(void)
837 {
838 /*
839 * Add the cannons, fuelstations, homebases,
840 * wormholes and gravity objects.
841 * A homebase should be free from influence from gravity objects.
842 */
843
844 struct xy {
845 int x,
846 y;
847 };
848
849 int margin,
850 h,
851 i,
852 hori,
853 vert,
854 off,
855 x,
856 y,
857 base,
858 cannon,
859 num_cannons,
860 grav,
861 num_gravs,
862 fuel,
863 num_fuels,
864 worm,
865 num_worms,
866 type,
867 wall_offset,
868 team,
869 tries;
870 struct xy *home;
871 unsigned size;
872
873 size = map.num_bases * sizeof(struct xy);
874 if ((home = (struct xy *) malloc(size)) == NULL) {
875 fprintf(stderr, "No mem\n");
876 exit(1);
877 }
878 margin = 2;
879 if (map.num_teams > map.num_bases) {
880 map.num_teams = map.num_bases;
881 }
882 team = map.num_teams;
883 for (i = 0; i < map.num_bases; i++) {
884 for (tries = map.datasize; tries; tries--) {
885 x = margin + fuzz_bound(map.width - 2*margin - 1);
886 y = margin + fuzz_bound(map.height - 2*margin - 1);
887 base = x + y * map.linewidth;
888 if (map.data[base] != BLOCK_SPACE) {
889 continue;
890 }
891 if (map.data[base + map.linewidth] != BLOCK_SOLID) {
892 continue;
893 }
894 if (map.data[base - map.linewidth] != BLOCK_SPACE) {
895 continue;
896 }
897 if (map.data[base - 2 * map.linewidth] != BLOCK_SPACE) {
898 continue;
899 }
900 if (map.data[base - 1] != BLOCK_SPACE) {
901 continue;
902 }
903 if (map.data[base + 1] != BLOCK_SPACE) {
904 continue;
905 }
906 if (--team < 0) {
907 team = map.num_teams - 1;
908 }
909 map.data[base] = '0' + team;
910 home[i].x = x;
911 home[i].y = y;
912 break;
913 }
914 if (tries == 0) {
915 break;
916 }
917 }
918
919 num_cannons = map.cannon_ratio * map.datasize;
920 margin = 1;
921 for (i = 0; i < num_cannons; i++) {
922 switch (fuzz_bound(3)) {
923 case 0:
924 type = BLOCK_CANNON_RIGHT;
925 wall_offset = 1;
926 break;
927 case 1:
928 type = BLOCK_CANNON_DOWN;
929 wall_offset = map.linewidth;
930 break;
931 case 2:
932 type = BLOCK_CANNON_LEFT;
933 wall_offset = -1;
934 break;
935 default:
936 type = BLOCK_CANNON_UP;
937 wall_offset = -map.linewidth;
938 break;
939 }
940 for (tries = map.datasize; tries; tries--) {
941 x = margin + fuzz_bound(map.width - 2*margin - 1);
942 y = margin + fuzz_bound(map.height - 2*margin - 1);
943 cannon = x + y * map.linewidth;
944 if (map.data[cannon] != BLOCK_SPACE) {
945 continue;
946 }
947 if (map.data[cannon + wall_offset] == BLOCK_SPACE) {
948 continue;
949 }
950 if (map.data[cannon + wall_offset] != BLOCK_SOLID) {
951 switch (type) {
952 case BLOCK_CANNON_RIGHT:
953 if (map.data[cannon + wall_offset] != BLOCK_UP_LEFT &&
954 map.data[cannon + wall_offset] != BLOCK_DOWN_LEFT) {
955 continue;
956 }
957 break;
958 case BLOCK_CANNON_DOWN:
959 if (map.data[cannon + wall_offset] != BLOCK_UP_LEFT &&
960 map.data[cannon + wall_offset] != BLOCK_UP_RIGHT) {
961 continue;
962 }
963 break;
964 case BLOCK_CANNON_LEFT:
965 if (map.data[cannon + wall_offset] != BLOCK_UP_RIGHT &&
966 map.data[cannon + wall_offset] != BLOCK_DOWN_RIGHT) {
967 continue;
968 }
969 break;
970 default:
971 if (map.data[cannon + wall_offset] != BLOCK_DOWN_LEFT &&
972 map.data[cannon + wall_offset] != BLOCK_DOWN_LEFT) {
973 continue;
974 }
975 break;
976 }
977 }
978 for (h = 0; h < map.num_bases; h++) {
979 if (((x < home[h].x)
980 ? (x + margin < home[h].x)
981 : (x - margin > home[h].x))
982 && ((y < home[h].y)
983 ? (y + margin < home[h].y)
984 : (y - margin > home[h].y))) {
985 continue;
986 }
987 break;
988 }
989 if (h < map.num_bases) {
990 continue;
991 }
992 map.data[cannon] = type;
993 break;
994 }
995 if (tries == 0) {
996 break;
997 }
998 }
999
1000 num_fuels = map.fuel_ratio * map.datasize;
1001 margin = 1;
1002 for (i = 0; i < num_fuels; i++) {
1003 for (tries = map.datasize; tries; tries--) {
1004 x = margin + fuzz_bound(map.width - 2*margin - 1);
1005 y = margin + fuzz_bound(map.height - 2*margin - 1);
1006 fuel = x + y * map.linewidth;
1007 if (map.data[fuel] != BLOCK_SOLID) {
1008 continue;
1009 }
1010 if (map.data[fuel + 1] != BLOCK_SPACE &&
1011 map.data[fuel - 1] != BLOCK_SPACE &&
1012 map.data[fuel + map.linewidth] != BLOCK_SPACE &&
1013 map.data[fuel - map.linewidth] != BLOCK_SPACE) {
1014 continue;
1015 }
1016 map.data[fuel] = BLOCK_FUEL;
1017 break;
1018 }
1019 if (tries == 0) {
1020 break;
1021 }
1022 }
1023
1024 margin = 11;
1025 num_gravs = map.grav_ratio * map.datasize;
1026 for (i = 0; i < num_gravs; i++) {
1027 switch (fuzz_bound(3)) {
1028 case 0:
1029 type = BLOCK_GRAV_POS;
1030 break;
1031 case 1:
1032 type = BLOCK_GRAV_NEG;
1033 break;
1034 case 2:
1035 type = BLOCK_GRAV_CLOCK;
1036 break;
1037 default:
1038 type = BLOCK_GRAV_ANTI_CLOCK;
1039 break;
1040 }
1041 for (tries = map.datasize; tries; tries--) {
1042 x = margin + fuzz_bound(map.width - 2*margin - 1);
1043 y = margin + fuzz_bound(map.height - 2*margin - 1);
1044 grav = x + y * map.linewidth;
1045 if (map.data[grav] != BLOCK_SPACE ||
1046 map.data[grav + 1] != BLOCK_SPACE ||
1047 map.data[grav - 1] != BLOCK_SPACE ||
1048 map.data[grav + map.linewidth] != BLOCK_SPACE ||
1049 map.data[grav - map.linewidth] != BLOCK_SPACE ||
1050 map.data[grav + map.linewidth + 1] != BLOCK_SPACE ||
1051 map.data[grav - map.linewidth + 1] != BLOCK_SPACE ||
1052 map.data[grav + map.linewidth - 1] != BLOCK_SPACE ||
1053 map.data[grav - map.linewidth - 1] != BLOCK_SPACE) {
1054 continue;
1055 }
1056
1057 for (h = 0; h < map.num_bases; h++) {
1058 if ((x < home[h].x)
1059 ? (x + margin < home[h].x)
1060 : (x - margin > home[h].x)) {
1061 continue;
1062 }
1063 if ((y < home[h].y)
1064 ? (y + margin < home[h].y)
1065 : (y - margin > home[h].y)) {
1066 continue;
1067 }
1068 break;
1069 }
1070 if (h < map.num_bases) {
1071 continue;
1072 }
1073 map.data[grav] = type;
1074 break;
1075 }
1076 if (tries == 0) {
1077 break;
1078 }
1079 }
1080
1081 margin = 3;
1082 num_worms = map.worm_ratio * map.datasize;
1083 for (i = 0; i < num_worms; i++) {
1084 switch (fuzz_bound(3)) {
1085 case 0:
1086 type = BLOCK_WORM_IN;
1087 break;
1088 case 1:
1089 type = BLOCK_WORM_OUT;
1090 break;
1091 default:
1092 type = BLOCK_WORM_BOTH;
1093 break;
1094 }
1095 for (tries = map.datasize; tries; tries--) {
1096 x = margin + fuzz_bound(map.width - 2*margin - 1);
1097 y = margin + fuzz_bound(map.height - 2*margin - 1);
1098 worm = x + y * map.linewidth;
1099 if (map.data[worm] != BLOCK_SPACE) {
1100 continue;
1101 }
1102
1103 for (vert = -margin; vert <= margin; vert++) {
1104 off = x - margin + (y + vert) * map.linewidth;
1105 for (hori = -margin; hori <= margin; hori++, off++) {
1106 switch (map.data[off]) {
1107 case BLOCK_SPACE:
1108 case BLOCK_GRAV_POS:
1109 case BLOCK_GRAV_NEG:
1110 case BLOCK_GRAV_CLOCK:
1111 case BLOCK_GRAV_ANTI_CLOCK:
1112 case BLOCK_WORM_BOTH:
1113 case BLOCK_WORM_IN:
1114 case BLOCK_WORM_OUT:
1115 continue;
1116 default:
1117 break;
1118 }
1119 break;
1120 }
1121 if (hori <= margin) {
1122 break;
1123 }
1124 }
1125 if (vert <= margin) {
1126 continue;
1127 }
1128
1129 for (h = 0; h < map.num_bases; h++) {
1130 if ((x < home[h].x)
1131 ? (x + margin < home[h].x)
1132 : (x - margin > home[h].x)) {
1133 continue;
1134 }
1135 if ((y < home[h].y)
1136 ? (y + margin < home[h].y)
1137 : (y - margin > home[h].y)) {
1138 continue;
1139 }
1140 break;
1141 }
1142 if (h < map.num_bases) {
1143 continue;
1144 }
1145 map.data[worm] = type;
1146 break;
1147 }
1148 if (tries == 0) {
1149 break;
1150 }
1151 }
1152
1153 free(home);
1154 }
1155
Border_map(void)1156 static void Border_map(void)
1157 {
1158 int i;
1159 char *left, *middle, *right;
1160
1161 left = &map.data[map.width - 1];
1162 middle = left + 1;
1163 right = &map.data[0];
1164 for (i = 0; i < map.height; i++) {
1165 *middle = '\n';
1166 if (*right == BLOCK_SOLID) {
1167 if (*left == BLOCK_DOWN_LEFT || *left == BLOCK_UP_LEFT) {
1168 *left = BLOCK_SOLID;
1169 }
1170 }
1171 if (*right == BLOCK_SPACE
1172 || *right == BLOCK_DOWN_RIGHT
1173 || *right == BLOCK_UP_RIGHT) {
1174 if (*left == BLOCK_DOWN_RIGHT || *left == BLOCK_UP_RIGHT) {
1175 *left = BLOCK_SPACE;
1176 }
1177 }
1178 if (*left == BLOCK_SOLID) {
1179 if (*right == BLOCK_DOWN_RIGHT || *right == BLOCK_UP_RIGHT) {
1180 *right = BLOCK_SOLID;
1181 }
1182 }
1183 if (*left == BLOCK_SPACE
1184 || *left == BLOCK_UP_LEFT
1185 || *left == BLOCK_DOWN_LEFT) {
1186 if (*right == BLOCK_DOWN_LEFT || *right == BLOCK_UP_LEFT) {
1187 *right = BLOCK_SPACE;
1188 }
1189 }
1190 left += map.linewidth;
1191 middle += map.linewidth;
1192 right += map.linewidth;
1193 }
1194 map.data[map.datasize] = '\0';
1195 }
1196
Dump_map(void)1197 static void Dump_map(void)
1198 {
1199
1200 printf("mapWidth: %d\n", map.width);
1201 printf("mapHeight: %d\n", map.height);
1202 printf("mapName: Wild Map %u\n", map.seed);
1203 printf("mapAuthor: The Wild Map Generator 1.2\n");
1204 printf("edgeWrap: True\n");
1205 printf("mapData: \\multiline: EndOfMapData\n");
1206 printf("%sEndOfMapData\n", map.data);
1207 }
1208
Picture_map(void)1209 static void Picture_map(void)
1210 {
1211 #ifdef DEVELOPMENT
1212 char name[1024];
1213 FILE *fp;
1214 int x, y;
1215 unsigned char *line;
1216
1217 if (!getenv("WILDMAPDUMP")) {
1218 return;
1219 }
1220
1221 sprintf(name, "wildmap.ppm");
1222 fp = fopen(name, "w");
1223 if (!fp) {
1224 perror(name);
1225 return;
1226 }
1227 line = (unsigned char *)malloc(3 * map.width);
1228 if (!line) {
1229 perror("No memory for wildmap dump");
1230 fclose(fp);
1231 return;
1232 }
1233 fprintf(fp, "P6\n");
1234 fprintf(fp, "%d %d\n", map.width, map.height);
1235 fprintf(fp, "%d\n", 255);
1236 for (y = 0; y < map.height; y++) {
1237 for (x = 0; x < map.width; x++) {
1238 switch (map.data[x + map.linewidth * y]) {
1239 case BLOCK_SPACE:
1240 line[x * 3 + 0] = 0;
1241 line[x * 3 + 1] = 0;
1242 line[x * 3 + 2] = 0;
1243 break;
1244 case BLOCK_SOLID:
1245 line[x * 3 + 0] = 0;
1246 line[x * 3 + 1] = 0;
1247 line[x * 3 + 2] = 255;
1248 break;
1249 case BLOCK_UP_RIGHT:
1250 case BLOCK_UP_LEFT:
1251 case BLOCK_DOWN_LEFT:
1252 case BLOCK_DOWN_RIGHT:
1253 line[x * 3 + 0] = 0;
1254 line[x * 3 + 1] = 0;
1255 line[x * 3 + 2] = 192;
1256 break;
1257 case BLOCK_CANNON_RIGHT:
1258 case BLOCK_CANNON_DOWN:
1259 case BLOCK_CANNON_LEFT:
1260 case BLOCK_CANNON_UP:
1261 line[x * 3 + 0] = 255;
1262 line[x * 3 + 1] = 255;
1263 line[x * 3 + 2] = 255;
1264 break;
1265 case BLOCK_FUEL:
1266 line[x * 3 + 0] = 255;
1267 line[x * 3 + 1] = 0;
1268 line[x * 3 + 2] = 0;
1269 break;
1270 case BLOCK_GRAV_POS:
1271 case BLOCK_GRAV_NEG:
1272 case BLOCK_GRAV_CLOCK:
1273 case BLOCK_GRAV_ANTI_CLOCK:
1274 line[x * 3 + 0] = 192;
1275 line[x * 3 + 1] = 192;
1276 line[x * 3 + 2] = 0;
1277 break;
1278 case BLOCK_WORM_BOTH:
1279 case BLOCK_WORM_IN:
1280 case BLOCK_WORM_OUT:
1281 line[x * 3 + 0] = 0;
1282 line[x * 3 + 1] = 255;
1283 line[x * 3 + 2] = 0;
1284 break;
1285 case '_':
1286 case '0':
1287 case '1':
1288 case '2':
1289 case '3':
1290 case '4':
1291 case '5':
1292 case '6':
1293 case '7':
1294 case '8':
1295 case '9':
1296 line[x * 3 + 0] = 0;
1297 line[x * 3 + 1] = 192;
1298 line[x * 3 + 2] = 192;
1299 break;
1300 default:
1301 break;
1302 }
1303 }
1304 fwrite(line, map.width, 3, fp);
1305 }
1306 free(line);
1307 fclose(fp);
1308
1309 fprintf(stderr, "Wildmap dumped to %s\n", name);
1310 #endif
1311 }
1312
Dealloc_map(void)1313 void Dealloc_map(void)
1314 {
1315 free(map.data);
1316 }
1317
main(int argc,char ** argv)1318 int main(int argc, char **argv)
1319 {
1320 Default_map();
1321 Option_map(argc, argv);
1322 Alloc_map();
1323 Generate_map();
1324 Connect_map();
1325 Partition_map();
1326 Smooth_map();
1327 Decorate_map();
1328 Border_map();
1329 Picture_map();
1330 Dump_map();
1331 Dealloc_map();
1332
1333 return 0;
1334 }
1335