patternjavaMinor
Java Connect Four "Four in a row" detection algorithms
Viewed 0 times
connectfourjavaalgorithmsdetectionrow
Problem
I am making a connect four type game for my end of the year project in my programming class. I am about to start building off of the console based version I have made and add a GUI, but I feel sort of if-y about the win algorithms and am wondering if I could improve them. The code for those is below:
```
public void checkWins(int player) {
int count = 0;
vertical: for(int y = 0; y=4) {
System.out.println("Player "+player+" won!");
win = true;
break vertical;
}
} else {
count = 0;
}
}
}
count = 0;
horizontal: for(int x = 0; x=4) {
System.out.println("Player "+player+" won!");
win = true;
break horizontal;
}
} else {
count = 0;
}
}
}
count = 0;
int y = height-1;
int x;
diagonalDownRightA: for(int loop = 0; y>=0; loop++) {
//System.out.println("diagonalDownRightA test "+loop);
x = 0;
int otherY = y;
while(x=4) {
System.out.println("Player "+player+" won!");
win = true;
break diagonalDownRightA;
}
} else {
count = 0;
}
x++;
otherY++;
y = height-1; // fixes skipping rows bug
}
y-=loop;
// start at (0,height-1)
// go up one row, x++ y++ until reached (width-1||height-1)
// go up one row, add one to x and y until reached a point of no return
// repeat above until reached the top
// when done checking for diagonals starting at (0,0)
// go to the next collumn add one to x and y until reached a point of no return
// go to the next collumn add one to x and y until reached a point of no return
// same thing until done
```
public void checkWins(int player) {
int count = 0;
vertical: for(int y = 0; y=4) {
System.out.println("Player "+player+" won!");
win = true;
break vertical;
}
} else {
count = 0;
}
}
}
count = 0;
horizontal: for(int x = 0; x=4) {
System.out.println("Player "+player+" won!");
win = true;
break horizontal;
}
} else {
count = 0;
}
}
}
count = 0;
int y = height-1;
int x;
diagonalDownRightA: for(int loop = 0; y>=0; loop++) {
//System.out.println("diagonalDownRightA test "+loop);
x = 0;
int otherY = y;
while(x=4) {
System.out.println("Player "+player+" won!");
win = true;
break diagonalDownRightA;
}
} else {
count = 0;
}
x++;
otherY++;
y = height-1; // fixes skipping rows bug
}
y-=loop;
// start at (0,height-1)
// go up one row, x++ y++ until reached (width-1||height-1)
// go up one row, add one to x and y until reached a point of no return
// repeat above until reached the top
// when done checking for diagonals starting at (0,0)
// go to the next collumn add one to x and y until reached a point of no return
// go to the next collumn add one to x and y until reached a point of no return
// same thing until done
Solution
Usablity
An issue I see with this algorithm is that it isn't easily transferable to a GUI application. It has
Performance
Nested loops are expensive (however necessary since this is a 2D array), but having 6 of them is overkill. On top of that, the method would probably have to be executed one time for each player, and when it finds four-in-a-row it still continues to look through the rest of the loops. An easier solution is to loop once, and check all around each element. Assuming the loops move along the
A Better Solution
I happen to have made this algorithm once before in a programming contest. It won an award for most creative solution, so hopefully it's credible. I've adapted it for "Connect-4", but originally it was for a "Connect-2".
An issue I see with this algorithm is that it isn't easily transferable to a GUI application. It has
System.out.println() embedded in it, and the return type is void, so the output has been restricted to console-only. To improve this algorithm's usefulness, change the return type to that of a player (int), and then change the parameter to be the board and make it a static method, or remove the parameter and keep it as an instance method. This will alter how the method is called and used. Instead of having to call checkWin for each player, you can do it once and have the method tell you who has won (if anyone).Performance
Nested loops are expensive (however necessary since this is a 2D array), but having 6 of them is overkill. On top of that, the method would probably have to be executed one time for each player, and when it finds four-in-a-row it still continues to look through the rest of the loops. An easier solution is to loop once, and check all around each element. Assuming the loops move along the
board bottom to top & left to right, you would only need to check each position for a win by looking up, up+right, up+left, and right.A Better Solution
I happen to have made this algorithm once before in a programming contest. It won an award for most creative solution, so hopefully it's credible. I've adapted it for "Connect-4", but originally it was for a "Connect-2".
public static int checkWin(int[][] board) {
final int HEIGHT = board.length;
final int WIDTH = board[0].length;
final int EMPTY_SLOT = 0;
for (int r = 0; r = 0 &&
player == board[r+1][c-1] && // look up & left
player == board[r+2][c-2] &&
player == board[r+3][c-3])
return player;
}
}
}
return EMPTY_SLOT; // no winner found
}Code Snippets
public static int checkWin(int[][] board) {
final int HEIGHT = board.length;
final int WIDTH = board[0].length;
final int EMPTY_SLOT = 0;
for (int r = 0; r < HEIGHT; r++) { // iterate rows, bottom to top
for (int c = 0; c < WIDTH; c++) { // iterate columns, left to right
int player = board[r][c];
if (player == EMPTY_SLOT)
continue; // don't check empty slots
if (c + 3 < WIDTH &&
player == board[r][c+1] && // look right
player == board[r][c+2] &&
player == board[r][c+3])
return player;
if (r + 3 < HEIGHT) {
if (player == board[r+1][c] && // look up
player == board[r+2][c] &&
player == board[r+3][c])
return player;
if (c + 3 < WIDTH &&
player == board[r+1][c+1] && // look up & right
player == board[r+2][c+2] &&
player == board[r+3][c+3])
return player;
if (c - 3 >= 0 &&
player == board[r+1][c-1] && // look up & left
player == board[r+2][c-2] &&
player == board[r+3][c-3])
return player;
}
}
}
return EMPTY_SLOT; // no winner found
}Context
StackExchange Code Review Q#127091, answer score: 6
Revisions (0)
No revisions yet.