Есть ли способ сделать более быстрый BFSLimit ()? - PullRequest
0 голосов
/ 26 января 2020
bool SceneTurn::BFSLimit(GameObject * go, int limit)
{
    std::vector<bool> visited;
    visited.resize(SceneData::GetInstance()->GetNoGrid() * SceneData::GetInstance()->GetNoGrid(), false);
    std::vector<MazePt> previous;
    previous.resize(SceneData::GetInstance()->GetNoGrid() * SceneData::GetInstance()->GetNoGrid(), false);
    std::queue<MazePt> queue;
    queue.push(go->curr);

    int loop = 0;
    MazePt curr = queue.front();
    m_maze.SetCurr(curr);
    queue.pop();

    if (curr.y < SceneData::GetInstance()->GetNoGrid() - 1)
    {
        MazePt next(curr.x, curr.y + 1);
        std::cout << next.x << ", " << next.y << std::endl;
        if (!visited[next.y * SceneData::GetInstance()->GetNoGrid() + next.x])
        {
            if (m_maze.CanMove(Maze::DIR_UP))
            {
                previous[next.y * SceneData::GetInstance()->GetNoGrid() + next.x] = curr;
                queue.push(next);
            }
            m_myGrid[next.y * SceneData::GetInstance()->GetNoGrid() + next.x] = m_maze.m_grid[next.y * SceneData::GetInstance()->GetNoGrid() + next.x];
            visited[next.y * SceneData::GetInstance()->GetNoGrid() + next.x] = true;
        }
    }
    if (curr.y > 0)
    {
        MazePt next(curr.x, curr.y - 1);
        std::cout << next.x << ", " << next.y << std::endl;
        if (!visited[next.y * SceneData::GetInstance()->GetNoGrid() + next.x])
        {
            if (m_maze.CanMove(Maze::DIR_DOWN))
            {
                previous[next.y * SceneData::GetInstance()->GetNoGrid() + next.x] = curr;
                queue.push(next);
            }
            m_myGrid[next.y * SceneData::GetInstance()->GetNoGrid() + next.x] = m_maze.m_grid[next.y * SceneData::GetInstance()->GetNoGrid() + next.x];
            visited[next.y * SceneData::GetInstance()->GetNoGrid() + next.x] = true;
        }
    }
    if (curr.x < SceneData::GetInstance()->GetNoGrid() - 1)
    {
        MazePt next(curr.x + 1, curr.y);
        std::cout << next.x << ", " << next.y << std::endl;
        if (!visited[next.y * SceneData::GetInstance()->GetNoGrid() + next.x])
        {
            if (m_maze.CanMove(Maze::DIR_RIGHT))
            {
                previous[next.y * SceneData::GetInstance()->GetNoGrid() + next.x] = curr;
                queue.push(next);
            }
            m_myGrid[next.y * SceneData::GetInstance()->GetNoGrid() + next.x] = m_maze.m_grid[next.y * SceneData::GetInstance()->GetNoGrid() + next.x];
            visited[next.y * SceneData::GetInstance()->GetNoGrid() + next.x] = true;
        }
    }
    if (curr.x > 0)
    {
        MazePt next(curr.x - 1, curr.y);
        std::cout << next.x << ", " << next.y << std::endl;
        if (!visited[next.y * SceneData::GetInstance()->GetNoGrid() + next.x])
        {
            if (m_maze.CanMove(Maze::DIR_LEFT))
            {
                previous[next.y * SceneData::GetInstance()->GetNoGrid() + next.x] = curr;
                queue.push(next);
            }
            m_myGrid[next.y * SceneData::GetInstance()->GetNoGrid() + next.x] = m_maze.m_grid[next.y * SceneData::GetInstance()->GetNoGrid() + next.x];
            visited[next.y * SceneData::GetInstance()->GetNoGrid() + next.x] = true;
        }
    }

    while (!queue.empty() && loop < limit - 1)
    {
        ++loop;
        for (int i = 0; i < pow(4, loop); ++i)
        {
            curr = queue.front();
            queue.pop();

            if (curr.y < SceneData::GetInstance()->GetNoGrid() - 1)
            {
                MazePt next(curr.x, curr.y + 1);
                std::cout << next.x << ", " << next.y << std::endl;
                if (!visited[next.y * SceneData::GetInstance()->GetNoGrid() + next.x])
                {
                    if (m_maze.CanMove(Maze::DIR_UP))
                    {
                        previous[next.y * SceneData::GetInstance()->GetNoGrid() + next.x] = curr;
                        queue.push(next);
                    }
                    m_myGrid[next.y * SceneData::GetInstance()->GetNoGrid() + next.x] = m_maze.m_grid[next.y * SceneData::GetInstance()->GetNoGrid() + next.x];
                    visited[next.y * SceneData::GetInstance()->GetNoGrid() + next.x] = true;
                }
            }
            if (curr.y > 0)
            {
                MazePt next(curr.x, curr.y - 1);
                std::cout << next.x << ", " << next.y << std::endl;
                if (!visited[next.y * SceneData::GetInstance()->GetNoGrid() + next.x])
                {
                    if (m_maze.CanMove(Maze::DIR_DOWN))
                    {
                        previous[next.y * SceneData::GetInstance()->GetNoGrid() + next.x] = curr;
                        queue.push(next);
                    }
                    m_myGrid[next.y * SceneData::GetInstance()->GetNoGrid() + next.x] = m_maze.m_grid[next.y * SceneData::GetInstance()->GetNoGrid() + next.x];
                    visited[next.y * SceneData::GetInstance()->GetNoGrid() + next.x] = true;
                }
            }
            if (curr.x < SceneData::GetInstance()->GetNoGrid() - 1)
            {
                MazePt next(curr.x + 1, curr.y);
                std::cout << next.x << ", " << next.y << std::endl;
                if (!visited[next.y * SceneData::GetInstance()->GetNoGrid() + next.x])
                {
                    if (m_maze.CanMove(Maze::DIR_RIGHT))
                    {
                        previous[next.y * SceneData::GetInstance()->GetNoGrid() + next.x] = curr;
                        queue.push(next);
                    }
                    m_myGrid[next.y * SceneData::GetInstance()->GetNoGrid() + next.x] = m_maze.m_grid[next.y * SceneData::GetInstance()->GetNoGrid() + next.x];
                    visited[next.y * SceneData::GetInstance()->GetNoGrid() + next.x] = true;
                }
            }
            if (curr.x > 0)
            {
                MazePt next(curr.x - 1, curr.y);
                std::cout << next.x << ", " << next.y << std::endl;
                if (!visited[next.y * SceneData::GetInstance()->GetNoGrid() + next.x])
                {
                    if (m_maze.CanMove(Maze::DIR_LEFT))
                    {
                        previous[next.y * SceneData::GetInstance()->GetNoGrid() + next.x] = curr;
                        queue.push(next);
                    }
                    m_myGrid[next.y * SceneData::GetInstance()->GetNoGrid() + next.x] = m_maze.m_grid[next.y * SceneData::GetInstance()->GetNoGrid() + next.x];
                    visited[next.y * SceneData::GetInstance()->GetNoGrid() + next.x] = true;
                }
            }
        }
    }

    return false;
}

В настоящее время я выполняю функцию BFSLimit (), которая в основном выполняет BFS, но для определенного количества шагов. Например, если диапазон установлен на 3, функция будет проверять BFS до 3 шагов от точки отправления. В настоящее время он используется для создания диапазона видимости, но я планирую использовать его и для других частей моей игры. Однако из-за использования pow () в for (int i = 0; i < pow(4, loop); ++i) FPS падает почти до 0.

Я пытался предотвратить ненужные BFS ранее посещенных узлов, используя std::vector<bool> visited, но это не меняет FPS много и фактически испортил видимость.

Есть ли какие-нибудь ненужные части кодов, которые я должен удалить, чтобы улучшить мой FPS, и есть ли другие способы go об обработке BFS узлов?

...