StackOverFlowError...
So you may remember my post about making ConnectFour, everything was going well until I decided to abandon lots of for loops for some recursion. I'm a little sloppy on my recursion but I did come up with something, unfortunately it gives me a StackOverFlowError. Heres the main code. Basically, given a move, I check to see if theres four in a row in any direction.
publicint checkVertical(Piece p,int row,int col)
{
if(!isValid(row,col)||isEmpty(row,col)||!pieceAt(row,col).getColor().equals(p.getColor()))
return 0;
return 1 + checkVertical(p,row-1,col)+checkVertical(p,row+1,col);
}
publicint checkHorizontal(Piece p,int row,int col)
{
if(!isValid(row,col)||isEmpty(row,col)||!pieceAt(row,col).getColor().equals(p.getColor()))
return 0;
return 1 + checkHorizontal(p,row,col-1)+checkHorizontal(p,row,col+1);
}
publicint checkMajor(Piece p,int row,int col)
{
if(!isValid(row,col)||isEmpty(row,col)||!pieceAt(row,col).getColor().equals(p.getColor()))
return 0;
return 1 + checkMajor(p,row+1,col+1)+checkHorizontal(p,row-1,col-1);
}
publicint checkMinor(Piece p,int row,int col)
{
if(!isValid(row,col)||isEmpty(row,col)||!pieceAt(row,col).getColor().equals(p.getColor()))
return 0;
return 1 + checkMinor(p,row+1,col-1)+checkHorizontal(p,row-1,col+1);
}
publicboolean winningMove(Piece p)
{
if(checkMinor(p,p.row(),p.col()) >=4 || checkMajor(p,p.row(), p.col()) >=4 || checkHorizontal(p, p.row(),p.col())>=4 || checkVertical(p, p.row(),p.col())>=4)
returntrue;
returnfalse;
}
Message was edited by:
JFactor2004
The problem is that every time one of these methods calls itself with different parameters, the method receiving different parameters calls the original again.
For example:
public int checkVertical(Piece p,int row,int col)
{
if( !isValid(row,col) || isEmpty(row,col) ||
!pieceAt(row, col).getColor().equals(p.getColor()) )
return 0;
return 1 + checkVertical(p,row-1,col)+checkVertical(p,row+1,col);
}
If the current piece (i.e. the piece currently being checked) passes the "if(...)" test, checkVertical will call itself again to test the piece above the current piece. Assume the current piece is at row 5. The first part of the return statement says "checkVertical( p, row - 1, col )". This will call checkVertical again with a new location for the current piece at row 4 (since the call just subtracts one from the current row). The problem is when this method, with the current piece at row 4, reaches the second part of its return statement, which says "checkVertical( p, row + 1, col)". This will invoke checkVertical for a third time, only this time with a row argument of 5. This third invocation with a row argument of 5 will invoke checkVertical again, identically to the way it did originally. This will repeat over and over until the stack overflows with too many stack frames. This problem appears to be present in at least one of your other methods as well (checkHorizontal) and possibly checkMajor and checkMinor as well.
Now that you know the problem, there is at least one easy solution. You can methods checkUp and checkDown which each only recurse in one direction (for example, with a return statement like "return 1 + checkUp(p, row - 1, col) + checkDown(p, row - 1, col)"). You can also create checkLeft and checkRight to fix checkHorizontal.
I'm not sure I did to good a job of explaining this, please let me know if anything is still unclear.
@modia at 2007-7-12 20:32:55 >
Just quickly eyeballing your code suggests that you are creating a little chain reaction. There are times and places for recursion, and this is probably not one of them. solution: don't do this recursively.
Also realize that you only have to check whether the newly added disk causes a win. This means looking both ways horizontally, but only looking down on the vertical axis (nothing will be above the newly added disk) and only looking down on both right and left angle axises(what's the pleural of axis?).
A basic rule of programming: don't do any more work than you have to!
For instance, here's part of the code of how I am checking for a win:
public enum Connect4Color
{
EMPTY,
YELLOW,
RED;
}
public class Connect4Grid
{
public static final int MAX_ROW = 6;
public static final int MAX_COL = 7;
//2-D grid of cells starting at 0,0 at left lower corner
private Connect4Cell[][] grid; // 2D array of cells (which have row, col and color fields)
public Connect4Grid()
..............
..............
..............
..............
..............
// called after piece added to grid at location (row, col)
public boolean checkIfWin(int row, int col)
{
return checkIfVerticalWin(row, col) ||
checkIfHorizWin(row, col) ||
checkIfRightAngleWin(row, col) ||
checkIfLeftAngleWin(row, col);
}
/**
* march down the rows to see if 4 colors in a row for a win.
* @param row, col
* @return true if 4 vertical discs in row w/ same color
*/
private boolean checkIfVerticalWin(int row, int col)
{
Connect4Color winningColor = grid[row][col].getColor();
if (winningColor == Connect4Color.EMPTY)
{
return false;
}
else if (row < 3) // if 3 or less in row, it can't be a winner
{
return false;
}
else
{
boolean temp = true;
for (int myRow = row; myRow > row - 4; myRow--)
{
temp &= (winningColor == grid[col][myRow].getColor());
}
return temp;
}
}
private boolean checkIfHorizWin(int row, int col)
..............
..............
..............
}
Thanks for the tips guys, I'll let you know how it works
Well I got rid of the StackOverFlow error but now its not working right. Its finding a win before there is one. I put in print statements to see where it finds the win but, when it finds one, for some reason it doesn't print true;
public int checkDown(Piece p,int row,int col)
{
if(!isValid(row,col)||isEmpty(row,col)||!pieceAt(row,col).getColor().equals(p.getColor()))
return 0;
return 1 + checkDown(p,row-1,col);
}
public int checkRight(Piece p,int row, int col)//goes with checkLeft
{
if(!isValid(row,col)||isEmpty(row,col)||!pieceAt(row,col).getColor().equals(p.getColor()))
return 0;
return 1 + checkRight(p,row,col+1);
}
public int checkLeft(Piece p,int row, int col)//goes with checkRight
{
if(!isValid(row,col)||isEmpty(row,col)||!pieceAt(row,col).getColor().equals(p.getColor()))
return 0;
return 1 + checkLeft(p,row,col-1);
}
public int checkUpRight(Piece p,int row, int col)//goes with checkDownLeft
{
if(!isValid(row,col)||isEmpty(row,col)||!pieceAt(row,col).getColor().equals(p.getColor()))
return 0;
return 1 + checkUpRight(p,row+1,col+1);
}
public int checkDownLeft(Piece p,int row, int col)//goes with checkUpRight
{
if(!isValid(row,col)||isEmpty(row,col)||!pieceAt(row,col).getColor().equals(p.getColor()))
return 0;
return 1 + checkUpRight(p,row-1,col-1);
}
public int checkUpLeft(Piece p,int row, int col)//goes with checkDownRight
{
if(!isValid(row,col)||isEmpty(row,col)||!pieceAt(row,col).getColor().equals(p.getColor()))
return 0;
return 1 + checkUpLeft(p,row+1,col-1);
}
public int checkDownRight(Piece p,int row, int col)//goes with checkUpLeft
{
if(!isValid(row,col)||isEmpty(row,col)||!pieceAt(row,col).getColor().equals(p.getColor()))
return 0;
return 1 + checkDownRight(p,row-1,col+1);
}
public boolean winningMove(Piece p)
{
if(checkDown(p,p.row(),p.col()) >=4 || checkRight(p,p.row(), p.col())+checkLeft(p,p.row(), p.col())>=4 || checkDownLeft(p, p.row(),p.col())+checkUpRight(p, p.row(),p.col())>=4 || checkDownRight(p, p.row(),p.col())+checkUpLeft(p, p.row(),p.col())>=4)
return true;
System.out.println(checkDown(p,p.row(),p.col()) >=4 );
System.out.println(checkRight(p,p.row(), p.col())+checkLeft(p,p.row(), p.col())>=4);
System.out.println( checkDownLeft(p, p.row(),p.col())+checkUpRight(p, p.row(),p.col())>=4);
System.out.println(checkDownRight(p, p.row(),p.col())+checkUpLeft(p, p.row(),p.col())>=4);
return false;
}
Not sure. Where does the false win come from? down? left-right? diagonal check?Though I do have to note that I'm seeing more OOP in your code, and that is a very good thing. Keep it up!Message was edited by: petes1234
another suggestion is to extract out a common function:
public boolean colorMatch(Piece p, int row, int col)
{
return (!isValid(row, col) || isEmpty(row, col) || !grid[row][col].getColor().equals(p.getColor()));
}
public int checkDown(Piece p, int row, int col)
{
if (colorMatch(p, row, col))
{
return 0;
}
else
{
return (1 + checkDown(p, row - 1, col));
}
}
public int checkRight(Piece p,int row, int col) //goes with checkLeft
{
if (colorMatch(p, row, col))
{
return 0;
}
else
{
return (1 + checkRight(p,row,col+1));
}
}
Problem: I'm thinking that you are counting the piece twice in the right-left and angle counts.
Do it like so:
if(
checkDown(p,p.row(),p.col()) >= 4 ||
checkRight(p,p.row(), p.col())+checkLeft(p,p.row(), p.col()) > 4 ||
checkDownLeft(p, p.row(),p.col())+checkUpRight(p, p.row(),p.col()) > 4 ||
checkDownRight(p, p.row(),p.col())+checkUpLeft(p, p.row(),p.col()) > 4)
{
return true;
}
Where you change the "> = 4" to "> 4" for the last 3 inequality checks. This will cancel out the adding piece twice to the sum in those situations.
Thanks for the help btw...I saw how it could have added an extra one so I used the >4 but now it doesn't record any wins at all
Well ok this is weird, I fixed some stuff so it records wins everywhere except the major diagonal which makes no sense b/c the code is all the same
public int checkDown(Piece p,int row,int col)
{
if(!isValid(row,col)||isEmpty(row,col)||!pieceAt(row,col).getColor().equals(p.getColor()))
return 0;
return 1 + checkDown(p,row-1,col);
}
public int checkRight(Piece p,int row, int col)//goes with checkLeft
{
if(!isValid(row,col)||isEmpty(row,col)||!pieceAt(row,col).getColor().equals(p.getColor()))
return 0;
return 1 + checkRight(p,row,col+1);
}
public int checkLeft(Piece p,int row, int col)//goes with checkRight
{
if(!isValid(row,col)||isEmpty(row,col)||!pieceAt(row,col).getColor().equals(p.getColor()))
return 0;
return 1 + checkLeft(p,row,col-1);
}
public int checkUpRight(Piece p,int row, int col)//goes with checkDownLeft
{
if(!isValid(row,col)||isEmpty(row,col)||!pieceAt(row,col).getColor().equals(p.getColor()))
return 0;
return 1 + checkUpRight(p,row+1,col+1);
}
public int checkDownLeft(Piece p,int row, int col)//goes with checkUpRight
{
if(!isValid(row,col)||isEmpty(row,col)||!pieceAt(row,col).getColor().equals(p.getColor()))
return 0;
return 1 + checkUpRight(p,row-1,col-1);
}
public int checkUpLeft(Piece p,int row, int col)//goes with checkDownRight
{
if(!isValid(row,col)||isEmpty(row,col)||!pieceAt(row,col).getColor().equals(p.getColor()))
return 0;
return 1 + checkUpLeft(p,row+1,col-1);
}
public int checkDownRight(Piece p,int row, int col)//goes with checkUpLeft
{
if(!isValid(row,col)||isEmpty(row,col)||!pieceAt(row,col).getColor().equals(p.getColor()))
return 0;
return 1 + checkDownRight(p,row-1,col+1);
}
public boolean winningMove(Piece p)
{
if(checkDown(p,p.row(),p.col()) >=4 || checkRight(p,p.row(), p.col())+checkLeft(p,p.row(), p.col())>4 || checkDownLeft(p, p.row(),p.col())+checkUpRight(p, p.row(),p.col())>4 || checkDownRight(p, p.row(),p.col())+checkUpLeft(p, p.row(),p.col())>4)
return true;
return false;
}
again, extract out the method as I mentioned above.Also, check out checkDownLeft in greater detail. It does not call itself recursively as it should.
Weird, I knew I copy pasted something wrong and I was staring right at it and didn't notice til now...
