GameMaker Studio 2. Урок 6. Алгоритмы поиска путей. Оптимизация игры⁠⁠

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

Сразу оговорюсь, что многое из того, что вы будете видеть - это моя адаптация того, что можно было свободно найти в интернете, в том числе скрипты. Я не являюсь их создателем или первооткрывателем, а потому везде будут присутствовать ссылки на те источники, что я использовал сам в своё время.
Может, вам их будет проще понять :)

Ссылки на предыдущие гайды:

Первый гайд - Знакомство.

Второй гайд - События отрисовки, коллизия, скрипты.

Третий гайд - Камера и разрешение экрана.

Четвертый гайд - Иерархия объектов. Глобальные переменные.
Пятый гайд - Структуры данных. Сетка комнаты и размещение объектов по сетке.

Оглавление:
- Поиск путей. Что это и как работает?
- Встроенные средства для работы с путями.
- Алгоритмы поиска путей. Какие существуют?
- Алгоритмы поиска путей. Скрипты.
- Оптимизация. Что это и зачем?
- Оптимизация. Исправляем ошибки и учимся их избегать.

Поиск путей. Что это и как работает?

Как понятно из названия, поиск путей решает ровно одну задачу - он ищет ближайший путь от точки А до точки Б. Все алгоритмы поиска путей решают эту задачу, но каждый по своему.
О существующих алгоритмах мы поговорим ниже. Пока стоит разобраться, как они работают в общих чертах.

Итак, представим сетку комнаты, которую мы делали ранее. Это набор точек, каждая из которых имеет собственные координаты.
Так как сетка у нас квадратная, то каждая точка, кроме крайних, имеет четыре (восемь, если учитывать диагонали) "соседей". Таким образом, из одной точки мы можем попасть в любую соседнюю.
Любой алгоритм поиска путей занимается тем, что пытается попасть из точки А в точку Б, перебирая соседние клетки. Занимая соседнюю клетку, он проходится по её "соседям" и так до тех пор, пока не будет достигнута точка конца или не кончатся "соседи".
На самом деле, необязательно иметь именно квадратную сетку, чтобы поиск путей работал, ведь поиск путей, по своей сути, работает на более высоком уровне: графах.

Граф - это модель, состоящая из множества вершин и множества соединяющих их рёбер.
Ниже - пример графа из заданий по информатике на экзаменах.

Таким образом, любая сетка - это лишь определённое представление графа.

Встроенные средства для работы с путями.

Для работы с путями в GMS 2 существует ряд функций, которые начинаются с приписки: mp, которая расшифровывается как планирование движения (motion planning), а также path.
Чтобы была возможность строить пути, прежде всего нужно создать сетку комнаты. Для этого существует команда:

global.grid_mp = mp_grid_create(0, 0, cells_x, cells_y, CellWidth, CellHeight)

Где cells_x, cells_y - количество сеток по осям x, y, а CellWidth и CellHeight - ширина и высота одной клетки.

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

var new_path = path_add()
var mp_path = mp_grid_path(global.grid_mp, new_path, fcell_coords[0] * CellWidth + 16, fcell_coords[1] * CellHeight + 16, scell_coords[0] * CellWidth + 16, scell_coords[1] * CellHeight + 16, 1)
if mp_path
{
draw_path(new_path, fcell_coords[0] * CellWidth + 16, fcell_coords[1] * CellHeight + 16, false)
}

Где fcell_coords и scell_coords - два массива, хранящие клетки по x,y старта и конца соответственно.
Функция path_add() - создаёт путь.
Функция mp_grid_path() строит путь между указанными координатами по сетке. Если путь существует, то возвращает true, иначе - false. Если путь существует, то сохраняет в переменную пути, указанную в скобках, точки, которые предстоит пройти.

Таким образом у вас будет отрисован путь по клеткам.
Чтобы увидеть сетку, нужно написать:

draw_set_alpha(0.25)
mp_grid_draw(переменная_которая_хранит_сетку)
draw_set_alpha(1)

Чтобы добавить на неё препятствия существуют команды:

mp_grid_add_cell() // Закрашивает одну определённую клетку, делая непроходимой.
mp_grid_add_instances()  // Закрашивает все клетки, на которых расположены определённые объекты.
mp_grid_add_rectangle() // Закрашивает определённую прямоугольную область.

