Как реализовать алгоритм преследования игрока с учётом препятствий-полигонов?

Question

[Magneto903]

Есть большая прямоугольная карта (5000 x 5000 px) и список выпуклых полигонов-препятствий (100-500 препятствий). И ещё есть боты (10-50 штук) , которые должны преследовать игрока не мешая друг-другу.

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

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

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

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

Однако если длина луча слишком длинная, то бот наоборот примет узкий проход за тупик, и будет обходить его

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

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

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

Я находил много решений для клеточных карт, например это
Однако у меня не клетки. И если я буду делить всё поле на клетки, то получится слишком большое поле, и это скажется на производительности (ведь игрок не стоит на месте, а убегает).

Также я нашёл решение через навигационную сетку (Nav Mesh), вот такое
Однако в нём сказано, что во-первых, выдаёт не всегда наикратчайший путь (The astar heuristic & cost functions need another pass. They don't always produce the shortest path. Implement incomplete funneling while building the astar path?).
И во-вторых тут нужны обязательно прямоугольные полигоны (Allow non-square navmesh polygons from Tiled - ideally, any convex shape.). Но у меня не только прямоугольные полигоны.

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

Answer 1

[Wataru]

Если боты должны обходить полигоны на каком-то расстоянии (не могут их касаться, как у вас на картинке), то раздуйте все полигоны на этот радиус (для каждой вершины найдите 2 внешние нормали к соседним сторонам, сдвиньте стороны на r вдоль этих нормалей и пересеките). Можно вывести формулу на бумажке через косинусы/синусы между нормалями (т.е. векторное/скалярное произведения нормалей). Надо будет к точке прибавить обе нормали, умноженные на 1/(cos(a/2)*sqrt(2+2cos(a))), где a - угол между нормалями.

Теперь можно считать ботов точками и они могут касаться полигонов.

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

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

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

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

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

Теперь - пересчет при движении игрока. Переодически надо пересчитывать пути для ботов. Для этого надо перестроить касательные от игрока и ботов на полигоны и снова прогнать Дейкстру.

Теперь про скорость. Можно делать просто, как я описал выше. Все что надо - это уметь проверять, что 2 отрезка пересекаются, и что полигон лежит по одну сторону от луча. Ну и алгоритм Дейкстры.

Касательные между препятствиями вы строите только один раз, тут скорость не так важна. Хуже с точками ботами и игроком. Тут касательные надо искать часто. Если полигоны очень большие, то можно искать точки пересечения и касательные за логарифм, но это очень заумные алгоритмы, через троичный поиск. Могу потом написать, если надо.

Самое медленное, это для каждой касательной проверять на пересечения со всеми полигонами (это n^2 проверок, если у вас n полигонов). Тут можно тоже очень хитро ускорить до n log n проверок, если все касательные отсортировать по углу и потом сделать что-то вроде алгоритма заметающей прямой, но вращать ваш взгляд вокруг точки. Это совсем сложно даже описать, не говоря уж о реализации. Надо складывать полигоны в что-то вроде сбалансированного дерева поиска, которое будет поддерживать их в отсортированном порядке относительно расстояния до точки. Каждая касательная или добавляет полигон, или удаляет его. Вы добавляете касательную только если при добавлении или удалении полигона он был самым ближайшим. Тут нужно будет уметь определять расстояние от точки до полигона вдоль прямой. Опять же, можно сделать тернарным поиском по точкам полигона.

Еще есть вариант через BSP (как в Думe. Дейстивительно эта задача, фактически, узнать, какие полигоны видны из любой точки. Очень близкро к компьютерной графике). Надо разбить всю плоскость на области и для каждой области хранить, на какие полигоны есть касательные из нее. Для этого надо все стороны полигонов продлить до прямых. Все со всем персечь, выделить области. Потом для любой точки в каждой области построить касательные и сохранить. Потом все эти области объеденить в BSP. Это очень хорошее ускорение, но оно работет только если у вас карта статичная. Можно предподсчитать и записывать в файл уже BSP.

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

Comments

[twobomb]

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

Или я не про тот радиус подумал?

[Wataru]

twobomb, Не этот. Бот маленький (если он помещается между треугольниками. Значит труегольники становятся чуть чуть больше, на расстояние примерно равное половине расстояния между ними. В итоге они начинают просто касаться. Далее алгоритм найдет касательную к верхней вершине левого треугольника. Из нее - касательную к нижней вершине правого треугольника, из нее - к синему квадрату.

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

[twobomb]

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

[Magneto903]

twobomb, Спасибо за такую развёрнутую статью! А вот можете навскидку сказать, если я сделаю все оптимизации (BSP), это будет работать скажем при 100 полигонах 10 ботах 60 раз в секунду или нет? И я не понял по поводу последней оптимизации поиска пути в графе с методом Флойда, я должен оставлять какие-то метки на рёбрах-касательных между полигонами?

[Wataru]

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

Ощущение, что вы вообще не в теме. С одной стороны несете лютый бред и предлагаете делать жадный алгоритм посика пути (Хоть немного теорию подучите, блин. Теория графов в любом курсе computer science дается в самом начале. Это самая заезженная и базовая тема!) С другой сторны, вы эту простейшую операцию, которая один раз проходит по всем вершинам полигонов, называете затратной. Блин, это прямо во время чтения координат можно делать!

Когда полигон залезет на полигон - значит там прохода не было. Бот не помещается в эту щель. Все ребра в графе через эту часть будут удалены, потому что они пересекаются с полигонами. Для алгоритма эти 2 полигона сольются в один.

[Wataru]

Magneto903, 100 полигонов, 10 ботов 60 раз в секунду будет работать даже без всех оптимизаций, если полигоны не большие (<10 вершин) Флойда наверно, надо, таки, вместо дейкстры использовать.

Если полигоны могут быть по 1000 вершин, то надо тернарный поиск ворочать. BSP будет работать моментально хоть для 1000 полигонов по 1000 вершин и 100 ботов.

[Magneto903]

wataru, Ну такие цифры очень радуют) Я планировал использовать полигоны не более 10 вершин. И ещё меня интересует вопрос: если я захочу, чтобы например были боты, которые преследуют, а были те, кто убегают, то получается надо будет ещё и боты-вершины соединить в рёбра, если они не будет пересекать полигоны?

[Magneto903]

wataru, Ну как Вы говорили прямой путь между ботом и игроком сделать, тоже самое между всеми ботами сделать. Насколько это будет затратно?

[Wataru]

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

Зачем что-то между ботами делать, мне не понятно, но ботов мало, вы можете и лучи между ними в граф добавить, все будет быстро.

[Magneto903]

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

[Wataru]

Magneto903,

Нет, если у вас боты приследуют убегающих ботов, то они все в графе (вернее все строят касательные на полигоны). С преследующим ботом просто - он, допустим выбирает ближайшего бота-цель или игрока и идет к ним. Убегающий, наврено, должен убегать от ближайшего? Тут сложно формализовать, что значит убегать. Ясно, когда прямая видемость - бежим строго от. А если нет? Вариант 1 - стоим на месте, вариант 2 - идем в сторону противоположную той, с которой занами едет ближайший преследователь (мы же знаем весь путь). Вариант 3 - бежим к вершине графа, наиболее удаленной от преследователя, а потом двигаемся жадно к соседней вершине графа, которая наиболее удалена от преследователя. Все варианты могут выдавать какое-то странное поведение.

[Magneto903]

wataru, Ну тут надо подумать будет... А как реализовать 2 вариант? Если просто бежать в противоположном направлении от ближайшего преследователя то мы можем упереться в стенку. Тут надо найти ближайший путь, который направлен максимально от преследователя, да?

[Wataru]

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

умнее вариант 3. Тут бот будет прятаться за препятствиями.

[Magneto903]

wataru, Возможно глупый вопрос, а этот метод ведь будет работать и с вогнутыми полигонами?

[Wataru]

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

Но можно любой полигон разбить на выпуклые (вместо буквы L - 2 прямоугольника). Это можно делать автоматически (в полигоне найти "вогнутую" вершину, потом взять ее диагональ, которая целиком внутри полигона и не делает два своих конца "вогнутыми". Или составитель карты должен добавлять только выпуклые многоугольники.

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

[Magneto903]

wataru, Можете пожалуйста поподробнее рассказать про раздутие полигона?
Я правильно понимаю, что я должен найти нормали к каждой стороне, т.е. координаты вектора (пару чисел), перпендикулярного к стороне и направленного от стороны наружу т.е. не в полигон, а от него.
Далее я должен к каждой вершине применить следующее преобразование:
1) Находим 2 стороны, которые включают эту вершину и берём от них нормали пусть vec_1 и vec_2
2) num=1/(cos(a/2)*sqrt(2+2cos(a))), где a - угол между нормалями.
3) к x вершины прибавляю (vec_1.x + vec_2.x) * num
4) к y вершины прибавляю (vec_1.y + vec_2.y) * num

