Minesweeper Clearing Algorithm

Question

I'm attempting to recreate Minesweeper in flash for a project and I've gotten as far as placing mines and numbers. I can't seem to figure out the recursive algorithm for the expansion of clicking on a tile and clearing its neighbors. There are two arrays, _map holds the background + mines & numbers, _clickable map holds the tiles that sit on top of the background. So basically, what I'm asking for is help with recursion. If this isn't clear enough, I'll update the question with necessary information.

private function onClick(e:MouseEvent):void 
{
    trace("on Click");

    var symbol = e.currentTarget;
    var tempTileMask:TileMask = symbol;
    var tempTile:Tile = _map[tempTileMask.yCoord][tempTileMask.xCoord]

    if (tempTile.hasMine)
    {
        for (var i:int = _gridSize - 1; i >= 0; i--)
            for (var j:int = _gridSize - 1; j >= 0; j--)
            {
                var temp:TileMask = _clickableMap[i][j];
                removeChild(temp);
            }

        //explosion();

        //gameOver();
    }

    if (tempTile.hasNumber)
    {
        removeChild(tempTileMask);
        tempTile.cleared = true;
    }

    else
    {
        clearTiles(tempTile.xCoord, tempTile.yCoord);
    }
}

This is the function I modified to clear mines

function clearTiles( x:int, y:int )
{
    // Get an object that contains the tile information for the location
    // we are checking
    if(_map[y][x] != null) 
    {
        var tempTile:Tile = _map[y][x];
        var tempTileMask:TileMask = _clickableMap[y][x];

        // Check if the location we are checking is out of the bounds of the
        // playable area

        trace(tempTile);
        if ( tempTile.outOfBounds(x, y) )
        {
            return;
        }

        // If the tile has already been revealed then there is nothing to do

        trace("before clearing");
        if ( tempTile.cleared )
        {
            trace("clearing tile");
            return;
        }

        // If the tile hasn't been revealed and it's an empty square we
        // reveal the location then call this function again for each
        // surrounding block

        trace("before check for surrounding tiles");
        if ( tempTile.hasNumber != true && tempTile.hasMine != true )
        {
            trace("check for surrounding tiles");

            // Remove the mask hiding the tiles property
            removeChild( tempTileMask );
            // Set the tile as cleared
            tempTile.cleared = true;

            if(_map[tempTile.yCoord][tempTile.xCoord - 1] != null)
            {
                var tile1:Tile =_map[tempTile.yCoord][tempTile.xCoord - 1]

                if(!tile1.cleared)
                    clearTiles( tempTile.xCoord - 1 , tempTile.yCoord ); //Check tile to the left
            }

            if(_map[tempTile.yCoord][tempTile.xCoord + 1] != null)
            {
                var tile2:Tile =_map[tempTile.yCoord][tempTile.xCoord + 1]

                if(!tile2.cleared)
                    clearTiles( tempTile.xCoord + 1 , tempTile.yCoord ); //Check tile to the left
            }

            if(_map[tempTile.yCoord - 1][tempTile.xCoord] != null)
            {
                var tile3:Tile =_map[tempTile.yCoord - 1][tempTile.xCoord]

                if(!tile3.cleared)
                    clearTiles( tempTile.xCoord, tempTile.yCoord - 1 ); //Check tile to the left
            }

            if(_map[tempTile.yCoord + 1][tempTile.xCoord] != null)
            {
                var tile4:Tile =_map[tempTile.yCoord + 1][tempTile.xCoord]

                if(!tile4.cleared)
                    clearTiles( tempTile.xCoord, tempTile.yCoord + 1 ); //Check tile to the left
            }

            if(_map[tempTile.yCoord - 1][tempTile.xCoord - 1] != null)
            {
                var tile5:Tile =_map[tempTile.yCoord - 1][tempTile.xCoord - 1]

                if(!tile5.cleared)
                    clearTiles( tempTile.xCoord - 1, tempTile.yCoord - 1 ); //Check tile to the left
            }

            if(_map[tempTile.yCoord + 1][tempTile.xCoord + 1] != null)
            {
                var tile6:Tile =_map[tempTile.yCoord + 1][tempTile.xCoord + 1]

                if(!tile6.cleared)
                    clearTiles( tempTile.xCoord + 1, tempTile.yCoord + 1 ); //Check tile to the left
            } 

            if(_map[tempTile.yCoord - 1][tempTile.xCoord + 1] != null)
            {
                var tile7:Tile =_map[tempTile.yCoord - 1][tempTile.xCoord + 1]

                if(!tile7.cleared)
                    clearTiles( tempTile.xCoord + 1, tempTile.yCoord - 1 ); //Check tile to the left
            }


            if(_map[tempTile.yCoord + 1][tempTile.xCoord - 1] != null)
            {
                var tile8:Tile =_map[tempTile.yCoord + 1][tempTile.xCoord - 1]

                if(!tile8.cleared)
                    clearTiles( tempTile.xCoord - 1, tempTile.yCoord + 1 ); //Check tile to the left
            }
        }
    }
    else
        return;

}

Answer 1

Please forgive if I screw up actionscript syntax. I just love recursive functions so I had to answer this. I'll just paste the code with the most accurate comments I can muster. If you have questions please ask. I'm sure you can convert anything you need to the appropriate function calls, property references etc.

// Function to check if a tile is an empty space and then call
// itself for the surrounding tiles

function clearTiles( x:int, y:int ):void
{
    // Check if the location we are checking is out of the bounds of the
    // playable area
    if ( outOfBounds( x, y ) )
    {
        return;
    }

    // Get an object that contains the tile information for the location
    // we are checking
    var tempTile:Tile = _map[x][y];


    // If the tile has already been revealed then there is nothing to do
    if ( tempTile.cleared )
    {
        return;
    }

    // If the tile is a number then reveal it and return without checking
    // surrounding tiles
    var tempTileMask:DisplayObject = getTileMask(x,y);
    // since we're no longer in the click handler context, we need
    // to initialize the variable with something [TODO]
    if ( tempTile.hasNumber )
    {
        removeChild( tempTileMask );
        tempTile.cleared = true;
        return;
    }


    // If the tile hasn't been revealed and it's an empty square we
    // reveal the location then call this function again for each
    // surrounding block

    if ( tempTile.isEmpty )
    {
        // Remove the mask hiding the tiles property
        removeChild( tempTileMask );
        // Set the tile as cleared
        tempTile.cleared = true;

        clearTiles( tempTile.x - 1 , tempTile.y ); //Check tile to the left
        clearTiles( tempTile.x + 1 , tempTile.y ); //Check tile to the right
        clearTiles( tempTile.x , tempTile.y - 1 ); //Check tile above
        clearTiles( tempTile.x , tempTile.y + 1 ); //Check tile below
    }

}

You'll have to create an outOfBounds() function to just check if the X and Y being checked are larger than the current game board. It looks like you reference _gridSize as a static number, so I assume all of your game boards are squares (ex: 4x4, 9x9, 120x120). In which case you can use something like this:

function outOfBounds( int x, int y )
{
    if ( x < 0 )
    {
        return true;
    }

    if ( y < 0 )
    {
        return true;
    }

    if ( x > _gridSize - 1 )
    {
        return true;
    }

    if ( y > _gridSize -1 )
    {
        return true;
    }

    return false;
}