optimization - war 迷雾和二维网格

Question

首先，我正在使用 XNA 框架开发 2D 策略游戏。

我正在为我的游戏实现 2D war 迷雾。图形部分已经完成并且工作得非常好，但我现在正在尝试实现这个 war 迷雾的“逻辑”部分。

我创建了一个代表我的级别的二维网格。每一帧，每个单元都会使用 Bresenham 算法更新其周围圆圈中的单元格(这似乎是找出给定圆圈中哪些单元格的最佳方法)。 这实际上是有效的...当我想知道给定位置是否可见时，我只需要获取单元格的状态...

问题是，当我有大量生成单位时，我的游戏运行得很慢...... 这个性能问题的第一个原因是，由于每个单元都会更新它周围的单元格，因此很多单元格会多次更新......但我看不到任何解决方案......

所以...也许我错误地以这种方式实现它，或者也许我错过了一个明显的优化，但我有点卡住了...

这是代码:

class LevelGridCell
{
    public void SetVisible(float a_time)
    {
        if (m_visibleTime < a_time)
            m_visibleTime = a_time;
    }
    public bool IsVisible(float a_time)
    {
        return (m_visibleTime != 0f && m_visibleTime >= a_time);
    }

    float m_visibleTime = 0;
}

class LevelGrid
{
    public LevelGridCell GetAt(int a_x, int a_y)
    {
        return m_grid[a_x + a_y * m_width];
    }

    public void SetVisible(float a_time, int a_x, int a_y, float a_radius)
    {
        GetAt(a_x, a_y).SetVisible(a_time);

        int intRadius = (int)(a_radius / m_cellSize);
        int x = 0, y = intRadius, p = 1 - intRadius;
        PlotSetVisible(a_x, a_y, x, y, a_time);
        while (x < y)
        {
            x++;
            if (p < 0)
                p += 2 * x + 1;
            else
            {
                y--;
                p += 2 * (x - y) + 1;
            }
            PlotSetVisible(a_x, a_y, x, y, a_time);
        }
    }
    private void SafeSetVisible(int a_x, int a_y, float a_time)
    {
        if (a_x >= 0 && a_x < m_width && a_y >= 0 && a_y < m_height)
        {
            GetAt(a_x, a_y).SetVisible(a_time);
        }
    }
    private void PlotSetVisible(int xctr, int yctr, int x, int y, float a_time)
    {

        for (int i = xctr - x; i <= xctr + x; ++i)
        {
            SafeSetVisible(i, yctr + y, a_time);
            SafeSetVisible(i, yctr - y, a_time);
        }
        for (int i = xctr - y; i <= xctr + y; ++i)
        {
            SafeSetVisible(i, yctr + x, a_time);
            SafeSetVisible(i, yctr - x, a_time);
        }
    }

    List<LevelGridCell> m_grid = new List<LevelGridCell>();
    float m_cellSize;
    int m_width;
    int m_height;
}

Answer 1

在没有看到您的代码的情况下，我们不得不猜测问题可能是什么。如果您已经分析过您的代码，您应该能够找出哪部分特别慢；有了这些信息，您就可以非常直接地解决问题。

以下是关于哪些位可能会变慢的一些猜测:

• 圆就是圆。您是否遵循每个单元的 Bresenham 圆算法？看起来你可以只计算一次相对于 (0,0) 的圆。然后，对于 (x,y) 处的单位，您可以简单地查找圆圈并将圆圈中的点偏移到 (x,y)，然后将 war 迷雾逻辑应用于该单位。

  <

• war 迷雾仅针对最近移动的单位发生变化。如果一个单位是静止的，那么您可能不需要再次计算其可见性。您能够将这种优化应用到您的 war 迷雾可见性规则中吗？

• Bresenham 圆算法可帮助您绘制圆的边缘。你如何填充圆圈内部？您是否应该找到更好的算法来填充范围内部？

有评论要求提供有关使用生成的圈子的更多详细信息，因此我在此添加一些相关注释。(编辑答案是做到这一点的方法吗？抱歉，我对这方面还比较陌生堆栈交换。)

“ war 迷雾”通常意味着一个单位可以看到其周围的一定半径。你们单位的半径是多少？每种单位类型的半径是否不同？有多少种单位类型？

假设一种单位类型的可见范围半径为 5 个方格。这给我们留下了一个看起来像这样的圆圈:

00001110000
00010001000
00100000100
01000000010
10000000001
10000x00001
10000000001
01000000010
00100000100
00010001000
00001110000

既然我们有一个圈子，我们知道我们不必做任何太困难的事情来填补它。一个简单的算法将在最右边的 1 和最左边的 1 之间遍历每一行填充。这比解析所有内部点的 Breshenham 算法要快得多。

通过实心圆，我们找到这个数组，然后:

00001110000
00011111000
00111111100
01111111110
11111111111
11111x11111
11111111111
01111111110
00111111100
00011111000
00001110000

现在，如果我们有一个半径为 5 个方格可见度的单位，则将 war 迷雾应用于该单位仅意味着将这个预先计算的数组应用于 war 迷雾数组，使得该预先计算的数组的中心位于该单位上我们正在处理。一旦您计算了距中心的偏移并将数组的边界剪切到 map 的边缘，您就可以通过一个简单的嵌套循环来做到这一点。

如果您有几个不同的 war 迷雾可见性半径，您可以预先计算几个不同的数组。如果你的规则规定你的 war 迷雾会因障碍物(如地形、建筑物或景观)而变化，那么你必须做更多的处理，但预计算的想法仍然可以应用。