游戏编程模式笔记——第二十章 空间分区

发表于   |   分类于   |  

“将对象存储在根据位置组织的数据结构中来高效地定位它们。”

动机

游戏世界具有空间感，对象则分布于空间之中。这一点从多方面展现出了游戏世界：一个明显的例子就是物理——对象的移动、碰撞和相互影响。
这意味着你的游戏引擎通常需要解决这个问题：“对象的附近有什么物体？”如果在每一帧中它不得不对此进行反复检测的话，那么它可能成为性能瓶颈。

战场上的部队

假设我们在制作一款即时策略游戏。对立阵营的上百个单位将在战场上相互厮杀。勇士们需要知道该攻击他们附近的哪个敌人，简单的方式处理就是查看每一个单位看看他们彼此距离的远近。

1
2
3
4
5
6
7
8
9
10
11
12
13
void handleMelee(Unit* units[], int numUnits)
{
    for( int a = 0; a < numUnits - 1; a++)
    {
        for(int b = a + 1; b < numUnits; b++)
        {
            if(units[a]->position() == units[b]->position())
            {
                handleAttack(units[a], units[b]);
            }
        }
    }
}

这里我们用了一个双重循环，这意味着我们每一帧成对检验的次数随着单位个数的平方增加。每增加一个额外的单位，都要与前面的所有单位进行比较。当单位数目非常大时，局面便会失控。

绘制战线

我们所处的困境在于单位数组无秩序可循。为了找到某位置附近的单位，我们不得不遍历整个数组。现在，设想将游戏简化一下。我们将战场想象成1维战场线，而不是2维的战场。
在这种情况下，我们通过单位在战场线上的位置来将数组排序，可以让事情变得更简单点。一旦我们做到了这点，我们便可以使用类似二分查找的方式来寻找附近的单位而不是遍历扫描整个数组。
我们来总结一下：如果我们将对象根据它们的位置信息来组织并存储为一个数据结构，我们就能更快地查找到它们。这个模式便是将这个想法应用到了1维以上的空间。

空间分区模式

对于一组对象而言，每一个对象在空间都有一个位置。将对象存储在一个根据对象的位置来组织的数据结构中，该数据结构可以让你高效地查询位于或靠近某处的对象。当对象的位置变化时，应更新该空间数据结构以便可以继续这样查找对象。

使用情境

这是一个用来存储活跃的、移动的游戏对象以及静态图像和游戏世界的几何形状等对象的常见模式。复杂的游戏常常有多个空间分区来应对不同类型的存储内容。
该模式的基本要求是你有一组对象，每个对象都具备某种位置信息，而你因为要根据位置做大量的查询来查找对象从而遇到了性能问题。

使用须知

空间分区将O(n)或者O(n^2)复杂度的操作拆解为更易于管理的结构。对象越多，模式的价值就越大。相反，如果你的n值很小，则可能不值得使用该模式。
由于该模式要根据对象的位置来组织对象，故对象位置的改变就变得难以处理了。你必须重新组织数据结构来跟踪物体的新位置，这会增加代码的复杂性并产生额外的CPU周期开销，你必须确保这么做是值得的。
空间分区会使用额外的内存来保存数据结构。就像许多的优化一样，它是以空间换取速度的。如果你的内存比时钟周期更吃紧的话，这可能是个亏本生意。

示例代码

一张方格纸

设想一下战场的整个区域。现在，往上铺一张方格大小固定的网，就像盖张方格纸那样。我们用这些网格中的单元格来取代一维数组以存储单位。每个单元格存储哪些处于其边界之内的单元列表。
我们在处理战斗时，只考虑在同一个单元格内的单位。我们不会将每个单位与游戏中的其他单位一一比较，取而代之的是，我们已经将战场划分成了一堆更小的小型战场，每一个小战场里的单位要少很多。

相连单位的网格

首先，做些准备工作。下面是Unit类：

1
2
3
4
5
6
7
8
9
10
11
class Unit
{
friend class Grid;

public:
    Unit(Grid* grid, double x, double y) : grid_(grid), x_(x), y_(y) {}
    void move(double x, double y);
private:
    double x_, y_;
    Grid* grid_;
};

我们将Grid作为友元类，就像我们看到的，当一个单位的位置发生改变时，我们不得不对网格进行处理确保一切都正常地更新。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Grid
{
public:
    Grid()
    {
        // Clear the grid.
        for(int x = 0; x < NUM_CELLS; x++)
        {
            for(int y = 0; y < NUM_CELLS; y++)
            {
                cells_[x][y] = NULL;
            }
        }
    }

    static const int NUM_CELLS = 10;
    static const int CELL_SIZE = 20;
private:
    Unit* cells_[NUM_CELLS][NUM_CELLS];
};

