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. Продолжение следует...

 


Индикаторы: Разное, Уроки
Постоянная ссылка

 

 

Ничего себе! Вот это мозг! Спасибо!

Vladimit
27 Августа 2015
— 20:05
#

Круто. Я Как раз занимаюсь поиском пути в графе, и тут Ваша статья. Конечно технической информации мало (да и не нужна) но теперь я знаю что на правильном пути.

BolT
28 Августа 2015
— 06:14
#

Спасибо за статью))

GreenFest
28 Августа 2015
— 09:38
#

Это опять я!

Серьёзно затягивает,так как вы объясняете всё понятно для тех кто ещё только начинает этим заниматься.
И спасибо кстати за то что все объяснили насчет языков в прошлой статье!

SQUASH
28 Августа 2015
— 09:45
#

Приятно видеть как блог оживает. :)

Несколько лет назад Ваши уроки помогли мне разобраться с Flash / AS3.

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

Спасибо!

little bisquit
28 Августа 2015
— 23:22
#

На первый взгляд все кажется довольно-таки сложным, но на деле оказалось вроде-как не так и сложно! Спасибо :)

Правда в своем игровом и небольшом проекте не рассчитываю делать рельеф локаций.

Георгий
29 Августа 2015
— 21:06
#

Что за движок у зомботрона? Самодельный?

Пехл
30 Августа 2015
— 15:26
#

@Пехл, да, в Зомботроне используется самодельный фреймворк Anthill. Он свободно распространяется с открытым исходным кодом, вы можете использовать его в своих проектах.

Ant.Karlov
30 Августа 2015
— 20:18
#

В предыдущей статье вопрос задавал.

@Ant.Karlov
> но спонсоры/издатели настойчиво уговаривают переходить на Unity.

Можно подробнее пожалуйста?

Насколько мне известно Chrome полностью отказывается от какого то плагина на котором вэб плеер юнити работает. Как читал на форумах фгл, у некоторых спонсоров, игры после отключения, потеряли 50 процентов пользователей. Y8 games создали тему в начале года с призывом порты на WebGL делать из unity5, но не похоже что они их покупают. у WebGL порта проблемы с утечкой памяти и команда юнити с нетерпением ждёт когда майкрософт выпустит кроссбраузерный плагин assembly, чтобы все проблемы WebGL порта решить, но случится это, если верить роадмапу юнити, не раньше лета 2016. Вот и интересно почему спонсоры просят на юнити переходить? если из за мобилок то понятно) а так не очень понятно.

AlexKLS
30 Августа 2015
— 23:50
#

Отличная игра! Когда будет продолжение Зомботрона? Жду с нетерпением!

Art2567
31 Августа 2015
— 10:26
#

@AlexKLS,

>> но спонсоры/издатели настойчиво уговаривают переходить на Unity.

> Можно подробнее пожалуйста?


Речь конечно же идет о PC/Mobile версии игры, поэтому спонсоры имеющие интерес к финансированию, хотят чтобы я использовал какой-то известный движок. Это позволит сделать быстро и удобно порты игры на разные платформы. Скорее всего для новой версии Зомботрона не будет флеш версии. Но пока каких-либо деталей по этому поводу не могу сообщить, так как ничего еще не решено.

Ant.Karlov
31 Августа 2015
— 18:11
#

@Ant.Karlov, то есть спонсоры потихоньку охладевают к вебу или вас как опытных разработчиков хотят видеть в более денежных отраслях? по сути извечный вопрос задаю "на сколько сильно умер флэш в вэбе"? :-) и есть ли шансы у веб портов Unity на FGL? спасибо

AlexKLS
31 Августа 2015
— 21:07
#

@AlexKLS,

> то есть спонсоры потихоньку охладевают к вебу или вас как опытных разработчиков хотят видеть в более денежных отраслях?

Это давно уже как общеизвестный факт :) Спонсоры ищут новые возможности для вкладывания денег. Впрочем тотального холода на флеш игры сейчас еще не наблюдается и флеш игры по прежнему продаются. Флеш порталы никуда не делись еще и требуют пополнения и обновления контента. Но спад определенно есть.

Про Unity порты ничего определенного пока сказать не могу так как мной эта тема не изучалась. Но мне казалось, что сама по себе эта технология хорошо работает в Web и у нее есть будущее, но все это было ровно до тех пор пока не случились последние события с массовым отключением Unity плеера :(

Ant.Karlov
31 Августа 2015
— 21:45
#

Салют!
У меня просьбопредложение на счет очередной темы урока.

Основная масса материалов по теме "Геймдев Для Чайников" дает возможность создать игру-песочницу. В смысле с полученным багажом знаний можно предложить пользователю "неблагополучную" среду и дать возможность как то ей противостоять. А дальше скомандовать либо "Держись изо всех сил!", либо "Доберись к воооон той точке...". А как быть с играми в жанре Квест или РПГ? Как в процессе игры предлагать (иногда опционально) выполнение отдельных задач; как эти задачи описать; как их обрабатывать; как отслеживать ход выполнения задачи (для сохранения/загрузки); как, в конце концов, вносить изменения в мир игры после выполнения или провала.

Я в эту тему не углублялся, так что даже толком сформулировать вопрос не могу. Но Рыцаретрон в этом плане далеко шагнул, по сравнению с предыдущими играми, а значит с многими вопросами пришлось столкнутся и даже успешно их решить. Очень бы хотелось увидеть цикл уроков по этой теме. Или даже не уроков, а скорее исповедей ;) . В смысле интересен скорее ход мысли, который привел к созданию квестового движка для игры, чем просто рецепт из справочника.

elder_Nosferatu
27 Сентября 2015
— 07:15
#