Привет всем! Сегодня я расскажу вам о своем опыте реализации алгоритма поиска пути на C# для игр на движке Unity3D.
Все началось с поиска "алгоритма поиска пути" на C# чисто под Unity. На AssetStore были найдены "вроде" работающие, но без бюджета на покупку ассета далеко не уедешь - а вдруг он не подойдет, такое же возможно:/ Решил поискать в Google - для этого то он и нужен, чтобы искать, не так ли?:) Поиск в гугле дал нам интересные алгоритмы поиска пути, а именно:
-
AStarFinder* -
BreadthFirstFinder* -
BestFirstFinder
-
DijkstraFinder* -
BiAStarFinder
-
BiBestFirstFinder
-
BiDijkstraFinder* -
BiBreadthFirstFinder* -
JumpPointFinder* -
OrthogonalJumpPointFinder* -
Trace
Одним из минусов было то, что времени на изучение алгоритма не было, и они были изначально сложны для понимания, поэтому я решил написать свое подобие алгоритма A*.
Что из этого вышло - вполне рабочий алгоритм для поиска пути.
Единственным его минусом было то, что он мог "запутаться" в поиске пути и считать, что больше выходов нет.
Как построен алгоритм:
У нас есть двумерная матрица - карта перемещений, будем называть ее массивом ячеек перемещения. У каждой ячейки есть свой индекс. Мы можем перемещаться по двумерной матрице в 6 разных
направлениях.
Чтобы все стало ясно будем использовать термины из Unity3D.
У нас есть генератор двумерной сетки,который инстантирует префабы ячейки. Есть префаб самой ячейки на котором есть скрипт-компонент отвечающий за эту ячейку, в котором описаны ссылки на
соседние ячейки. При спавне, ячейка записывается в главный массив ячеек, а также получает список всех соседних ячеек по ID в матрице. Также в скрипте есть метод, возвращающий соседнюю клетку
исходя из направления, по которому требуется найти путь, если клетка перекрыта, получаем открытую клетку из рядом стоящих клеток, вот той закрытой клетки и возвращаем ее ID.
Также есть главный скрипт поиска пути, который в принципе оперирует всеми ячейками и выстраивает из них путь к выходу.
Что же в нем такого есть. А есть в нем метод, который возвращает следующую открытую ячейку исходя из направления. Этот метод нам нужен для составления пути. Главным методом является тот,
который составляет путь, - как же он это делает?! В метод мы получаем текущую позицию и начинаем записывать путь. Берем текущую ячейку, получаем следующую открытую ячейку по одному из шести
направлений, делаем текущую позицию указателя на ячейку на эту открытую ячейку и опять получаем следующую открытую ячейку по тому же направлению, по которому и запустили поиск пути.
Итак по кругу пока не дойдем до выхода. Если выхода в конце нет - значит путь не подходит и он удаляется. После нахождения всех доступных путей, мы перебираем все найденные пути, выбираем самый
ближайший и начинаем перемещаться по этому пути. О, и да, также у нас есть метод, который запускает поиск пути по 6 направлениях.
Вот и все, теперь можно спокойно юзать этот простой алгоритм поиск пути. Конечно, до идеала ему далеко, но в небольших играх где не требуется четкий поиск пути можно в принципе его
использовать - по крайней мере, меня он пока устраивает и, возможно я улучшу его и расскажу вам о нем еще что то.
Спасибо за внимание - с вами был Artem FG Shyriaiev.
Write a comment