注意到每一个单元格都是指向一个unit的指针。下面我们将用next和prev指针来扩展Unit:

1
2
3
4
5
6
7
class Unit
{
// Previous code...
private:
    Unit* prev_;
    Unit* next_;
};

这下我们能用一个双重链表来组织Unit以取代数组了，网格中的每个单元都会指向单元格之内Unit列表的第一个Unit，而其后每个Unit都有指针用来指向列表中之前和之后的Unit。我们很快就能明白为什么要这么做。

进入战场

我们需要做的第一件事就是要确保单位被创建时就被置入网格之中。我们在Unit类的构造函数中处理:

1
2
3
4
5
Unit::Unit(Grid* grid, double x, double y)
 : grid_(grid), x_(x), y_(y), prev_(NULL), next_(NULL)
{
    grid_->add(this);
}

add()方法实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void Grid::add(Unit* unit)
{
    // Determine which grid cell it's in.
    int cellX = (int)(unit->x_ / Grid::CELL_SIZE);
    int cellY = (int)(unit->y_ / Grid::CELL_SIZE);

    // Add to the front of list for the cell it's in.
    unit->prev_ = NULL;
    unit->next_ = cells_[cellX][cellY];
    cells_[cellX][cellY] = unit;

    if( unit->next_ != NULL)
    {
        unit->next_->prev_ = unit;
    }
}

我们找到单位所处的单元格然后将它添加到链表的前面。如果单位列表已经存在，则将 其后的单位与之链接起来。

刀光剑影的战斗

当所有单位被置入单元格后，我们便让它们开始相互攻击。在Grid类中，处理战斗的主要函数如下：

1
2
3
4
5
6
7
8
9
10
void Grid::handleMelee()
{
    for(int x = 0; x < NUM_CELLS; x++)
    {
        for(int y = 0; y < NUM_CELLS_; y++)
        {
            handleCell(cells_[x][y]);
        }
    }
}

正如你所见，我们确实已经将大战场切分成了一些孤立的小规模冲突。每个单元格处理战斗函数如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void Grid::handleCell(Unit* unit)
{
    while( unit != NULL)
    {
        Unit* other = unit->next_;
        while( other != NULL)
        {
            if( unit->x_ == other->x_ && unit->y_ == other->y_)
            {
                handleAttack(unit, other);
            }
            other = other-next_;
        }
        unit = unit->next_;
    }
}

看上去我们这么做使得性能变得更差了。我们将单元格遍历一个双重嵌套循环遍成了遍历三重嵌套循环。但这里的窍门是，这两个内部循环现在都只在小数目的单元内进行遍历，这将足以抵消外部循环遍历单元格的开销。不过这尤其取决于我们单元格的颗粒度。单元格尺寸过小，则外部循环将开始对性能产生影响。
唯一的区别是，我们不再需要比较战斗中的所有对方单位——只是比较在同一个单元格内、足够接近的单位。这便是优化的核心所在。

冲锋陷阵

我们已经解决了性能问题，但却遇到了一个新的问题：单位现在都呆在单元格里面。如果将单位从它所在的单元格移动出去，那么这个单元格中的其他单位将不会再看到这个单位，而其他任何单位也不会再看到。
为了修正这个问题，我们还需要在单位每次移动的时候做一点工作。如果单位越过了单元格的边界线，则需要将单位从单元格移除掉并且添加到新的单元格中。首先，我们给Unit类添加一个方法来改变它的位置：

1
2
3
4
void Unit::move(double x, double y)
{
    grid_->move(this, x, y);
}

从调用的角度上看，这段代码可以被计算机控制单位的AI代码调用，也可以被玩家控制单位的用户输入代码调用。它所做的就是将控制权交给网格类，网格类的move方法如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
void Grid::move(Unit* unit, double x, double y)
{
    // See which cell it was in.
    int oldCellX = (int)(unit->x_ / Grid::CELL_SIZE);
    int oldCellY = (int)(unit->y_ / Grid::CELL_SIZE);

    // See which cell it's moving to.
    int cellX = (int)(x / Grid::CELL_SIZE);
    int cellY = (int)(y / Grid::CELL_SIZE);

    unit->x_ = x;
    unit->y_ = y;

    // If it didn't change cells. we're done.
    if (oldCellX == cellX && oldCellY == cellY) return;

    // Unlink it from the list of its old cell.
    if( unit->prev_ != NULL)
    {
        unit->prev->next_ = unit->next_;
    }

    if( unit->next_ != NULL)
    {
        unit->next_->prev_ = unit->prev_;
    }

    // If it's the head of a list, remove it.
    if(cells_[oldCellX][oldCellY] == unit)
    {
        cells_[oldCellX][oldCellY] = unit->next_;
    }

    // Add it back to the grid at its new cell.
    add(unit);
}