но результат какой-то не очень вышел (красный - внутренний, зеленый - внешний)
и из этого я делаю вывод, что я что-то неправильно понял

[Wataru]

Magneto903, Все проще, если у вас полигон задан в порядке обхода против часовой стрелки (можно и по, но надо, чтобы все полигоны так были заданы). Можно понять, в каком порядке задан полигон, если посмотреть на знак векторного произведения двух соседних векторов-сторон. Далее, трюк - можно индексы брать по модулю. Если у вас n точек в полигоне, то они пронумерованы от 0 до n-1 в массиве. И следующая за последней будет ((n-1)+1)%n = 0.

Дальше, мы хотим подвинуть i-ую веришину. Проще создавать раздутый полигон в новом массиве. Предыдущая имеет номер j=(i+n-1)%n, следующая k=(i+1)%n.

Далее, вектора нормалей можно взять просто повернув вектора стороны на 90 градусов влево. Если первая сторона имеет вектор (x[i]-x[j], y[i]-y[j]), то нормаль наружу будет (y[i]-y[j], -(x[i]-x[j])). На бумажке проверьте, что это так, например, для вектора (1,0) - нормаль наружу будет идти вниз (0, -1). Точно так же, вторая нормаль будет (y[k]-y[i], -(x[k]-x[i])). Да, эти вектора еще надо обязательно сделать длиной r - на сколько у вас боты обходят полигоны. Поделите на sqrt(vx*vx+vy*vy) и умножте на r все координаты.

Далее, формулу надо сначала преобразовать через cos(a) и sin(a) - их можно получить, если взять векторное/скалярное произведения нормалей и поделить на длины нормалей):

