空间分区

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

网格法

将地图区域划分为网格

// 一个网格拥有多个Cell
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_;
};

// 网格
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的指针

class Unit
{
//Previous code...

private:
　Unit* prev_;
　Unit* next_;
};

进入战场

我们需要做的第一件事就是确保单位被创建时就被置入网格之中。

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

玩家对象被在Grid上的cell上拉成链表

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;
　}
}

做什么操作，都可以轻松的快速查找遍历处理某个角色周围的9个Grid。

这也就是大家熟知的九宫格法。

其他方法

二叉空间分割(BSPs)、k-d树(k-d trees) 这样的空间分区方式会递归地将世界分割开来，以使得每部分包含着数目几乎相同的对象。

四叉树(quadtrees)分割了2维空间。3维模拟的是八叉树（octree），它作用于体积并将之分割成8个立方体。除了额外的一个维度，它工作的原理和四叉树一样。