Готовый перевод Game Programming Patterns / Паттерны программирования в играх: 5.4 Spatial Partition

Намеренение

Мотивация

Игры позволяют нам посещать другие миры, но эти миры обычно не сильно отличаются от нашего.

Они часто используют ту же основы физики и реальность, что и наш мир.

Поэтому они ощущаются реальными, несмотря на то, что созданы из обычных битов и пикселей.

Это проявляется в нескольких вещах.

Самая очевидная - физика: объекты движутся, сталкиваются и взаимодействуют, однако это еще не все.

Это означает, что вашему игровому движку часто придется отвечать на вопрос: "Какие объекты расположены неподалеку от этой локации?"

Если в каждом кадре ему придется отвечать слишком часто на этот вопрос, это станет узким местом в производительности.

Скажем, мы создаем стратегию реального времени.

Враждующие армии с сотнями боевых единиц столкнутся друг с другом на поле боя.

Войнам нужно знать, в какого близлежащего противника можно вонзить клинок.

Простейший способ обработать такую ситацию - сравнивать юниты попарно, выясняя насколько далеки они друг от друга:

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]);

}

}

}

}

На самом деле внутренний цикл не проходит по всем юнитам.

Однако в нотации О-большого это до сих пор O(n²).

Хорошо, давайте напишем код.

Сначала немного подготовительной работы.

Наш базовый класс юнита:

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

};

Каждый юнит имеет позицию (в 2D)

и указатель на Сетку, на которой он живет.

Небольшой набросок сетки:

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

};

class Unit

{

// Предыдущий код...

private:

Unit* prev_;

Unit* next_;

};

Unit(Grid* grid, double x, double y)

: grid_(grid)

,

x_(x)

,

y_(y)

,

prev_(NULL)

,

next_(NULL)

{

grid_->add(this)

;

}

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)

;

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 y = 0; y < NUM_CELLS; y++)

{

for (int x = 0; x < NUM_CELLS; x++)

{

handleCell(cells_[x][y]);

}

}

}

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

}

}

void Unit::move(double x, double y)

{

grid_->move(this, x, y)

;

}

void Grid::move(Unit* unit, double x, double y)

{

int oldCellX = (int)

Переведено на Нотабеноиде
http://notabenoid.org/book/51192/215233

Переводчики: kabanov, Deo