Magneto903, Вообще, мы убегая точно упремся в стену, если преследователь прямо на нас смотрит, а за нами только стена. Убегающий может действовать только локально. Т.е. вариант 2 - это построить кратчайший путь от преследоваля до убегающего. А потом смотрим, как этот путь идет и продлеваем его. Но тут мы точно упремся в стенку или в другой полигон.
умнее вариант 3. Тут бот будет прятаться за препятствиями.
Нет, если у вас боты приследуют убегающих ботов, то они все в графе (вернее все строят касательные на полигоны). С преследующим ботом просто - он, допустим выбирает ближайшего бота-цель или игрока и идет к ним. Убегающий, наврено, должен убегать от ближайшего? Тут сложно формализовать, что значит убегать. Ясно, когда прямая видемость - бежим строго от. А если нет? Вариант 1 - стоим на месте, вариант 2 - идем в сторону противоположную той, с которой занами едет ближайший преследователь (мы же знаем весь путь). Вариант 3 - бежим к вершине графа, наиболее удаленной от преследователя, а потом двигаемся жадно к соседней вершине графа, которая наиболее удалена от преследователя. Все варианты могут выдавать какое-то странное поведение.
Magneto903, Если вы хотите убегающих ботов, то это немного другая задача. Можно использовать уже найденные расстояния от игрока до всех точек в графе и, например, стремится все время идти к той точке, которая от игрока наиболее удалена локально. Тогда бот будет идти от игрока и пытаться прятаться за препятствием. Ну и отдельно, если игрок в прямой видимости - идти прямо от него.
Зачем что-то между ботами делать, мне не понятно, но ботов мало, вы можете и лучи между ними в граф добавить, все будет быстро.
twobomb, Про A* вы первый раз написали. И это не жадный алгоритм и называть его жадным некорректно, хоть жадность там и использутеся в качестве эвристики. Далее, в данной задаче, даже если работать на сетке, BFS может оказаться сильно быстрее, если гнать его один раз от игрока и найти пути для всех ботов сразу же. A* так сделать не получится.
Magneto903, 100 полигонов, 10 ботов 60 раз в секунду будет работать даже без всех оптимизаций, если полигоны не большие (<10 вершин) Флойда наверно, надо, таки, вместо дейкстры использовать.
Если полигоны могут быть по 1000 вершин, то надо тернарный поиск ворочать. BSP будет работать моментально хоть для 1000 полигонов по 1000 вершин и 100 ботов.
twobomb
> Ну это затратная операция раздувания каждого, хотя можно сделать ее один раз в начале и хранить для каждого параметры раздутого и сдутого, ору... ну там опять вылезут всякие приколы когда полигон в полигон залазит, и понятно как это считать крч...
Ощущение, что вы вообще не в теме. С одной стороны несете лютый бред и предлагаете делать жадный алгоритм посика пути (Хоть немного теорию подучите, блин. Теория графов в любом курсе computer science дается в самом начале. Это самая заезженная и базовая тема!) С другой сторны, вы эту простейшую операцию, которая один раз проходит по всем вершинам полигонов, называете затратной. Блин, это прямо во время чтения координат можно делать!
Когда полигон залезет на полигон - значит там прохода не было. Бот не помещается в эту щель. Все ребра в графе через эту часть будут удалены, потому что они пересекаются с полигонами. Для алгоритма эти 2 полигона сольются в один.
twobomb, У вашего алгоритма проблема в том, что проход мужду полигонами может быть не выравнен по сетке. Т.е. и текущий квадрат и чуть левее пересекают полигоны. А посерединке пройти можно. Но и без этого - он слишком медленный. Видно, что вы не в курсе алгоритмов. Предлягать для поиска кратчайшего пути жадный алгоритм - это дичь. Есть куча стандартных алгоритмов поиска пути на графе Хоть тот же BFS. Но для работы на сетке есть еще более быстрый алгоритм - jump point search. Только в этой задаче с произвольными полигонами он не подходит.
twobomb, Не этот. Бот маленький (если он помещается между треугольниками. Значит труегольники становятся чуть чуть больше, на расстояние примерно равное половине расстояния между ними. В итоге они начинают просто касаться. Далее алгоритм найдет касательную к верхней вершине левого треугольника. Из нее - касательную к нижней вершине правого треугольника, из нее - к синему квадрату.
Но лучше, чтобы проблем с точностью не было, не делать так, что боты впритык к полигонам ходят. Лучше оставить между треугольниками чуть больше расстояния. Тогда после раздувания они будут очень близко, но не будут касаться.
Magneto903, Надо еще для каждого ребра графа тут проверять, что оно не пересекается с ни с одним полигоном. Еще, как я распиал в своем ответе, достаточно рассматривать только касательные между точками к полигону (ну и стороны полигонов). Это сильно снижает количество ребер и ускоряет поиск на графе.
mIka01, Все-равно непонятно. Какая фигура в основе сетки на картинке?
Можете как-то формализовать задачу? Вот есть набор точек с координатами. Фигура (полигон? Набор точек?) образует сетку, если... что? Например, набор точек состоит из нескольких сдвинутых копий фигуры относительно одной прямой с равным сдвигом. Или все заданные точки покрываются копиями фигуры, сдвинутыми вдоль прямоугольной сетки.
Dragon1, Это же условие для вывода "not defined" (судя по последнему, которое проверяет, что знаменатель == 0). И оно not defined, если корень из отрицательного числа, или x+1<0 или x < -1.
Dragon1, Да, потому что cos(x) == 1 только для чисел вида pi/2, 3pi/2,...
Вы эти числа в программе никогда не получите, если только прямо с них не начинаете.
Что значит, с заранее известной факторизацией? Так-то если она дана, то p-1 известно, а значит и p фиксировано. Или надо, чтобы p-1 делилось на заданные простые числа?
умнее вариант 3. Тут бот будет прятаться за препятствиями.