A-tit indd

Рисуем линию сражения
Проблема в отсутствии какого-либо порядка в массиве 
боевых юнитов. Чтобы найти воина рядом с неким ме-
стом, нам надо пройти по всему массиву. А теперь упро-
стим нашу игру. Вместо двухмерного 
поля
боя сделаем 
одномерную 
линию
боя.
Внутренний цикл на са-
мом деле проходит 
не через всех юнитов, 
а только через тех, кто 
еще не был обработан 
внешним циклом. Таким 
образом мы избегаем 
повторного
сравнения 
пары, где те же эле-
менты располагаются 
в другом порядке. Мы 
уже проверили положе-
ние А относительно В, 
нам не нужно проверять 
В относительно А.
Но в терминах слож-
ности алгоритмов это 
по-прежнему 
O(n
2
)
.

---

Паттерны программирования игр
— Паттерны оптимизации
409
Рис. 20.1.
Одномерная линия боя
Упростим себе жизнь, 
отсортировав
юнитов относи-
тельно их позиции на линии боя. Как только мы это сде-
лаем, то сможем использовать двоичный поиск, чтобы 
найти близлежащие юниты без необходимости прове-
рять весь массив.
Мораль довольно проста: если мы будем хранить 
объекты в структуре данных, организованной в соответ-
ствии с расположением, мы сможем находить нужное 
нам намного быстрее. Паттерн Пространственное раз-
биение (Spatial Partition) о том, как применить эту идею 
для пространства, где более одного измерения.
Паттерн
В наборе 
объектов
каждый имеет 
позицию в про-
странстве
. Храните их в пространственной структуре 
данных, которая располагает объекты в соответствии 
с их позицией. Такая структура данных позволит вам 
осуществлять