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

- На плоском пространстве есть огромное число окружностей двух типов:
а) непроходимые
б) замедляют движение в 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Д моделлер, и немного всего остального :)
- Окружности не постоянны, т.е. могут возникать или исчезать со временем

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

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

Войти через центр авторизации
Похожие вопросы
21 авг. 2019, в 13:03
15000 руб./за проект
21 авг. 2019, в 12:59
10000 руб./за проект