Unity: Поиск пути
Alex SilaevДавайте поговорим про поиск пути. Я не буду описывать реализацию алгоритмов, хочу лишь описать возможные варианты, а если вас устроит один из них - вы без труда найдете готовую реализацию или напишете сами.
Для начала определимся какие обычно встречаются варианты графов:
- Grid - массив точек
2. Mesh - треугольники или mesh
3. Point - граф из точек
4. Circles - граф с круглыми препятствиями
По сути это 4 основных варианта, у каждого может быть много подвидов, давайте рассмотрим их подробнее.
Существует множество алгоритмов, которые обычно применяют для поиска пути в гридах: A*, dijkstra, JPS, RSR, ну и всякие различные модификации (Кстати, A* является модификацией dijkstra, а JPS дополнение к A*).
По сути любой из этих алгоритмов можно использовать в любом из графов, т.к. любой граф остается графом и не важно как именно он представлен: сеткой, мешом или точками.
Все графы сводятся к тому, что существуют ноды и их соседи, которые описаны в этих нодах (Если граф Grid, то описывать соседей не нужно, т.к. можно просто смещаться в массиве для поиска соседа). Если добавить к каждой ноде графа вес, то можно строить путь с учетом различных препятствий, которые замедляют или ускоряют передвижение.
В любом A* like алгоритме на вход даются 2 точки: откуда и куда. На выходе же мы получаем массив точек, по которым нужно пройти, чтобы дойти до цели. Проблема такого алгоритма при перемещении - это эффекты, которые могут действовать на персонажа во время передвижения. Как только вы сходите с пути - вам нужно либо перестроить путь, либо построить дополнительный путь для возврата на изначальную траекторию. Опять же проблемой будут являться двигающиеся объекты (например, дорога в какой-то момент может оказаться перекрыта совсем или двигающаяся стена меняет свою позицию). В любом случае придется перестраивать путь, если на пути окажется подобное препятствие.
Существует еще такой алгоритм как FlowField и его разновидности. В таком алгоритме нас не интересует начальная точка, интересует только конечная. Смысл сводится к тому, что мы просчитываем все поле сразу для единственной конечной точки, а каждой ноде присваиваем направление. Такой алгоритм начинается с конечной точки и заканчивается, когда все ноды графа будут обработаны. Из плюсов - это бесплатное перестроение пути, если юнита выталкивают с его изначального пути, это является проблемой для A* или NavMesh, но не является проблемой для FlowField, т.к. тут из любой точки мира путь уже найден. Чтобы передвигаться по такому пути, нам не нужно хранить массив точек для перемещения, а нужно всего лишь иметь ссылку на массив направлений. Все еще проблемой будут динамические препятствия, но уже в меньшей степени, т.к. можно будет пересчитать только зону этого препятствия, не затрагивая остальные вектора. Из минусов такого алгоритма - это потребление памяти, т.к. хранить для каждой целевой точки необходимо вектора для каждой ноды, т.е. даже если это массив байт с указанием направления, то это width * height байт. Может быть проблемой для больших миров.
Часто для решения проблем с поиском пути используют смешанные подходы, для больших расстояний используют JPS или A* + Point, а для конкретики - уже A*, FlowField и прочие. Таким образом мы понимаем примерное направление куда хотим идти, а детальный путь строим уже в процессе перемещения.
Для того, чтобы определиться какой алгоритм стоит использовать - нужно исходить из вашей игры и вашего мира.
Вот несколько основных вариантов, которые можно использовать:
- Если у вас в игре большая толпа юнитов, которая идет в одну точку - используйте Grid + FlowField.
- Если у вас один персонаж, а мир - лабиринт (т.е. мало открытых пространств), используйте Grid + A* или NavMesh.
- Если у вас один персонаж, а мир большой и открытый, используйте Grid + JPS или NavMesh.
- Если у вас большой мир с открытыми пространствами, препятствия которого можно описать как круги, то используйте граф из кругов + A*.
