• Игролог
• Игры
• Об авторе

Knighttron. Поиск пути

Ландшафт получается интересный за счет того, что, двигая тайлы вверх и вниз по импровизированной оси Z, можно придавать некоторый объем локациям. Но, когда речь заходит о поиске пути в таком ландшафте, то сразу становится понятно, что простой способ поиска пути, о котором я рассказывал ранее — тут не подходит. Проблема заключается в том, что я не могу просто расставить препятствия в определенные клетки и отталкиваться только от этой информации. Ведь когда мы поднимаем/опускаем один или несколько тайлов на критическую высоту, которая для персонажа не доступна, то получается так, что препятствиями должен стать не сам тайл, а его грани! Окружающие тайлы могут быть проходимыми, но мы не можем пересечь конкретно какую-то одну стенку между ними, потому что разница в высоте между этими тайлами может быть слишком большой.

�? как теперь производить поиск пути с учетом проходимости и не проходимости определенных граней?

Поиск пути в графе

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

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

В итоге основной задачей становится написать правильное построение ссылок между тайлами. В моем случае правило линкования тайла с соседними клетками заключается только в том, что текущий тайл не должен быть выше или ниже по оси Z, например на 20px, чем его соседи.

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

Далее остается только решить несколько небольших задачек, и уже казалось бы столько всего готово — это вдохновляет!

Непроходимые препятствия

�?значально маску карты я пытался построить таким образом, чтобы при перемещении в ней непроходимых объектов, например будь-то сундук или персонаж — ссылки бы на соседние тайлы автоматически удалялись и добавлялись. Если изменять только карту проходимости можно сделать очень простой алгоритм поиска пути, отказавшись от лишних проверок и при добавлении новых объектов в игру не пришлось бы добавлять новые условия, так как в этом случае алгоритму поиску пути не нужно ничего знать об объектах, достаточно следовать созданным связям и все!

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

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

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

Определение текущего тайла

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

В случае с плоскими картами все понятно: зная ширину и высоту тайла, мы просто делим текущие координаты мыши на них и получаем координаты тайла, например:

tileX = Math.ceil(mouse.x / tileWidth);
tileY = Math.ceil(mouse.y / tileHeight);

Но как же быть с тайлами, которые могут быть сдвинуты по Z вверх или вниз?! Конечно, о таком простом и лаконичном определении текущего тайла уже не могло быть и речи.

Пришлось для всех тайлов сделать чувствительные зоны (boundbox), которые определяли поверхность тайлов. Далее при перемещении мыши, или каждый 2-3 кадр игрового цикла выполняется проверка попадания точки курсора мыши в чувствительные зоны тайлов.

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

Построение пути

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

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

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

Что дальше?

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

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

О даа! Еще до того, как в игре появились первые монстры, я понял что в игре должна быть физика на базе Box2D, но зачем это нужно в игре с top-down видом?! Об этом я расскажу в следующий раз...

Другие записи из этой серии

1. С чего все начиналось
2. Ландшафтные приключения
3. Анимация персонажей
4. Поиск пути
5. Физика в Knighttron
6. Продолжение следует...