Карта

В предыдущей статье я разобрал, что из себя представляет новая система задач Job system, как она работает, как создавать задачи, наполнять их данными и выполнять многопоточные вычисления и лишь в двух словах объяснил где можно использовать эту систему. В этой статье я попробую разобрать конкретный пример того где можно использовать эту систему, чтобы получить большую производительность.

Так как система изначально разработана с целью выполнения работы с данными, она отлично подходит для решения задач по поиску пути.

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


В примере на карте строиться сетка, есть бот и препятствие. Сетка перестраивается каждый раз когда мы изменим какие либо свойства карты, будь то ее размер или позицию.

Для плоскостей я использовал простой SpriteRenderer, у этого компонента есть отличное свойство bounds с помощью которого можно легко узнать размеры карты.

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

Начнем со скриптов. И первым будет скрипт препятствия Obstacle.


Внутри класса Obstacle будем отлавливать все изменения препятствий на карте, к примеру изменение позиции или размера объекта.
Далее можно создать класс карты Map, на котором будет строиться сетка и унаследуем его от класса Obstacle.


Класс Map также будет отслеживать все изменения на карте, чтобы перестроить сетку если будет нужно.

Для этого наполним базовый класс Obstacle всеми необходимыми переменными и методами для отслеживания изменений объекта.


Здесь переменная renderer будет иметь ссылку на компонент SpriteRenderer, а переменные tempSize и tempPos будут использоваться для отслеживания изменений размера и позиции объекта.

Виртуальный метод Awake будет использоваться для инициализации переменных, а виртуальный метод CheckChanges будет отслеживать текущие изменения размера и позиции объекта и возвращать boolean результат.

На этом пока оставим скрипт Obstacle и перейдем к самому скрипту карты Map где также наполним его необходимыми параметрами для работы.


Переменная nodeSize будет указывать размер ячеек на карте, здесь я ее ограничил размера от 0.1 до 1, чтобы ячейки на сетке не были слишком мелкими, но и слишком большими. Переменная offset будет использоваться для отступа на карте при постройке сетки, чтобы сетка не строилась по краям карты.

Раз теперь на карте есть две новые переменные, то получается что их изменения также нужно будет отслеживать. Для этого добавим пару переменных и перегрузить метод CheckChanges в классе Map.


Готово. Теперь на сцене можно создать спрайт карты и кинуть на него скрипт Map.



Тоже самое проделаем с препятствием — создадим простой спрайт на сцене и кинем на него скрипт Obstacle.



Теперь у нас есть на сцене объекты карты и препятствия.

За отслеживание всех изменений на карте будет отвечать скрипт Map где в методе Update каждый кадр будем проверять этим самые изменения.


Таким образов в методе UpdateChanges карта будет отслеживать пока только свои изменения. Можно даже сейчас запустить игру и попытаться изменить размер карты или отступ offset, чтобы убедиться, что все изменения отслеживаются.

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

В классе Map создадим список всех возможных препятствий на карте и пару статических методов для их регистрации.


В статическом методе RegisterObstacle будем регистрировать новое препятствие Obstacle на карте и добавлять его в список, но прежде важно учитывать, что сама карта также наследуется от класса Obstacle и поэтому первым действием в методе нужно проверять не пытаемся ли мы зарегистрировать саму карту как препятствие.

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

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

Также, чтобы иметь простой доступ к скрипту Map из любого скрипта, я создал статическое свойство Instance которое вернет мне этот самый экземпляр карты Map.

Теперь вернемся обратно в скрипт Obstacle где будем регистрировать препятствие на карте, для этого добавим в него пару методов OnEnable и OnDisable.


Каждый раз когда мы будем создавать новое препятствие во время игры на карте, оно будет автоматически регистрироваться в методе OnEnable, где будет учитываться при постройки новой сетки и убирать себя с карты в методе OnDisable при его уничтожении или отключении.

Осталось только отследить изменения самих препятствий в скрипте Map в перегруженном методе CheckChanges.


Теперь у нас есть карта, препятствия — в общем все, что нужно для постройки сетки и теперь можно переходить к самому главному.

Постройка сетки

Сетка, в простейшем варианте это двумерный массив точек. Чтобы ее построить нужно знать размеры карты и размер точек на ней, после некоторых расчетов получаем кол-во точек по горизонтали и вертикали, это и есть наша сетка.

