4
\$\begingroup\$

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<height; y++) {
        //System.out.println("Vertical test "+y+" of "+height+"-1");
        for(int x=0; x<width; x++) {
            if(board[x][y] == player) {
                count++;

                if(count>=4) {
                    System.out.println("Player "+player+" won!");
                    win = true;
                    break vertical;
                }
            } else {
                count = 0;
            }
        }
    }

    count = 0;

    horizontal: for(int x = 0; x<width; x++) {
        //System.out.println("Horizontal test "+x+" of "+width+"-1");
        for(int y = 0; y<height; y++) {
            if(board[x][y] == player) {
                count++;    // If there is a break in this code, count will be reset

                if(count>=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<=width-1 && otherY<=height-1) { // Go diagonally right downwards
            //System.out.println("dDRA testing at "+x+","+otherY);
            if (board[x][otherY] == player) {
                count++;
                //System.out.println("Found a result, count++");
                if(count>=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
    }

    count = 0;

    x = width-1;
    diagonalDownRightB: for(int loop = 0; x>=0; loop++) {
        //System.out.println("diagonalDownRightB test "+loop);
        y = 0;
        int otherX = x; // =x

        while(y<=height-1 && otherX<=width-1) { // Go diagonally right downwards for other half of the board
            //System.out.println("dDRB testing at "+otherX+","+y);
            if (board[otherX][y] == player) {
                count++;

                if(count>=4) {
                    System.out.println("Player "+player+" won!");
                    win = true;
                    break diagonalDownRightB;
                }
            } else {
                count = 0;
            }
            y++; 
            otherX++;
            x = width-1;
        }
    x-=loop;
    }

    y = height-1;

    diagonalDownLeftA: for(int loop = 0; y>=0; loop++) {
        //System.out.println("diagonalDownLeftA test "+loop);
        x = width-1;

        int otherY = y;

        while(x>=0 && otherY<=height-1) {
            //System.out.println("dDLA testing at "+x+","+otherY);
            if (board[x][otherY] == player) {
                count++;
                //System.out.println("Found a result, count++");
                if(count>=4) {
                    System.out.println("Player "+player+" won!");
                    win = true;
                    break diagonalDownLeftA;
                }
            } else {
                count = 0;
            }
            x--; 
            otherY++;
            y = height-1; // fixes skipping rows bug
        }
        y-=loop;
    }

    count = 0;

    x = width-1;
    diagonalDownLeftB: for(int loop = 0; x>=0; loop++) {
        //System.out.println("diagonalDownLeftB test "+loop);
        y = 0;
        int otherX = x;

        while(y<=height-1 && otherX>=0) {
            //System.out.println("dDLB testing at "+otherX+","+y);
            if (board[otherX][y] == player) {
                count++;

                if(count>=4) {
                    System.out.println("Player "+player+" won!");
                    win = true;
                    break diagonalDownLeftB;
                }
            } else {
                count = 0;
            }
            y++; 
            otherX--;
            x = width-1;
        }
        x-=loop;
    }
}
}
\$\endgroup\$
4
\$\begingroup\$

Usablity

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 < 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
}
\$\endgroup\$
  • \$\begingroup\$ I have never used 'continue' before in my code, so I ran a quick google search and found that it does save a lot of execution time on this algorithm, so thanks for showing me that! \$\endgroup\$ – Smarticles101 Apr 29 '16 at 23:38
  • \$\begingroup\$ Yeah, a continue is like a break, but it's used to skip over a single iteration instead of the whole loop. It's necessary here for functionality so that it won't see 4-in-a-row of empty slots and think it's a win. \$\endgroup\$ – 4castle Apr 29 '16 at 23:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.