使用深度优先搜索，如何检索坐标列表列表来确定岛屿？

Question

我正在尝试在 2D 数组/图块地图上使用 DFS 来确定醉汉行走算法后生成的岛屿。步行雕刻出一个预先分配的二维数组（删除图块），我想确定岛屿（或我的场景中的平台，对于二维横向卷轴），这样我就可以沿着这些平台/岛屿适当地放置山丘。

问题是，当我在外周尝试 DFS 时，我不断遇到堆栈溢出，我传递的 std 向量达到大约 3000~ (ptr) 元素。我在捕获大约 20 - 50 个元素的内岛时没有任何问题。

我使用 0、1 和 2 的伪图来确定发生了什么。 1在这里是平铺的，没有勾选 0 为空 找到 2 个图块，已添加到岛屿列表

    if (pseudoMap[y][x] == 1)
    {
    Uint8 platform = 1;

    PlatformDFS(&pseudoMap, x, y, &platform, visitedPlatform);

    if (platform == 1) {
        SDL_SetRenderDrawColor(graphicsRef->GetRenderer(), 0, 0, 255, 255);

        platformsFound.push_back(visitedPlatform);

        for (Vector2 gridPos : visitedPlatform) {
            tileMap[(int)gridPos.y][(int)gridPos.x]->SetTileLayer(TileLayer::Platform);
            SDL_Rect r((int)gridPos.x * 5, int(gridPos.y) * 5, 5, 5);
            SDL_RenderDrawRect(graphicsRef->GetRenderer(), &r);
            SDL_RenderPresent(graphicsRef->GetRenderer());
        }

        PrintTileMapToConsole(1);
        std::cout << "Platform found starting at " << x << "," << y << std::endl;
    }
    else {
        std::cout << " NO platform found at " << x << "," << y << std::endl;
        visitedPlatform.clear();
    }
    }

我将伪图传递给dfs fcn进行标记 要检查的当前 x,y 如果我们出界，该标志将被标记为 0，这意味着我们正在检查洞穴本身 以及属于当前岛屿/平台的图块列表

    void TileManager::PlatformDFS(std::vector<std::vector<Uint8>>* pmap, int x, int y, Uint8* platformFlag, std::vector<Vector2>& platformTiles)
    {
    if (IsNotInBounds(x, y)) {
        platformFlag = 0;
        return;
    }
    
    if ((*pmap)[y][x] != 1)
        return;

    Vector2 pos = Vector2(x, y);

    platformTiles.push_back(pos); <--- This is my issue, when we check on the cave perimeter

    (*pmap)[y][x] = 2;
    PlatformDFS(pmap, x, y + 1, platformFlag, platformTiles);
    PlatformDFS(pmap, x, y - 1, platformFlag, platformTiles);
    PlatformDFS(pmap, x + 1, y, platformFlag, platformTiles);
    PlatformDFS(pmap, x - 1, y, platformFlag, platformTiles);
    PlatformDFS(pmap, x + 1, y + 1, platformFlag, platformTiles);
    PlatformDFS(pmap, x - 1, y - 1, platformFlag, platformTiles);
    PlatformDFS(pmap, x + 1, y - 1, platformFlag, platformTiles);
    PlatformDFS(pmap, x - 1, y + 1, platformFlag, platformTiles);
    }


    bool TileManager::IsNotInBounds(int x, int y)
    {
        return y < 0 || y >= tileMap.size() || x < 0 || x >= tileMap[y].size();
    }

在附图中，蓝色框是标记的平台，表明它在一定程度上有效。

Answer 1

这是一个简单的错误，忘记将 ptr 取消引用到我传递给 fcn 的标志。将ptr地址设置为0，而不是设置值。所以告诉我的 DFS 停止搜索的分配是不正确的。

platformFlag = 0;

与

*platformFlag = 0;

我添加了对 DFS 中第一个转义条件的检查，以处理当前位置是否设置为 0。