Я пытаюсь установить более быстрый механизм нахождения пути в игре, над которой я работаю, для графа подключенных узлов. Узлы делятся на два типа: «Сети» и «Маршрутизаторы».
На этом рисунке синие кружки представляют маршрутизаторы и сети серых прямоугольников.
Каждая сеть хранит список маршрутизаторов, к которым она подключена, и наоборот. Маршрутизаторы не могут подключаться напрямую к другим маршрутизаторам, а сети не могут подключаться напрямую к другим сетям.
Список сетей, к которым они подключены.
Маршрутизаторы делают то же самое
Мне нужно получить алгоритм, который будет отображать путь, измеренный по количеству пересекаемых сетей, для каждой возможной сети источника и назначения, исключая пути, где источник и пункт назначения являются одной и той же сетью. У меня есть один прямо сейчас, однако он необычайно медленен, занимает около двух секунд, чтобы отобразить пути, что становится невероятно заметным для всех подключенных игроков.
Текущий алгоритм - это грубый поиск в глубину (он был составлен примерно за час, чтобы просто заработало кэширование пути), который возвращает массив сетей в порядке их прохождения, что объясняет, почему это так медленный. Существуют ли более эффективные алгоритмы?
В качестве дополнительного примечания: хотя эти примеры графиков имеют четыре сети, на практике графики имеют 55 сетей и около 20 используемых маршрутизаторов. Также возможны пути, которые невозможны, и в любое время может измениться топография графа сети / маршрутизатора, требующая перестройки кэша путей.
Какой подход / алгоритм, вероятно, обеспечит наилучшие результаты для этого типа графика?