Размещаем до 2000 юнитов (XNA)

Привет, в этом посте будет представлено немного кода, пару картинок и несколько видео, про то, как я реализовывал быстрый алгоритм взаимодействия ракет и юнитов на XNA (2000 — 3000 юнитов) и не только.




Об ошибках пишите в личку

С чего всё начилось

Начну с того, что при написании игры, встал вопрос о взаимодействии снарядов с юнитами. Сначала я подумал — «Ну сейчас уйдёт пару минут на условия с циклом и всё будет в шоколаде».

Вот что первое было на уме:

foreach (var rocket in rockets)
{
    foreach (var unit in units)
    {
        if (Contact(rocket, unit)) // Если ракета контактирует с юнитом
        {
            unit.HP -= rocket.damage; // То нанести данному юниту урон
        }
    }
}

На моём месте, скорее всего, большинство новичков, использовали тоже самое.

Проблема

Работало это быстро до тех пор, пока я не ввёл AI систему, которая управляла несколькими кораблями. Сначала было 6 юнитов (плюс мой корабль) и две команды. Всё было прекрасно, но явно не хватало драйва. И я изменил одну строчку countBot = 6; на countBot = 100; и тут понеслись лаги (21 FPS), сначала я был в недоумении и толком понять не мог, где надо оптимизировать.

Вот, нашёл самую первую версию игры, где ещё 6 юнитов.

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

Ну а теперь вернёмся к поиску и решению проблемы.
В поиске лагов помогла старая, добрая изолента конструкция:

DateTime start = DateTime.Now; // Засекаем грубо говоря таймер
// ... Метод или кусок кода
TimeSpan finish = DateTime.Now - start; // Высчитываем пройденное время
Write(finish); // Вывод на экран или в консоль результатов

Эта конструкция замеряет время исполнения кода, что позволяет найти места торможения. Считаете, что всегда легко найти такие места? А вот нет. Мой случай, конечно, простой, но были и моменты по серьёзнее.

Вывод выглядил примерно так (при 100 юнитах):

Как видно, на обработку метода уходило по 41 ms. что равно примерно 23 — 24 FPS

Так ушла одна минута на поиск проблемы, она, как вы догадались, была в тех строчках, которые были предложены для решения задачи о столкновениях. Так в чём же была проблема? А она была в том, что использовались два вложенных цикла. Ну представьте себе 100 юнитов, каждый выпускает по 13 ракет в секунду, что примерно равно 1300 ракетам в секунду (тут конечно я загнул, так, как у меня не стреляли одновременно все юниты, но всё же). 1300 ракет нужно проверить с сотней кораблей или 1300 * 100 = 130 тыс. проверок в секунду.

А я хотел игру с 2000, даже 3000 юнитов. Была и есть такая игра "Казаки: Снова война", в ней взаимодействует over 9999 много юнитов, разных типов, с физикой и другими фитчами. А раз такая игра была (такая, что в ней спокойно помещалось до 10000 юнитов), то значит выход есть.

Сначала были глупые попытки оптимизировать код, появилась куча условий, всякой фигни, но ничего не помогало. Пришлось смириться с тем, что надо придумывать новый алгоритм обработки. Спустя два три дня, в голову пришла уже более продвинутая идея.

Идея

Суть идеи заключалось в том, чтобы делить карту на 12 больших зон проверки (помечены голубыми линиями на рисунке), затем надо было сортировать юнитов по этим зонам и проверять только внутри этих зон. Знаете, это сработало, скорость возросла в несколько раз — это чертовски сильно меня обрадовало. Ну, далее, почему бы не поэкспериментировать? Я уменьшил сами зоны, тем самым увеличив их количество, теперь их было 48 (розовые линии на рисунке). Скорость ещё сильнее возросла, далее уже было просто интересно, на каком этапе увеличения количества зон производительность начнёт умирать (такой момент был, но я не помню сколько зон тогда было).

Итог

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

Как это выглядит у меня в коде:

public int gridWidth = (int)(Ship.Size.X); // Размеры ячейки двумерного массива
public int gridHeight = (int)(Ship.Size.Y);

public List<Ship>[,] grid; // Наш массив списка кораблей (об этом после кода)

