A-tit indd

Паттерны программирования игр
— Паттерны оптимизации
411
Листок бумаги в клетку
Представьте все поле боя. А теперь наложите на него 
сетку с ячейками одного размера, подобную листку бу-
маги в клетку. Вместо того чтобы хранить юниты в од-
ном массиве, мы разместим их в ячейках сетки. Каждая 
ячейка будет хранить список юнитов, которые распола-
гаются внутри нее.
Рис. 20.2.
Поле боя, разбитое на квадраты
Когда мы обрабатываем сражение, мы рассматрива-
ем только воинов в пределах одной ячейки. Вместо того 
чтобы сравнивать юнит со всеми остальными юнитами 
игры, мы разбили поле боя на набор более мелких мини-
полей боя, в каждом из которых всего несколько воинов.
Сетка связанных юнитов
Итак, перейдем к написанию кода. Для начала немного 
подготовки. Вот наш базовый класс 
Unit
:
class Unit
{
friend class Grid;
public:
Unit(Grid* grid, double x, double y)

---

412
Пространственное разбиение (Spatial Partition) — 
Паттерны программирования игр
: grid_(grid),
x_(x),
y_(y)
{}
void move(double x, double y);
private:
double x_, y_;
Grid* grid_;
};
У каждого есть позиция (два измерения) и указатель 
на 
Grid
, в котором он находится. Мы делаем класс 
Grid
дружественным (
friend
), ведь, как мы увидим позже, 
когда позиция юнита меняется, приходится произво-
дить сложные операции, и мы должны убедиться, что 
все обновляется верно.
Вот набросок сетки:
class Grid
{
public:
Grid()
{
// 7 .
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
:

---