Автор: Spose
WEB-сайт: http://daddy.mirgames.ru

Когда я только начинал делать игру В ОСАДЕ, я долго думал как реализовать воинами (юнитами) поиск противников. Первый способ был такой:

У каждого юнита была своя ширина и высота (это квадрат). Каждый юнит в каждую единицу времени проверял весь список юнитов и смотрел: не зализают ли их квадраты на его. Этот метод был в корне не правильный. Во-первых:

1. Количество поисков в единицу времени растет в геометрической прогрессии. Например при 16 юнитах проверка будет проведена 256 раз. А при 256 юнитах уже 65536 раз.
2. Метод очень не надежный, ширина и высота не могут точно описать контур юнита, посему часто юниты начинали бить по воздуху.
3. Данным методом можно пользоваться только в том случае, если не планируется иметь более 100 юнитов в сражении.

Второй способ:

Вся карта состоит из ячеек (у меня 32х32). У каждой ячейки есть ссылка на находящегося в данный момент в ней юнита (если в ячейке нет юнита то этот параметр = nil).

Юнит раз в секунду проверяет все клетки в радиусе равном 5 от себя (это он осуществляет поиск противника взглядом) и если он кого-то обнаружил проверяет (эта проверка идет несколько раз в секунду, но только если враг находится в радиусе) не находится ли этот кто-то в одной из соседних ячеек.

Этот способ намного лучше предыдущего:

1. Количество поисков намного меньше, что дает плюс к производительности.
2. Насколько я знаю — метод ячеек самый лучший.
3. Он запросто держит до 5000 юнитов в сражении.

Но в Казаках заявлено до 8000 юнитов, а в Завоевании Америки и того больше. Как этого достигли?

Да очень просто. Вся карта разбита на ячейки по 64х64(большая), каждая из которых разбита на ячейки по 8х8 (малая). Если юнит той или иной рассы попадает в большую ячейку в ней автоматически ставится флаг, что в ней присутствует юнит данной рассы и сразу записывается сслыка на него. Попутно юнит записывается в малые ячейки. И так мы получаем, что любой юнит проверяет всего 9 больших ячеек вокруг себя (девятая, это та в которой он сам находится) раз в полторы секунды и если обнаруживается, что в одной из них находится противник, то из ячейки берется ссылка на него и без проверки 64 клеток (маленьких) определяется точное местоположение юнита. Местоположение нужно знать, чтобы стрелки знали в каком направлении им повернуться и выстрелить. Возникает вопрос: А зачем юнит прописывается в маленькие ячейки? А за тем, чтобы остальные юниты в большой ячейки случайно на него не наступили!

Этот способ лучше предыдущего:

1. Количество поисков еще меньше, что дает плюс к производительности.
2. Так как ячейки 64х64 а не 32х32 то карты соответственно в 4 или более раз больше.
3. Он запросто держит до 16000 юнитов в сражении.

Этот способ хуже предыдущего:

1. Из-за проверки раз в полторы секунды реакция юнитов слишком медленная.

В итоге получается, если вы хотите создать стратегическую игру реального времени, с колосальными побоищами (элеметы тактики сойдут на нет при такой каше) то берите метод Казаков. Если вы хотите создать игру с элеметами тактики то вам подойдет второй метод. Ну а если же вы хотите сделать аналог Settlers (Поселенцы), то для вас сойдет и первый метод!

Чуть не забыл! Поиск пути организован тоже по большим ячейкам!

На этом все. Удачи!