我们首先检查单位是否越过了单元格的边界。如果没有，那么只需要更新单位的位置就完成了。
如果单位离开了所在的单元格，那么我们将它从单元格的链表中移除掉，然后将之添加回网格中恰当的单元格里。就像添加一个新单位一样，这样会将单位插入到新单元格的单位链表之中。
这就是为什么我们会使用一个双重链表——我们通过设定少量几个指针就可以非常快速地从链表中添加和移除单位。在每一帧有着大量的单位移动时，这样就显得非常重要。

近在咫尺，短兵相接

对于更逼真的游戏来说，通常要考虑到攻击距离：

1
2
3
4
if(distance(unit, other) < ATTACK_DISTANCE)
{
    handleAttack(unit, other);
}

当进入攻击范围时，我们需要考虑到一种边界情况：在不同的单元格内的单位也可以足够靠近从而相互作用。
为了处理这种情况，我们不仅需要比较相同单元格的单位，还要比较相邻单元格的单位。为此，首先我们将handleCell()的内部循环拆分出来。

1
2
3
4
5
6
7
8
9
10
11
void Grid::handleUnit(Unit* unit, Unit* other)
{
    while(other != NULL)
    {
        if(distance(unit, other) < ATTACK_DISTANCE)
        {
            handleAttack(unit, other);
        }
        other = other->next_;
    }
}

现在我们的函数对一个单一的单位与另一链表的其他单位逐个判断是否有相互作用。然后我们用handleCell()这么做:

1
2
3
4
5
6
7
8
9
10
void Grid::handleCell(int x, int y)
{
    Unit* unit = cells_[x][y];
    while( unit != NULL)
    {
        // Handle other units in this cell.
        handleUnit(unit, unit->next_);
        unit = unit->next_;
    }
}

注意，我们将单元格的坐标也传入了进去，而不只是单位链表。眼下，这个和上面的例子做的事情没有什么不同，但我们将会稍微扩展一下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void Grid::handleCell(int x, int y)
{
    Unit* unit = cells_[x][y];
    while( unit != NULL)
    {
        // Handle other units in this cell.
        handleUnit(unit, unit->next_);

        // Also try the neighboring cells.
        if (x > 0) handleUnit(unit, cells_[x - 1][y]);
        if( y > 0) handleUnit(unit, cells_[x][y - 1]);
        if( x > 0 && y > 0)
            handleUnit(unit, cells_[x - 1][y - 1]);
        if( x > 0 && y < NUM_CELLS - 1)
            handleUnit(unit, cells_[x - 1][y + 1]);
        unit = unit->next_;
    }
}

handleUnit()函数用来处理当前单位和相邻8个单元格其中4个单元格之内的战斗。如果在相邻单元格中的任何单位离当前单位的攻击半径足够近，它将会处理战斗。
我们只查看一半相邻的单元格，这与之前的原因一样，因为内部循环是从当前单位开始的——为了避免对同对单元比较两次。

设计决策

分层是层级的还是扁平的

在网格例子中，我们将网格划分成了一个单一扁平的单元格集合。与此相反，层级空间分区则是将空间划分成几个区域。然后，如果这些区域中仍然包含着许多的对象，就会继续划分。这个递归过程持续到每个区域的对象数目都少于某个约定的最大对象数量为止。
如果它是一个扁平的分区

  • 相对简单。扁平的数据结构相对来说更易于推理和实现。
  • 内存使用量恒定。由于添加新对象不需要创建新的分区，所以空间分区使用的内存通常可以提前确定。
  • 当对象改变位置时可以更为快速地更新。当一个对象移动时，数据结构需要更新以便在新的位置找到对象。使用层级空间分区，这可能意味着调整层次结构中的若干层。

如果它是一个层级的分区

  • 它可以更有效地处理空白的空间。想象一下，在我们前面的例子中，如果战场的一整侧是空白的，那么就会产生大量的空白单元格，而我们不得不在每帧中为他们分配内存并进行遍历。
    因为层级空间不会细分稀疏区域，所以一个大的空白空间仍然是一个单独的分区，而不是大量细小的分区。
  • 它在处理对象稠密区域时更为有效。这是硬币的另一面：如果你有一堆对象成群的在一起，非层级分区是低效的。你最终会有一个包含着许多对象的、可能根本没有分区的分割。层级分区将会自适应地将其细分成更小的分区，使得你一次只需考虑少数几个对象。

分区依赖于对象集合吗