1/(cos(a/2)*sqrt(2+2cos(a)) = 1/(1+cos(a)). Внезапно сильно сократилось. И эта формула имеет смысл. Если нормали совпадают, то надо сдвинуться на вектор длины 1. А значит сумму двух нормалей надо будет поделить на 2. И действительно, при a=0, формула даст 1/2. Если нормали перпендикулярны, то они образуют квадрат со сдвинутыми сторонами и их сумма как раз даст диагональ. Надо домножить сумма на 1. Если же нормали прямо в разные стороны смотрят (a=180), то пересечение как-бы в бесконечности (стороны-то параллельны). И действительно, формула даст 1/0.

Вот вы знаете нормали (длины 1). Взяли их скалярное произведение, получили cosa. И потом к текущей точке прибавьте эти 2 нормали, домноженные на 1/(1+cosa). Не забудьте новую точку считать в новом массиве. Иначе вы для следующей точки будете стороной считать вектор с уже сдвинутой вершины.

[Wataru]

Magneto903, А в вашем скрипте ошибка тут:

var angle = ( vec_1.x * vec_2.x + vec_1.y * vec_2.y )/r*r;
var num =  1/(Math.cos(angle/2)*Math.sqrt(2+2*Math.cos(angle)))

В angle у вас храниться значение cos(a), а не угол. А вы потом от этого значения косинуса еще берете косинус.

Может еще где что-то есть.

[Magneto903]

wataru, Спасибо за пояснения! Скорее всего я просто неаккуратно написал скрипт, вероятно его надо будет переписать.

[Magneto903]

wataru, Я разобрался как раздувать полигоны. Но... Я реализовал шаг, где мы должны от каждой точки каждого полигона сгенерировать касательные на все остальные полигоны. Но скорость получается слишком низкая. Для всего 20 полигонов генерируется аж 1800+ касательных, и это почти за 4 секунды. Но сколько будет генерировать 100 полигонов? 1000? Может я как-то неправильно понял идею?

[Wataru]

Да, важный момент - отрезки между полигонами можно смотреть только касательные к обоим полигонам. Это можно до пересечения с чем-то еще проверить, что отрезок касается того полигона, с которого вы касательные опустили на второй. Обычно таких касательных всего 4 (если полигоны не пересекаются). Но их может быть и сколько угодно, если полигоны торчат друг из друга всеми вершинами (представьте правильные k-угольники с общим центром, но чуть чуть повернутые вокруг центра).

Еще одна хорошая оптимизация - это bounding box. Не надо проверять на пересечение полигоны, если добавляемое ребро не пересекается с его обрамляющим прямоугольником. Можно еще дальше пойти и запилить Rtree на полигонах. Оно не сильно ускоряет на случайно сгенерированных полигонах, но может сильно помочь если есть структура у карты.

И еще, мое предложение о раздутии не очень хорошее. Если есть острые углы, то путь будет обходить их очень далеко. Но можно их усечь. Лучший вариант - вместо одной вершины добавлять 2, тоже на сдвинутых на r сторонах. Добавлять их так, что прямая меджду ними отстоит от вершины на r. Тут если порисовать вылезает tg(a/4). Посмотрите в код на Polygon::Inflate в Polygon.cpp в архиве внизу. Еще хорошо видно, как оно обходит, если включить прорисовку ребер.

Я запилил демку на C++ (не умею в JS) - строит граф 16мс для 100 полигонов по 10 вершин. Дальше ищет путь мгновенно. Т.е. если у вас карта не обновляется, то можно один раз в начале вызвать AddPolygons. Иначе можно допустить просадку по кадрам при обновлении карты. Еще можно разбить AddPolygons на этапы (добавлять ребра для трети/половины полигонов за раз. Или смотреть по тайм-лимиту). И не строить пути, пока нужное количество вызовов не наберется. Тогда просадки по кадрам не будет, но боты не будут двигаться первые несколько кадров.

Там в архиве екзешник и код для Visual Studio 19. Если не запуститься, гуглите visual studio redistributables.

Как пользоваться демкой: там меню. В debug->Generate polygons можно заполнить карту полигонами. Еще в debug можно переключать прорисовку ребер и bounding boxes. Еще там можно отключить rtree, вряд ли вы его захотите реализовывать.

Можно перетаскивать начало или конец мышкой. Можно в меню Move выбрать что вы хотите подвинуть и кликнуть куда. В меню polygon можно выбрать добавление или удаление. При добавлении клики добавляют вершину к текущему полигону. Правый клик - добавляет его на карту. Еще один выключает режим добавления. При удалении левый клик удаляет все полигоны вокруг курсора (они красным подсвечены). Правый клик выключает режим удаления.

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

Вы заметите, что там всегда 0, если двигать начало или конец. Но при нажатии generate polygons, если после этого не двигать мышку, вы заметите 16мс (двигание мышки вызывает перерисовку, которая моментальная).

Структура кода: Vec, Segment, Polygon - геометрические примитивы. PathFinder строит граф и ищет по нему пути. NavMesh - интерфейс и основная логика. Остальное - артефакты от visual studio.

[Magneto903]

wataru, Ого!!! Спасибо Вам огромное за демку! Буду изучать)

[Magneto903]

Илья Николаевский, я попытался частично реализовать вашу библиотеку, а именно функционал нахождения касательных. В принципе, у JavaScript и C++ много общего в синтаксисе.
Отличия моей реализации от вашей в следующем:
1) Т.к. переопределение операторов не поддерживается в JavaScript я реализовал эти операторы через методы классов:

Point - Point -> Point.minus(Point)
Point == Point -> Point.equal(Point)
Point * Point -> Point.multi(Point)
Point ^ Point -> Point.p_multi(Point)

2) В JavaScript как такого оператора ^ нет, поэтому я реализовал его в функции XOR:

function XOR(a,b) {
  return ( a || b ) && !( a && b );
}

3) Вместо .Size() я использовал .length
4) Другой способ генерации выпуклого полигона
5) Другая реализация метода Polygon.IsInside()

this.IsInside = function(a) {
   var vs = this.points;
   var x = a.x, y = a.y;
	    
   var inside = false;
   for (var i = 0, j = vs.length - 1; i < vs.length; j = i++) {
      var xi = vs[i].x, yi = vs[i].x;
      var xj = vs[j].x, yj = vs[j].x;
	        
     var intersect = ((yi > y) != (yj > y)) && (x < (xj - xi) * (y - yi) / (yj - yi) + xi);
     if (intersect) inside = !inside;
   }	    
   return inside;
}

6) В массиве касательных я обращаюсь к первому/второму элементу не через .first/.second а по индексу
7) У меня динамическая типизация

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



Например вот так:


На каком этапе могла возникнуть ошибка?
(Я предполагал, что в методе GetTangentIds(), однако я несколько раз сверялся, различий не обнаружил. Может у меня проблема в порядке вершин полигона?)

[Wataru]

Magneto903, К сожалению, у меня нет времени досканально копаться в вашем коде. Могу лишь дать советы.

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

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

Ваша картинка указывает, что скорее всего ошибка в IsTangent и в Intersects.

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

