1 /* -*- Mode: C; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
3 * Copyright (c) 2002 by Edwin de Jong <mauddib@gmx.net>.
5 * Permission to use, copy, modify, and distribute this software and its
6 * documentation for any purpose and without fee is hereby granted,
7 * provided that the above copyright notice appear in all copies and that
8 * both that copyright notice and this permission notice appear in
9 * supporting documentation.
11 * This file is provided AS IS with no warranties of any kind. The author
12 * shall have no liability with respect to the infringement of copyrights,
13 * trade secrets or any patents by this file or any part thereof. In no
14 * event will the author be liable for any lost revenue or profits or
15 * other special, indirect and consequential damages.
20 #include "pacman_level.h"
30 #define BLOCK_EMPTY ' '
31 #define BLOCK_DOT_1 '`'
32 #define BLOCK_DOT_2 '.'
33 #define BLOCK_WALL '#'
34 #define BLOCK_GHOST_ONLY '='
35 #define BLOCK_WALL_TL '\''
36 #define BLOCK_WALL_TR '`'
37 #define BLOCK_WALL_BR ','
38 #define BLOCK_WALL_BL '_'
39 #define BLOCK_WALL_HO '-'
40 #define BLOCK_WALL_VE '|'
41 #define BLOCK_DOT_BONUS 'o'
43 /* This is more or less the standard pacman level (without the left-right
45 static const lev_t stdlevel = {
46 "########################################",
47 "########################################",
48 "#######````````````##````````````#######",
49 "#######`####`#####`##`#####`####`#######",
50 "#######`####`#####`##`#####`####`#######",
51 "#######`####`#####`##`#####`####`#######",
52 "#######``````````````````````````#######",
53 "#######`####`##`########`##`####`#######",
54 "#######`####`##`########`##`####`#######",
55 "#######``````##````##````##``````#######",
56 "############`#####`##`#####`############",
57 "############`#####`##`#####`############",
58 "############`##``````````##`############",
59 "############`##`###==###`##`############",
60 "############`##`########`##`############",
61 "############````########````############",
62 "############`##`########`##`############",
63 "############`##`########`##`############",
64 "############`##``````````##`############",
65 "############`##`########`##`############",
66 "############`##`########`##`############",
67 "#######````````````##````````````#######",
68 "#######`####`#####`##`#####`####`#######",
69 "#######`####`#####`##`#####`####`#######",
70 "#######```##````````````````##```#######",
71 "#########`##`##`########`##`##`#########",
72 "#########`##`##`########`##`##`#########",
73 "#######``````##````##````##``````#######",
74 "#######`##########`##`##########`#######",
75 "#######`##########`##`##########`#######",
76 "#######``````````````````````````#######",
77 "########################################"
80 #define TILES_COUNT 11U
83 #define GO_LEFT 0x0002U
84 #define GO_RIGHT 0x0004U
85 #define GO_DOWN 0x0008U
87 static const struct tiles def_tiles[TILES_COUNT] = {
89 * ' ' == dont care == BLOCK_EMPTY
90 * '#' == set wall, and not clear == BLOCK_WALL
91 * '`' == clear == BLOCK_DOT_1
92 * middle position is always set as cleardef
95 " # " " # " " ``` " " # " " # ", {
96 GO_LEFT, GO_RIGHT, 0, 0}, 2,
97 (unsigned) (1 << 0 | 1 << 6 | 1 << 8 | 1 << 10)}, {
98 " " " ` " "##`##" " ` " " ", {
99 GO_UP, GO_DOWN, 0, 0}, 2,
100 (unsigned) (1 << 1 | 1 << 7 | 1 << 9 | 1 << 10)}, {
101 " ##" "##`##" "##`` " "#### " "#### ", {
102 GO_UP, GO_RIGHT, 0, 0}, 2,
103 (unsigned) (1 << 2 | 1 << 6 | 1 << 7 | 1 << 10)}, {
104 "#### " "#### " "##`` " "##`##" " ##", {
105 GO_RIGHT, GO_DOWN, 0, 0}, 2,
106 (unsigned) (1 << 3 | 1 << 7 | 1 << 8 | 1 << 10)}, {
107 " ###" " ###" " ``##" "##` " "## ", {
108 GO_LEFT, GO_DOWN, 0, 0}, 2,
109 (unsigned) (1 << 4 | 1 << 8 | 1 << 9 | 1 << 10)}, {
110 "## " "##`##" " ``##" " ####" " ####", {
111 GO_LEFT, GO_UP, 0, 0}, 2,
112 (unsigned) (1 << 5 | 1 << 6 | 1 << 9 | 1 << 10)}, {
113 "##`##" "##`##" "`````" " ### " " ### ", {
114 GO_LEFT, GO_UP, GO_RIGHT, 0}, 3, (unsigned) 1 << 6}, {
115 " `##" "##`##" "##```" "##`##" " `##", {
116 GO_UP, GO_RIGHT, GO_DOWN, 0}, 3, (unsigned) (1 << 7)}, {
117 " ### " " ### " "`````" "##`##" "##`##", {
118 GO_LEFT, GO_RIGHT, GO_DOWN, 0}, 3, (unsigned) (1 << 8)}, {
119 "##` " "##`##" "```##" "##`##" "##` ", {
120 GO_UP, GO_DOWN, GO_LEFT, 0}, 3, (unsigned) (1 << 9)}, {
121 "##`##" "##`##" "`````" "##`##" "##`##", {
122 GO_UP, GO_DOWN, GO_LEFT, GO_RIGHT}, 4, (unsigned) (1 << 10)}
125 /* probability array for each of the tiles */
126 #define MAXTILEPROB 22
127 static const unsigned tileprob[MAXTILEPROB] =
128 { 0, 0, 0, 1, 1, 2, 3, 4, 5, 6, 6, 6, 7, 7, 8, 8, 8, 9, 9, 10, 10, 10 };
131 static int creatlevelblock (pacmangamestruct *pp,
132 lev_t * level, const unsigned x,
137 { TOP_LEFT, TOP_RIGHT, BOTTOM_LEFT, BOTTOM_RIGHT };
139 /* Sets a block in the level to a certain state. */
141 setblockto (lev_t * level, const unsigned x, const unsigned y, const char c)
143 if (!(x < LEVWIDTH && y < LEVHEIGHT))
148 /* check if a block is set */
150 checkset (lev_t * level, const unsigned x, const unsigned y)
152 if (!(x < LEVWIDTH && y < LEVHEIGHT) ||
153 (*level)[y][x] == BLOCK_WALL || (*level)[y][x] == BLOCK_GHOST_ONLY)
158 /* Check if a block is not set */
160 checksetout (lev_t * level, const unsigned x, const unsigned y)
162 if (!(x < LEVWIDTH && y < LEVHEIGHT) || checkset (level, x, y) != 0)
168 /* Check if a block cannot be set */
170 checkunsetdef (lev_t * level, const unsigned x, const unsigned y)
172 if (!(x < LEVWIDTH && y < LEVHEIGHT))
174 if ((*level)[y][x] == BLOCK_DOT_1)
179 /* Initializes a level to empty state. */
181 clearlevel (lev_t * level)
185 for (y = 0; y < LEVHEIGHT; y++)
186 for (x = 0; x < LEVWIDTH; x++)
187 (*level)[y][x] = BLOCK_EMPTY;
190 /* Changes a level from the level creation structure ((array to array) to
193 copylevel (char *dest, lev_t * level)
197 for (y = 0; y < LEVHEIGHT; y++)
198 for (x = 0; x < LEVWIDTH; x++)
199 dest[y * LEVWIDTH + x] = (*level)[y][x];
202 /* Creates a jail to work around, so we can finish it later. */
204 createjail (lev_t * level, const unsigned width, const unsigned height)
206 unsigned x, y, xstart, xend, ystart, yend;
208 if (LEVWIDTH < width || LEVHEIGHT < height)
211 xstart = LEVWIDTH / 2 - width / 2;
212 xend = LEVWIDTH / 2 + width / 2;
213 ystart = LEVHEIGHT / 2 - height / 2;
214 yend = LEVHEIGHT / 2 + height / 2;
216 for (y = ystart - 1; y < yend + 1; y++)
217 for (x = xstart - 1; x < xend + 1; x++)
218 setblockto (level, x, y, BLOCK_DOT_1);
220 for (y = ystart; y < yend; y++)
221 for (x = xstart; x < xend; x++)
222 setblockto (level, x, y, BLOCK_WALL);
226 pacman_get_jail_opening ( int *x, int *y)
228 int xstart = LEVWIDTH / 2 - JAILWIDTH / 2;
229 int ystart = LEVHEIGHT / 2 - JAILHEIGHT / 2;
230 *x = xstart + JAILWIDTH / 2;
234 /* Finishes a jail so it is empty and the ghostpass is on top. */
236 finishjail (lev_t * level, const unsigned width, const unsigned height)
238 unsigned x, y, xstart, xend, ystart, yend;
240 xstart = LEVWIDTH / 2 - width / 2;
241 xend = LEVWIDTH / 2 + width / 2;
242 ystart = LEVHEIGHT / 2 - height / 2;
243 yend = LEVHEIGHT / 2 + height / 2;
245 for (y = ystart + 1; y < yend - 1; y++)
246 for (x = xstart + 1; x < xend - 1; x++)
247 setblockto (level, x, y, BLOCK_EMPTY);
249 for (x = xstart - 1; x < xend + 1; x++) {
250 setblockto (level, x, ystart - 1, BLOCK_EMPTY);
251 setblockto (level, x, yend, BLOCK_EMPTY);
254 for (y = ystart - 1; y < yend + 1; y++) {
255 setblockto (level, xstart - 1, y, BLOCK_EMPTY);
256 setblockto (level, xend, y, BLOCK_EMPTY);
259 setblockto (level, xstart + width / 2 - 1, ystart, BLOCK_GHOST_ONLY);
260 setblockto (level, xstart + width / 2, ystart, BLOCK_GHOST_ONLY);
263 /* Tries to set a block at a certain position. Returns true if possible,
264 and leaves level in new state (plus block), or False if not possible,
265 and leaves level in unpredictable state. */
267 tryset (lev_t * level, const unsigned xpos, const unsigned ypos,
270 register unsigned x, y;
271 register char locchar;
275 if ((*level)[ypos][xpos] == BLOCK_DOT_1)
281 for (y = 0; y < TILEHEIGHT; y++)
282 for (x = 0; x < TILEWIDTH; x++) {
283 locchar = block[y * TILEWIDTH + x];
284 if (locchar == BLOCK_EMPTY)
286 if (locchar == BLOCK_DOT_1 &&
288 xstart + x >= LEVWIDTH - 1 ||
290 ystart + y >= LEVHEIGHT - 1 ||
291 checkset (level, xstart + x, ystart + y) != 0))
293 else if (locchar == BLOCK_WALL &&
295 xstart + x < LEVWIDTH &&
297 ystart + y < LEVHEIGHT - 1) &&
298 checkunsetdef (level,
299 (unsigned) (xstart + x),
300 (unsigned) (ystart + y)) != 0)
304 /* and set the block in place */
306 xend = (xstart + TILEWIDTH < LEVWIDTH - 1) ?
307 TILEWIDTH : LEVWIDTH - xstart - 2;
308 yend = (ystart + TILEHEIGHT < LEVHEIGHT - 1) ?
309 TILEHEIGHT : LEVHEIGHT - ystart - 2;
311 for (y = (ystart < 1) ? (unsigned) (1 - ystart) : 0U; y < yend; y++)
312 for (x = (xstart < 1) ? (unsigned) (1 - xstart) : 0U; x < xend; x++) {
313 locchar = block[y * TILEWIDTH + x];
314 if ((locchar == BLOCK_WALL) &&
315 ((*level)[ystart + y][xstart + x] == BLOCK_EMPTY)) {
316 (*level)[ystart + y][xstart + x] = BLOCK_WALL;
318 [LEVWIDTH - (xstart + x + 1)] = BLOCK_WALL;
322 (*level)[ypos][xpos] = BLOCK_DOT_1;
323 (*level)[ypos][LEVWIDTH - xpos - 1] = BLOCK_DOT_1;
328 /* Tries certain combinations of blocks in the level recursively. */
330 nextstep (pacmangamestruct *pp,
331 lev_t * level, const unsigned x, const unsigned y,
332 unsigned dirvec[], unsigned ndirs)
334 unsigned dirpos, curdir, inc = 0;
343 dirpos = NRAND (ndirs);
344 curdir = dirvec[dirpos];
345 /* nope, no bufoverflow, but ndirs - 1 + 1 */
346 dirvec[dirpos] = dirvec[ndirs];
347 dirvec[ndirs] = curdir;
352 if (y < 1 || (ret = creatlevelblock (pp, level, x, y - 1))
357 if (x > LEVWIDTH - 2 || (ret = creatlevelblock (pp, level, x + 1, y))
362 if (y > LEVHEIGHT - 2 || (ret = creatlevelblock (pp, level, x, y + 1))
367 if (x < 1 || (ret = creatlevelblock (pp, level, x - 1, y))
372 inc += (unsigned) ret;
380 creatlevelblock (pacmangamestruct *pp,
381 lev_t * level, const unsigned x, const unsigned y)
383 unsigned tried = GETNB (TILES_COUNT);
389 pp->tiles = (struct tiles *) malloc (sizeof (def_tiles));
390 memcpy (pp->tiles, def_tiles, sizeof (def_tiles));
393 if (!((x < LEVWIDTH) && (y < LEVHEIGHT)))
396 if (checkunsetdef (level, x, y) != 0)
402 tried &= ~(1 << 4 | 1 << 5 | 1 << 6 | 1 << 8 | 1 << 9 | 1 << 10);
403 else if (x == LEVWIDTH - 1)
405 else if (x == LEVWIDTH - 2)
406 tried &= ~(1 << 2 | 1 << 3 | 1 << 6 | 1 << 7 | 1 << 8 | 1 << 10);
409 tried &= ~(1 << 2 | 1 << 5 | 1 << 6 | 1 << 7 | 1 << 9 | 1 << 10);
412 else if (y == LEVHEIGHT - 1)
414 else if (y == LEVHEIGHT - 2)
415 tried &= ~(1 << 3 | 1 << 4 | 1 << 7 | 1 << 8 | 1 << 9 | 1 << 10);
417 /* make a copy of the current level, so we can go back on the stack */
418 (void) memcpy (&savedlev, level, sizeof (lev_t));
420 /* while there are still some blocks left to try */
421 while (tried != 0x00) {
422 tilenr = tileprob[NRAND (MAXTILEPROB)];
424 if (!TESTNB (tried, tilenr))
427 if (tryset (level, x, y, pp->tiles[tilenr].block) != 0) {
428 if ((ret = nextstep (pp, level, x, y, pp->tiles[tilenr].dirvec,
429 pp->tiles[tilenr].ndirs)) != 0) {
432 (void) memcpy (level, &savedlev, sizeof (lev_t));
434 tried &= ~(pp->tiles[tilenr].simular_to);
439 /* Fills up all empty space so there is wall everywhere. */
441 filllevel (lev_t * level)
445 for (y = 0; y < LEVHEIGHT; y++)
446 for (x = 0; x < LEVWIDTH; x++)
447 if ((*level)[y][x] == BLOCK_EMPTY)
448 (*level)[y][x] = BLOCK_WALL;
452 /* Check to see if the x and y value are in the corners.
453 * we could probable compute these values once and avoid
454 * go through the loops every time.
457 top_left (lev_t * level, unsigned int *passed_x, unsigned int *passed_y)
460 for (y = 0; y < LEVHEIGHT; y++)
461 for (x = 0; x < LEVWIDTH; x++) {
462 if (checkset (level, x, y) == 0) {
472 bottom_left (lev_t * level, unsigned int *passed_x, unsigned int *passed_y)
475 for (y = LEVHEIGHT; y > -1; y--)
476 for (x = 0; x < LEVWIDTH; x++) {
477 if (checkset (level, x, y) == 0) {
486 top_right (lev_t * level, unsigned int *passed_x, unsigned int *passed_y)
490 for (y = 0; y < LEVHEIGHT; y++)
491 for (x = LEVWIDTH; x >= 0; x--) {
492 if (checkset (level, x, y) == 0) {
501 bottom_right (lev_t * level, unsigned int *passed_x, unsigned int *passed_y)
505 for (y = LEVHEIGHT; y >= 0; y--)
506 for (x = LEVWIDTH; x >= 0; x--) {
507 if (checkset (level, x, y) == 0) {
516 init_bonus_dots (pacmangamestruct *pp, lev_t * level)
518 unsigned int x = 0, y = 0;
519 top_left (level, &x, &y);
520 pp->bonus_dots[TOP_LEFT].x = x;
521 pp->bonus_dots[TOP_LEFT].y = y;
522 pp->bonus_dots[TOP_LEFT].eaten = False;
523 top_right (level, &x, &y);
524 pp->bonus_dots[TOP_RIGHT].x = x;
525 pp->bonus_dots[TOP_RIGHT].y = y;
526 pp->bonus_dots[TOP_RIGHT].eaten = False;
527 bottom_left (level, &x, &y);
528 pp->bonus_dots[BOTTOM_LEFT].x = x;
529 pp->bonus_dots[BOTTOM_LEFT].y = y;
530 pp->bonus_dots[BOTTOM_LEFT].eaten = False;
531 bottom_right (level, &x, &y);
532 pp->bonus_dots[BOTTOM_RIGHT].x = x;
533 pp->bonus_dots[BOTTOM_RIGHT].y = y;
534 pp->bonus_dots[BOTTOM_RIGHT].eaten = False;
538 pacman_is_bonus_dot (pacmangamestruct *pp, int x, int y, int *idx)
542 for (i = 0; i < NUM_BONUS_DOTS; i++) {
543 /* fprintf(stderr,"is bonus: passed x (%d, %d) bonus (%d, %d)\n",x,y,bonus_dots[i].x, bonus_dots[i].y); */
544 if (x == pp->bonus_dots[i].x && y == pp->bonus_dots[i].y) {
554 check_bonus_idx (int idx)
556 assert (0 <= idx && idx < NUM_BONUS_DOTS);
560 pacman_bonus_dot_eaten (pacmangamestruct *pp, int idx)
562 check_bonus_idx (idx);
563 return pp->bonus_dots[idx].eaten;
567 pacman_eat_bonus_dot (pacmangamestruct *pp, int idx)
569 check_bonus_idx (idx);
570 pp->bonus_dots[idx].eaten = True;
574 pacman_bonus_dot_pos (pacmangamestruct *pp, int idx, int *x, int *y)
576 check_bonus_idx (idx);
577 *x = pp->bonus_dots[idx].x;
578 *y = pp->bonus_dots[idx].y;
581 /* Changes a level from a simple wall/nowall to a wall with rounded corners
582 and such. Stupid algorithm, could be done better! */
584 frmtlevel (pacmangamestruct *pp, lev_t * level)
589 register unsigned poscond;
590 register unsigned poscond2;
592 clearlevel (&frmtlev);
593 init_bonus_dots (pp, level);
594 for (y = 0; y < LEVHEIGHT; y++)
595 for (x = 0; x < LEVWIDTH; x++) {
597 if (checkset (level, x, y) == 0) {
598 if (pacman_is_bonus_dot (pp, x, y, &idx)) {
599 frmtlev[y][x] = BLOCK_DOT_BONUS;
602 frmtlev[y][x] = BLOCK_DOT_2;
607 if ((*level)[y][x] == BLOCK_GHOST_ONLY) {
608 frmtlev[y][x] = BLOCK_GHOST_ONLY;
613 (checksetout (level, x - 1, y - 1) != 0 ?
615 (checksetout (level, x + 1, y - 1) != 0 ?
617 (checksetout (level, x + 1, y + 1) != 0 ?
619 (checksetout (level, x - 1, y + 1) != 0 ? 0x08U : 0U);
622 (checksetout (level, x - 1, y) != 0 ?
624 (checksetout (level, x, y - 1) != 0 ?
626 (checksetout (level, x + 1, y) != 0 ?
628 (checksetout (level, x, y + 1) != 0 ? 0x08U : 0);
631 /* completely filled */
632 case 0x01U | 0x02U | 0x04U | 0x08U:
633 frmtlev[y][x] = BLOCK_EMPTY;
636 /* left to top corner */
638 frmtlev[y][x] = BLOCK_WALL_TL;
640 /* top to right corner */
642 frmtlev[y][x] = BLOCK_WALL_TR;
644 /* right to bottom corner */
646 frmtlev[y][x] = BLOCK_WALL_BR;
648 /* bottom to left corner */
650 frmtlev[y][x] = BLOCK_WALL_BL;
656 case 0x01U | 0x04U | 0x08U:
657 case 0x01U | 0x04U | 0x02U:
658 frmtlev[y][x] = BLOCK_WALL_HO;
661 case 0x02U | 0x08U | 0x01U:
662 case 0x02U | 0x08U | 0x04U:
663 frmtlev[y][x] = BLOCK_WALL_VE;
666 frmtlev[y][x] = BLOCK_WALL_TL;
669 frmtlev[y][x] = BLOCK_WALL_TR;
672 frmtlev[y][x] = BLOCK_WALL_BR;
675 frmtlev[y][x] = BLOCK_WALL_BL;
679 case 0x02U | 0x04U | 0x08U:
680 frmtlev[y][x] = BLOCK_WALL_TL;
682 case 0x01U | 0x04U | 0x08U:
683 frmtlev[y][x] = BLOCK_WALL_TR;
685 case 0x01U | 0x02U | 0x08U:
686 frmtlev[y][x] = BLOCK_WALL_BR;
688 case 0x01U | 0x02U | 0x04U:
689 frmtlev[y][x] = BLOCK_WALL_BL;
692 frmtlev[y][x] = BLOCK_EMPTY;
694 (void) memcpy ((lev_t *) level, (lev_t *) & frmtlev, sizeof (lev_t));
697 /* Counts the number of dots in the level, and returns that number. */
699 countdots (pacmangamestruct *pp)
701 unsigned i, count = 0;
703 for (i = 0; i < LEVWIDTH * LEVHEIGHT; i++)
704 if (pp->level[i] == BLOCK_DOT_2 || pp->level[i] == BLOCK_DOT_BONUS)
710 /* Creates a new level, and places that in the pacmangamestruct. */
712 pacman_createnewlevel (pacmangamestruct *pp)
715 unsigned dirvec[1] = { GO_UP };
716 unsigned ret = 0, i = 0;
718 if ((level = (lev_t *) calloc (1, sizeof (lev_t))) == NULL)
721 if (NRAND (2) == 0) {
725 createjail (level, JAILWIDTH, JAILHEIGHT);
726 if ((ret = nextstep (pp, level, LEVWIDTH / 2 - 1,
727 LEVHEIGHT / 2 - JAILHEIGHT / 2 - 3,
729 (void) free ((void *) level);
732 } while (ret * 100 < (LEVWIDTH * LEVHEIGHT * MINDOTPERC));
735 frmtlevel (pp, level);
736 finishjail (level, JAILWIDTH, JAILHEIGHT);
739 (void) memcpy (level, stdlevel, sizeof (lev_t));
740 frmtlevel (pp, level);
743 copylevel (pp->level, level);
744 pp->dotsleft = countdots (pp);
746 (void) free ((void *) level);
750 /* Checks if a position is allowable for ghosts/pacs to enter. */
752 pacman_check_pos (pacmangamestruct * pp, int y, int x, int ghostpass)
754 if ((pp->level[y * LEVWIDTH + x] == BLOCK_DOT_2) ||
755 (pp->level[y * LEVWIDTH + x] == BLOCK_EMPTY) ||
756 (pp->level[y * LEVWIDTH + x] == BLOCK_DOT_BONUS) ||
757 ((pp->level[y * LEVWIDTH + x] == BLOCK_GHOST_ONLY) && ghostpass)) {
763 /* Checks if there is a dot on the specified position in the level. */
765 pacman_check_dot (pacmangamestruct * pp, unsigned int x, unsigned int y)
767 if (x >= LEVWIDTH || y >= LEVHEIGHT)
769 if (pp->level[y * LEVWIDTH + x] == BLOCK_DOT_2)