Как лучше искать путь среди окружностей?

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

Как для конкретного момента времени найти почти оптимальный путь из точки А в точку Б, состоящий из отрезков (ломаная линия)?
spoiler
5d3065f8052e6757471186.png
spoiler
5d306725c7d17420219801.png
spoiler
5d3067e5d6d5f185264322.png
  • Вопрос задан
  • 413 просмотров
Решения вопроса 1
tsarevfs
@tsarevfs
C++ developer
Достаточно легко доказать что пути будут лежать по общим касательным и дугам между точек касания для непроходимых сфер. Можно строить динамический граф и использовать A*.
C тормозящими кругами может быть сложнее. Если они не могут пересекаться с препятствиями, то их выгоднее обходить по дуге, которая не более чем в pi/2 (~1.5) длинее хорды.
Если могут, то если аналитическое решение найти трудно, я бы добавил несколько точек на границе медленных зон в граф и искал приближенное решение.
Про непроходимые круги: https://redblobgames.github.io/circular-obstacle-p...
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
Slavik_Kenny
@Slavik_Kenny
3Д моделлер, и немного всего остального :)
- Окружности не постоянны, т.е. могут возникать или исчезать со временем

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

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

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