Это вряд ли влияет на ваши тесты, но ваш IsInside с ошибкой. Вы считаете количество пересечений луча из точки вправо. Это хороший алгоритм, но тут крайний случай, если луч проходит через вершину полигона.

Можно исправить это, изменив вашу проверку (yi > y) != (yj > y) на y > min(yi, yj) && y <= max(yi,yj). Тут важно брать один из концов (верхний или нижний) включительно, а второй пропускать. Тогда все случаи разберутся правильно.

[Magneto903]

Илья Николаевский, Спасибо Вам огромное! Так и сделаю!

[Wataru]

Magneto903, Кстати, исправленная и дополненная версия лежит на гитхабе.

[Magneto903]

Илья Николаевский, Я правильно понимаю, что зеленые - касательные - это правильные, а красные - нет?
.

И на всякий случай, такой вопрос, в полигоне последняя вершина должна совпадать с первой или нет?

[Wataru]

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

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

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

[Magneto903]

Илья Николаевский, Я понял, в чем проблема, она заключалась в функции GetTangentIds(). Почему-то второй индекс касательной был на 1 меньше, чем надо, На всякий случай перепроверьте её у себя ещё.

[Magneto903]

Илья Николаевский, И последний (очень надеюсь) вопрос. В финальном графе должны быть ребра (например как красное) между вершинами полигонов, которые не является касательными как в графе видимости или нет?

Просто, я что-то не нашел, в каком месте вы их добавляете

[Wataru]

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

[Magneto903]

Илья Николаевский, Хорошо! Ещё раз огромное спасибо!

[Magneto903]

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


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

[Wataru]

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

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

Это будет работать плохо только если зеленый уже в тупике и прижат красным.

[Magneto903]

Илья Николаевский, Если зеленый в тупике и прижат красным, то тут мне кажется уже ничего не поможет))

[Magneto903]

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

Куда теперь должен идти зеленый бот?

[Wataru]

Magneto903,

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

Посмотрите на все соседние вершины от зеленого бота. Одни из них ближе к самой далекой вершине и ведут к ней, другие - дальше. Можно ввести что-то типа косинуса - отношение изменения расстояния до самой далекой точки и длины ребра. Так, ребро, лежащее на пути в эту наиудаленнейшую точку будет давать 1. Ребра, ведущие от этой точки будут давать -1. Аналогично можно найти эту метрику относительно вершины в которой красный бот. Это косинус вашего синего угола на графике (-1 для идти от красного бота и +1 для идти на него), если есть прямая видимость.

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

Можно сделать бота ходящего не по вершинам графа. Вот вы нашли путь от красного бота до зеленого и у вас есть входящий вектор - последнее ребро. Еще вы нашли путь от самой дальней точки (для красного бота) до этого же зеленого бота. Опять, есть входящий вектор по последнему ребру - разверните его. Теперь у вас есть 2 вектора - один от красного бота, другой - в самую далекую точку. И вам надо как-то между этими векторами выбирать. Например, складывайте их с разными коэффициентами - вот и будет ваше направление для зеленого бота.

Надо экспериментировать.

[Magneto903]

Илья Николаевский, А если 2 и больше красных бота преследуют зеленый, то искать дальнюю точку для ближайшего красного бота? Или надо 2+ дальних точки получить? Или одну так, чтобы суммарное расстояние до двух или более красных ботов было максимальным?

[Wataru]

Я бы искал точку для которой максимально расстояние до ближайшего бота. Это делается одной дейкстрой - добавьте в граф новую вершину и ребра длины 0 во всех красных ботов. Потом ищите самую далекую точку от этой новой.

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

[Magneto903]

Илья Николаевский, Я сделал, как вы писали. В принципе зеленые теперь неплохо убегают, но иногда всё-таки в тупик заходят.
И ещё, для поиска минимального пути я использовал алгоритм Дейкстры. И когда я его 4 раза вызываю (2 раза для красных и 2 раза для зеленых) каждую итерацию т.е. 60 раз в секунду, всё заметно проседает. Как тут можно оптимизировать? Прогнать Флойда для всех статичных вершин конечно можно, но что делать с динамичными вершинами? A* алгоритм даёт значительное преимущество по скорости или нет?

[Wataru]

Magneto903, Сколько у вас в графе ребер и вершин?

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

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

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

[Magneto903]

Илья Николаевский, примерно 160 вершин и 350 рёбер.

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

[Wataru]

Magneto903, Ну вот есть у вас несколько самых далеких вершин от двух красных ботов, по разные стороны от зеленого. куда ему бежать?

Да, кстати, а кто за кем гоняется? у каждого зеленого бота свой красный, или красный гонится за ближайшим зеленым?

Так-то дейкстра на 160 вершинах 60*4 раз в секунду особо не должна нагружать ничего. Тем более, если с кучей делать. Можно в 100 раз больше в секунду успесть сделать на не самом мощном железе. Что-то у вас не так, возможно, в релизации.

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

Да, самые далекие точки нужно только статические смотреть.

[Magneto903]

Илья Николаевский, красный гоняется за ближайшим

[Magneto903]

Илья Николаевский, Я посмотрел, у меня алгоритм Дейкстры на 160 вершин и 350 рёбер требует 14 ms.
Это видимо много, раз у меня 60 раз в секунду, т.е. 16.7 ms на кадр
реализацию брал отсюда:
https://levelup.gitconnected.com/finding-the-short...

[Wataru]

Magneto903, javascript - боль. Ну блин, там в дейкстре надо 160 раз пройтись по всем вершинам и выбрать минимум, переписать пару значений в массивах и пройтись по всем ребрам суммарно по одному разу. У вас там что, цикл до 160*160*60*10=15m целую секунду выполнятся будет?

Поищите другую реализацию, без всяких объектов, преобразования к строкам.

Хотя, у меня вообще подозрение, что операция ```visited.includes(node)``` выполняется за линию в shortestDistanceNode. Что там за ```let visited = []``` в которую делается ```visited.push(node)```? это же массив, да? Если вместо этого использовать тупо массив из 160 булов и там помечать обойденность вершины, то будет работать в ~160 раз быстрее. Или на Set заменить хотябы.

