Есть ли возможность реализовать алгоритм поиска кратчайшего пути для большого числа вершин графа с минимальным временем работы?
Здравствуйте!
Есть небольшой проект, суть которого - что-то типа создания упрощённой версии Simulink. Моя задача - сформулировать алгоритм автоматического создания линий связи между блоками с обхождением препятствий в виде других блоков и линий. По сути, это просто задача нахождения кратчайшего пути по графу (pathfinding). Я пробовал использовать волновой алгоритм Ли, алгоритм А*, но все они работают недостаточно быстро для такого размера графа (рабочее поле представляется в виде таблицы и состоит из количества клеток, равного ширине окна умноженной на высоту).
Существует ли какой-нибудь алгоритм, способный без задержек находить кратчайший путь на таблице большого размера? Вычисления пути будут происходить достаточно часто - при перемещении курсора.
WTFAYD , так у тебя все таки граф или равномерная сетка?
Дай численные характеристики. Дай ширину и высоту поля (хотя-бы "от" и "до"). Дай время работы алгоритма Ли и A* на конкретном поле конкретных размеров.
Объясни свою реализацию A*.
Узлы в твоей сетке/графе одноранговые?
Из описания не понятно откуда берётся граф.
Связь же, наверное, идёт через "пустоту".
Понятно, что можно построить сетку и свести к графу. Но без декомпозиции это как раз будет медленно.
Самые эффективные алгоритмы поиска пути уже известны, и находятся в открытом доступе. Ни у кого нет секретного способа, который работает быстрее уже известных. Попробуйте как то сократить количество вершин, например исключайте заведомо неверные узлы из обхода.
В большей степени меня интересует вопрос - вообще, реально ли работать с большим количеством ячеек сетки (миллионы и больше) в алгоритмах без задержек во времени?
А с какого времени считается, что алгоритм работает "с задержкой"?
И что вы подразумеваете под неверными узлами?
Тут всё сильно индивидуально зависит от задачи. Например: если это просто какие то объекты, хаотично расставленные по полю достаточно разряжено, то при поиске пути между двумя точками можно использовать только достаточно узкий коридор около прямой, проведённой от старта до финиша. Или, например: привязывать размеры, форму и координаты объектов к какой то сетке и тогда можно увеличить шаг этой сетки и сократить общее количество вершин в разы (увеличив шаг сетки в n раз, количество вершин уменьшается в n^2 раза).
WTFAYD , при 60FPS на один кадр отводится всего 16мсек. Ты точно уверен что ~20мсек на поиск пути будет приемлемо?
Для чего на каждом кадре искать путь?
Средний
