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

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, Совсем забыл, когда формат описывал. А длины ребер-то какие? Надо по три числа выдавать.

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

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

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

1 2
2 3
1 3

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

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

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

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

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

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

Magneto903,

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

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

Самая быстрая реализация алгоритма Дейкстры на javascript?

Magneto903, ускорение не в n раз. До этого было n^2+m, теперь стало (n+m) log n операций. Да и операции чуть посложнее стали. Где-то 10 раз и есть ускорение. Этого вам теперь должно хватить.

Самая быстрая реализация алгоритма Дейкстры на javascript?

this.indexes у вас должен быть map из item в место в очереди.

В swap надо делать:

this.indexes.set(this.heapContainer[indexOne], indexOne);
this.indexes.set(this.heapContainer[indexTwo], indexTwo);

Надо в poll тоже переписывать index у pop-нутого элемента:
this.indexes.set(this.heapContainer[0], 0);

В remove тоже есть место где вы на место indexToRemove ставите последний элемент. Надо

indexes[heapContainer[indexToRemove]] = indexToRemove;

сделать.

Воде все косяки, что я нашел.

Самая быстрая реализация алгоритма Дейкстры на javascript?

Magneto903, Странный у вас какой-то граф. Я правильно понял, что индекс в массиве - это начальная вершина, ключ в map - это вторая вершина, а значение - длина ребра?
У вас ребра вперед и назад разной длины, есть связь всех вершин с четвертой, а она назад только с третьей. Но дейкстра и в ориентированных графах работет, так что это не проблема.

Дабавьте еще вывода туда, где newDistance считается и в очереди что-то обновляется или добавляется. Проблема там, где второй раз выводится current_node 1. Видимо на предыдущей итерации он ее добавляет в очередь из дуги 1=>3

Как он ей делает distance = 3? Ведь в начале вы делаете distances.set(startNode, 0); и только уменьшаете расстояние.

Видимо косяк в этом коде:

if (!distances.get(child[0]) || distances.get(child[0]) > newdistance)

когда child[0] == 1, distances[1] ==0, newdistance ==3 он переписывает. Проверьте приоритет операций, что возвращает !distances.get(). Пройдитесь дебаггером.

Как создать радиус в любое расстояние м/км расположенного вокруг координаты и получить список этих координат?

agent_2203, У вас есть шаг изменения широты, чтобы отступить на один метр.

Откладывайте его от x0, y0, пока расстояние от текущей точки до центра не станет больше вашего радиуса (исходные данные в вашей задаче).

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

Так вы получите все точки в сетке с расстоянием примерно в 1м в пределах заданного радиуса.

Как создать радиус в любое расстояние м/км расположенного вокруг координаты и получить список этих координат?

agent_2203, Еще смотрите, что расстояние возвращенное haversine в тех же единицах, что и required_dist. Модуль по ссылке в ответе, вроде без дополнительных параметров возвращает в километрах.

Как создать радиус в любое расстояние м/км расположенного вокруг координаты и получить список этих координат?

agent_2203, Потому что опечатка, надо в условии цикла поменять знак на >.

Как создать радиус в любое расстояние м/км расположенного вокруг координаты и получить список этих координат?

agent_2203, required_dist - это ваш 1м, заданный в условии задачи.

Как создать радиус в любое расстояние м/км расположенного вокруг координаты и получить список этих координат?

agent_2203,

// x,y - точка от которой ищем +1м вверх
// -180 <=x<=180, -90<=y<=90.
l = 0
// required_dist - нужное приращение
r = min(180, 90-y);
while r-l < 1e-10:
  m=(r+l)/2;
  dist = haversine((x,y),(x,y+m)); // Формула для расстояния между точками.
  if dist > required_dist: r = m
  else l = m
step = l; // шаг по широте, чтобы сдвинутся на required_dist.

Как создать радиус в любое расстояние м/км расположенного вокруг координаты и получить список этих координат?

agent_2203, расстояние между точками. 1 метр.

Но на самом деле там фигня у меня написана... лучше тупо до 180 по долготе и до 90 по широте гнать и не доумать.

Самая быстрая реализация алгоритма Дейкстры на javascript?

Magneto903, Смотрите внимательно в отладке, этот цикл доходит до стартовой вершины? Выведите parents.

Самая быстрая реализация алгоритма Дейкстры на javascript?

Magneto903, с этим циклом алгоритм не выполняется фактически.

Самая быстрая реализация алгоритма Дейкстры на javascript?

Magneto903, Выглядит нормально.

Самая быстрая реализация алгоритма Дейкстры на javascript?

Magneto903, давайте...

Самая быстрая реализация алгоритма Дейкстры на javascript?

Magneto903, Не знаю, может minHeap коряво написан.

Вряд ли это причина ваших проблем, но changePriority (вернее вызываемый им remove) тут работает за линию. Поэтому в итоге решение, когда заработает, будет тормозить. Это можно вылечить, если переписать minHeap возвращать номер позиции куда добавленный элемент был воткнут в add. Ее надо в priorityQueue.add и changePriority сохранять. При вызове remove или changePriority надо удалять с этой позиции (немного переписать minHeap.remove не вызывая find, ведь номер позиции уже известен).

Добавляйте всюду отладочный вывод в консоль (minheap тоже), смотрите где память выделяется, куда девается.

Самая быстрая реализация алгоритма Дейкстры на javascript?

Magneto903, Попробуйте воткнуть changePriority в конце. поменяйте 5 на 2. Должно вернуть a, c, b.

Добавьте отладочный вывод в дейкстру или вообще пройдитесь отладчиком по падающему тесту. Я не помниаю, как оно может падать по памяти. Смотрите, сколько вершин в очереди.

Еще дайте ссылку на реализацию priorityQueue. Может там косяк.