在我们的示例代码中，网格的间距是预先固定的，并且我们将单位放置了单元格中。其他的分区方案是自适应的，它们根据实际的对象集合及其世界总的位置来选择分区的边界。
我们的目标是实现一个均衡的分区，每一个分区都有大致相同的对象个数以获得最佳的性能。以我们的网格为例考虑下，如果所有单位都集中在了战场的一个角落，那么它们将会处在同一个单元格内，找寻单位间攻击的代码又会回到原来我们要试图解决的O(n^2)问题这一原点。
如果分区依赖于对象

  • 对象可以被逐步地添加。添加一个对象意味着要找到正确的分区并且将对象放置进去，所以你可以在不影响性能的情况下一次性完成这个动作。
  • 对象可以快速地移动。对于固定的分区，移动一个单位意味着将单位从一个单元格中移除然后添加到另外一个单元格。如果分区边界本身基于对象集合来改变，那么移动对象会引起边界的移动，从而可能需要大量的其他对象移动至其他分区。
  • 分区可以不平衡。当然，这么做的硬伤在于你对最终呈现的非均匀分区的掌控力会很薄弱。如果对象拥挤在一起，那么你会因为在空白区域浪费了内存而令而令其性能变得很糟糕。
    这很类似于红黑树或者AVL树这样的二叉搜索树。

如果分区自适应于对象集合
像二叉空间分割(BSPs)和k-d树(k-d trees)这样的空间分区方式会递归地将世界分割开来，以使得每部分包含着数目几乎相同的对象。要做到这点，在选取要进行分区的层级前，你必须计算每个阵营包含的对象数目。边界体积层次结构（Bounding volume hierarchies）是空间分区中的另外一种类型，用于优化世界中的特定对象集合。

  • 你可以确保分区间的平衡。这不仅仅带来优秀的性能表现，而且会是持续稳定的表现：如果每个分区有着相同数量的对象，你便可以确保对世界中的任意分区的查询时间开销均等。当需要维持稳定的帧速率时，这种稳定性比原始性能更为重要。
  • 对整个对象集合进行一次性的分区时更为高效。当对象集合影响到边界时，最好在分区之前对所有对象进行审视。这就是为什么这种类型的分区越来越多地应用于游戏过程中保持不变的事物诸如美术和静态几何。
  • 如果分区不依赖于对象，而层级却依赖于对象。

四叉树同时具备了固定分区和自适应性分区的优良性质。
四叉树从将整个空间作为一个单一的分区开始。如果空间中对象的数目超过了某一个阈值，则空间便被切分成四个较小的正方形。这些正方形的边界是固定的：它们总是将空间对半切分。
然后对于四个正方形中的每一个而言，我们重复同样的过程，递归下去直到每一个正方形内部只有少量的对象。由于我们只是递归地将高密度对象区域切分开，因此这个分区会自适应于对象集合，但分区是不会移动的。

  • 可以逐步地添加对象。添加一个新对象意味着要寻找合适的区域并且放置进去。如果对象放入区域时超过了最大对象数，那么该区域会被继续细分。在区域中的其他对象也会被分到更细小的区域中去。而这需要一些工作，但工作量是固定的：你要移动的对象始终要比最大的对象数少。添加单个对象也不会触发一次以上的拆分工作。
    删除对象同样简单。你将对象从它所在的区域中移除，如果它的父区域的对象总数低于了一个阈值，那么你就可以合并这些细分的区域。
  • 对象可以快速地移动。这个当然，和上面一样。“移动”一个对象只是一次添加和一次删除，两者在四叉树下速度很快。
  • 分区是平衡的。由于任何给定的区域中的对象数目都比最大对象数要小，因此即使对象聚集在一起，也不会容纳着大量对象的单一分区。

对象只存储在分区中吗

你可以将空间分区看作是游戏中对象存活的地方，或者你可以只将它看作是二级缓存，相比直接有对象列表的集合而言，查询能够更快速。
如果它是对象唯一存储的地方
这避免了两个集合的内存开销和复杂性。当然，将东西存成一份比两份的代价要小。另外如果你有两个集合，那么你必须确保集合间的同步。每次当一个对象被创建或者被删除时，将不得不从两者中对其进行添加或者删除。
如果存在存储对象的另外一个集合
遍历所有的对象会更为快速。如果问题中对象是“存活”的并且它们需要做一些处理，则你可能会发现自己要频繁地访问每一个对象，无论对象的位置在哪。试想一下，在我们前面的例子中，大部分单元格都是空的。遍历网格中所有单元各来找到哪些非空单元格是在浪费时间。第二个仅用于存储对象的集合令你可以直接对全部对象进行遍历。你有两个数据结构，其中一个针对每个用例进行了优化。