-
Connect 5 Algorithm in C
Hi,
I'm making a connect 5 kind of game with a two-dimensional array. I have the board all set up but I'm trying to figure out the best way to check if there is 5 in a row up,down or diagonal. It should start checking with the chip that was just placed on the board. Any suggestions?? Thanks.
-
Assuming you check each time a chip is placed, and start with an empty board, yes just checking from the chip that was placed will reveal if a win is present.
-
Well, you have a 2D array - lets call them X and Y, so the dim is (X,Y).
When a chip is placed, first look at X. See how many chips are to the left of the chip. Something like
start_of_run = chip.x ;
for (i = chip.x-1, i >= 0 && (i,Y) == a_chip ; i--) start_of_run = i ;
Then go to the right
end_of_run = chip.x ;
for (i = start_of_run ; i <= max(X) && (i,Y) == a_chiip ; i++ ) end_of_run = i ;
To see if 5 in a row,
if (end_of_run - start_of_run >= 5) winner!
and so on.
For the diagonal, you'll have to increment x & y, AND, decrement X & Y to check bottom left to top right. For top left to bottom right, you'll have to decrement x & increment Y, AND, increment X and decrement Y.
Get it?
-
So you're writing a Gomoku game then?
To check for 5 in a row you just need some loop. For each of the 8 directions set up some deltas between -1 and 1 for each of the x and y directions, then loop in that direction until you hit an edge or you've iterated overy 5 pieces.
Something roughly like:
Code:
static const int xdirs[] = {0,1,1,1,0,-1,-1,-1};
static const int ydirs[] = {-1,-1,0,1,1,1,0,-1};
for (int i=0; i<8; ++i)
{
int x = startx, y = starty, numInARow=0;
for (int j = 0; j < 5 && IsWithinBoard(x, y); ++j)
{
// *** Test this cell here, maybe increment numInARow ***
x += xdirs[i];
y += ydirs[i];
}
}
Just give it a shot and see how you go.