A-tit indd

414
Пространственное разбиение (Spatial Partition) — 
Паттерны программирования игр
int cellX = (int)(unit->x_ / Grid::CELL_SIZE);
int cellY = (int)(unit->y_ / Grid::CELL_SIZE);
// 3 6 6.
unit->prev_ = NULL;
unit->next_ = cells_[cellX][cellY];
cells_[cellX][cellY] = unit;
if (unit->next_ != NULL)
{
unit->next_->prev_ = unit;
}
}
Немного громоздко, как, собственно, и в любом коде, 
где используются связанные списки, но сама идея доста-
точно проста. Мы находим ячейку, в которой располага-
ется юнит, а затем помещаем его в начало списка. Если 
в ячейке уже есть юниты, то мы помещаем их за новым.
 

Как только все юниты размещены в сетке, мы можем на-

чать наше сражение. С нашей новой сеткой обработка 
сражения выглядит теперь так:
void Grid::handleMelee()
{
for (int x = 0; x < NUM_CELLS; x++)
{
for (int y = 0; y < NUM_CELLS; y++)
{
handleCell(cells_[x][y]);
}
}
}
Мы проходим по каждой из ячеек и вызываем метод 
handleCell()
для них. Как видите, по сути, мы разби-
ли поле боя на мелкие изолированные стычки. Каждая 
клетка обрабатывает сражение примерно так:
void Grid::handleCell(Unit* unit)
{
while (unit != NULL)
{
Разделение на ячейки 
превращает координаты 
мира в сетчатое про-
странство. Приводя ре-
зультат к типу 
int
и от-
брасывая дробную 
часть, мы получаем ин-
декс ячейки.

---

Паттерны программирования игр
— Паттерны оптимизации
415
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_;
}
}
Помимо махинаций с указателем для прохода по свя-
занному списку, обратите внимание: все та же наша 
примитивная реализация обработки сражения. Сравни-
вается каждая пара юнитов и проверяется, находятся ли 
противники достаточно близко.
Единственная разница в том, что нам больше не нуж-
но сравнивать 
всех
юнитов сражения друг с другом —
только оказавшихся в одной ячейке. Такова суть данной 
оптимизации.