Как скомпилировать этот код c++ в WebAssembly (или почему вывод wasm-файла отличается от вывода c++ программы)?

Фокс Йовович, а как wasm-модуль вообще мог собраться, если у меня UB?

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

Илья Николаевский, ну я тестировал на простом графе, где всего 5 вершин и 6 рёбер. Ошибка вроде не в этом. Но я думаю, что действительно стоит увеличить это число для больших графов

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

Илья Николаевский, Ладно, на самом деле мне кажется, что проблема в моём коде c++. Я не очень хорошо знаю C++.
В общем, я переписал тот нестабильный, но быстрый алгоритм на C++. Ну всё работало в C++, я думал значит будет работать и в wasm. Но когда я скомпилировал, то начала возникать ошибка Uncaught RuntimeError: memory access out of bounds. (При выполнении get_dists())Насколько я понял, это значит, что я обращаюсь к чему-то неинициализированному. Может c++ как-то на это не обращал внимание, но wasm чувствителен.

Можете пожалуйста посмотреть, где я делаю "опасные" операции (сам я ничего не нашел, но повторюсь, я не силен в c++)

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

Илья Николаевский, а вы знакомы с wasm?

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

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

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

Илья Николаевский, можете помочь с вашим кодом 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)

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

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

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

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

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

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

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

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

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

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

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

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

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

Илья Николаевский, По поводу вашей реализации: там есть в вашем 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? В большую, меньшую или по правилам округления?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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