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