# 空间分区

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

## 网格法

将地图区域划分为网格

```cpp
// 一个网格拥有多个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的指针

```cpp
class Unit
{
//Previous code...

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

## 进入战场

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

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

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

```cpp
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个立方体。除了额外的一个维度，它工作的原理和四叉树一样。

* 网格 Grid spatial_index
* 四叉树、八叉树
* 二叉空间分割
* k-dimensional树
* 层次包围盒

* 网格是一个连续的桶排序
* 二叉空间分割、k-d树，以及层次包围盒都是二叉查找树，一看到二叉查找树大多数人脑海就会被红黑树或AVL树支配。
* 四叉树和八叉树都是Trie树。