Best algorithm for recursive adjacent tiles?

Question

In my game I have a set of tiles placed in a 2D array marked by their Xs and Zs ([1,1],[1,2], etc).

Now, I want a sort of "Paint Bucket" mechanism: Selecting a tile will destroy all adjacent tiles until a condition stops it, let's say, if it hits an object with hasFlag.

Here's what I have so far, I'm sure it's pretty bad, it also freezes everything sometimes:

void destroyAdjacentTiles(int x, int z) {
    int GridSize = Cubes.GetLength(0);
    int minX = x == 0 ? x : x-1;
    int maxX = x == GridSize - 1 ? x : x+1;
    int minZ = z == 0 ? z : z-1;
    int maxZ = z == GridSize - 1 ? z : z+1;

    Debug.Log(string.Format("Cube: {0}, {1}; X {2}-{3}; Z {4}-{5}", x, z, minX, maxX, minZ, maxZ));

    for (int curX = minX; curX <= maxX; curX++) {
        for (int curZ = minZ; curZ <= maxZ; curZ++) {
            if (Cubes[curX, curZ] != Cubes[x, z]) {
                Debug.Log(string.Format("        Checking: {0}, {1}", curX, curZ));
                if (Cubes[curX,curZ] && Cubes[curX,curZ].GetComponent<CubeBehavior>().hasFlag) {
                    Destroy(Cubes[curX,curZ]);
                    destroyAdjacentTiles(curX, curZ);
                }
            }
        }
    }
}

Update: I'm trying the recursive version of the Flood-fill algorithm, but I'm having trouble. In order to check the west adjacent tile, I use x-1, for the east, x+1 etc. Problem is, as soon as x = 0, it will infinitely loop between 0 and 1. I also have to check that that tile exists, so I'm using ifs to figure it out in order to not get an IndexOutOfRangeException (I tried using try/catch, but it's pretty much the same result, I figured this would be simpler). Here's my code right now (yes, I'm reproducing mineSweeper):

bool destroyAdjacentTiles(int x, int z) {
    int GridSize = Cubes.GetLength(0);
    int minX = x == 0 ? x : x-1;
    int maxX = x == GridSize - 1 ? x : x+1;
    int minZ = z == 0 ? z : z-1;
    int maxZ = z == GridSize - 1 ? z : z+1;

    Debug.Log(string.Format("Cube: {0}, {1}; X {2}-{3}; Z {4}-{5}", x, z, minX, maxX, minZ, maxZ));

    CubeBehavior thisCube = Cubes[x, z].GetComponent<CubeBehavior>();

    if (thisCube.isMine) { Destroy(thisCube); Cubes[x,z] = null; return false; } // TO DO: Make this = game over
            // BELOW: Always, no matter what, causes the object to destroy, dunno why. So I removed it for the time being.
    //if (thisCube.surroundingMines >= 1) Destroy(thisCube); return true;

            // if the function doesn't return by now, means it's a to-be-destroyed cube, so destroy it
    //Destroy(thisCube.gameObject);
    //Cubes[x,z] = null;

            //
    if (x > 0) {
        if (Cubes[x-1,z].gameObject) destroyAdjacentTiles(x-1, z);
        if (x < GridSize - 1)
            if (Cubes[x+1,z].gameObject) destroyAdjacentTiles(x+1, z);
    }
    if (z > 0) {
        if (Cubes[x,z-1].gameObject) destroyAdjacentTiles(x, z-1);
        if (z < GridSize - 1)
            if (Cubes[x,z+1].gameObject) destroyAdjacentTiles(x, z+1);
    }

    return true;
}

Answer 1

There's no point in reinventing the wheel. There is an existing algorithm that does what you want. It's called the Flood Fill algorithm. The basic steps from Wikipedia:

Flood-fill (node, target-color, replacement-color):
 1. If the color of node is not equal to target-color, return. 
 2. Set the color of node to replacement-color.
 3. Perform Flood-fill (one step to the west of node, target-color, replacement-color).
     Perform Flood-fill (one step to the east of node, target-color, replacement-color).
     Perform Flood-fill (one step to the north of node, target-color, replacement-color).
     Perform Flood-fill (one step to the south of node, target-color, replacement-color).
  4. Return.

Of course instead of changing colors, you'll be destroying tiles, but the process is the same. Looks like you're trying to do an 8 way flood fill, the algorithm only changes slightly with you checking all 8 orthogonal and diagonal positions instead of the 4 orthogonal like in the pseudo code shown above.

Also keep in mind, when creating recursive algorithms it's very important to have a clearly defined base condition. The reason you program "freezes up" every once in a while is because you're running into an infinite loop. You should be checking that the tile you're about to perform on is neither destroyed nor has the flag.

Depending on the size of your grid (if it were very, very large), you can use a non-recursive algorithm. I don't think you'd run into an issue with stack overflows, so it's not critical. Another method that's more complex, but pretty interesting is the fixed memory method. It would be interesting to implement, but again, I don't imagine you'd run into memory issues.

EDIT

I have simplified your code. You may have been confusing things by trying to change the x and z values depending on where they were. Just globally define the minimum and maximum for your grid, then check against those. You only need to check once if a position is out of bounds. Your base conditions are:

• Square is out of bounds (the first check of x and z compared to their bounds)
• Square is exploded already (I guess you set tiles to null to be exploded)
• Square is not a mine (the tile doesn't have the isMine flag set to true)

If any of those conditions are reached, you're at the bottom of that recursion, so you stop the recursion down that path.

bool destroyAdjacentTiles(int x, int z) {

    if(x<minXBound || x > maxXBound || z < minZBound || z > maxZBound) {
        return false;
    }

    CubeBehavior thisCube = Cubes[x, z].GetComponent<CubeBehavior>();

    if(thisCube == null || !thisCube.isMine)
        return false;

    Destroy(thisCube);
    Cubes[x,z] = null;

    destroyAdjacentTiles(x-1, z);
    destroyAdjacentTiles(x+1, z);
    destroyAdjacentTiles(x, z-1);
    destroyAdjacentTiles(x, z+1);

    return true;
}

Answer 2

You want to try to avoid recursive algorithms in cases like this. It's better to use stack/queue based methods as they are faster and won't cause stack overflows for large areas. This page details and has source examples for both recursive and stack based flood fill algorithms as well as execution speed comparisons: http://lodev.org/cgtutor/floodfill.html