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

Question

[dollar]

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

Как для конкретного момента времени найти почти оптимальный путь из точки А в точку Б, состоящий из отрезков (ломаная линия)?

spoiler

spoiler

spoiler

Comments

[Slavik KENNY]

Маленькая придирка - надо бы еще уточнить что подразумевается под "оптимальным" путем.
Самый быстрый или самый короткий?
Обычно короткий ищется, но раз некоторые круги только замедляют, значит надо на время ориентироваться, а не на дистанцию?

[dollar]

Вячеслав Новиков, если скорость = константа, то самый короткий = самый быстрый, очевидно. В вопросе оптимальный = самый быстрый, потому что скорость не постоянна.

Answer 1

[tsarevfs]

Достаточно легко доказать что пути будут лежать по общим касательным и дугам между точек касания для непроходимых сфер. Можно строить динамический граф и использовать A*.
C тормозящими кругами может быть сложнее. Если они не могут пересекаться с препятствиями, то их выгоднее обходить по дуге, которая не более чем в pi/2 (~1.5) длинее хорды.
Если могут, то если аналитическое решение найти трудно, я бы добавил несколько точек на границе медленных зон в граф и искал приближенное решение.
Про непроходимые круги: https://redblobgames.github.io/circular-obstacle-p...

Comments

[dollar]

Получается, что для построения сетки (графа) нужно провести всевозможные касательные между ними. А потом посчитать всевозможные пересечения касательных.

Не слишком ли сложная сетка получится для поиска пути?

И не слишком ли сложно строить саму такую сетку? Всевозможные касательные для N окружностей - это N^2 действий. А нахождение точек пересечения - это уже N^4.

Для 100 окружностей будет примерно 100 млн. точек пересечений всевозможных касательных (узлов графа).

[tsarevfs]

dollar, точки пересечения вроде не нужны.
Секция "Delayed edge generation" в статье про одну из возможных оптимизаций.

Answer 2

[Slavik KENNY]

- Окружности не постоянны, т.е. могут возникать или исчезать со временем

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

Comments

[dollar]

Поверх персонажа окружность не может возникнуть. В вопросе упрощенное описание механик, связанных с созданием объектов, зон, а также с туманом войны.

Непроходимый путь может быть, конечно. Вообще о появлении новых окружностей сказано к тому, что нельзя заранее вручную разметить зоны. Так-то динамика не учитывается. То есть условно можно считать, что есть процедурно-сгенерированная произвольная карта, которая не меняется, время заморожено, и в данный момент нужно просчитать оптимальный путь, как будто ничего в будущем не поменяется.

[Slavik KENNY]

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

[dollar]

Хорошая идея.

Правда, есть вариант с коридором, когда персонаж приблизится к тупику и повернет назад, а потом отдалится от тупика и перестанет видеть, что это тупик, и снова пойдет внутрь. Довольно идиотское поведение. Но и ситуация редкая. Разве что игрок захочет абузить ИИ таким образом.

[Slavik KENNY]

А есть статичные круги, которые никогда не исчезнут?
Если таких кругов нет, то любой тупик рано или поздно станет проходимым :)
Как я раньше сказал - если движение не приближает к конечной точке, то просто стоять на месте, пока тупик не исчезнет.

Хотя если есть статичные круги, то строить траекторию только по ним, и движение делать не точке ближайшей к В, а поближе к этой траектории.

[Сергей Водаков]

Вячеслав Новиков, ну, прям при таком алгоритме путь к цели будет всегда проходить по прямой, с остановками, и ожиданием когда исчезнет препятствие.

[Slavik KENNY]

Вы не правы.
Если перед персонажем непроходимый круг, то движение будет не по прямой, и вместе с тем будет приближать к конечной точке.
Стоять и ждать придется только тогда, когда приближающее движение невозможно.