Есть много способов поиска пути на сетке. В этой статье все же главное понять как правильно использовать возможности системы задач, поэтому здесь я не буду рассматривать разные варианты поиска пути, их преимущества и недостатки, а возьму простейший вариант поиска A*.

В этом случае все точки на сетке должны иметь помимо позиции также координаты и свойство проходимости.

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


Почему координаты?
Дело в том, что в unity для указания позиции объекта в пространстве используется простой float который весьма неточен и может быть дробным или отрицательным числом, поэтому его будет сложно использовать для реализации поиска пути на карте. Координаты же выполнены в виде четкого int который всегда будет положительным и с которым работать намного проще при поиске соседних точек.

Для начала определим объект точки, это будет простая структур Node.


Эта структура будет содержать позицию position в виде Vector2, где с помощью этой переменной мы будем отрисовывать точку в пространстве. Переменная координат coords в виде Vector2Int будут указывать координаты точки на карте, а переменная id ее числовой номер по счету с помощью нее мы будем сравнивать разные точки на сетке и проверять существование точки.

Проходимость точки будет указываться в виде ее boolean свойства, но так как мы не можем использовать преобразуемые типы данных в системе задач, то укажем ее проходимость в виде int числа, для этого я использовал простое перечисление NodeType, где: 0 — это не проходимая точка, а 1 — проходимая.


Также для удобства работы с точкой я перегружу метод Equals, чтобы было проще сравнивать точки и также дополню проверочный метод на существование точки.


Так как номер id точки на сетке будет начинаться с 1 единицы, то я буду проверять существование точки как условие что ее id больше 0.

Переходим в класс Map где подготовим все для создания карты.
У нас уже есть проверка на изменение параметров карты, теперь нужно определить как именно будет выполняться процесс построения сетки. Для этого создадим одну новую переменную и несколько методов.


Свойство rebuilding будет показывать идет ли процесс построения сетки. Метод Rebuild будет собирать данные и задачи для построения сетки, далее метод OnRebuildStart будет запускать процесс построения сетки и метод OnRebuildFinish будет выполнять сбор данных из задач.

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


Как вы видите теперь в методе UpdateChanges есть условие, что пока идет построение старой сетки не начинать строить новую, а также в методе Rebuild первый действием проверяется не идет ли уже процесс построение сетки.

Решение задачи

Теперь немного о самом процессе постройки карты.
Так как для построения карты мы будем использовать систему задач и строить сетку параллельно, я использовал тип задачи IJobParallelFor, которая будет выполняться определенное число раз. Чтобы не нагружать процессом постройки какую-то одну отдельную задачу, будем использовать пул задач упакованных в один JobHandle.

Чаще всего, чтобы построить сетку используют два цикла вложенных друг в друга, чтобы строить к примеру по горизонтали и вертикали. В этом примере мы также будем строить сетку сначала по горизонтали, а потом по вертикали. Для этого в методе Rebuild вычислим кол-во горизонтальных и вертикальных точек, потом там же в методе Rebuild пройдемся циклом по вертикальным точкам, а горизонтальные уже будем строить параллельно в задаче. Чтобы лучше представить себе процесс построения взглянем на анимацию ниже.


Кол-во вертикальных точек будет указывать на кол-во задач, в свою очередь каждая задача будет строить точки только по горизонтали, после выполнения всех задач точки суммируются в одном списке. Именно поэтому мне и необходимо использовать задачу типа IJobParallelFor, чтобы в метод Execute передавать индекс точки на сетке по горизонтали.

И так структура точек у нас есть, теперь можно создать саму структуру задачи Job и унаследовать ее от интерфейса IJobParallelFor, тут все просто.


Возвращаемся в методе Rebuild класса Map, где произведем нужные расчеты по замеру сетки.


В методе Rebuild рассчитаем точный размер карты mapSize с учетом отступа, далее в verticals запишем кол-во точек по вертикали, а в horizontals кол-во точек по горизонтали. Если кол-во точек по вертикали равна 0 значит прекращаем постройку карты и вызываем метод OnRebuildFinish, чтобы завершить процесс. Переменная origin укажет место откуда мы будем начинать строить сетку — в примере это левая нижняя точка на карте.

