Trouble with recursion

Hi,

I'm working on a flood fill algorithm and half the time pressing the play button causes Unity to crash. I'm guessing it goes into an infinite loop but I can't figure out when. I'm using this on a 2D grid of ints that is filled with 0's and 1's.

Code (CSharp):

1.  
2.      int[,] locations;
3.      static int x = 200;
4.      static int y = 200;
5.      private List<Area> areaList;
6.  
7.     void Start()
8.         {
9.             locations= new int[x, y];
10.             CreateAreas();
11.         }
12.    
13.      private void CreateAreas()
14.         {
15.             for (int i = 0; i < x; i++)
16.             {
17.                 for (int j = 0; j < y; j++)
18.                 {
19.                     if (locations[i, j] == 0)
20.                     {
21.                         Area plate= CreateArea(i, j,new Area());
22.                         areaList.Add(plate);
23.                     }
24.                 }
25.             }
26.     }
27.      private Area CreateArea(int i, int j, Area plate)
28.         {
29.             if (i > x - 1 || i < 0) return plate;
30.             if (j > y - 1 || j < 0) return plate;
31.             if (locations[i, j] == 0)
32.             {
33.                 locations[i, j] = 2;
34.    
35.                 plate.addPiste(i, j);
36.                 CreateArea(i + 1, j, plate);
37.                 CreateArea(i, j + 1, plate);
38.                 CreateArea(i - 1, j, plate);
39.                 CreateArea(i, j - 1, plate);
40.    
41.             }
42.             return plate;
43.         }
44. }
45.  

The Area-class looks like this:

Code (CSharp):

1.  
2. public class Area
3. {
4.  
5.     private List<int[]> list;
6.  
7.     public Area()
8.     {
9.         list= new List<int[]>();
10.     }
11.  
12.     public void addPoint(int x, int y)
13.     {
14.         list.Add(new int[] { x, y });
15.     }
16. }
17.  

The goal would be to have a bunch of "Area"-objects that would contain all the points that belong in that area and I'm certain it's this recursive part that's causing the trouble.

Thanks for any help!

 

Recursion is a pain. Any reason why you have to use recursion?

 

Am I reading this right? You are making a 200x200 array, each cell of which has a 200x200 count of list objects?

If so, you're proposing to do about 1.6 billion operations. Even if you have enough RAM to hold all this (you probably do not!) it's gonna take a pretty long time to run.

Reduce your X,Y size to 5 and 5 and see if it finishes.

To understand recursion, you must first understand recursion.

 

If I'm reading the code properly, it should only make one area for the whole array, which contains a 200x200 length list. But that's still not quick, and that includes 20 or so resize operations. Which could still freeze up a system and make it appear to be an infinite loop.

Working on a small array first is definitely the way to start.

 

In my "game" there is this x*y grid of 0's that is split into smaller areas that are separated by lines of 1's and I thought using recursion would be an "easy" way of creating objects that would contain the coordinates of all the points in a certain area. I have done a few recursion programs that have worked so in theory I should at least have an idea of what I'm doing. Plus I think recursion is quite fascinating and I'd like to use it to learn more about it although I might have to use some other way to get what I want.

Each successful run takes about a second (and the program does some other stuff too) and in the end I have between 10 and 40 Area-objects each of which has between 1 and 10 000 points (The total is less than 40 000). Also looking at the task manager before and after running the memory use increases by about 2MB. But then again, I have no idea what it does while running.

Using a similar code in a project outside Unity on a 200x200 array causes stack overflow exception. Might that also be the case here and if so, why wouldn't Unity tell me about it even though it has thrown stack overflows in my previous attempt?

 

Recursion is fine for many things, but I don't think floodfill is one of them. For a typical floodfill I just use iterations and keep track whether anything changed. So, where 0 is a starting point, -1 is undefined and everything under -1 is not accessible:

Code (csharp):

1.  
2. // Assuming data, width and height are set
3. int [] dx = new int [] {0, 1, 0, -1}; // Horizontal movements
4. int [] dy = new int [] {1, 0, -1, 0}; // Vertical movements
5. bool updated = true;
6. while (updated)
7. {
8.    updated = false;
9.    for (int y = 0;y < height;y++)
10.    {
11.       for (int x = 0;x < width;x++)
12.       {
13.          if (data [x][y] < 0) continue; // Source has no information (yet)
14.          for (int m = 0;m < dx.Length;m++)
15.          {
16.             int x2 = x + dx [m];
17.             if (x2 < 0) continue;
18.             if (x2 >= width) continue;
19.             int y2 = y + dy [m];
20.             if (y2 < 0) continue;
21.             if (y2 >= height) continue;
22.             if (data [x2][y2] < -1) continue; // Target is not accessible
23.             if (data [x][y] + 1 >= data [x2][y2]) continue;
24.             data [x2][y2] = data [x][y] + 1; // (Shorter) path found
25.             updated = true;
26.          }
27.       }
28.    }
29. }
30.  

Code is 100% untested of course.

 

Infinite recursion debugging is where you really want to learn to use a debugger. Debug.Log-printing won't work as the logs won't show up until the method finished, which it never does.

As long as you're writing code in an IDE (MonoDevelop, Visual Studio, etc. (not Notepad++/gedit)), it should be possible. In Visual Studio, the workflow is:
- click in the left margin of your code to create a breakpoint
- click the bug "attach to Unity" button
- run the code.

Now the code will stop executing at your breakpoint, and you'll be able to step through the code line-by-line, and see the values of all variables as you go. That'll give you a really good understanding of how your loop is behaving.

 

A flood fill is basically a breadth first search. Read Introduction to A* from Red Blob Games, specifically the part near the beginning where it discusses breadth first search and shows the algorithm. It doesn't require recursion, it will be easier to debug, and will likely perform better.

 

It is like a breadth first search, but a fairly specific one where it is very easy to keep track of what is already done. A sliding puzzle can also be solved with both breadth first search and A*, but you have to take better care of the states you've visited, since they are not readily available in the data itself. (Only if no answer can be found, the algorithm can end in a continuous loop if the visited states are not blocked.)

So, even though a breadth first search works fine to solve a floodfill, it is not needed to actually know breadth first search. Or even implement it that way. My floodfill code above is certainly not breadth first, it's more like greedy search with good brakes. The good brakes part is the most important here.

Besides that, breadth first search tries to actually find an solution state. Like you've reached the exit of the maze or you've solved this sliding puzzle. In the case of a floodfill, you won't find any solution state. The goal is simply to explore all options.

 

Yeah a better approach would be something like:

Code (csharp):

1.  
2. list = new List<int[]>(10000);
3.  

Or whatever the total count would be... and if it's variable you can then use list.TrimExcess() to get rid of the extra elements. Still "moving" a lot of data and/or pointers but it's a single resize operation.

 

Since we are throwing them up, here is how I typically approach flood fill type problems. I find using the collections and iterating through them makes it much easier to understand.

Code (CSharp):

1. // The collection to investigate
2. List<Node> allNodes;
3. // The collection for the results
4. List<List<Node>> individualAreas;
5.  
6. foreach (Node startNode in allNodes) {
7.     if (!startNode.visited)
8.         List<Node> area = new List<Node>();
9.         individualAreas.Add(area);
10.    
11.         area.Add(node);
12.         startNode.visited = true;
13.  
14.         int index = 0;
15.  
16.         while (index < area.Count){
17.             foreach (Node neighbour in area[index].GetNeighbours()){
18.                 if (!neighbour.visited) {
19.                     area.Add(neighbour);
20.                     neighbour.visited = true;
21.                 }
22.             }
23.             index++;
24.         }
25.     }
26. }