checking if there are four in a row
I'm writing a simple 4-in a row game. I'm having problems making a simple check if the player has a vertical, horiyontal or diagonal group at a spec. position.
the board is an int[][], 42 squares, [7][6] to be exact.
I need some help writing a somewhat effecient method, without a million ifs and switches. The method I've starded with looks something like this:
public boolean isFourInARow(int x, int y) {
//check the directions of the pos board[x][y] if these are groups of 4.
...
return true eller false
}
anybody has a nice solution? Mine is full of ifs and wont even work in the diagonals.
Merry christmas to you all.
[687 byte] By [
_Yonder_a] at [2007-10-2 8:11:26]
I suggest you use a database and a query to look for one of the pattern matches.
>I suggest you use a database and a query to look for one of the pattern matches.
I suggest this is either a joke, or Gargoyle should stick to spouting water off cathedrals.
Lets assume your possible values of each grid location are {0,1,2} where 0 is no data, and 1 and 2 repesent the different players moves (like red and black for Connect Four™). A simple algorithm is to loop over the array, from top to bottom, and left to right. If at any location, a 1 or 2 exists, a further search is needed. This search uses three directions, right, down right, and down. If the next three moves in any of these directions yields the same value as the starting point, there are four in a row.
My search was implemented in 28 lines of code.
☮
Yep, thanks. Database is one way, but I think it's a bit overkill here. Hmm and about the searching, wouldnt it be faster to just check around the actual position that i put a brick in? Since nowhere else would change than exactly where I put the brick. And with the method you suggest, I'm not sure how to do the diagonals. Is it possible to do this recursivly maybe as well?
>wouldnt it be faster to just check around the actual position that i put a brick in?
Correct, it would be an optimization, but to check a small array each time costs virtually nothing. If checking only each added brick, you would need to expand the search in all 8 directions.
> I'm not sure how to do the diagonals.
0 1
0 X
1X
If theres a X at 0,0 and you want to check on 1,1, you add 1 to both x and y.
>Is it possible to do this recursivly maybe as well?
Sure, though its probably more work.
> Yep, thanks. Database is one way, but I think it's a> bit overkill here.You are right.
class MerryChristmas {
static int i, j, n, in;
static int[][] data = {
{ 1, 0, 0, 0, 0, 0 },
{ 0, 1, 0, 0, 0, 0 },
{ 0, 0, 1, 0, 0, 1 },
{ 0, 0, 1, 0, 1, 0 },
{ 0, 0, 0, 1, 0, 0 },
{ 0, 0, 1, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0 }
};
public static void main( String[] argcv){
System.out.println(checkAll( 3 , 4 ));
}
public static int checkAll(int x, int y){
if(checkRow( x, y ) == 1 || checkColumn( x, y ) == 1
|| checkDiagonal( x , y ) == 1 || checkDiagonalReverse( x, y) == 1 ) return 1;
else
return 0;
}
public static int checkRow(int x, int y){
n = 0;
in = 0;
for( i = 0; i < 6 ; i++ ){
if(data[ x ][ i ] == 1){
n++;
if( y == i ) in = 1;
if( n == 4 ) return (in == 1 ? 1 : 0);
}
else{
if(n != 0){
n--;
in = 0;
}
}
}
return 0;
}
public static int checkColumn(int x, int y){
n = 0;
in = 0;
for( i = 0; i < 7 ; i ++ ){
if(data[ i ][ y ] == 1){
n++;
if( x == i ) in = 1;
if( n == 4 ) return (in == 1 ? 1 : 0);
}
else{
if(n != 0){
n--;
in = 0;
}
}
}
return 0;
}
///////////////////////////////////////////////////////////////////////////////
public static int checkDiagonal(int x, int y){
n = 0;
int a, b, inc;
in = 0;
if( x > y){
a = x - y;
b = 0;
inc = 7 - a;
for( i = 0; i < inc ; i ++ ){
if(data[ a + i ][ b + i] == 1){
n++;
if( x == (a + i) && y == (b + i)) in = 1;
if( n == 4 ) return (in == 1 ? 1 : 0);
}
else{
if(n != 0){
n--;
in = 0;
}
}
}
}
if( x <= y){
a = 0;
b = y - x ;
inc = 6 - b;
for( i = 0; i < inc ; i++ ){
if(data[ a + i ][ b + i] == 1){
n++;
if( x == (a + i) && y == (b + i)) in = 1;
if( n == 4 ) return (in == 1 ? 1 : 0);
}
else{
if(n != 0){
n--;
in = 0;
}
}
}
}
return 0;
}
///////////////////////////////////////////////////////////////////////////////
public static int checkDiagonalReverse(int x, int y){
n = 0;
int a, b, inc;
in = 0;
if((x + y ) <= 5){
a = x + y;
for (int i = 0; i < a + 1; i++ ){
if(data[ a - i ][ i ] == 1){
n++;
if( x == (a - i) && y == i) in = 1;
if( n == 4 ) return (in == 1 ? 1 : 0);
}
else{
if(n != 0){
n--;
in = 0;
}
}
}
}
if((x + y ) > 5){
a = 6 - x;
b = y - a;
inc = a + ( 5 - y);
for (int i = 0; i < inc + 1 ; i++ ){
if(data[ 6 - i ][ b + i ] == 1){
n++;
if( x == (6 - i) && y == (b + i)) in = 1;
if( n == 4 ) return (in == 1 ? 1 : 0);
}
else{
if(n != 0){
n--;
in = 0;
}
}
}
}
return 0;
}
///////////////////////////////////////////////////////////////////////////////
}
> I suggest this is either a joke, or Gargoyle should> stick to spouting water off cathedrals.Not intended as a joke. Must be the cold nights! Sorry. I got a bit carried away with MySQL 5.0 I think!
Thanks everybody, with the help of you all I came up with the following solution (if somebody is doing the same): the board is represented in an array instead of a matrix. Element x,y is acessed: board[x+y*7]
public boolean hasFourInARow(short x, short y) {
if (board[x+y*7] == 0)
return false;
//check horizontal
for(int i = 0; i <= 3; i++)
if (inRow(board[i+y*7], board[(i+1)+y*7], board[(i+2)+y*7], board[(i+3)+y*7]))
return true;
//check vertical
for(int i = 0; i <= 2; i++)
if (inRow(board[x+i*7], board[x+(i+1)*7], board[x+(i+2)*7], board[x+(i+3)*7]))
return true;
//check diagonal\
for(int i = 0; i <= 3; i++)
for(int j = 0; j <= 2; j++)
if (inRow(board[i+j*7], board[(i+1)+(j+1)*7], board[(i+2)+(j+2)*7], board[(i+3)+(j+3)*7]))
return true;
//check diagonal/
for(int i = 3; i <= 6; i++)
for(int j = 0; j <= 2; j++)
if (inRow(board[i+j*7], board[(i-1)+(j+1)*7], board[(i-2)+(j+2)*7], board[(i-3)+(j+3)*7]))
return true;
return false;
}
public boolean inRow(short a, short b, short c, short d) {
return a != 0 && a == b && b == c && c == d;
}
