/* XBubble - cell.c Copyright (C) 2002 Ivan Djelic Copyright (C) 2003 Martin Quinson This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */ #include #include #include #include #include "utils.h" #include "setting.h" #include "bubble.h" #include "cell.h" static int debug=0; /* * The playing board is paved with hexagonal cells ( drawing a Voronoi * diagram of bubble centers ). Bubbles are periodically lowered by one * row, thus the cells pavement depends on "parity" : * * if ( parity == 1 ) if ( parity == -1 ) * ____________________ ____________________ * |/ \ / \ / \ / \ / \| |\ / \ / \ / \ / \ /| * | 0 | 1 | 2 | 3 | 4 | row 0 | | 1 | 2 | 3 | 4 | | * |\ / \ / \ / \ / \ /| |/ \ / \ / \ / \ / \| * | | 6 | 7 | 8 | 9 | | row 1 | 5 | 6 | 7 | 8 | 9 | * |/ \ / \ / \ / \ / \| |\ / \ / \ / \ / \ /| * |10 |11 | | | | row 2 | |11 | | | | | * ......... ......... * ... * * Note that on each row of parity -1, the last cell is lost * * "board->array->cells" stores the content of each cell ( either a stuck * bubble or EMPTY_CELL ), it is indexed as shown above. * * The default array cell is then: * * parity = 1 parity = -1 * _________________________________ _________________________________ * |/ \ / \ / \ / \ / \ / \ / \ / \| |\ / \ / \ / \ / \ / \ / \ / \ /| * | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 0 | | 1 | 2 | 3 | 4 | 5 | 6 | 7 | | * |\ / \ / \ / \ / \ / \ / \ / \ /| |/ \ / \ / \ / \ / \ / \ / \ / \| * | | 9 |10 |11 |12 |13 |14 |15 | | 1 | 8 | 9 |10 |11 |12 |13 |14 |15 | * |/ \ / \ / \ / \ / \ / \ / \ / \| |\ / \ / \ / \ / \ / \ / \ / \ /| * |16 |17 |18 |19 |20 |21 |22 |23 | 2 | |17 |18 |19 |20 |21 |22 |23 | | * |\ / \ / \ / \ / \ / \ / \ / \ /| |/ \ / \ / \ / \ / \ / \ / \ / \| * | |25 |26 |27 |28 |29 |30 |31 | | 3 |24 |25 |26 |27 |28 |29 |30 |31 | * |/ \ / \ / \ / \ / \ / \ / \ / \| |\ / \ / \ / \ / \ / \ / \ / \ /| * |32 |33 |34 |35 |36 |37 |38 |39 | 4 | |33 |34 |35 |36 |37 |38 |39 | | * |\ / \ / \ / \ / \ / \ / \ / \ /| |/ \ / \ / \ / \ / \ / \ / \ / \| * | |41 |42 |43 |44 |45 |46 |47 | | 5 |40 |41 |42 |43 |44 |45 |46 |47 | * |/ \ / \ / \ / \ / \ / \ / \ / \| |\ / \ / \ / \ / \ / \ / \ / \ /| * |48 |49 |50 |51 |52 |53 |54 |55 | 6 | |49 |50 |51 |52 |53 |54 |55 | | * |\ / \ / \ / \ / \ / \ / \ / \ /| |/ \ / \ / \ / \ / \ / \ / \ / \| * | |57 |58 |59 |60 |61 |62 |63 | | 7 |56 |57 |58 |59 |60 |61 |62 |63 | * |/ \ / \ / \ / \ / \ / \ / \ / \| |\ / \ / \ / \ / \ / \ / \ / \ /| * |64 |65 |66 |67 |68 |69 |70 |71 | 8 | |65 |66 |67 |68 |69 |70 |71 | | * |\ / \ / \ / \ / \ / \ / \ / \ /| |/ \ / \ / \ / \ / \ / \ / \ / \| * | |73 |74 |75 |76 |77 |78 |79 | | 9 |72 |73 |74 |75 |76 |77 |78 |79 | * |/ \ / \ / \ / \ / \ / \ / \ / \| |\ / \ / \ / \ / \ / \ / \ / \ /| * |80 |81 |82 |83 |84 |85 |86 |87 |10 | |81 |82 |83 |84 |85 |86 |87 | | * |\ / \ / \ / \ / \ / \ / \ / \ /|---|/ \ / \ / \ / \ / \ / \ / \ / \|---- under that, you're dead * | |89 |90 |91 |92 |93 |94 |95 | |11 |88 |89 |90 |91 |92 |93 |94 |95 | * +---------------#---------------+ +---------------#---------------+ (#=canon) * 0 1 2 3 4 5 6 7 p=1 1 2 3 4 5 6 7 * 1 2 3 4 5 6 7 p=-1 0 1 2 3 4 5 6 7 */ /* prototypes */ static void cell_array_neighbor_recompute(CellArray ca); CellArray cell_array_new( int moving_ceiling ) { int i; CellArray ca; ca = (CellArray) xmalloc( sizeof( struct _CellArray )); memset( ca->tagged, 0, sizeof(int)*NB_CELLS ); ca->first_row = 0; ca->parity = 1; ca->moving_ceiling = moving_ceiling; for ( i = 0; i < NB_CELLS; i++ ) ca->cell[i] = EMPTY_CELL; ca->list1 = vector_new( NB_CELLS ); ca->list2 = vector_new( NB_CELLS ); cell_array_neighbor_recompute(ca); return ca; } void cell_array_free( CellArray ca ) { vector_free(ca->list1); vector_free(ca->list2); free(ca); } void cell_array_empty( CellArray ca ) { int i; ca->first_row = 0; for ( i = 0; i < NB_CELLS; i++ ) ca->cell[i] = EMPTY_CELL; } int cell_array_is_empty( CellArray ca ) { int i, first, last; first = first_cell(ca); last = first + COLS - 1; for ( i = first; i <= last; i++ ) if ( ca->cell[i] != EMPTY_CELL ) return 0; return 1; } void cell_array_lower( CellArray ca ) { int i; if ( ca->first_row < ROWS - 1 ) { ca->parity *= -1; for ( i = NB_CELLS-1; i >= first_cell(ca) + COLS; i-- ) ca->cell[i] = ca->cell[ i - COLS ]; for ( i = first_cell(ca); i < first_cell(ca) + COLS; i++ ) ca->cell[i] = EMPTY_CELL; if ( ca->moving_ceiling ) ca->first_row++; } cell_array_neighbor_recompute(ca); } int cell_array_is_overflow( CellArray ca ) { int i; for ( i = NB_CELLS - COLS; i < NB_CELLS; i++ ) if ( ca->cell[i] != EMPTY_CELL ) return 1; return 0; } int cellCL( CellArray ca, int row, int column ) { if (( column < row_start( ca, row) )||( column > COLS-1 )|| ( row < ca->first_row )||( row >= ROWS )) { return OUT_OF_BOUNDS; } return COLS*row + column; } static void cell_array_neighbor_recompute(CellArray ca) { int cell; for ( cell = 0; cell < NB_CELLS; cell++ ) { int column, row, shift; row = cell / COLS; column = cell % COLS; shift = 1 - row_start( ca, row); ca->neighbor[cell][EAST] = cellCL( ca, row, column+1 ); ca->neighbor[cell][WEST] = cellCL( ca, row, column-1 ); ca->neighbor[cell][NORTH_EAST] = cellCL( ca, row-1, column+shift ); ca->neighbor[cell][SOUTH_EAST] = cellCL( ca, row+1, column+shift ); ca->neighbor[cell][NORTH_WEST] = cellCL( ca, row-1, column+shift-1 ); ca->neighbor[cell][SOUTH_WEST] = cellCL( ca, row+1, column+shift-1 ); } } #define neighbor_cell(ca,cell,quadrant) (ca->neighbor[cell][quadrant]) #if 0 int neighbor_cell( CellArray ca, int cell, Quadrant quadrant ) { int column, row, shift; row = cell / COLS; column = cell % COLS; shift = 1 - row_start( ca, row); switch ( quadrant ) { case EAST: column++; break; case WEST: column--; break; case NORTH_EAST: column += shift; row--; break; case SOUTH_EAST: column += shift; row++; break; case NORTH_WEST: column += shift-1; row--; break; case SOUTH_WEST: column += shift-1; row++; break; } return cellCL( ca, row, column ); } #endif void cell_center( CellArray ca, int cell, double *x, double *y) { int column, row; row = cell / COLS; column = cell % COLS; *x = column + 0.5*(1 - row_start(ca, row)); *y = row*ROW_HEIGHT + 0.5; } int floating_cell( CellArray ca, int cell ) { Quadrant q; for ( q = 0; q <= 5; q++ ) if ( cell_not_empty( ca, neighbor_cell( ca, cell, q ))) return 0; return 1; } int find_random_empty_cell( CellArray ca, int from_top ) { int col, column, r, c; /* pick a random column */ column = rnd( COLS ); /* search for target cell */ if (from_top && 0) { for ( r = ROWS-1 ; r > ca->first_row ; r-- ) { /* compute location of cell on upper row */ col = column + row_start( ca, r-1); if ( col >= COLS ) col = COLS - 1; c = col + (r-1)*COLS; /* if it's empty, compute location on this row, and go for it */ if ( ca->cell[c] != EMPTY_CELL ) { col = column + row_start( ca, r); if ( col >= COLS ) col = COLS - 1; c = col + r*COLS; if ( ca->cell[c] == EMPTY_CELL ) return c; } } } else { for ( r = ca->first_row; r < ROWS; r++ ) { col = column + row_start( ca, r); if ( col >= COLS ) col = COLS - 1; c = col + r*COLS; if ( ca->cell[c] == EMPTY_CELL ) return c; } } return OUT_OF_BOUNDS; } extern int xbubble_path_cache[2][ROWS][NB_ANGLES][2][TRAJ_MAX_LENGTH]; int target_cell( CellArray ca, int angle, double *target_y, Vector outpath /* used in player vs computer mode (cf opponent.c)*/ ) { int i; int parity=ca->parity<0?0:1; int ceiling=ca->first_row; #define target_cell_neighbor(i) xbubble_path_cache[parity][ceiling][angle][0][i] #define target_cell_position(i) xbubble_path_cache[parity][ceiling][angle][1][i] if (outpath) vector_empty(outpath); for (i=0; ineighbor->size*/; i++) { if (target_cell_neighbor(i)==OUT_OF_BOUNDS) { /* ceiling encountered */ if (debug) { printf("Stick to top on %d\n", target_cell_position(i) ); fflush(stdout); } if (target_y) *target_y=cell_y(target_cell_position(i)); return target_cell_position(i); } else if (ca->cell[ target_cell_neighbor(i) ] == EMPTY_CELL) { if (debug) printf ("%d ", target_cell_neighbor(i) ); if (outpath) { vector_push( outpath, target_cell_position(i) ); } } else { /* get sticked on an non empty cell */ if (debug) { printf("Stick to %d because of %s %p at %d\n", target_cell_position(i), name_color_get( ca->cell[ target_cell_neighbor(i) ]->color ), ca->cell[ target_cell_neighbor(i) ], target_cell_neighbor(i) ); fflush(stdout); } if (target_y) *target_y=cell_y(target_cell_position(i)); return target_cell_position(i); } } return OUT_OF_BOUNDS; } void hook_cell( CellArray ca, int i) { Quadrant q; if (( cell_not_empty( ca, i))&&( ! ca->tagged[i] )) { ca->tagged[i] = 1; /* hook neighbors */ for ( q = 0; q <= 5; q++ ) hook_cell( ca, neighbor_cell( ca, i, q )); } } int count_floating_bubbles( CellArray ca, Vector floating ) { int i; vector_empty( floating ); /* hook first row and propagate */ for ( i = 0; i < COLS; i++ ) hook_cell( ca, i + first_cell(ca)); /* count floating bubbles */ for ( i = first_cell(ca); i < NB_CELLS; i++ ) if ( ca->cell[i] != EMPTY_CELL ) { if ( ! ca->tagged[i] ) vector_push( floating, i); ca->tagged[i] = 0; } return floating->size; } int count_explosive_bubbles( CellArray ca, int cell, Set explosive, Vector explosion_dates ) { Bubble bubble; Bubble bubble2; Quadrant q; Vector old, new, tmp; int i, c, neighbor, date; old = ca->list1; new = ca->list2; vector_empty(old); vector_empty(new); set_empty(explosive); if ( explosion_dates != NULL ) vector_empty(explosion_dates); date = 1; ca->tagged[cell] = 1; vector_push( old, cell ); while ( old->size > 0 ) { for ( i = 0; i < old->size; i++ ) { c = old->element[i]; bubble = ca->cell[c]; set_add( explosive, bubble ); if ( explosion_dates != NULL ) vector_push( explosion_dates, date ); /* propagate explosion to neighbors */ for ( q = EAST; q <= SOUTH_EAST; q++ ) { neighbor = neighbor_cell( ca, c, q ); if (( neighbor != OUT_OF_BOUNDS )&&( ! ca->tagged[neighbor] )) { bubble2 = ca->cell[neighbor]; if (( bubble2 != EMPTY_CELL )&& ( bubble2->color == bubble->color )) { vector_push( new, neighbor ); ca->tagged[neighbor] = 1; } } } } /* swap lists */ tmp = old; old = new; new = tmp; vector_empty(new); date++; } /* cleanup */ for ( i = 0; i < explosive->size; i++ ) { bubble = explosive->element[i]; ca->tagged[bubble->cell] = 0; } return explosive->size; } #if 0 int count_reacting_bubbles( CellArray ca, Set explosive, Set reacting, Vector destinations ) { int falling_colors[NB_COLORS]; int neighbor_colors[NB_COLORS]; int i; quadrant q; Bubble bubble; Bubble bubble2; Set removed_bubbles; set_empty(reacting); vector_empty(destinations); return 0 if (!explosive->size); memset(falling_colors,0,sizeof(falling_colors)); /* which color can chain-react ? */ for ( i = 0; i < explosive->size; i++ ) { bubble = explosive->element[i]; falling_colors[bubble->color] ++; } /* - tag bubbles that are next to another bubble of the same color - hook all cells (no falling bubble yet) */ for ( cell = first_cell(ca); cell < NB_CELLS; cell++ ) { bubble = ca->cell[cell]; ca->tagged[cell] |= CELL_HOOKED; if ( bubble != EMPTY_CELL ) { for ( q = EAST; q < SOUTH_EAST; q++ ) { neighbor = neighbor_cell( ca, cell, q ); if ( neighbor != OUT_OF_BOUNDS ) { bubble2 = ca->cell[neighbor]; if (( bubble2 != EMPTY_CELL )&& ( falling_colors[ bubble->color ]) { ca->tagged[cell] |= CELL_REACTING; ca->tagged[neighbor] |= CELL_REACTING; } } } } } /* tag empty location next to two balls of the same color or of a ball already tagged */ for ( cell = first_cell(ca); cell < NB_CELLS; cell++ ) { if (ca->cell[cell] == EMPTY_CELL) { memset(neighbor_colors,0,sizeof(neighbor_colors)); for ( q = EAST; q < SOUTH_EAST; q++ ) { neighbor = neighbor_cell( ca, cell, q ); if ( neighbor != OUT_OF_BOUNDS ) { /* next to an exploding and hooked group of a reacting color? */ if ((ca->tagged[ neighbor ] & (CELL_REACTING | CELL_HOOKED))&& (falling_colors[ ca->cell[ neighbor ]->color ])) { ca->tagged[ cell ] |= CELL_REACTING; break; } else { /* 2 neighbor of same color, both hooked ? */ bubble2 = ca->cell[neighbor]; if (( bubble2 != EMPTY_CELL ) && ( falling_colors[ bubble2->color ] )) { neighbor_colors[ bubble2->color ]++; } } } } for ( i=0; i 1) { ca->tagged[ cell ] = 1; break; } } } } /* cleanup */ for ( i = 0; i < NB_CELLS; i++ ) { ca->tagged[i] = 0; } } #endif void dump_array(CellArray ca) { int i, j, k; printf("_________________________________\n"); for (i = 0, k=0; i < NB_CELLS; k++) { if (((k + (ca->parity>0?0:1)) % 2)) { printf("|\\ / \\ / \\ / \\ / \\ / \\ / \\ / \\ /|\n"); printf("| |"); } else { printf("|/ \\ / \\ / \\ / \\ / \\ / \\ / \\ / \\|\n"); printf("|"); } for (j = 0; j < 8; j++, i++) if (!(ca->cell[i] == EMPTY_CELL)) printf(" %i |", ca->cell[i]->state); else if (!((k + (ca->parity>0?0:1)) % 2) || (j!=0)) printf(" |"); if (((k + (ca->parity>0?0:1)) % 2)) { printf(" |\n"); } else { /*if (!((ca->cell[i] == EMPTY_CELL))) printf(" %i |", ca->cell[i]->state); else if (j!=0) printf(" |"); j++; i++;*/ printf("\n"); } } printf("---------------#---------------|\n"); printf(" 0 1 2 3 4 5 6 7 \n"); printf(" 1 2 3 4 5 6 7 \n"); }