@Magneto903

Как реализовать алгоритм преследования игрока с учётом препятствий-полигонов?

Есть большая прямоугольная карта (5000 x 5000 px) и список выпуклых полигонов-препятствий (100-500 препятствий). И ещё есть боты (10-50 штук) , которые должны преследовать игрока не мешая друг-другу.

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

Но эта идея:
Во-первых очень трудоёмка. (надо проверять от каждого бота лучи, которые ещё и поворачиваются пересекаются ли они с каждым ребром полигона, которых много).

Во-вторых не всегда приводит к ожидаемым результатам:
Если длина луча слишком короткая, то бот может залезть в тупик, и потом ему придётся из него выбираться (и это явно не оптимальный маршрут)
5f928f1424657172864235.png
бот пойдет оранжевым путём, когда красный - это явно оптимальнее.

Однако если длина луча слишком длинная, то бот наоборот примет узкий проход за тупик, и будет обходить его
5f9290032479a766173202.png
Тут серый - это сенсор, который пересек полигоны, поэтому бот пойдёт оранжевым, хотя красный - также лучше.

И тут непонятно, есть ли компромисс по длине сенсора, чтобы и тупики обходил, и не путал их с узкими проходами?

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

Я находил много решений для клеточных карт, например это
Однако у меня не клетки. И если я буду делить всё поле на клетки, то получится слишком большое поле, и это скажется на производительности (ведь игрок не стоит на месте, а убегает).

