Search code examples
c++stack-overflowdepth-first-search

What can cause a Stack Overflow in this function?


I was writing a casual minesweeper, and wanted to realize a method to track an empty cells at the field, so I had wrote this algorothm:

//bigger array was taken to prevent out of range,when init mines and numbers
 /*creating mines in 1 to FIELD_NUM range(0 -non-active field,1-active field)
 * {
 *  0   0   0   0   0   0
 *  0   1   1   1   1   0
 *  0   1   1   1   1   0
 *  0   1   1   1   1   0
 *  0   1   1   1   1   0
 *  0   0   0   0   0   0
 * }
 */
//view is a display vect,x and y are mouse interp. coord.

void MinerField::OpenCell(vector<vector<int>>& view, int x, int y)
{   
    if (gridLogic[x][y] == 9)
    {
        for (int i = 1; i <= FIELD_NUM; i++)
            for (int j = 1; j <= FIELD_NUM; j++)
            {
                view[i][j] = gridLogic[i][j];
            }
    }
    else
    {
        if (gridLogic[x][y] == 0)
            OpenVoidCells(view, x, y);
        else
            view[x][y] = gridLogic[x][y];
    }
}

And the second func,that is causing Stack-Overflow:

void MinerField::OpenVoidCells(vector<vector<int>>& view, int x, int y)
{
    if (x >= (FIELD_NUM) || y >= (FIELD_NUM))//check out of range
        return;
    if (gridLogic[x][y] == 10 || gridLogic[x][y]==11 ||gridLogic[x][y]==-1)
        return;
    if ((gridLogic[x][y] <= 8) && (gridLogic[x][y] >= 1))
    {
        view[x][y] = gridLogic[x][y];
        return;
    }
    view[x][y] = gridLogic[x][y];
    OpenVoidCells(view,x + 1, y); //North;
    OpenVoidCells(view,x - 1, y); //South
    OpenVoidCells(view,x, y + 1); //East
    OpenVoidCells(view, x, y - 1); //West

    OpenVoidCells(view, x - 1, y - 1); //South-West
    OpenVoidCells(view, x + 1, y + 1);  //North-East
    OpenVoidCells(view, x - 1, y + 1);  //South-East
    OpenVoidCells(view, x + 1, y - 1);  //North-West
}

gridLogic vector is MinerField local and have the same size as view. Run fails with FIELD_NUM=10. What can cause a stack overflow?


Solution

  • OpenVoidCells doesn't have anything to prevent visiting the same square over and over. It will go north, south, north, south, north, south ... forever, until you run out of stack. You need to keep track of visited squares and avoid re-checking them.