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

Намеренение

Deo 22.08.14 в 18:12

Мотивация

kabanov 24.06.14 в 12:53

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

Deo 22.08.14 в 18:17

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

Deo 22.08.14 в 18:19

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

Deo 22.08.14 в 18:20

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

Deo 22.08.14 в 19:52

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

Deo 22.08.14 в 19:55

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

Deo 22.08.14 в 20:01

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

Deo 22.08.14 в 20:03

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

Deo 22.08.14 в 20:04

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

Deo 22.08.14 в 20:05

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

Deo 22.08.14 в 20:06

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

Deo 22.08.14 в 20:08

void handleMelee(Unit* units[], int numUnits)

kabanov 24.06.14 в 12:53

{

kabanov 24.06.14 в 12:53

for (int a = 0; a < numUnits - 1; a++)

kabanov 24.06.14 в 12:53

{

kabanov 24.06.14 в 12:53

for (int b = a + 1; b < numUnits; b++)

kabanov 24.06.14 в 12:53

{

kabanov 24.06.14 в 12:53

if (units[a]->position() == units[b]->position())

kabanov 24.06.14 в 12:53

{

kabanov 24.06.14 в 12:53

handleAttack(units[a], units[b]);

kabanov 24.06.14 в 12:53

}

kabanov 24.06.14 в 12:54

}

kabanov 24.06.14 в 12:54

}

kabanov 24.06.14 в 12:54

}

kabanov 24.06.14 в 12:54

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

kabanov 24.06.14 в 12:55

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

kabanov 24.06.14 в 12:56