Также я нашёл решение через навигационную сетку (Nav Mesh), вот такое
Однако в нём сказано, что во-первых, выдаёт не всегда наикратчайший путь (The astar heuristic & cost functions need another pass. They don't always produce the shortest path. Implement incomplete funneling while building the astar path?).
И во-вторых тут нужны обязательно прямоугольные полигоны (Allow non-square navmesh polygons from Tiled - ideally, any convex shape.). Но у меня не только прямоугольные полигоны.

Ну вот и возникает вопрос, как реализовать поставленную задачу: Генерация пути для бота в режиме реального времени до игрока с оптимальным обходом препятствий (полигонов) и с учётом траектории других ботов
  • Вопрос задан
  • 321 просмотр
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, гуглер, экс-олимпиадник.
Если боты должны обходить полигоны на каком-то расстоянии (не могут их касаться, как у вас на картинке), то раздуйте все полигоны на этот радиус (для каждой вершины найдите 2 внешние нормали к соседним сторонам, сдвиньте стороны на r вдоль этих нормалей и пересеките). Можно вывести формулу на бумажке через косинусы/синусы между нормалями (т.е. векторное/скалярное произведения нормалей). Надо будет к точке прибавить обе нормали, умноженные на 1/(cos(a/2)*sqrt(2+2cos(a))), где a - угол между нормалями.

Теперь можно считать ботов точками и они могут касаться полигонов.

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

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

Теперь, для каждого бота и игрока сделайте то же самое - постройте касательные на все многоугольники, удалите те, которые пересекаются с другими полигонами. Также добавтье прямые пути игрок-бот, если нет пересечений с полигонами. В этом графе нужно найти кратчайшие пути (лучше Дейкстрой от игрока до всех ботов).

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

Они будут толпиться в узких проходах, но в итоге выстроятся шеренгой и пойдут друг за другом. Но это если игрок один. Тогда боты идут в одну сторону. Если они могут ходить против друг друга, то будет хуже. Они могут запереть друг друга в узком проходе и долго выталкивать друг друга.

Теперь - пересчет при движении игрока. Переодически надо пересчитывать пути для ботов. Для этого надо перестроить касательные от игрока и ботов на полигоны и снова прогнать Дейкстру.

Теперь про скорость. Можно делать просто, как я описал выше. Все что надо - это уметь проверять, что 2 отрезка пересекаются, и что полигон лежит по одну сторону от луча. Ну и алгоритм Дейкстры.

Касательные между препятствиями вы строите только один раз, тут скорость не так важна. Хуже с точками ботами и игроком. Тут касательные надо искать часто. Если полигоны очень большие, то можно искать точки пересечения и касательные за логарифм, но это очень заумные алгоритмы, через троичный поиск. Могу потом написать, если надо.

Самое медленное, это для каждой касательной проверять на пересечения со всеми полигонами (это n^2 проверок, если у вас n полигонов). Тут можно тоже очень хитро ускорить до n log n проверок, если все касательные отсортировать по углу и потом сделать что-то вроде алгоритма заметающей прямой, но вращать ваш взгляд вокруг точки. Это совсем сложно даже описать, не говоря уж о реализации. Надо складывать полигоны в что-то вроде сбалансированного дерева поиска, которое будет поддерживать их в отсортированном порядке относительно расстояния до точки. Каждая касательная или добавляет полигон, или удаляет его. Вы добавляете касательную только если при добавлении или удалении полигона он был самым ближайшим. Тут нужно будет уметь определять расстояние от точки до полигона вдоль прямой. Опять же, можно сделать тернарным поиском по точкам полигона.

Еще есть вариант через BSP (как в Думe. Дейстивительно эта задача, фактически, узнать, какие полигоны видны из любой точки. Очень близкро к компьютерной графике). Надо разбить всю плоскость на области и для каждой области хранить, на какие полигоны есть касательные из нее. Для этого надо все стороны полигонов продлить до прямых. Все со всем персечь, выделить области. Потом для любой точки в каждой области построить касательные и сохранить. Потом все эти области объеденить в BSP. Это очень хорошее ускорение, но оно работет только если у вас карта статичная. Можно предподсчитать и записывать в файл уже BSP.

Поиск пути в графе тоже можно подускорить. Без добавления ботов и игрока в граф найдите все кратчайшие пути методом Флойда. Теперь, когда вы построили все касательные, для каждого бота переберите касательную его и касательную из игрока. Вы можете моментально подсчитать кратчайший путь через эти касательные, ведь часть пути внутри графа на полигонах уже предподсчитана из алгоритма Флойда. Это будет заметно быстрее, чем гнать дейкстру каждый раз, ибо касательныйх сильно меньше, чем вершин всего в графе.
Ответ написан
Пригласить эксперта
Ответы на вопрос 4
@linesb
Если препятствия с углами и нет прямого пути то на первый взгляд кажется что бот должен двигатся по углам. Значит можно представить углы препятствии как вершины графа (бот и игрок тоже вершины) и найти путь от вершины где находится бот до вершины игрока. Пути между вершинами могут иметь стоимость (длинна пути), некоторые пути могут быть заблокированны (например другими ботами исли они там долго будут стоять)
5f92aa7482bc1427798465.png
Ответ написан
twobomb
@twobomb
Делите поле на клетки, это лучше всего, и подумайте важно ли вам найти именно кратчайший путь или можно через A* с эвристическим алгоритмом.
Ну и нужно думать оптимизацию если скорость будет не достаточной, чем больше размер клетки тем быстрее будет работать алгоритм, но тем меньше точность, не следует делать размер клеток больше размеров бота(он просто может не пролезть в маленькие щели). Не нужно искать путь на каждом шаге, делайте это реже. Возможно стоит искать путь не для каждого бота отдельно, а например берет бота и все кто от него в определенном радиусе и прямой видимости и ищем путь для всей этой группы. Ну сделайте сначала самым не оптимизированным способом, а дальше уже смотрите по скорости работы
Ответ написан
@HellWalk
Алгоритмы поиска пути называют A star. Да, примеры в основном сделаны на клеточных полях, но, в самом определении алгоритма:

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


Ничего не сказано про то, что он работает только на клеточном поле. Так что я бы поискал примеры реализации данного алгоритма - наверняка найдется тот, что вам подойдет.
Ответ написан
maaGames
@maaGames
Погроммирую программы
Раз карта прямоугольная (или может быть описана сеткой) и размер у неё маленький (5К*5К это маленький), то идеальное решение - волновая трассировка, она же одна из реализаций поиска в ширину. Будет находиться кратчайший путь, но каждый многоугольник нужно сперва "нарисовать" в сетку, чтобы в ячейку нельзя было войти.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы