BW (bwolf33) wrote,
BW
bwolf33

Учусь программировать. Настоящий поиск пути. А*.

ч.3 Учусь программировать. Знакомлюсь в теорией поиска пути.

Закончив, интсрумент по созданию путевых точек, у меня стали спрашивать, а можно ли этим инструментом создавать тоже самое в процессе игры ? Я не стал добавлять поддержку создания путей в рантайме, потому что в интернете полно описаний и готовых решений реализации различного рода поисков пути и в самом игровом движке даже в Free Версии есть встроенный поиск пути. Зачем делать одно и тоже думал я :)...

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

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

В интернете полно различного рода реализаций поиска пути, которые хороши для простых задач, но требуют доработки и заточки для более сложных. Так начались поиски наиболее универсального и достаточно быстрого алгоритма, снова чтение описаний, изучение преимуществ и недостатков, на которые я потратил несколько дней, а также же поиск более менее сносной документации. И снова на русском языке что либо найти оказалось весьма проблематично, поэтому приходилось вновь применять навыки переводчика :)). Тогда для меня это казалось неимоверно сложным, сейчас я уже вижу, что 80-90% текста описаний алгоритмов - это ненужная вода, и порой даже попытки запутать неискушенного в этом деле.


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

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

Первые результаты появились уже через пару дней. Это была еще достаточно кривая реалзация, но по скорости вычисления она уже не уступала некоторым имеющимся в сети реализациям. Я даже пробовал качать демо версию коммерческого проекта для Unity, чтобы сравнить скорости :). Тут же пригодились уже изученные навыки построения Mesh, которые и легли в основу визуализации проходимости клетки. Я тут же создал тему на форуме где описывал чего же уже сделано тема с поиском пути



Путь вычислялся не совсем правильно, но начало уже было положено. Основная проблема, с которой сталкиваются многие изучающие алгоритм А* заключается в том, что если на поле имеются достаточно большие препятствия и узкие проходы между ними и нужно найти путь от одного конца карты в другой, то проверяется огромное количество клеток. А если путь вообще невозможно проложить, допустим цель закрыта препятствием со всех сторон, то для больших карт - это верная смерть и жестокие провисоны :). Так сформировались две задачи которые необходимо было решать уже самостоятельно.

Не буду расписывать подробностей, но первую задачу я решил дня через 3-4 упорных экспериментов, увеличив скорость вычисления пути на картах с подобными препятствиями в 150 раз.
Вот что я имел ввиду: первый запуск - старая реализации, второй уже улучшенная:


Для меня это был прорыв. Я впервые смог улучшить достаточно сложную вещь :). Как видно уже были исправлены некоторые неточности в самом поиске, и кратчайший маршрут ищется правильно.

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

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

Я нашел несколько статей с описанием создания таких легендарных игры как WarCraft и StarCraft. В них авторы также кратно описывали некоторые сложности с созданием поиска пути.

А затем, я натолкнулся на две весьма любопытные игры-песочницы: RimWorld и Factorio. В них была интересная система контроля энергетических ресурсов. В качестве примера я взял первую игру, и стал детально ее изучать. В RimWorld уже имеется динамическая система поиска пути, основанная на том же А*, плюс распределение электричества от генераторов к потребителям (лампочкам, различным устройствам) так же происходит по похожему алгоритму.
Повозившись с кодом у меня получилась похожая система. Это был первый вариант динамического поиска, в виде поиска источника энергии :).


А следующим шагом стала почти полная динамика поиска пути персонажами. Почему почти ? я так и не смог даже на сегодняший день полнолстью реализовать обход персонажами друг друга в реалтайм движении. Для тактических игр с пошаговым передвижением персонажей на сегодняший день уже сделал :).

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

В процессе поиска различных готовых решений, а также для сравнения скорости, я натолкнулся вот на такую тему, где описывался самый быстрый поиск пути по А*, который автор назвал Crystal Path Finding
но использовал низкоуровневое программирование и кучу оптимизаций, до который у меня даже мозгов не хватает. Скорость его алгоритма еще в 30 раз быстрее моего, по крайней мере исходя из тестовой сцены, что он выложил. Есть куда стремиться :).

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

Поэтому отложив получившийся вариант на полочку, я начал писать уже полностью свою реализацию А* с нуля затачивая ее чисто для 2Д режима, а на сегодняший день готово и для 3Д, но об этом будет описано дальше...

ч5. Учусь программировать. Первый 2Д редактор карты.
Tags: gamedev, unity3d, Учусь программировать, дневник разработчика, программирование
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 0 comments