Теперь можно переходить к самим задачам и наполнить их данными.
Во время постройки сетки в задаче нужен будет массив NativeArray куда мы будем помещать полученные точки, также раз у нас есть препятствия на карте нужно так же их будет передавать в задачу, для этого будем использовать еще один массив NativeArray, далее нам понадобиться в задаче размер точек, начальная позиция откуда будем строить точки, а также начальные координаты ряда.


Массив точек array я пометил атрибутом WriteOnly так как в задаче необходимо будет только “записывать” полученные точки в массив, напротив же массив препятствий bounds помечен атрибутом ReadOnly так как в задаче мы будем только “читать” данные из этого массива.

Ну и пока все, к расчету самих точек перейдем позже.

Теперь вернемся в класс Map где обозначим все переменные задействованные в задачах.
Здесь во-первых нам понадобиться глобальный handle задач, массив препятствий в виде NativeArray, список задач который будет содержать все точки полученные на сетке и Dictionary со всеми координатами и точками на карте, чтобы удобней было их искать потом.


Теперь опять возвращаемся в метод Rebuild и продолжим строить сетку.
Для начала инициализируем массив препятствий bounds, чтобы передать его в задачу.


Здесь мы создаем экземпляр NativeArray через новый конструктор с тремя параметрами. Первые два параметра я разбирал в прошлой статье, а вот третий параметр нам поможет немного сэкономить время создания массива. Дело в том, что мы будем записывать данные в массив сразу же после его создания, а значит нам не нужно убедиться в его очистке. Этот параметр полезно использовать для NativeArray которые будут только использоваться в режиме “чтения” в задаче.

И так, далее наполним массив bounds данными.


Теперь можно переходит к созданию задач, для этого пройдемся циклом по всем вертикальным рядам сетки.


Для начала в xPos и yPos получаем начальную позицию ряда по горизонтали.


Далее создаем простой массив NativeArray куда будут помещаться точки в задаче, здесь для массива array нужно указать сколько точек будет создано по горизонтали и тип аллокации Persistent, ведь задача может выполняться дольше чем один кадр.
После, создаем сам экземпляр задачи Job, помещаем в нее начальные координаты ряда startCoords, начальную позицию ряда startPos, размер точек nodeSize, массив препятствий bounds и уже в конце сам массив точек array.
Осталось только поместить задачу в handle и глобальный список задач.


Готово. У нас есть список задач и их общий handle, теперь можно запустить этот handle вызвав его метод Complete в методе OnRebuildStart .


Так как переменная rebuilding будет указывать, что идет процесс построения сетки, в самом методе UpdateChanges нужно также указать условие, когда этот процесс закончиться, используя handle и его свойство IsCompleted.


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


Для начала очищаем словарь nodes от предыдущих точек, далее с помощью цикла foreach перебираем все полученные точки из задач и помещаем их в словарь nodes , где ключ это координаты(НЕ позиция!) точки, а значение — сама точка. С помощью этого словаря нам будет проще искать соседние точки на карте. После наполнения очищаем массив array с помощью метода Dispose и в конце очищаем сам список задач jobs.

Также нужно будет очистить массив препятствий bounds, если он был ранее создан.

После всех этих действий получаем список всех точек на карте и теперь можно их отрисовать на сцене.


Для этого в классе Map создадим метод OnDrawGizmos где будем отрисовывать точки.


Теперь через цикл отрисуем каждую точку.


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


Для поиска соседних точек нам понадобиться просто найти нужную точку по ее координатам в 8 направлениях, поэтому в классе Map заведем простой статический массив направлений Directions и метод поиска ячейки по ее координатам GetNode.


Метод GetNode будет возвращать точку по координатам из списка nodes, но делать это нужно осторожно ведь если координаты Vector2Int будут неправильными возникнет ошибка, поэтому здесь используем блок обхода исключений try catch, который поможет обойти исключение и не “повесить” все приложение с ошибкой.

Далее пройдемся циклом по всем направления и попробуем найти соседние точки в методе OnDrawGizmos, и главное не забывайте учитывать проходимость точки.


Теперь можно смело запустить игру и посмотреть, что же вышло.


В этом примере мы строили только сам граф с помощью задач, но вот, что получилось у меня после того как я прикрутил к этой системе сам алгоритм А*, который так же использует Job system для нахождения пути, исходник в конце статьи.


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

Как и в предыдущей статье здесь система задач используется без ECS, если же использовать эту систему в паре с ECS, можно добиться просто потрясающего результата в приросте производительности. Удачи!

Исходник проекта поиска пути