Алгоритмы "убегания"

[uhm]

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

ЗЫ Если кому-то интересно, могу дать достаточно точную постановку задачи, а не "в общих чертах", как выше.

[alibek]

Насколько быстрее?
Потому что если "охотники" окружают жертву и половину периметра "окружения" пройдут быстрее, чем жертва пройдет "радиус окружения", то не убежать жертве.

[uhm]

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

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

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

[Amed]

В сторону, противоположную градиенту плотности охотников на поле?

[uhm]

А можно еще раз, но словами попроще?

На самом деле, поясни, пожалуйста, что такое плотность в твоем понимании?

[GAGArin]

Если плоскость в клеточку и направлений всего 8, то вобщем-то нужно просто сделать перебор. До 5 ходов тогда в принципе вполне просто. Потом оценить срендюю удаленность и расстояние до ближайшего.

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

[GAGArin]

:shock:

А можно еще раз, но словами попроще?

На самом деле, поясни, пожалуйста, что такое плотность в твоем понимании?

Я так понимаю закрасить плоскость складывающимся градиентом с центрами - охотниками. И бежать там где цвет слабее всего.

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

[uhm]

GAGArin, мне нравится идея с перебором, она мне как-то в голову не пришла...

Не знаю, правда, насколько она реализуется на практике, поскольку реальная задачка не совсем та же, что модель, которую я описал, но я попробую

[Amed]

:shock:

А можно еще раз, но словами попроще?

На самом деле, поясни, пожалуйста, что такое плотность в твоем понимании?

RTFM!
Учим теорию поля.
Если сказать проще, то надо связать с каждым охотником определенное число - степень его опасности. Скажем, 1/L, где L - расстояние до охотника. Затем строим векторы длиной 1/L, направленные от каждого охотника к жертве. Переносим их в точку, где находится жертва. Складываем вместе. Нормируем. Получаем единичный вектор направления, куда надо двигаться.

[uhm]

"Надо же, агроном!"

Теперь понял. Видимо, тоже попробую.

[GAGArin]

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

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

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

[uhm]

Про линию и полуплоскости - это я уже догадался, у меня именно такой критерий успешного "убегания" и был - дальше можно бежать в сторону "от всех охотников". Идея с перебором мне понравилась больше всего, потому что обычно охотники находятся на расстоянии в пределах 6-7 клеток от жертвы. Кроме того, на плоскости могут быть препятствия (не сказал об этом раньше, сорри), с точки зрения большинства алгоритмов, это усложняет дело, а с точки зрения перебора - как раз упрощает.

Спасибо всем за идеи! Буду потихонечку пробовать...