// Обновление сетки
public void UpdateGrid()
{
    grid = new List<Ship>[map.border.Width / gridWidth, map.border.Height / gridHeight];
    // map.border - размер игровой карты

    foreach (var ship in ships)
    {
        if (ship.isDead) // Бесполезно добавлять трупа в сетку
            continue;

        int x = (int)(ship.position.X / gridWidth); // Местоположение в двумерном массиве
        int y = (int)(ship.position.Y / gridHeight);

        if (x < 0) // Своего рода костыль, если вдруг корабль улетит за пределы карты
            x = 0;
        if (y < 0)
            y = 0;
        if (x + 1 > grid.GetLength(0))
            x = grid.GetLength(0) - 1;
        if (y + 1 > grid.GetLength(1))
            y = grid.GetLength(1) - 1;

        if (grid[x, y] == null) // У меня двумерный массив списков (подробнее после кода)
            grid[x, y] = new List<Ship>();
        grid[x, y].Add(ship); // На случай если в одной ячейки оказалось более одного корабля
    }
}

// Проверка на столкновения 
public void RocketContact()
{
// foreach не для этого случая, так как кол-во элементов меняется в ходе цикла
    for (int i = 0; i < rockets.Count; i++) 
	{
        int x = (int)(rockets[i].position.X / gridWidth); // Позиция ракеты в двумерном массиве
        int y = (int)(rockets[i].position.Y / gridHeight);

        if (x < 0) // Вдруг ракета уже за пределами карты
            x = 0;
        if (y < 0)
            y = 0;
        if (x + 1 > grid.GetLength(0))
            x = grid.GetLength(0) - 1;
        if (y + 1 > grid.GetLength(1))
            y = grid.GetLength(1) - 1;

        if (grid[x, y] != null) // Если есть корабль в данной ячейки, то идём дальше
        {
            Ship ship = grid[x, y][0]; // У нас один снаряд - значит он может поразить только одну цель
            if (!ship.isDead) // Лишний раз можно проверить, вдруг умер за один такт =)
                {
                    if (ship.teamID != rockets[i].teamID) // Пусть ракеты уничтожают только врагов
                    {

                        ship.HP -= rockets[i].damage;

                        if (rockets[i].hostPlayer != null) // Ну далее присуждение определённому игроку очков
                        {
                            rockets[i].hostPlayer.rocketHit++; // Кол - во попаданий
                            if (ship.isDead) // Если убил
                            {
                                rockets[i].hostPlayer.AddKill(); // добавить очко
                            }
                        }

                        if (ship.isDead && ship.hostPlayer != null) // Тоже, что и выше, только добавление очка смерти
                            ship.hostPlayer.AddDead();

                        rockets.RemoveAt(i); // Уничтожаем ракету из списка (она же попала в корабль)
                        i--;
                    }
                }
	}
}

Теперь вопросы, которые могли возникнуть в ходе рассмотрения кода.

• Зачем нам двумерный массив списков кораблей? У меня в игре один корабль может вплотную лететь с другим кораблём, а снаряд у нас один, значит можно поразить только один корабль. Я понимаю, что было бы уместнее написать что — то типа того: Ship ship = grid[x, y][Random.Next(grid[x, y].Count)]; Но пост не о том.
• Что на счёт производительности? Производительность увеличилась ровно в сто раз. Теперь было не 1,3 млн. проверок а всего лишь 13 тыс.
• Почему костыль? Потомучто, это мой старый код, в новом коде немного иначе. Там, если, объект за пределами массива, то он просто не просчитывается.
• Много ли расходуется оперативной памяти на данную конструкцию? Смотря какой размер карты и сколько объектов, у меня карта 10000x10000 pix, размер сетки 100x100 pix при 2000 юнитах — около 2 — 10 мб. памяти. Если есть ещё вопросы задавайте в комментариях (Ваш преданный КЭП).

Сравнение

До: Попытки оптимизировать старую конструкцию привели к страданиям и потере времени возможности размещать до 225 кораблей.

Если заметили — курсор стал проще и информативнее, хотя меня этот тоже бесит.

После: Оптимизация прошла настолько успешно, что я смог размещать до 2000 юнитов. Видео немного подлагивает (как и предыдущие) только из — за того, что использовалась программа для захвата экрана.

В последней версии появилась музыка (в самой игре — она играет на видео), движущийся фон, за счёт которого частично решается проблема ориентации.

End

Все текстуры рисовал сам, к сожалению я не художник, чтобы нарисовать лучше. Это к тому, что мне не хватает 2D художника для простых игрушек типо этой.

TDS Vis 0.21 — когда, я доделаю её (если доделаю), то опубликую проект на GitHub. Если будут интересные моменты, тогда о них обязательно появится посты.

Если интересно, то могу написать про полную разработку игры от начала и до конца.

Первая бета версия игры (не судите сильно)

P.S. Ещё раз, об ошибках и очепятках пишите в личку.
P.S2 Песни из видео:
Remorse Code – Transcend
Katie Melua – The Flood (Jakwob remix)
Пару песен Eric Brosius из игры Tribes