--- /dev/null
+/*-
+ * Copyright (c) 2002 by Edwin de Jong <mauddib@gmx.net>.
+ *
+ * Permission to use, copy, modify, and distribute this software and its
+ * documentation for any purpose and without fee is hereby granted,
+ * provided that the above copyright notice appear in all copies and that
+ * both that copyright notice and this permission notice appear in
+ * supporting documentation.
+ *
+ * This file is provided AS IS with no warranties of any kind. The author
+ * shall have no liability with respect to the infringement of copyrights,
+ * trade secrets or any patents by this file or any part thereof. In no
+ * event will the author be liable for any lost revenue or profits or
+ * other special, indirect and consequential damages.
+ */
+
+#define NONE 0x0000
+#define LT 0x1000
+#define RT 0x0001
+#define RB 0x0010
+#define LB 0x0100
+#define ALL 0x1111
+
+#define BLOCK_EMPTY ' '
+#define BLOCK_DOT_1 '`'
+#define BLOCK_DOT_2 '.'
+#define BLOCK_WALL '#'
+#define BLOCK_GHOST_ONLY '='
+#define BLOCK_WALL_TL '\''
+#define BLOCK_WALL_TR '`'
+#define BLOCK_WALL_BR ','
+#define BLOCK_WALL_BL '_'
+#define BLOCK_WALL_HO '-'
+#define BLOCK_WALL_VE '|'
+
+/* This is more or less the standard pacman level (without the left-right
+ tunnel. */
+static const lev_t stdlevel = {
+ "########################################",
+ "########################################",
+ "#######````````````##````````````#######",
+ "#######`####`#####`##`#####`####`#######",
+ "#######`####`#####`##`#####`####`#######",
+ "#######`####`#####`##`#####`####`#######",
+ "#######``````````````````````````#######",
+ "#######`####`##`########`##`####`#######",
+ "#######`####`##`########`##`####`#######",
+ "#######``````##````##````##``````#######",
+ "############`#####`##`#####`############",
+ "############`#####`##`#####`############",
+ "############`##``````````##`############",
+ "############`##`###==###`##`############",
+ "############`##`########`##`############",
+ "############````########````############",
+ "############`##`########`##`############",
+ "############`##`########`##`############",
+ "############`##``````````##`############",
+ "############`##`########`##`############",
+ "############`##`########`##`############",
+ "#######````````````##````````````#######",
+ "#######`####`#####`##`#####`####`#######",
+ "#######`####`#####`##`#####`####`#######",
+ "#######```##````````````````##```#######",
+ "#########`##`##`########`##`##`#########",
+ "#########`##`##`########`##`##`#########",
+ "#######``````##````##````##``````#######",
+ "#######`##########`##`##########`#######",
+ "#######`##########`##`##########`#######",
+ "#######``````````````````````````#######",
+ "########################################"};
+
+#define TILEWIDTH 5U
+#define TILEHEIGHT 5U
+#define TILES_COUNT 11U
+
+#define GO_UP 0x0001U
+#define GO_LEFT 0x0002U
+#define GO_RIGHT 0x0004U
+#define GO_DOWN 0x0008U
+
+/* This are tiles which can be places to create a level. */
+static struct {
+ char block[TILEWIDTH * TILEHEIGHT + 1];
+ unsigned dirvec[4];
+ unsigned ndirs;
+ unsigned simular_to;
+} tiles[TILES_COUNT] = {
+/*
+ * ' ' == dont care == BLOCK_EMPTY
+ * '#' == set wall, and not clear == BLOCK_WALL
+ * '`' == clear == BLOCK_DOT_1
+ * middle position is always set as cleardef
+ */
+ { " # "
+ " # "
+ " ``` "
+ " # "
+ " # ",
+ { GO_LEFT, GO_RIGHT, 0, 0 }, 2,
+ (unsigned) (1 << 0 | 1 << 6 | 1 << 8 | 1 << 10) },
+ { " "
+ " ` "
+ "##`##"
+ " ` "
+ " ",
+ { GO_UP, GO_DOWN, 0, 0 }, 2,
+ (unsigned) (1 << 1 | 1 << 7 | 1 << 9 | 1 << 10) },
+ { " ##"
+ "##`##"
+ "##`` "
+ "#### "
+ "#### ",
+ { GO_UP, GO_RIGHT, 0, 0 }, 2,
+ (unsigned) (1 << 2 | 1 << 6 | 1 << 7 | 1 << 10) },
+ { "#### "
+ "#### "
+ "##`` "
+ "##`##"
+ " ##",
+ { GO_RIGHT, GO_DOWN, 0, 0 }, 2,
+ (unsigned) (1 << 3 | 1 << 7 | 1 << 8 | 1 << 10) },
+ { " ###"
+ " ###"
+ " ``##"
+ "##` "
+ "## ",
+ { GO_LEFT, GO_DOWN, 0, 0 }, 2,
+ (unsigned) (1 << 4 | 1 << 8 | 1 << 9 | 1 << 10) },
+ { "## "
+ "##`##"
+ " ``##"
+ " ####"
+ " ####",
+ { GO_LEFT, GO_UP, 0, 0 }, 2,
+ (unsigned) (1 << 5 | 1 << 6 | 1 << 9 | 1 << 10) },
+ { "##`##"
+ "##`##"
+ "`````"
+ " ### "
+ " ### ",
+ { GO_LEFT, GO_UP, GO_RIGHT, 0 }, 3,
+ (unsigned) 1 << 6 },
+ { " `##"
+ "##`##"
+ "##```"
+ "##`##"
+ " `##",
+ { GO_UP, GO_RIGHT, GO_DOWN, 0}, 3,
+ (unsigned) (1 << 7) },
+ { " ### "
+ " ### "
+ "`````"
+ "##`##"
+ "##`##",
+ { GO_LEFT, GO_RIGHT, GO_DOWN, 0}, 3,
+ (unsigned) (1 << 8) },
+ { "##` "
+ "##`##"
+ "```##"
+ "##`##"
+ "##` ",
+ { GO_UP, GO_DOWN, GO_LEFT, 0 }, 3,
+ (unsigned) (1 << 9) },
+ { "##`##"
+ "##`##"
+ "`````"
+ "##`##"
+ "##`##",
+ { GO_UP, GO_DOWN, GO_LEFT, GO_RIGHT }, 4,
+ (unsigned) (1 << 10) }
+};
+
+/* probability array for each of the tiles */
+#define MAXTILEPROB 22
+static const unsigned tileprob[MAXTILEPROB] =
+ { 0, 0, 0, 1, 1, 2, 3, 4, 5, 6, 6, 6, 7, 7, 8, 8, 8, 9, 9, 10, 10, 10 };
+
+/* Sets a block in the level to a certain state. */
+static void
+setblockto(lev_t *level, const unsigned x, const unsigned y,
+ const char c)
+{
+ if (!(x < LEVWIDTH && y < LEVHEIGHT)) return;
+ (*level)[y][x] = c;
+}
+
+/* check if a block is set */
+static int
+checkset(lev_t *level, const unsigned x, const unsigned y)
+{
+ if (!(x < LEVWIDTH && y < LEVHEIGHT) ||
+ (*level)[y][x] == BLOCK_WALL ||
+ (*level)[y][x] == BLOCK_GHOST_ONLY)
+ return True;
+ return False;
+}
+
+/* Check if a block is not set */
+static int
+checksetout(lev_t *level, const unsigned x, const unsigned y)
+{
+ if (!(x < LEVWIDTH && y < LEVHEIGHT) ||
+ checkset(level, x, y) != 0)
+ return True;
+
+ return False;
+}
+
+/* Check if a block cannot be set */
+static int
+checkunsetdef(lev_t *level, const unsigned x, const unsigned y)
+{
+ if (!(x < LEVWIDTH && y < LEVHEIGHT))
+ return False;
+ if ((*level)[y][x] == BLOCK_DOT_1) return True;
+ return False;
+}
+
+/* Initializes a level to empty state. */
+static void
+clearlevel(lev_t *level)
+{
+ unsigned x, y;
+
+ for (y = 0; y < LEVHEIGHT ; y++)
+ for (x = 0 ; x < LEVWIDTH ; x++)
+ (*level)[y][x] = BLOCK_EMPTY;
+}
+
+/* Changes a level from the level creation structure ((array to array) to
+ array. */
+static void
+copylevel(char *dest, lev_t *level)
+{
+ unsigned x, y;
+
+ for (y = 0; y < LEVHEIGHT ; y++)
+ for (x = 0; x < LEVWIDTH ; x++)
+ dest[y * LEVWIDTH + x] = (*level)[y][x];
+}
+
+/* Creates a jail to work around, so we can finish it later. */
+static void
+createjail(lev_t *level, const unsigned width,
+ const unsigned height)
+{
+ unsigned x, y, xstart, xend, ystart, yend;
+
+ if (LEVWIDTH < width || LEVHEIGHT < height) return;
+
+ xstart = LEVWIDTH/2 - width/2;
+ xend = LEVWIDTH/2 + width/2;
+ ystart = LEVHEIGHT/2 - height/2;
+ yend = LEVHEIGHT/2 + height/2;
+
+ for (y = ystart - 1; y < yend + 1; y++)
+ for (x = xstart - 1; x < xend + 1; x++)
+ setblockto(level, x, y, BLOCK_DOT_1);
+
+ for (y = ystart; y < yend; y++)
+ for (x = xstart; x < xend; x++)
+ setblockto(level, x, y, BLOCK_WALL);
+}
+
+/* Finishes a jail so it is empty and the ghostpass is on top. */
+static void
+finishjail(lev_t *level, const unsigned width,
+ const unsigned height)
+{
+ unsigned x, y, xstart, xend, ystart, yend;
+
+ xstart = LEVWIDTH/2 - width/2;
+ xend = LEVWIDTH/2 + width/2;
+ ystart = LEVHEIGHT/2 - height/2;
+ yend = LEVHEIGHT/2 + height/2;
+
+ for (y = ystart + 1; y < yend - 1 ; y++)
+ for (x = xstart + 1; x < xend - 1; x++)
+ setblockto(level, x, y, BLOCK_EMPTY);
+
+ for (x = xstart - 1; x < xend + 1; x++) {
+ setblockto(level, x, ystart - 1, BLOCK_EMPTY);
+ setblockto(level, x, yend, BLOCK_EMPTY);
+ }
+
+ for (y = ystart - 1; y < yend + 1; y++) {
+ setblockto(level, xstart - 1, y, BLOCK_EMPTY);
+ setblockto(level, xend, y, BLOCK_EMPTY);
+ }
+
+ setblockto(level, xstart + width/2 - 1, ystart, BLOCK_GHOST_ONLY);
+ setblockto(level, xstart + width/2, ystart, BLOCK_GHOST_ONLY);
+}
+
+/* Tries to set a block at a certain position. Returns true if possible,
+ and leaves level in new state (plus block), or False if not possible,
+ and leaves level in unpredictable state. */
+static int
+tryset(lev_t *level, const unsigned xpos, const unsigned ypos,
+ const char *block)
+{
+ register unsigned x, y;
+ register char locchar;
+ int xstart, ystart;
+ unsigned xend, yend;
+
+ if ((*level)[ypos][xpos] == BLOCK_DOT_1) return False;
+
+ xstart = xpos - 2;
+ ystart = ypos - 2;
+
+ for (y = 0 ; y < TILEHEIGHT ; y++)
+ for (x = 0 ; x < TILEWIDTH ; x++) {
+ locchar = block[y * TILEWIDTH + x];
+ if (locchar == BLOCK_EMPTY)
+ continue;
+ if (locchar == BLOCK_DOT_1 &&
+ (xstart + x < 1 ||
+ xstart + x >= LEVWIDTH - 1 ||
+ ystart + y < 1 ||
+ ystart + y >= LEVHEIGHT - 1 ||
+ checkset(level, xstart + x, ystart + y) != 0))
+ return False;
+ else if (locchar == BLOCK_WALL &&
+ (xstart + x > 1 &&
+ xstart + x < LEVWIDTH &&
+ ystart + y > 1 &&
+ ystart + y < LEVHEIGHT - 1) &&
+ checkunsetdef(level,
+ (unsigned)(xstart + x),
+ (unsigned)(ystart + y)) != 0)
+ return False;
+ }
+
+ /* and set the block in place */
+
+ xend = (xstart + TILEWIDTH < LEVWIDTH - 1) ?
+ TILEWIDTH : LEVWIDTH - xstart - 2;
+ yend = (ystart + TILEHEIGHT < LEVHEIGHT - 1) ?
+ TILEHEIGHT : LEVHEIGHT - ystart - 2;
+
+ for (y = (ystart < 1) ? (unsigned)(1 - ystart) : 0U ;
+ y < yend ; y++)
+ for (x = (xstart < 1) ?
+ (unsigned)(1 - xstart) : 0U ;
+ x < xend ; x++) {
+ locchar = block[y * TILEWIDTH + x];
+ if ((locchar == BLOCK_WALL) &&
+ ((*level)[ystart + y][xstart + x] == BLOCK_EMPTY)) {
+ (*level)[ystart + y][xstart + x] = BLOCK_WALL;
+ (*level)[ystart + y]
+ [LEVWIDTH - (xstart + x + 1)] =
+ BLOCK_WALL;
+ }
+ }
+
+ (*level)[ypos][xpos] = BLOCK_DOT_1;
+ (*level)[ypos][LEVWIDTH-xpos-1] = BLOCK_DOT_1;
+
+ return True;
+}
+
+/* Tries certain combinations of blocks in the level recursively. */
+static unsigned
+nextstep(lev_t *level, const unsigned x, const unsigned y,
+ unsigned dirvec[], unsigned ndirs)
+{
+ unsigned dirpos, curdir, inc = 0;
+ int ret = 0;
+
+ while (ndirs > 0) {
+ ndirs--;
+ if (ndirs == 0) {
+ curdir = dirvec[0];
+ }
+ else {
+ dirpos = NRAND(ndirs);
+ curdir = dirvec[dirpos];
+ /* nope, no bufoverflow, but ndirs - 1 + 1 */
+ dirvec[dirpos] = dirvec[ndirs];
+ dirvec[ndirs] = curdir;
+ }
+
+ switch (curdir) {
+ case GO_UP:
+ if (y < 1 ||
+ (ret = creatlevelblock(level, x, y - 1))
+ == 0)
+ return 0;
+ break;
+ case GO_RIGHT:
+ if (x > LEVWIDTH - 2 ||
+ (ret = creatlevelblock(level, x + 1, y))
+ == 0)
+ return 0;
+ break;
+ case GO_DOWN:
+ if (y > LEVHEIGHT - 2 ||
+ (ret = creatlevelblock(level, x, y + 1))
+ == 0)
+ return 0;
+ break;
+ case GO_LEFT:
+ if (x < 1 ||
+ (ret = creatlevelblock(level, x - 1, y))
+ == 0)
+ return 0;
+ }
+ if (ret != -1)
+ inc += (unsigned)ret;
+ }
+ if (inc == 0) inc = 1;
+ return inc;
+}
+
+static int
+creatlevelblock(lev_t *level, const unsigned x, const unsigned y)
+{
+ unsigned tried = GETNB(TILES_COUNT);
+ unsigned tilenr;
+ unsigned ret;
+ lev_t savedlev;
+
+ if (!((x < LEVWIDTH) && (y < LEVHEIGHT)))
+ return 0;
+
+ if (checkunsetdef(level, x, y) != 0)
+ return -1;
+
+ if (x == 0)
+ tried &= ~(1<<0);
+ else if (x == 1)
+ tried &= ~(1<<4 | 1<<5 | 1<<6 | 1<<8 | 1<<9 | 1<<10);
+ else if (x == LEVWIDTH-1)
+ tried &= ~(1<<0);
+ else if (x == LEVWIDTH-2)
+ tried &= ~(1<<2 | 1<<3 | 1<<6 | 1<<7 | 1<<8 | 1<<10);
+
+ if (y == 1)
+ tried &= ~(1<<2 | 1<<5 | 1<<6 | 1<<7 | 1<<9 | 1<<10);
+ else if (y == 0)
+ tried &= ~(1<<1);
+ else if (y == LEVHEIGHT-1)
+ tried &= ~(1<<1);
+ else if (y == LEVHEIGHT-2)
+ tried &= ~(1<<3 | 1<<4 | 1<<7 | 1<<8 | 1<<9 | 1<<10);
+
+ /* make a copy of the current level, so we can go back on the stack */
+ (void) memcpy(&savedlev, level, sizeof(lev_t));
+
+ /* while there are still some blocks left to try */
+ while (tried != 0x00) {
+ tilenr = tileprob[NRAND(MAXTILEPROB)];
+
+ if (!TESTNB(tried, tilenr))
+ continue;
+
+ if (tryset(level, x, y, tiles[tilenr].block) != 0) {
+ if ((ret = nextstep(level, x, y, tiles[tilenr].dirvec,
+ tiles[tilenr].ndirs)) != 0) {
+ return ret + 1;
+ }
+ (void) memcpy(level, &savedlev, sizeof(lev_t));
+ }
+ tried &= ~(tiles[tilenr].simular_to);
+ }
+ return 0;
+}
+
+/* Fills up all empty space so there is wall everywhere. */
+static void
+filllevel(lev_t *level)
+{
+ unsigned x, y;
+
+ for (y = 0; y < LEVHEIGHT; y++)
+ for (x = 0; x < LEVWIDTH; x++)
+ if ((*level)[y][x] == BLOCK_EMPTY)
+ (*level)[y][x] = BLOCK_WALL;
+}
+
+/* Changes a level from a simple wall/nowall to a wall with rounded corners
+ and such. Stupid algorithm, could be done better! */
+static void
+frmtlevel(lev_t *level)
+{
+ lev_t frmtlev;
+ register unsigned x, y;
+ register unsigned poscond;
+ register unsigned poscond2;
+
+ clearlevel(&frmtlev);
+
+ for (y = 0; y < LEVHEIGHT; y++)
+ for (x = 0; x < LEVWIDTH; x++) {
+
+ if (checkset(level, x, y) == 0) {
+ frmtlev[y][x] = BLOCK_DOT_2;
+ continue;
+ }
+
+ if ((*level)[y][x] == BLOCK_GHOST_ONLY) {
+ frmtlev[y][x] = BLOCK_GHOST_ONLY;
+ continue;
+ }
+
+ poscond =
+ (checksetout(level, x - 1, y - 1) != 0 ?
+ 0x01U : 0U) |
+ (checksetout(level, x + 1, y - 1) != 0 ?
+ 0x02U : 0U) |
+ (checksetout(level, x + 1, y + 1) != 0 ?
+ 0x04U : 0U) |
+ (checksetout(level, x - 1, y + 1) != 0 ?
+ 0x08U : 0U);
+
+ poscond2 =
+ (checksetout(level, x - 1, y) != 0 ?
+ 0x01U : 0) |
+ (checksetout(level, x, y - 1) != 0 ?
+ 0x02U : 0) |
+ (checksetout(level, x + 1, y) != 0 ?
+ 0x04U : 0) |
+ (checksetout(level, x, y + 1) != 0 ?
+ 0x08U : 0);
+
+ switch (poscond) {
+ /* completely filled */
+ case 0x01U | 0x02U | 0x04U | 0x08U:
+ frmtlev[y][x] = BLOCK_EMPTY; continue;
+
+ /* left to top corner */
+ case 0x01U:
+ frmtlev[y][x] = BLOCK_WALL_TL; continue;
+ /* top to right corner */
+ case 0x02U:
+ frmtlev[y][x] = BLOCK_WALL_TR; continue;
+ /* right to bottom corner */
+ case 0x04U:
+ frmtlev[y][x] = BLOCK_WALL_BR; continue;
+ /* bottom to left corner */
+ case 0x08U:
+ frmtlev[y][x] = BLOCK_WALL_BL; continue;
+ }
+
+ switch (poscond2) {
+ case 0x01U | 0x04U:
+ case 0x01U | 0x04U | 0x08U:
+ case 0x01U | 0x04U | 0x02U:
+ frmtlev[y][x] = BLOCK_WALL_HO; continue;
+ case 0x02U | 0x08U:
+ case 0x02U | 0x08U | 0x01U:
+ case 0x02U | 0x08U | 0x04U:
+ frmtlev[y][x] = BLOCK_WALL_VE; continue;
+ case 0x01U | 0x02U:
+ frmtlev[y][x] = BLOCK_WALL_TL; continue;
+ case 0x02U | 0x04U:
+ frmtlev[y][x] = BLOCK_WALL_TR; continue;
+ case 0x04U | 0x08U:
+ frmtlev[y][x] = BLOCK_WALL_BR; continue;
+ case 0x08U | 0x01U:
+ frmtlev[y][x] = BLOCK_WALL_BL; continue;
+ }
+ switch (poscond) {
+ case 0x02U | 0x04U | 0x08U:
+ frmtlev[y][x] = BLOCK_WALL_TL; continue;
+ case 0x01U | 0x04U | 0x08U:
+ frmtlev[y][x] = BLOCK_WALL_TR; continue;
+ case 0x01U | 0x02U | 0x08U:
+ frmtlev[y][x] = BLOCK_WALL_BR; continue;
+ case 0x01U | 0x02U | 0x04U:
+ frmtlev[y][x] = BLOCK_WALL_BL; continue;
+ }
+ frmtlev[y][x] = BLOCK_EMPTY;
+ }
+ (void) memcpy((lev_t *)level, (lev_t *)&frmtlev, sizeof(lev_t));
+}
+
+/* Counts the number of dots in the level, and returns that number. */
+static unsigned
+countdots(ModeInfo * mi)
+{
+ pacmangamestruct *pp = &pacmangames[MI_SCREEN(mi)];
+ unsigned i, count = 0;
+
+ for (i = 0 ; i < LEVWIDTH*LEVHEIGHT ; i++)
+ if (pp->level[i] == BLOCK_DOT_2) count++;
+
+ return count;
+}
+
+/* Creates a new level, and places that in the pacmangamestruct. */
+static int
+createnewlevel(ModeInfo * mi)
+{
+ pacmangamestruct *pp = &pacmangames[MI_SCREEN(mi)];
+ lev_t *level;
+ unsigned dirvec[1] = { GO_UP };
+ unsigned ret = 0, i = 0;
+
+ if ((level = (lev_t *)calloc(1, sizeof(lev_t))) == NULL)
+ return i;
+
+ if (NRAND(2) == 0) {
+
+ do {
+ clearlevel(level);
+ createjail(level, JAILWIDTH, JAILHEIGHT);
+ if ((ret = nextstep(level, LEVWIDTH/2 - 1,
+ LEVHEIGHT/2 - JAILHEIGHT/2 - 3,
+ dirvec, 1)) == 0) {
+ (void) free((void *) level);
+ return i;
+ }
+ } while (ret * 100 < (LEVWIDTH * LEVHEIGHT * MINDOTPERC));
+
+ filllevel(level);
+ frmtlevel(level);
+ finishjail(level, JAILWIDTH, JAILHEIGHT);
+ } else {
+ (void) memcpy(level, stdlevel, sizeof(lev_t));
+ frmtlevel(level);
+ i = 1;
+ }
+ copylevel(pp->level, level);
+ pp->dotsleft = countdots(mi);
+
+ (void) free((void *) level);
+ return i;
+}
+
+/* Checks if a position is allowable for ghosts/pacs to enter. */
+static int
+check_pos(pacmangamestruct *pp, int y, int x, int ghostpass)
+{
+ if ((pp->level[y*LEVWIDTH + x] == BLOCK_DOT_2) ||
+ (pp->level[y*LEVWIDTH + x] == BLOCK_EMPTY) ||
+ ((pp->level[y*LEVWIDTH + x] == BLOCK_GHOST_ONLY) && ghostpass)) {
+ return 1;
+ }
+ return 0;
+}
+
+/* Checks if there is a dot on the specified position in the level. */
+static int
+check_dot(pacmangamestruct *pp, unsigned int x, unsigned int y)
+{
+ if (x >= LEVWIDTH || y >= LEVHEIGHT) return 0;
+ if (pp->level[y * LEVWIDTH + x] == BLOCK_DOT_2) return 1;
+ return 0;
+}
projects / xscreensaver / blobdiff