[Magneto903]

Илья Николаевский, насчёт цикла до 160*160*60*10, то если например в теле цикла брать случайное число, т.е. вот так:

var s_time = performance.now()
var max_i = 160*160*60*10
var x;
for (var i=0; i < max_i; i++) {
    x = Math.random()
}

console.log(performance.now()-s_time)

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

[Wataru]

Там уже сложность операций в множителе 10 заложена. Попробуйте инкрементировать переменную.
Ну и, 400ms значит, что вы 40% времени будете тратить на эти поиски. Если построение графа в оставшиеся 60% влезает, то вы все успеваете.

[Wataru]

Magneto903, Ах да, если делать с дейкстру кучей то оно раз в 10 должно быть быстрее.

[Magneto903]

Илья Николаевский, если просто инкрементировать переменную x, то 120-135 ms

[Magneto903]

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

[Wataru]

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

Осталось реализацию дейкстры исправить не с массивом visited самих номеров вершин и линейным поиском в нем, а массив из N пометок 0/1.

[Magneto903]

Илья Николаевский, я вроде нашёл неплохую реализацию (по крайней мере работала быстро).

Но почему-то из-за неё иногда начинает всё резко тормозить, полагаю где-то происходит зацикливание.

В самой первой реализации, которую я вам прислал нужно просто исправить работу с массивом visited или что-то ещё?

[Wataru]

Magneto903, Да, в первой реалзации очевидная проблема с visited.

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

Вообще js явно страдает от отсутствия вменяемых стандартных структур данных.

Советую исправлять первый вариант.

[Magneto903]

Илья Николаевский, я исправил visited

код

var shortestDistanceNode = (distances, visited) => {
  // create a default value for shortest
    var shortest = null;
    
    // for each node in the distances object
    for (var node in distances) {
        // if no node has been assigned to shortest yet
        // or if the current node's distance is smaller than the current shortest
        var currentIsShortest =
            shortest === null || distances[node] < distances[shortest];
            
        // and if the current node is in the unvisited set
        if (currentIsShortest && visited[node] != true) {
        	//visited[node] == false
            // update shortest to be the current node
            shortest = node;
        }
    }
    return shortest;
};

var findShortestPath = (graph, startNode, endNode) => {
 
 // track distances from the start node using a hash object
   var distances = {};
 distances[endNode] = "Infinity";
 distances = Object.assign(distances, graph[startNode]);
// track paths using a hash object
 var parents = { endNode: null };
 for (var child in graph[startNode]) {
  parents[child] = startNode;
 }
  
 // collect visited nodes
   var visited = {};
// find the nearest node
   var node = shortestDistanceNode(distances, visited);
 
 // for that node:
 while (node) {
 // find its distance from the start node & its child nodes
  var distance = distances[node];
  var children = graph[node]; 
      
 // for each of those child nodes:
      for (var child in children) {
  
  // make sure each child node is not the start node
        if (child === startNode) {
          continue;
       } else {
          // save the distance from the start node to the child node
          var newdistance = distance + children[child];
// if there's no recorded distance from the start node to the child node in the distances object
// or if the recorded distance is shorter than the previously stored distance from the start node to the child node
          if (!distances[child] || distances[child] > newdistance) {
// save the distance to the object
     distances[child] = newdistance;
// record the path
     parents[child] = node;
    } 
         }
       }  
      // move the current node to the visited set
      visited[node] = true;
// move to the nearest neighbor node
      node = shortestDistanceNode(distances, visited);
    }
  
 // using the stored paths from start node to end node
 // record the shortest path
 var shortestPath = [endNode];
 var parent = parents[endNode];
 while (parent) {
  shortestPath.push(parent);
  parent = parents[parent];
 }
 shortestPath.reverse();
  
 //this is the shortest path
 var results = {
  distance: distances[endNode],
  path: shortestPath,
  all_distances: distances
 };
 // return the shortest path & the end node's distance from the start node
   return results;
};

стало работать быстрее, но не в 160 раз, а раза в 3-4 только. Т.е. вместо 15 ms 3-6ms

Я что-то неправильно сделал?

[Wataru]

Magneto903, Выглядит правильно.
Видимо, js-боль. Не знаю, попробуйте вместо хэш таблиц использовать тупо массивы. Сделайте, чтобы у вас вершины нумеровались тупо числами от 0 до сколько-их-там. Структуру соседей сделайте массивом-массивов, а не хешами всякими.

Еще, в цикле не надо проверять ```if (child === startNode) {``` можно просто в начале startNode запихать в visited. Это тоже сколько-то ускорит.

[Magneto903]

Илья Николаевский, Нашёл довольно крутую штуку
Но когда я попытался взять тот алгоритм, то он почему-то выдаёт расстояние до всех точек - Infinity
Так алгоритм работает ~1 ms, что уже лучше, но всё равно не очень быстро.

Может конечно проблема в данных, но я делал вроде всё правильно...

как я делал

var right_graph = new Graph();
		var startPoint;

		for (var i in edges) {
			var p1 = new GraphVertex(edges[i][0].name);
			var p2 = new GraphVertex(edges[i][1].name);

			if (edges[i][0].name == this.id) {
				startPoint = p1
			}

			if (edges[i][1].name == this.id) {
				startPoint = p2
			}

			var weight = edges[i][3]

			var edge = new GraphEdge(p1, p2, weight)
			right_graph.addEdge(edge)

		}

		var res = dijkstra(right_graph, startPoint);

структура edges:

[Wataru]

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

[Magneto903]

Илья Николаевский, да, вы оказались правы. Это помогло. Но к сожалению это библиотека делает всё это слишком долго. За ~10 ms.

[Magneto903]