Создать путь - это только первый шаг. Второй - это запустить по нему объект двигаться. Для этого есть функция:

path_start(путь, скорость, что_сделать_в_конце_пути, абсолютный_путь_или_к_текущей_позиции)

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

Но у такого подхода есть и минусы. Главный из них - ограниченность инструментария. Он позволяет нормально работать только с квадратными сетками и не учитывает "стоимость" клеток, по которым проложен путь.
Рекомендую использовать встроенные средства в тех случаях, когда вы создаёте простую игру, где о подобных мелочах можно не заботиться. Они достаточно хорошо оптимизированы. А мы идём дальше.

Алгоритмы поиска путей. Какие существуют?

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

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

Поиск в ширину.

Это рекурсивный алгоритм поиска всех вершин графа или дерева. Обход начинается с корневого узла и затем алгоритм исследует все соседние узлы. Затем выбирается ближайший узел и исследуются все неисследованные узлы.

Сам алгоритм:

1. Перейдите на соседнюю нерассмотренную вершину. Отметьте как рассмотренную. Отобразите это. Вставьте ее в очередь.
2. Если смежная вершина не найдена, удалите первую вершину из очереди.
3. Повторяйте шаг 1 и шаг 2, пока очередь не станет пустой.

Если же говорить своими словами, то данный алгоритм равномерно исследует все доступные точки. Такой алгоритм часто применяется при генерации карт, либо для их исследования. Правда, он не строит пути как таковые. Он просто показывает, как мы можем посетить все точки на карте.
Источник

Алгоритм Дейкстры.
Данный алгоритм находит кратчайшие пути от одной из вершин графа до всех остальных. Работает только для графов без рёбер с отрицательным весом, иными словами - не может работать в тех случаях, когда стоимость клетки отрицательная. Это важно.
Таким образом, суть алгоритма заключается в том, чтобы найти найти все возможные пути из точки А в каждую из других существующих, а затем среди них выбрать самые дешёвые.
Алгоритм действенный и полезный, но достаточно медленный, если речь заходит о поиске пути между двумя конкретными точками. Но, это не беда, ведь существует следующий алгоритм.

Алгоритм A* (A star).
Данный алгоритм является вариацией алгоритма Дейкстры, скрещённого с жадным поиском и эвристическим поиском. То есть, он старается выбирать и самые дешёвые пути, и самые "близкие" к конечной точке.

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

Квадратная сетка.

abs(a[0] - b[0]) + abs(a[1] - b[1]) // a[0],b[0] - координаты по оси x, a[1], b[1] - по оси y. abs возвращает абсолютное (всегда положительное независимо от результата) значение.

Гексогональная сетка.

(abs(qa - qb) + abs(ra - rb) + abs(sa - sb)) / 2 // где q, r, s - это координаты в кубической системе.

Источник для гексов
Статья с Хабра с подробным разбором, взятая за основу.

Алгоритмы поиска путей. Скрипты.

Переходим ко вкусному.
Поиск соседей на квадратной сетке.
***
Алгоритм А* на GML.
Небольшая особенность данного скрипта. Если клетка, в которую мы хотим прийти, является непроходимой, то мы всё равно строим до неё путь. Встать на неё мы всё равно не сможем, но получим ближайший к данной точке путь.
Важно. Работает это только для соседних к конечной клеток.
Как работает:
Если найден, возвращает путь в виде массива между двумя точками. Точки старта и конца должны быть переданы в виде их порядкового номера. Если путь не найден, возвращает noone.
Соответственно, чтобы отрисовать путь - нужно будет пройтись по массиву из точек.

Поиск соседей на гексагональной сетке отличается только координатами. Вместо x и y мы используем q, r, s, которые являются трёхмерным представлением двумерных координат.

col - это столбец, row- это строка. x и y по сути.
q = col
r = row - (col - (col & 1)) / 2
s = -q - r

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

По сути - всё. Дальше стандартно: проверяем, что мы не выходим за границы сетки и если стоимость гекса != 0 (или больше 0), то добавляем его.

Оптимизация. Что это и зачем?

Я думаю, каждый знаком с термином "оптимизация". Если же нет, то вики говорит нам:

Оптимизация — процесс максимизации выгодных характеристик, соотношений (например, оптимизация производственных процессов и производства), и минимизации расходов.

