We closed this forum 18 June 2010. It has served us well since 2005 as the ALPHA forum did before it from 2002 to 2005. New discussions are ongoing at the new URL http://forum.processing.org. You'll need to sign up and get a new user account. We're sorry about that inconvenience, but we think it's better in the long run. The content on this forum will remain online.
IndexProgramming Questions & HelpPrograms › recursion issue
Page Index Toggle Pages: 1
recursion issue (Read 1314 times)
recursion issue
Mar 24th, 2010, 1:13pm
 
so im getting a stack overflow error:this sketch is attempting too much recursion error. i understand why but i have no idea how to go about fixing it as i need to recursively check a set of values in an arraylist. any help would be greatly appreciated  Grin the issue is cropping up at the end of my blockcheck() function so you know where to look.

Code:
ArrayList blocks = new ArrayList();
ArrayList adjlocs = new ArrayList();
public int tracer = 0;

void setup(){
 size(960,600);
 for(int i = 0; i< 10;i++){
   for(int x = 0; x< 10;x++){
     blocks.add(new Block(width/2+i*25, height/2+x*25, 25, int(random(0,2))));
   }
 }
 println(blocks.size());
}

void draw(){
 background(0);
 for(int i=0;i<blocks.size();i++){
   Block tempblock = (Block) blocks.get(i);
     if(tempblock.activated == false){
       tempblock.display();
     }
     else{
       tempblock.nodisplay();
     }
   }
 }


void mouseClicked(){
 for(int i=0;i<blocks.size();i++){
   Block tempblock = (Block) blocks.get(i);
     if(dist(mouseX, mouseY, tempblock.blockx, tempblock.blocky) <=12.5){
       tempblock.activated = true;
       println(i);
       blockcheck(i);
     }
   }
 }

class Block{
 public float blockx;
 public float blocky;
 private float blocksize;
 public boolean activated;
 public int type;

 Block(float x, float y, float _blocksize, int _type){
   blockx = x;
   blocky = y;
   blocksize = _blocksize;
   activated = false;
   type = _type;
 }

 void nodisplay(){
   
 }

 void display(){
   if(activated == false){
     strokeWeight(1);
     if(this.type == 0){
       stroke(0,80,250);
     }
     else if(this.type == 1){
       stroke(250,45,45);
     }
   }
   else if(activated == true){
     strokeWeight(2);
     if(this.type == 0){
       stroke(0,80,250);
     }
     else if(this.type == 1){
       stroke(250,45,45);
     }
   }
   if(this.type == 0){
     fill(0,80,250,75);
   }
   else if(this.type == 1){
     fill(250,45,45,75);
   }
   rectMode(CENTER);
   rect(blockx, blocky, blocksize,blocksize);

 }
}

void blockcheck(int pos){
 Block tempblock = (Block) blocks.get(pos);

 //top
 if(pos !=0 && pos%10 != 0){
   Block topblock = (Block) blocks.get(pos-1);
   if(topblock.type == tempblock.type){
     topblock.activated = true;
     adjlocs.add(new Checkint(pos-1));
   }
 }

 //right
 if(pos >= 90){
 }
 else{
   Block rightblock = (Block) blocks.get(pos+10);
   if(rightblock.type == tempblock.type){
     rightblock.activated = true;
     adjlocs.add(new Checkint(pos+10));
   }
 }

 //bottom
 if(pos%10 != 9 ){
   Block bottomblock = (Block) blocks.get(pos+1);
   if(bottomblock.type == tempblock.type){
     bottomblock.activated = true;
     adjlocs.add(new Checkint(pos+1));
   }
 }

 //left
 if(pos <= 9){
 }
 else{
   Block leftblock = (Block) blocks.get(pos-10);
   if(leftblock.type == tempblock.type){
     leftblock.activated = true;
     adjlocs.add(new Checkint(pos-10));
   }
 }

if(adjlocs.size() != 0){
   Checkint tempint = (Checkint) adjlocs.get(0);
   int  newpos = tempint.posvalue;
   //println(adjlocs);
   if(pos == newpos){
     adjlocs.remove(0);
   }

   blockcheck(newpos);
 }

}

class Checkint{
 int posvalue;
 
 Checkint(int temp){
   posvalue = temp;
 }
}
Re: recursion issue
Reply #1 - Mar 24th, 2010, 2:15pm
 
adjlocs can't be global - if it is then adjlocs.get(0) is the same on every iteration = infinite loop. make it local to blockcheck() and adjlocs.get(0) will only be relevant to THIS iteration.

(i've not tested this)
Re: recursion issue
Reply #2 - Mar 24th, 2010, 2:21pm
 
nope, didn't help, same problem, slightly different values.

what is the code meant to be doing? it helps to know what we're meant to be debugging...

seed fill?
Re: recursion issue
Reply #3 - Mar 24th, 2010, 4:53pm
 
what im trying to do is check the adjacent blocks to block you click to see if they are the same color. and if they are i am trying to check the blocks adjacent to each of the ones that is the same, to see if there are others that are the same color. basically trying to make all the blocks of one color that are touching( non-diagonally) disappear
Re: recursion issue
Reply #4 - Mar 24th, 2010, 11:51pm
 
like Minefield? that's a seed fill or a flood fill.

http://en.wikipedia.org/wiki/Flood_fill

which is probably the second most famous recursive algorithm after exponential numbers (but like all recursive stuff is fiddly to implement).

might be easier to use an iterative method rather than a recursive one:

put initial position in a list.

while there are things in the list {
 remove first thing from list
 make it 'disappear'
 add similar coloured neighbours to end of list
}
Re: recursion issue
Reply #5 - Mar 24th, 2010, 11:58pm
 
which, i realise now, is close to what you have. i think you might be mixing the recursive and iterative methods though.

also, what you have to be careful of is

Code:

 A
B C D
 E


looking at C and adding A B D and E but not marking C as processed. then when you look at A you add C back to the list...
Re: recursion issue
Reply #6 - Mar 25th, 2010, 4:31am
 
awesome that should hopefully be enough for me to figure out what it going on, thanks for all your help
Page Index Toggle Pages: 1