Илья Николаевский, Я в вопросе про эффективную реализацию алгоритма Дейкстры написал о том, что самое последнее что я получил, с использованием кучи всё равно медленно работает.
Вероятно, я исчерпал возможности алгоритма Дейкстры и нужно искать что-то другое.
Если я сделаю прогон Флойда по статичным вершинами, то мне поможет это?
По идее мне тогда останется для динамичных вершин аккуратно найти корректных статичных соседей, добавить ребра и т.п. Это ведь явно будет быстрее алгоритма Дейкстры?

[Wataru]

Magneto903,

Похоже вы исчерпали возможности джаваскрипта.

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

[Magneto903]

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

[Magneto903]

Илья Николаевский, а кстати, на C++ сколько примерно бы занимал один проход последней реализации Дейкстры (который с правильной кучей - Priority Queue) для 160 вершин и 350 рёбер? Просто может проблема, что я какую-то неоптимальную структуру использую и т.п.

[Wataru]

Magneto903, По моим расчетам, ~0.05ms. +-в пару раз разброса в зависимости от машины. Если вы мне дадите js скрипт, который фиксированный тест прогоняет 1000 раз и меряет среднее время, и заодно тест в тектовом виде (не json, а тупо список ребер парами номеров), то я могу замерить на C++ и сравнить оба решения на одной машине.

[Magneto903]

Илья Николаевский, Хорошо скину js скрипт, а как именно вам скинуть тест?
так?

[
[1, 2],
[2, 3],
[1, 4]
[2, 4]
]

[Wataru]

Magneto903, Лучше просто текстом без всякого синтаксиса. в c++ json нет и надо как-то прикручивать парсинг, дополнительный.

1 2
2 3
1 3

И сначала - сколько ребер, какая вершина начальная, какая конечная.

Можно console.log(a+" "+b) для всех ребер делать.

Для проверки идентичности решений, например, пусть ваш JS бенчмарк считает сумму всех вершин в кратчайшем пути. Или сумму произведений <вершина>* (0 для startNode).

[Magneto903]

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

[Magneto903]

Илья Николаевский, всё, залил. Я завернул в HTML файл, чтобы можно было прямо из браузера запустить. Сам скрипт внутри тегов В конце скрипта в комментариях граф (а именно его ребра) в нужном вам формате.

[Wataru]

Magneto903, Совсем забыл, когда формат описывал. А длины ребер-то какие? Надо по три числа выдавать.

И да, ребра у вас одинаковой длины в разные стороны?

[Magneto903]

Илья Николаевский, да, длины рёбер p1 p2 и p2 p1 равны. Сейчас добавлю длины

[Magneto903]

Илья Николаевский, всё, добавил длины

[Wataru]

Magneto903, Js код работает 0.508ms. Мой С++ код - 0.024ms
Сумма и там и там одинаковая: 401.

Если хотите проверить, вставьте в текстовый файл "348 157 159" в первую строку, а потом ваши ребра (начало, конец, длина). Скомпилировать можно вот этой коммандой:

g++ dijkstra.cpp -O2 -Wall -std=c++14 -static-libgcc -static-libstdc++ -o dijkstra.exe

Скормить текстовый файл можно через командную строкуdijkstra.exe <input.txt.

Мой код чуть проще того minHeap что у вас используется, потому что там слишком общий. Можете попробовать так же обрезать ваш, но в 20 раз вы ускорения не получите.

Эти 20 раз - это объекты, мапы везде вместо тупых интов и массивов.

[Magneto903]

Илья Николаевский, Ну ясно) Значит я ещё не исчерпал возможности javascript. Я почитал, что типизированные массивы в js работают быстрее чем обычные + всё-таки Map работает медленнее чем нативный массив.
Также есть идея скомпилировать c++ код в wasm. Вроде как ускоряет.
Буду пытаться

[Magneto903]

Илья Николаевский, По поводу вашей реализации: там есть в вашем Heap ShiftUp:

void ShiftUp(int i) {  
    while (i > 0) {
      int p = (i - 1) / 2;
      if (heap_[p] > heap_[i]) {
        Swap(p, i);
        i = p;
      } else {
        break;
      }
    }
  }

Каким образом сравниваются две пары? По первому или второму элементу?
И ещё в какую сторону округляется (i-1) / 2? В большую, меньшую или по правилам округления?

[Wataru]

Magneto903, Пары сравниваются по первым частям, потом по вторым, если равенство в первом случае. На самом деле там недочет у меня. Можно, как в ShiftDown сравнивать только heap_[i].first. Будет даже чуть чуть быстрее.

Деление на 2 в целых числах округляется вниз. Для 1 и 2 (i-1)/2 даст 0, для 3 и 4 - 1. Точно также в вашей реализации кучи действует getParentIndex.

[Magneto903]

Илья Николаевский, я переписал вашу реализацию на C++ на JavaScript.
Теперь на моем компьютере работает за 0.17-0.2ms!

[Magneto903]

Илья Николаевский, а я правильно понимаю, что BFS не подойдёт в нашем случае? Ну и что нету более быстрого алгоритма, чем Дейкстра для этой задачи?

[Wataru]

Magneto903, Да. Bfs работает только если все ребра одинаковой длины. Ну или можно его обобщить, когда все длины - целые числа от 0 до какого-то маленького K, если использовать K+1 очереди.

[Magneto903]

Илья Николаевский, Можете пожалуйста провести ещё раз сравнение реализации на C++ с этим

[Wataru]

Magneto903, Эта реализация пишет 0.034 в консоль. Видимо - это ms на прогон. Си-шная моя по прежнему 0.024ms. Весьма близко.

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

[Magneto903]

Илья Николаевский, да, новая версии выдаёт тот же путь, что и старая, т.е. 157 -> 43 -> 42 -> 159.
Вроде правильно работает.

[Wataru]

Magneto903,
О, я понял, почему этот алгоритм работает.
Это что-то типа волнового алгоритма и алгоритма Белла. Всякий раз как где-то ребро релаксируется, конец снова добавляется для рассмотрения.

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

