Как заставить ботов убегать от преследователей?

Question

[Magneto903]

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


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


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

Мне нужны другие боты (пусть зеленые), которые будут убегать от ботов, которые умеют преследовать (от красных). Желательно, чтобы зеленые боты умели обходить тупики, т.к. если они туда зайдут, они попадут в ловушку.
Подразумевается, что боты знают всю геометрию мира, т.е. местоположения всех препятствий.



Какой алгоритм должен быть у зеленых ботов?

Comments

[Ярослав Иванов]

Raycasting ? Бросать лучи и бежать к лучу, который дальше.

[Magneto903]

Ярослав Иванов, следуя такому алгоритму зеленый бот оказавшись в ситуации как на картинке ниже пойдет в тупик, где его догонит красный бот.

[Ярослав Иванов]

Magneto903, Ну как и в жизни. Откуда вам знать что там нет пути пока не окажитесь там?

[Magneto903]

Ярослав Иванов, Пока считается, что боты всевидящие и в курсе всей геометрии своего мира

[Ярослав Иванов]

Magneto903, а сквозь камни они еще не ходят?)

[Magneto903]

Ярослав Иванов, нет)

[Ярослав Иванов]

Сделайте красного бота медленнее зеленого. Тогда успеет на разведку в тупик забежать чтобы оценить обстановку и вовремя убежать)

[Ярослав Иванов]

Magneto903, На чем делаете и можно ли посмотреть результат?

[Magneto903]

Ярослав Иванов, Делаю на JavaScript. Результат чего вы хотите увидеть?

[Ярослав Иванов]

Magneto903, Поиграть в то, что сейчас есть

[Magneto903]

Ярослав Иванов, Боюсь пока это будет немного сложно. А зачем вам? Там пока ничего такого нет) Красные боты преследуют игрока и обходят препятствия)

[Ярослав Иванов]

Magneto903, любопытно)

Answer 1

[GavriKos]

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

Comments

[Magneto903]

Навигация красных ботов использует граф. Благодаря нему они могут двигаться в определенную точку с обходом препятствий. Если я уберу тупики из графа, то красные боты не смогут туда попасть, фактически я упрощу мир, а этого не хочется. Также я не совсем понял фразу "двигаться по тем вершинам графа, которые позволят вернутся в исходную точку/цель не проходя по одному маршруту дважды".

[GavriKos]

Magneto903, никто не мешает вам для красных и синих использовать разные графы ;-)

Ну смотрите. Как определить что вы в тупике? Нет выхода. На уровне графов - это означает что у вершины есть только 1 ребро. Как найти такие вершины? Ну если в целом список всех вершин есть - то просто. А если нет и нужен обход графа - то как только для дальнейшего движения по графу вам нужно пройти по ребру, по которому вы только что прошли - вот он тупик.

Теперь разовьем до ваших зеленых ботов. У них цель "убегания" вообще какая? Что такое убегание? Движение куда то в конкретную точку, или "в противоположном направлении"? Это вот пока непонятно из вашего ответа. Я предположил что просто движение в сторону от противника. Как тогда понять не в тупик ли мы движемся? Да просто найти все обратные маршруты в исходную точку. Если есть хоть один маршрут, в котором не надо двигаться по уже пройденным ребрам - то это не тупик. Может я не прав и есть более простой алгоритм - но общая идея именно такая.

[GavriKos]

Magneto903, Но это справедливо только для таких тупиков как вы нарисовали. Я бы советовал сразу выделить все проблемные ситуации и строить алгоритм исходя из них

[Magneto903]

GavriKos, Что касается "убегания", то это значит двигаться таким образом, чтобы как можно дольше сохранять дистанцию с красным ботом, чтобы он не прикоснулся.

[GavriKos]

Magneto903, Ну т.е. "бегать по кругу" вполне вписывается. Вот и проверяйте сможет ли он при выборе очередной вершины дальше бежать по кругу ))
Но я бы все таки заранее такие вершины убрал.

[Magneto903]

GavriKos, хорошо, я так понимаю граф - это что-то наподобие waypoints. Однако вопрос в том, как его процедурно построить для нетайловой карты?) И конечно есть опасения, что траектории ботов станут слишком однообразными

[Magneto903]

В графе для навигации красных ботов, у меня вершины - вершины полигонов + позиции ботов + точки, куда идут боты. А ребра - это касательные между полигонами + касательные на полигоны из точек, которые не являются вершинами. Что-то наподобие неполного графа видимости

[GavriKos]

Magneto903, про траектории - верные опасения. Нужен рандом хороший.

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

[Евгений Шатунов]

Magneto903, тебе стоит почитать про Navmesh building и Convex Hulling.
Результирующее навигационное пространство может содержать дополнительные свойства, в числе которых может быть свойство тупиковой ветви движения (ближе-дальше относительно тупика), свойство поверхности передвижения, свойство габаритов прохода.
Такие дополнительные свойства добавляются в пространство для того чтобы варьировать поведение разных аниматов в рамках единого навигационного пространства.

Answer 2

[uvelichitel]

Пусть дорогу метят, те и другие, своим цветом.

Навигация красных ботов использует граф.

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

Comments

[Magneto903]

Граф, которые используют красные боты похож скорее на упрощённый граф видимости, чем на waypoints. Насколько я знаю, алгоритм муравьев помогает искать кратчайший путь между двумя точками. В случае с красными ботами понятно- кратчайший путь между ним и какой-то движущейся целью. Эту задачу я решаю и без муравьиного алгоритма. Вопрос заключается в том, куда должны идти зелёные боты, чтобы максимально долго сохранять дистанцию с красным? Как муравьиный алгоритм на это отвечает?

[uvelichitel]

Magneto903, боты должны метить пути при прохождении. Красные красным, зеленые зеленым. По путям у которых красных меток больше зеленым ботам ходить не рекомендуется. Так работает муравьиный алгоритм в природе, а не в математике.) Простейший способ пометить путь - изменить вес ребра графа.

[Magneto903]

uvelichitel, А вы учитываете, что красные специально преследуют зеленых?)

[uvelichitel]

Magneto903, например в тупик красный входит и выходит, то есть делает две метки. Зеленый только входит оставляя только одну метку. Таким образом на тупиковых путях красных меток будет больше. Те же суждения можно распространить и шире.

Answer 3

[mayton2019]

Проблема кроется в самой постановке. Боту недостаточно убегать от красных. Ему надо заранее прокладывать траекторию так чтобы при равных скоростях они оба бегали бесконечно. Я так понимаю что это будет успех.

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

Comments

[Magneto903]

В идеале конечно да, но на практике необязательно. Зеленые боты могут уметь более высокую угловую скорость, чем красную, и за счёт этого отрываться от от красных на поворотах.
А вот насчёт того, что нужно тыкаться в углы. Зачем тыкаться, если бот имеет представление о всей геометрии игрового мира?