DataMuseum.dk

top - metrics - download

    Length: 4381 (0x111d)
    Types: TextFile
    Names: »polyfill.c«

└─⟦b20c6495f⟧ Bits:30007238 EUUGD18: Wien-båndet, efterår 1987
    └─⟦this⟧ »EUUGD18/X/Qix/polyfill.c« 

TextFile

/*
    File:   polyfill.c
    By:     Sky Schulz
  
    For:    Yaq (Yet Another Qix)

    Routine to fill the playing field (and to count the number of cells
    claimed, for scoring purposes).
  
    Friday, May 8th, 1987 - Sky
    Making mods to support the new/old data structure implementation.
  
    Just a little note to remind whom-ever:
	The coordinate values (x and y) used in polyfill() are NOT the actual
	coordinate values of the board.  Instead, they are twice the size of
	the board and represent the quadrants within a cell.
*/

#include    "qix.h"
#ifdef X11
struct pr_pos {
    short x, y;
};
#endif /* X11 */

static region_score;

/* Polygon fill point stack structure */
typedef struct pr_pos pnt;

/* Polygon fill stack */
#define MAX_PFILL_PNTS 128
pnt pnts[MAX_PFILL_PNTS];

int pntr;	/* Stack pointer */

/* Filled areas look-up tables */
int fill_table[2][2] = {	/* Filled state bits */
    {CL_PNT_UL, CL_PNT_UR},
    {CL_PNT_LL, CL_PNT_LR}
};
int edge_table[4][2][2] = {	/* Edge state bits */
    {			/* Look left */
	{0, CL_LN_UP},
	{0, CL_LN_DN}
    },
    {			/* Look right */
	{CL_LN_UP, 0},
	{CL_LN_DN, 0}
    },
    {			/* Look up */
	{0, 0},
	{CL_LN_LF, CL_LN_RT}
    },
    {			/* Look down */
	{CL_LN_LF, CL_LN_RT},
	{0, 0}
    }
};

/* Macro for testing and changing the current (x,y) points state */
pttest(x,y)
register int x, y;
{
    return (board[(x)/2][(y)/2] & fill_table[(y)&1][(x)&1]);
}

lntest(x,y,d)
register int x, y;
{
    return (board[(x)/2][(y)/2] & edge_table[d-LEFT][(y)&1][(x)&1]);
}

ptset(x,y)
register int x,y;
{
    board[x/2][y/2] |= fill_table[y&1][x&1], region_score++;
#ifdef DEBUG
    if (debug)
	box(convert_x(x/2)-3 + ((x&1)*4), convert_y(y/2)-3 + ((y&1)*4),
	    convert_x(x/2)-3 + ((x&1)*4)+2, convert_y(y/2)-3 + ((y&1)*4)+2,
	    PIX_SRC);
#endif DEBUG
}

push(x,y)
register int x, y;
{
    if (++pntr == MAX_PFILL_PNTS) {
        /* Serious problem folks... */
        msg ("Polygon fill stack overflow! (%d, %d)", x, y);
	sleep(2);
	remove_msgs(0);
        --pntr;
    } else
        pnts[pntr].x = x, pnts[pntr].y = y;
}

pop(x,y)
register int *x, *y;
{
    if (pntr < 0)
	return FALSE;

    *x = pnts[pntr].x;
    *y = pnts[pntr].y;
    pntr--; 
    return TRUE;
}

/* polyfill(x, y) - Flood the enclosed region found to surround (x,y) */
polyfill(x, y)
register int x, y;
{
    int org_x, org_y;
    int i, j;

    /* Make sure stack is reset (should be if all works well) */
    pntr = -1;
    region_score = 0;

    /* Save start point */
    org_x = x;
    org_y = y;

    /*
     * Main loop - uses x,y to start each push to the left and right on entry
     * x and y come from the call parameters on subsequent trips around the
     * loop x and y come from pop() returning points saved with push()
     * calls 
     */
    do  {
	/* Remember start point */
	x = org_x;
	y = org_y;

	/* Check points above and below start */
	/* test point above empty */
	if (!lntest(x, y, UP) && !pttest(x, y - 1))
	    push(x, y - 1);	/* Yes, save it */

	if (!lntest(x, y, DOWN) && !pttest(x, y + 1))
	    push(x, y + 1);	/* Yeah, save it */

	/* Fill in initial point */
	ptset(x, y);

	/* if we can move left, then do it */
	if (!lntest(x, y, LEFT)) {
	    /* Push to the left first.  Stop when we hit the edge */
	    for (x--;;x--) {
		/* See if we need to save points above and below */
		if (lntest(x, y-1, RIGHT) && (!lntest(x, y, UP)))
		    push(x, y - 1);
		if (lntest(x, y+1, RIGHT) && (!lntest(x, y, DOWN)))
		    push(x, y + 1);
		/* Fill in current point */
		ptset(x, y);

		/* See if we hit the edge */
		if (lntest(x, y, LEFT))
		    break;
	    }
	}
	/* Now try moving to the right */
	x = org_x;
	y = org_y;

	if (lntest(x, y, RIGHT))	/* can we move right? */
	    continue;	/* No, get another point */
	for (x++;;x++) {	/* Go until we hit the right edge */
	    /* Check points above and below to see if we can seep thru */
	    if (lntest(x, y-1, LEFT) && (!lntest(x, y, UP)))
		push(x, y - 1);
	    if (lntest(x, y+1, LEFT) && (!lntest(x, y, DOWN)))
		push(x, y + 1);
	    /* Fill in current point */
	    ptset(x, y);

	    /* Remove "surrounded" edges */
	    /* lnkill(x, y); */

	    /* See if we hit the edge yet */
	    if (lntest(x, y, RIGHT))
		break;
	}
    }
    while (pop(&org_x, &org_y));	/* Go until our stack is empty */

    return region_score;
}			/* end of polyfill */