Можно вообще сделать так, что длина очереди будет O(2^n) для n вершин. Но это будут весьма искусственные тесты. Может в вашем случае оно в среднем будет работать лучше.

[Magneto903]

Илья Николаевский, если такой алгоритм реализовать на c++ будет быстрее работать чем Дейкстра на c++? Я просто думаю, может реализовать на c++ а потом скомпилировать в wasm модуль и просто через js его вызывать?

[Wataru]

Magneto903, Зависит от графа. Дейкстра работает всегда более или менее одинаково. Этот алгоритм может работать в несколько раз быстрее или в сотни раз медленнее.

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

[Magneto903]

Илья Николаевский, ну на первый взгляд оно работает нормально. А как-то нельзя этот алгоритм исправить, чтобы оно более стабильно работал? Или если его стабилизировать то и получится Дейкстра?

[Wataru]

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

[Magneto903]

Илья Николаевский, можете помочь с вашим кодом c++. Я просто не очень хорошо знаю c++. Мне нужны 2 функции:

get_path(graph, start, end) возвращает массив вершин-пути и длину пути
get_dists(graph, start)) возвращает массив, вершин и соответственных дистанций до них

graph - двумерный массив такого вида:

[[a1, b1, dist1], [a2, b2, dist2], ... [an, bn, distn]]

.ai, bi - номера вершины, disti - дистанция (длина ребра ai-bi)

[Wataru]

Dijkstra возвращает путь - это get_paths.

Если вам нужна get_dists, то можете взять dijkstra и вернуть массив distances после цикла while. Остальной код не нужен.

Что бы 2 раза не гонять дейкстру для расстояний и пути можно вернуть одновременно массив distances и prev. Тогда по prev кодом в Dijsktra после while можно построить путь, если он нужен.

Ваш массив graph перобразуется в Graph в функции Load.
Это фактически и есть двумерый массив, но там ребра из каждой вершины сгруппированы в одну строчку.

[Magneto903]

Илья Николаевский, а как в c++ передать в функцию двумерный массив произвольной длины? Я должен передать <vector <vector>> или как-то по-другому? Просто на данный момент у меня проблема, как настроить считывание входных данных js -> c++

[Wataru]

Magneto903, По идее, vector

Вы в сишный код передавайте массив дуг, который можно сделать тремя массивами (начало, конец и длина отдельно). А вектор векторов уже можете строить в сишном коде.

Answer 2

[Ben L]

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

Comments

[Magneto903]

Т.е. я правильно понимаю, что имеет смысл просто применить A* алгоритм для графа, у которого вершины -
это все точки полигонов + позиция бота + позиция игрока?

[twobomb]

1.Про вершины вы описали, а вот про ребра не ясно, на рисунке они указаны на ваше человеческое воcприятие.
2. А если два полигона стоят рядом друг с другом и между ними есть расстояние, но не достаточное для прохода бота. то как быть?

[Magneto903]

twobomb, Ну у меня для каждого полигона есть ещё и список рёбер. А вот по поводу второго пункта то да, хороший вопрос)

[twobomb]

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

[Magneto903]

twobomb, Да... Я что-то забыл про это. Ну видимо придётся изучать как-же работают навигационные сетки, либо упросить полигоны до прямоугольников или же как-то оптимизировать мой метод со сканерами

[Wataru]

Magneto903, Надо еще для каждого ребра графа тут проверять, что оно не пересекается с ни с одним полигоном. Еще, как я распиал в своем ответе, достаточно рассматривать только касательные между точками к полигону (ну и стороны полигонов). Это сильно снижает количество ребер и ускоряет поиск на графе.

[twobomb]

Magneto903, Разбиваете ваше поле на квадраты, например размером в AABB вашего бота.

let botWidthHeight = Math.Max(bot.width,bot.height);
for(let x = 0; x <= 5000; x+= botWidthHeight)
 for(let y = 0; y <= 5000; y+= botWidthHeight)
     arrQuads[x][y] = {x:x,y:y,width:botWidthHeight,height:botWidthHeight};

Находим квадрат где стоит наш бот это старт и где игрок, далее если нужно быстро найти делаем через A* с эвристическим алгоритмом если нужно найти именно самый кратчайший путь, то проверяем все, но искать будет долго.
Проверку на то, можно ли пройти на следующий квадрат, делаем через проверку коллизии прямоугольник\полигон, НО! Для ускорения крайне рекомендую делать проверку прямоугольник\прямоугольник, для это у каждого полигона предварительно также записать его AABB, и если происходит коллизия прямоугольник\прямоугольник, тогда уже делаем прямоугольник\полигон
Да ну и все, в итоге получаем нужный путь, если не устраивает по скорости работы думаем как оптимизировать(некоторые варианты писал ранее)

[Wataru]

twobomb, У вашего алгоритма проблема в том, что проход мужду полигонами может быть не выравнен по сетке. Т.е. и текущий квадрат и чуть левее пересекают полигоны. А посерединке пройти можно. Но и без этого - он слишком медленный. Видно, что вы не в курсе алгоритмов. Предлягать для поиска кратчайшего пути жадный алгоритм - это дичь. Есть куча стандартных алгоритмов поиска пути на графе Хоть тот же BFS. Но для работы на сетке есть еще более быстрый алгоритм - jump point search. Только в этой задаче с произвольными полигонами он не подходит.

[twobomb]

wataru, Ну по поводу скорости, он достаточно быстрый для этого случая подойдет вполне.
BFS в сотни раз медленнее и затратнее чем A* в жадной вариации, это очевидно. Про Jump point search вообще не в курсе. По поводу чуть левее чуть правее знаю, но маловероятно что это будет играть большую роль в данном случае, а если это так важно то нужно будет придумать дополнительную серию проверок, производительность конечно упадет, но точность повысится

[Wataru]

twobomb, Про A* вы первый раз написали. И это не жадный алгоритм и называть его жадным некорректно, хоть жадность там и использутеся в качестве эвристики. Далее, в данной задаче, даже если работать на сетке, BFS может оказаться сильно быстрее, если гнать его один раз от игрока и найти пути для всех ботов сразу же. A* так сделать не получится.

