Учусь программировать. Настоящий поиск пути. А*.
ч.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Д редактор карты.
Закончив, интсрумент по созданию путевых точек, у меня стали спрашивать, а можно ли этим инструментом создавать тоже самое в процессе игры ? Я не стал добавлять поддержку создания путей в рантайме, потому что в интернете полно описаний и готовых решений реализации различного рода поисков пути и в самом игровом движке даже в Free Версии есть встроенный поиск пути. Зачем делать одно и тоже думал я :)...
А затем я попробовал воспользоваться некоторыми такими инструментами и понял, что большинство универсальных вещей часто ущербны, если делаются не настоящими профессионалами и для каждой контретной задачи часто нужен свой подход к решению. Мой инструмент для создания путевых точек тоже был своего рода универсальным инструментом, который можно расширять и развивать, но поскольку я не профессионал - то получилась не самая лучшая штука, хотя для простых задач она весьма удобна и даже проще большинтва других решений.
Поиск пути - это один из сложнейших механизмов любой игры. А хороший поиск пути - это зависть, куча текста и обсуждений, а также повод гордиться :).
В интернете полно различного рода реализаций поиска пути, которые хороши для простых задач, но требуют доработки и заточки для более сложных. Так начались поиски наиболее универсального и достаточно быстрого алгоритма, снова чтение описаний, изучение преимуществ и недостатков, на которые я потратил несколько дней, а также же поиск более менее сносной документации. И снова на русском языке что либо найти оказалось весьма проблематично, поэтому приходилось вновь применять навыки переводчика :)). Тогда для меня это казалось неимоверно сложным, сейчас я уже вижу, что 80-90% текста описаний алгоритмов - это ненужная вода, и порой даже попытки запутать неискушенного в этом деле.
Мне гораздо проще даются некие структурированные вещи. К примеру алгоритм поиска типа NavMesh - это несколько более хаотичное представление. Поэтому выбор пал на алгоритм А*, как наиболее распространенный, достаточно быстрый, упорядоченный и универсальный алгоритм.
И снова начались упорные поиски уже некоторых решений алгоритма. Скажу честно, чужой сложный код без подробных описаний я читаю даже сейчас с трудом, но на тот момент моих знаний было недостаточно, чтобы делать подобное самостоятельно и найдя наиболее подробное описание и код, я начал переносить буквально пошагово проверяя, а что будет если сделать вот так или изменить вот тут и вникал в суть.
Первые результаты появились уже через пару дней. Это была еще достаточно кривая реалзация, но по скорости вычисления она уже не уступала некоторым имеющимся в сети реализациям. Я даже пробовал качать демо версию коммерческого проекта для Unity, чтобы сравнить скорости :). Тут же пригодились уже изученные навыки построения Mesh, которые и легли в основу визуализации проходимости клетки. Я тут же создал тему на форуме где описывал чего же уже сделано тема с поиском пути
Click to viewПуть вычислялся не совсем правильно, но начало уже было положено. Основная проблема, с которой сталкиваются многие изучающие алгоритм А* заключается в том, что если на поле имеются достаточно большие препятствия и узкие проходы между ними и нужно найти путь от одного конца карты в другой, то проверяется огромное количество клеток. А если путь вообще невозможно проложить, допустим цель закрыта препятствием со всех сторон, то для больших карт - это верная смерть и жестокие провисоны :). Так сформировались две задачи которые необходимо было решать уже самостоятельно.
Не буду расписывать подробностей, но первую задачу я решил дня через 3-4 упорных экспериментов, увеличив скорость вычисления пути на картах с подобными препятствиями в 150 раз.
Вот что я имел ввиду: первый запуск - старая реализации, второй уже улучшенная:
Для меня это был прорыв. Я впервые смог улучшить достаточно сложную вещь :). Как видно уже были исправлены некоторые неточности в самом поиске, и кратчайший маршрут ищется правильно.
Честно признаюс, вторую задачу я решил, но несколько иначе, чем это должно решаться. По идее при создании таких непроходимых зон их нужно отделять от основной зоны, тем самым сразу прерывая поиск пути и не затрачивая драгоценное время. Но для этого необходимо научиться правилам заливки многоугольников (это любой видел в Paint или других графических редакторах). Я в эту тему пока не вникал, но что читать уже есть и возможно в ближайшее время свое текущее решение я все же заменю на правильное. Для большинства задач вполне достаточно уже того, что получилось.
Статическая карта с препятствиями это конечно неплохо, но я на этом не остановился, ведь основная моя метча создать полностью изменяемый мир, а значит и поиск пути это должен учитывать.
Я нашел несколько статей с описанием создания таких легендарных игры как WarCraft и StarCraft. В них авторы также кратно описывали некоторые сложности с созданием поиска пути.
А затем, я натолкнулся на две весьма любопытные игры-песочницы: RimWorld и Factorio. В них была интересная система контроля энергетических ресурсов. В качестве примера я взял первую игру, и стал детально ее изучать. В RimWorld уже имеется динамическая система поиска пути, основанная на том же А*, плюс распределение электричества от генераторов к потребителям (лампочкам, различным устройствам) так же происходит по похожему алгоритму.
Повозившись с кодом у меня получилась похожая система. Это был первый вариант динамического поиска, в виде поиска источника энергии :).
А следующим шагом стала почти полная динамика поиска пути персонажами. Почему почти ? я так и не смог даже на сегодняший день полнолстью реализовать обход персонажами друг друга в реалтайм движении. Для тактических игр с пошаговым передвижением персонажей на сегодняший день уже сделал :).
На видео динамичный поиск пути 200 персонажей, которые гоняются за управляемым мной ботом без каких либо тормозов. Их путь постоянно изменяется, повляются/удаляются препятствия. Скажу честно - это еще не максимальная скорость обработки, которой я смог достичь, но на тот момент для это было весьма хорошим достижением.
В процессе поиска различных готовых решений, а также для сравнения скорости, я натолкнулся вот на такую тему, где описывался самый быстрый поиск пути по А*, который автор назвал Crystal Path Finding
но использовал низкоуровневое программирование и кучу оптимизаций, до который у меня даже мозгов не хватает. Скорость его алгоритма еще в 30 раз быстрее моего, по крайней мере исходя из тестовой сцены, что он выложил. Есть куда стремиться :).
Поигравшись еще какое то время, я решил попробовать сделать еще один минипроект в 2Д и стокнулся с новой трудностью. То, что уже получилось, содержало много излишков для 2Д игр и было ущербной недосистемой для 3Д.
Поэтому отложив получившийся вариант на полочку, я начал писать уже полностью свою реализацию А* с нуля затачивая ее чисто для 2Д режима, а на сегодняший день готово и для 3Д, но об этом будет описано дальше...
ч5. Учусь программировать. Первый 2Д редактор карты.