Search code examples
javarecursionstack-overflow

StackOverflowError from recursive function

I'm trying to make the maze generator from the game Pengo in java and I have some troubles.

I have a class "Cellule" which means Cell in english (sorry I'm french and I didn't think to ask questions to you guys)

public class Cellule{
    int x;
    int y;
    int val;

    public Cellule(int x,int y,int val)
    {
        this.x=x;
        this.y=y;
        this.val=val;
    }

    public int getX() {
        return x;
    }

    public void setX(int x) {
        this.x = x;
    }

    public int getY() {
        return y;
    }

    public void setY(int y) {
        this.y = y;
    }

    public int getVal() {
        return val;
    }

    public void setVal(int val) {
        this.val = val;
    }

}

Then I have a class "Plateau" which means board which contains my cell tab and all the functions to initialise and generate the maze

public class Plateau {
Cellule[][] tab;
int m,n; //doivent etre des nombres impaires/ must be odd numbers
Cellule curPosVer;
Cellule curPosGen;
int verifX;
int verifY;

public Plateau(int m, int n){
    if(m%2==1 && n%2==1){
        this.tab = new Cellule[m][n];
        this.m=m;
        this.n=n;
        this.curPosGen=new Cellule(m-1,0,9);
        this.curPosVer=new Cellule(m-1,0,9);
        this.verifX=0;
        this.verifY=0;
    }
    else{
        System.out.println("Les nombre m et n doivent etre des nombres impaires");
    }
}

void initPlateau(){
    for(int i=0;i<this.m;i++){
        for(int j=0;j<this.n;j++){
            this.tab[i][j]=new Cellule(i,j,1);
        }
    }
    this.tab[m-1][0].setVal(0);
}

void affichePlateau(){
    System.out.println("Test");
     for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            System.out.print(this.tab[i][j].getVal()+" ");
        }
         System.out.println("");
    }
}

/*void pathFinder(){ //cherche un chemin à partir de curCellVer    
      if(this.tab[this.curPosVer.getX()-2][this.curPosVer.getY()].getVal()==0){
          if(this.tab[this.curPosVer.getX()][this.curPosVer.getY()+2].getVal()==0){

          }
      }
}*/

void pathGen(){ //genere un chemin à partir de curPosGen/ generate a path from curPosGen
    int dir;

    while((this.curPosGen.getX()+2<=m-1)&&(this.tab[this.curPosGen.getX()+2][this.curPosGen.getY()].getVal()==1)  ||
          (this.curPosGen.getX()-2>=0)&&(this.tab[this.curPosGen.getX()-2][this.curPosGen.getY()].getVal()==1)  ||
          (this.curPosGen.getY()+2<=n-1)&&(this.tab[this.curPosGen.getX()][this.curPosGen.getY()+2].getVal()==1)  ||
          (this.curPosGen.getY()-2>=0)&&(this.tab[this.curPosGen.getX()][this.curPosGen.getY()-2].getVal()==1)){

        dir=(int)(Math.random()*4);


        switch(dir){
            case 0://Nord
            {
                if(this.curPosGen.getX()-2>=0){
                    if(this.tab[this.curPosGen.getX()-2][this.curPosGen.getY()].getVal()==1){
                        this.tab[this.curPosGen.getX()-1][this.curPosGen.getY()].setVal(0);
                        this.tab[this.curPosGen.getX()-2][this.curPosGen.getY()].setVal(0);
                        this.curPosGen.setX(this.curPosGen.getX()-2);
                    }
                }
            }
            break;

            case 1://Est
            {
                if(this.curPosGen.getY()+2<=this.n){
                    if(this.tab[this.curPosGen.getX()][this.curPosGen.getY()+2].getVal()==1){
                        this.tab[this.curPosGen.getX()][this.curPosGen.getY()+1].setVal(0);
                        this.tab[this.curPosGen.getX()][this.curPosGen.getY()+2].setVal(0);
                        this.curPosGen.setY(this.curPosGen.getY()+2);
                    }
                }
            }
            break;

            case 2://Sud
            {
                if(this.curPosGen.getX()+2<=this.m-1){
                    if(this.tab[this.curPosGen.getX()+2][this.curPosGen.getY()].getVal()==1){
                        this.tab[this.curPosGen.getX()+1][this.curPosGen.getY()].setVal(0);
                        this.tab[this.curPosGen.getX()+2][this.curPosGen.getY()].setVal(0);
                        this.curPosGen.setX(this.curPosGen.getX()+2);
                    }
                }
            }
            break;

            case 3://Ouest
            {
                if(this.curPosGen.getY()-2>0){
                    if(this.tab[this.curPosGen.getX()][this.curPosGen.getY()-2].getVal()==1){
                        this.tab[this.curPosGen.getX()][this.curPosGen.getY()-1].setVal(0);
                        this.tab[this.curPosGen.getX()][this.curPosGen.getY()-2].setVal(0);
                        this.curPosGen.setY(this.curPosGen.getY()-2);
                    }
                }
            }
            break;
        }
        this.pathGen();
    }
}
}

The recursive function which causes the problem is pathGen()

Finally, my main looks like this

public class TestMain {
public static void main(String args[]){
    Plateau p=new Plateau(13,15);
    p.initPlateau();
    p.affichePlateau();
    p.pathGen();
    p.affichePlateau();
}
}

It returns me something like this about 1/10 times

java errors

It would be awesome if you could help me! Thanks a lot

Solution

  • I think that I don't get the complete meaning of your code but as stated by the exception, you are exceeding the capacity of the invocation stack with recursive calls to pathGen.

    Why do you need recursion in this case? You have already defined the condition for ending in the while clause

     while((this.curPosGen.getX()+2<=m-1)&&(this.tab[this.curPosGen.getX()+2][this.curPosGen.getY()].getVal()==1)  ||
      (this.curPosGen.getX()-2>=0)&&(this.tab[this.curPosGen.getX()-2][this.curPosGen.getY()].getVal()==1)  ||
      (this.curPosGen.getY()+2<=n-1)&&(this.tab[this.curPosGen.getX()][this.curPosGen.getY()+2].getVal()==1)  ||
      (this.curPosGen.getY()-2>=0)&&(this.tab[this.curPosGen.getX()][this.curPosGen.getY()-2].getVal()==1)){

    just keep on iterating, without invoking another pathGen().