[twobomb]

wataru, Ну не знаю как там правильно назвать его, может это вы специалист по всем алгоритмам для графов, мне один раз приходилось находить поиск пути (чисто из интереса), а так моя работа ничего даже приближенного к этой теме не имеет. Я использовал A*, все было медленно, применил дополнительно эвристический алгоритм это значительно ускоряет время работы алгоритма.
И всё же врядли BFS будет быстрее даже если умудрится просчитать за один проход для всех ботов, возможно это будет оптимально если боты на одном краю карты, а игрок на другом, ну обычно в играх боты всетаки спаунятся около игрока(максимум за зоной его видимости), и на пути к игроку возникает максимум пара тройка препятствий.

Answer 3

[twobomb]

Делите поле на клетки, это лучше всего, и подумайте важно ли вам найти именно кратчайший путь или можно через A* с эвристическим алгоритмом.
Ну и нужно думать оптимизацию если скорость будет не достаточной, чем больше размер клетки тем быстрее будет работать алгоритм, но тем меньше точность, не следует делать размер клеток больше размеров бота(он просто может не пролезть в маленькие щели). Не нужно искать путь на каждом шаге, делайте это реже. Возможно стоит искать путь не для каждого бота отдельно, а например берет бота и все кто от него в определенном радиусе и прямой видимости и ищем путь для всей этой группы. Ну сделайте сначала самым не оптимизированным способом, а дальше уже смотрите по скорости работы

Comments

[Magneto903]

Проблема в том, что у меня не тайловое поле. И даже при очень мелкой сетке траектория будет не оптимальная и достаточно странная т.к. бот уже ограничен 8-мью направлениями. Идеальный вариант был бы NavMesh но для треугольных областей, а не только для прямоугольных. Тогда можно было бы сделать триангуляцию карты с учётом препятствий и всё было бы хорошо

[twobomb]

Magneto903, Разницы нет тайловое или не тайловое, странно почему он ограничен 8ю направлениями если поле не тайловое. И почему траектория при маленькой сетке будет не оптимальная и странная? Мне кажется как раз наоборот, ну странная может потому-что они будут прям рядом проходить возле препятствий.
Ну если хотите чтобы выглядело не странно и у вас допустим есть дороги по которым они должны ходить, то стоит прописать все пути по которым они могут ходить один раз и это невероятно ускорит работу, конечно если у вас карта не процедурно генерируемая, хотя даже в такой случае можно придумать алгоритм который будет строить нам красивые пути, по сути запущен он будет 1 раз например при запуске, и потом уже по этим путями мы будем искать ближайшую дорогу.
По поводу NavMesh если ему нужны прямоугольные полигоны может стоит попробовать или брать по ограничивающему прямоугольнику полигон (AABB) или разбивать полигоны на на прямоугольники по какому нибудь умному алгоритму, ну по сути они хоть по первому алгоритму хоть по второму и так будут обрабатываться квадратиками и как бы ступенчатые будут, ну я думаю это не важно, вам же не нужно чтобы в расчете пути участвовал каждый пиксель каждого препятствия.

Answer 4

[HellWalk]

Алгоритмы поиска пути называют A star. Да, примеры в основном сделаны на клеточных полях, но, в самом определении алгоритма:

алгоритм поиска, который находит во взвешенном графе маршрут наименьшей стоимости от начальной вершины до выбранной конечной.

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

Answer 5

[maaGames]

Раз карта прямоугольная (или может быть описана сеткой) и размер у неё маленький (5К*5К это маленький), то идеальное решение - волновая трассировка, она же одна из реализаций поиска в ширину. Будет находиться кратчайший путь, но каждый многоугольник нужно сперва "нарисовать" в сетку, чтобы в ячейку нельзя было войти.

Comments

[Magneto903]

Но ведь для карты 5k на 5k это будет 2 с половиной миллиона операций на одного бота! Разве это будет быстро работать? Или я неправильно понял идею?

[maaGames]

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

P.S. не сразу заметил про JS. Может и пару секунд искать будет на полной карте (у меня недоверие к JS). Если сперва искать по укрупнённой матрице, то будет мгновенно искать. Например, сделать 500*500 размер и предрасчитать возможность перехода из ячейки в соседнии. Сперва искать по укрупнённой, а потом уже по полной, используя только выбранные ячейки.

[Magneto903]

maaGames, ЭЭЭ, я планировал делать пересчёт каждый кадр, т.е. 60 раз в секунду...

[maaGames]

Magneto903, Зачем? В этом нет вобще никакого смысла.
В таких случаях реализуют сразу два механизма перемещения: глобальный и локальный. Глобально - пройти из одной части местности до другой, например, по большой ячейстой структуре с ячейками по 10 метров (условно). Это может быть граф или прямойгольная матрица - не имеет значения. Просто глобальное задание того, куда персонаж должен идти. Локальный вариант уточняет движение в пределах ячейки, чтобы обходить мелкие препятствия, не сталкиваться с другими персонажами и тому подобное, при этом он всё равно стремится идти в глобально заданном направлении. Т.е. он шёл, наткнулся на пенёк, сделал шаг в сторону и вернулся к "основному плану". При этом глобальный путь вычисляется или один раз или в случаи какого-то критического события (мост взрвали, дорогу перегородили т .п.), а локальный путь пересчитывается или каждый кадр или с каким-то тикрейтом. Напрмиер, если один шаг персонажа занимает 0,5 секунды, то пересчитывать путь чаще, чем 2 раза в секунду не имеет смысла. За эти 0,5 секунды может отрисоваться 120 кадров, при этом персонаж физически не может изменить траекторию движения.

[Magneto903]

maaGames, У меня персонаж как бешеный убегает от шаров) И я боюсь, что персонаж успеет даже за 0.5 секунд продвинутся так, что путь шара придётся поменять

[maaGames]

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

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