Infinite loop help, please.

EvilManagedCare

Senior member
Nov 6, 2004
324
0
0
Schoolwork alert! Just looking for explanation, not a solution to the entire thing.

Hi, I am writing a java program. The gist of the following code snippet is a reference to a Cell object that points (ptr) to another Cell object, measures the number of walls in the cell (value numWall) and if it is greater than one will loop. The Cells are arranged in an ArrayList 'in' which means they are part of a maze. They are in order by their Cell id. findReachable Cell returns an integer corresponding to the next reachable cell in the maze not blocked by walls. Anyway, in the following code, I get an infinite loop if I delete the three System.out.println statements, which I didn't really want to include, but I'm willing to if it makes the damn thing work. This is the last part and I have tried various things. What am I overlooking. I am trying to use java references somewhat like a pointer here in C++, but I must be doing it wrong. Yes I know Java doesn't explicitly have pointers. Anyway, thanks for an explanation.

Code:
public void solveMaze(Cell maze[][])
	{
		
				
		Set<Cell> deadEndSet = new TreeSet<Cell>();
				
		Collections.sort(in);
		for (Cell i : in)
		{
			if (i.countCellWalls(i.getWalls()) == 3)
				deadEndSet.add(i);
		}
		
		for (Cell de : deadEndSet)
		{
			Cell ptr = in.get(de.getID());
			
			/*
				 Point to a dead end
			*/
			int numWall;
			do
			{
								
			       if (pathSet.contains(ptr))
                                                pathSet.remove(ptr);
                                             
			          System.out.println("Ptr points to cell " +   ptr.getID());
			          ptr = in.get(findReachableCell(ptr));	
			          System.out.println("Ptr now points to " + ptr.getID());
			          numWall = ptr.countCellWalls(ptr.getWalls());	
			          System.out.println("New value of numWall is        
                                                +  numWall);
			}while (numWall > 1);
			
		}
			
		// ---------------------------------------------------------
		// Copying maze solution to ArrayList.  Maze is solved. 
                          for (Cell s : pathSet)
		{
			// if (in.get(s.getID()).getSymbol() != 'S');
			 in.get(s.getID()).setPath(true);
		}
			
		
		
	}// end solveMaze()
 
Last edited:

degibson

Golden Member
Mar 21, 2008
1,389
0
0
Right off the bat, I see two issues... but since I don't fully understand what is going on, they may or may not be contributing to the problem.

(1)
Code:
System.out.println("New value of numWall is        
                                                +  numWall);"
I'm a little rusty on Java, but I don't think this will compile. The quote is outside the closing paren.

(2)
Code:
if (pathSet.contains(ptr))
			          pathSet.remove(ptr);
			          System.out.println("Ptr points to cell " + ptr.getID());
			          ptr = in.get(findReachableCell(ptr));	
			          System.out.println("Ptr now points to " + ptr.getID());
			          numWall = ptr.countCellWalls(ptr.getWalls());	
			          System.out.println("New value of numWall is        
                                                +  numWall);"
Based on the indentation, it looks like you're trying to put all of this into the if's shadow, but without enclosing braces, only the first statement is shadowed by the if. The intent of this code is unclear to me because of the indentation and/or lack of {}.

Other ideas:
You say that deleting the S.o.pln's causes an infinite loop. Does getID() change the Cell in any way? (i.e., does it have side effects?)
Does the program need all three S.o.pln's to complete, or just one or two of them?
 

PhatoseAlpha

Platinum Member
Apr 10, 2005
2,131
21
81
Can we see your Cell class?

System.out.println shouldn't do anything related to your loop. Which leaves a single suspect, that ptr.getID() is doing more then simply returning a value.
 

Net

Golden Member
Aug 30, 2003
1,592
2
81
will :

numWall = ptr.countCellWalls(ptr.getWalls());

ever be less then 1?

print it out and see:

System.out.println("New value of numWall is: "+ numWall);

More Advice added

You should find the source of an infinite loop in a few seconds if your using your tools correctly.

Are you using eclipse? Click on debug and start stepping, or press play and see where it gets stuck.

You can also pepper the loops where you think its happening with print statements, which ever loop prints a billion times is the one.
Then use your debugger to inspect the values to see why.
 
Last edited:

EvilManagedCare

Senior member
Nov 6, 2004
324
0
0
Thanks for the responses so far. @ degibson, the lack of braces was intended. I pasted the code rather hurredly and some text got distorted. You are right, that one println ()line wouldn't have compiled, I edited it.

As far as getID(), I double checked it, and all it does is return the value for variable id, which will be an int.

Is my syntax for changing which cell reference ptr points to correct? That is,
Cell ptr = in.get(de.getID()); is to start ptr pointing to the Cell in the 'in' ArrayList with the same id as element de from the deadEndSet, then I point to the next adjacent cell with
ptr = in.get(findReachableCell(ptr)); While the cells are being held in different collections, their attributes should be the same, that is, Cell 0 in deadEndSet should have the same attributes as Cell 0 in the ArrayList.
 
Last edited:

sao123

Lifer
May 27, 2002
12,653
205
106
just a curiosity... I feel like you should be doing a recursive depth first search... although i know the algorithm gets complex with a trinary tree, it should be possible.
 

Ken g6

Programming Moderator, Elite Member
Moderator
Dec 11, 1999
16,481
4,329
75
just a curiosity... I feel like you should be doing a recursive depth first search... although i know the algorithm gets complex with a trinary tree, it should be possible.
Personally, to solve a maze, I'd do a breadth-first search, marking the depth as I went, and not following any depth less than the one I was at. Then, once done, I'd do a single search "downhill" from the end (just making sure the numbers count backwards) to the beginning, to find the optimal path.
 

veri745

Golden Member
Oct 11, 2007
1,163
4
81
it's possible that it's not techically in an "infinite loop" but if your algorithm is poor and the maze is large, it might just take a really long time to solve.

I've had that happen where a student implemented an O(2^n) algorithm, and we we're trying to debug his so-called "infinite loop" but couldn't find anything wrong with it.
 

Tech_savy

Member
Nov 18, 2009
111
0
0
Sorry i'm late to the theard.Anyway you have the solution to your problem.

Hey that's a good way of debugging.
 

Sureshot324

Diamond Member
Feb 4, 2003
3,370
0
71
I think we need to see the code for findReachableCell. What do you mean it finds the 'next' reachable cell in the maze? At any point there could be up to 4 ways to go, so how do you decide which to go to next?

while (numWall > 1);

So the loop will keep going until it finds a cell with only 1 or 0 walls? Depending on what findReachableCell does, it could be going back and forth between 2 cells the whole time, never finding one with <= 1 wall.

Also it appears you don't quite grasp Java's pass by reference system. In Java everything is a reference, so when you add a Cell from the 'in' set to the 'deadEndSet', you are adding a reference to the SAME object, NOT a duplicate. So unless I'm missing something, the following statement is useless:

Cell ptr = in.get(de.getID());

ptr and de are the same object, so you could get rid of that statement and just refer to de.