Мы, как разработчики, должны позаботиться об оптимизации игры. Первое, что бросается в глаза - это оптимизация кода. Покрывая наши потребности, он должен при этом быть максимально простым и лёгким, чтобы не давать лишнюю нагрузку на ПК.

Конкретно в случае с GMS, есть некоторые моменты, которые стоит запомнить.
- Используйте локальные переменные.
Вместо того, чтобы постоянно получать результат функции, сохраните его один раз в переменную и используйте её в дальнейшем.
Вместо постоянного обращения к глобальным переменным, сохраните глобальную переменную в локальную и обращайтесь к ней. И так далее. Это быстрее.

- Старайтесь использовать объекты по минимуму.
На фоне предыдущих гайдов это прозвучит несколько странно, ведь мы заполняли комнату объектами полностью. Делалось это с целью теста, не более того.
В нашем с вами случаем, ребята, гораздо быстрее хранить информацию о каждой клетке в массиве, а клетки отрисовывать через тайлмап.
Объект, даже если он занимается только отрисовкой собственного спрайта, нагружает систему больше. Поэтому проще отрисовать спрайт отдельно. Прирост ФПС составит до 6 раз. ( Замерял, выросло с 500 до 2500 в среднем :) )

О том, как это работает и реализацию покажу ниже. :)

- Не рисуйте объекты, которые находятся за границами камеры.
Очевидный, но важный совет, так как draw event является крайне ресурсоёмким, как и step.

- Не делайте проверку коллизий там, где это не нужно. Если делаете, то сохраняйте результат в локальную переменную.

Оптимизация. Исправляем ошибки и учимся их избегать.

Первое, что мы сделаем - это создадим один большой спрайт, на котором разместим все наши игровые спрайты. Важно, чтобы первая клетка была пустой!
Затем - создайте объект Tileset и назначьте ему этот спрайт.
На скриншоте ниже показано, почему первая клетка должна быть пустой.

Дальше - создайте слой комнаты типа "Тайл" и назначьте ему тайлсет.

Всё, теперь мы готовы использовать вместо объектов - тайлы. Причём сразу для всех видов: и для фона, и для непосредственно отрисовки объектов, и для украшательств: спрайтовых теней.
Теперь в oGrid нужно будет заменить старый код на новый.
Ссылка на код.

Кратко пробежимся по тому, что мы используем и как.
lay_id_blocks = layer_get_id("Название_Слоя") - Здесь мы получаем ID нашего слоя.

var map_id_blocks = layer_tilemap_get_id(lay_id_blocks) - Здесь мы получаем слой тайлов, используя ID слоя.
tilemap_set(map_id_blocks, Tile.ground, _x, _y) - Здесь мы устанавливаем у слоя тайлов, по определённым координатам, определённую картинку. Tile.ground возвращает 1, следовательно будет отрисована первая клетка из нашего тайлсета. Нулевая клетка - пустая, используется для удаления тайлов.
С-но, для получения текущего тайла существует команда tilemap_get(map_id_blocks, клетка_x, клетка_y). Если по указанной позиции установлен тайл, вернёт его номер. Если нет - вернёт ноль. Вернёт -1, если есть ошибка.

Специально не обращаю внимание на то, как пришлось переписывать код, так как по сути изменилось лишь взаимодействие, которое вкратце - описано выше.

Для отрисовки теней используется отдельный слой, где в определённом порядке расположены тени. Это важно, так как используется скрипт для автоматического тайлинга, то есть - автоматического определения того, какую тень нам нужно рисовать.

Ссылка на оригинальный скрипт для интересующихся:
https://github.com/iAmMortos/autotile

Как ускорить проекты, сделанные на Gamemaker Studio 2 под Windows

Здесь есть вся нужная информация. Делается с помощью компиляции под С++.
https://help.yoyogames.com/hc/en-us/articles/235186048-Setti...

Будем прощаться, ребята.

Ссылка на исходник
Там два файла. YYZ - для тех, кто хочет повтыкать в код. В папке - уже скомпилированный проект, для тех, кто просто хочет потыкать и посмотреть, как это всё добро работает.

Темы, которые осталось разобрать:
- Сохранение. Встроенное VS самописное. Работа с файлами.

- Звуки.

Дальше в формате небольших постов будут выкладываться полезные скрипты (и не только) для стратегий, плюс буду рассказывать о ходе разработки. Фактически, уже на данном этапе у вас есть "скелет" игры.

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