Какие алгоритмы вычисляют направления от точки A к точке B на карте?

Вероятно, подобный ответу на предварительно вычисленных маршрутах между крупнейшими местоположениями и разделенными на уровни картами, но моим пониманием то, что в играх, для ускорения* у Вас есть карта, которая очень крупна для макро-навигации и мелкомодульной карты для навигации к границе макро-направлений. Таким образом, у Вас есть 2 небольших пути для вычисления, и следовательно пространство поиска очень намного меньше, чем простое выполнение единственного пути к месту назначения. И если бы Вы находитесь в бизнесе выполнения этого много, у Вас было бы много тех данных предварительно вычисленным так, по крайней мере, часть поиска является поиском предварительно вычисленных данных, а не поиска пути.

Я не работал над Google или Картами Microsoft или Yahoo прежде, таким образом, я не могу сказать Вам, как они работают.

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

Мы использовали технику под названием ACO (Оптимизация колонии муравьев), чтобы запланировать и направить грузовики. Эта техника является методом AI, который был применен к проблеме коммивояжера для решения проблем маршрутизации. Прием с ACO должен создать ошибочное вычисление, основанное на известных фактах маршрутизации так, чтобы модель решения графика знала, когда выйти (когда достаточно небольшая ошибка).

можно google ACO или TSP для нахождения больше на этой технике. Я не использовал ни одного из инструментов AI с открытым исходным кодом для этого однако, так не может предложить один (хотя я слышал, что РОЙ был довольно всесторонним).

Просто обратившись к треугольным нарушениям неравенства, надо надеяться, дополнительным фактором, для которого они оптимизируют, является здравый смысл. Вы не обязательно хотите самый короткий или самый быстрый маршрут, поскольку он может привести к хаос и разрушение . Если Вы хотите, чтобы Ваши направления предпочли главные маршруты, которые благоприятны для грузовика и могут справиться с отправлением каждого sat-nav-following драйвера вниз их, Вы быстро отбрасываете треугольное неравенство [1].

, Если Y является узкой жилой улицей между X и Z, Вы, вероятно, только хотите использовать ярлык через Y, если пользователь явно просит X-Y-Z. Если они просят X-Z, они должны придерживаться главных дорог, даже если это немного далее и берет немного дольше. Это подобно парадокс Braess - если все пытаются следовать самым коротким, самым быстрым маршрутом, получающаяся перегрузка означает, что это не самый быстрый маршрут ни для кого больше. Отсюда мы отклоняемся от теории графов в теорию игр.

[1] На самом деле, любая надежда, что произведенные расстояния будут функцией расстояния в математическом смысле, умирает, когда Вы позволяете односторонние дороги и теряете требование симметрии. Потеря треугольного неравенства также просто втирает соль в рану.

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

Лучшее решение, которое я сделал, было использование A * с расстоянием по прямой в качестве эвристической функции. Но тогда вам нужны какие-то координаты для каждой точки (пересечения или вершины) на карте. Вы также можете попробовать разные веса для эвристической функции, например

f(n) = k*h(n) + g(n)

, где k - некоторая константа больше 0.

Я немного удивлен, не увидев здесь упомянутого алгоритма Флойда Уоршалла . Этот алгоритм очень похож на алгоритм Дейкстры. У него также есть одна очень приятная функция, которая позволяет вам вычислять столько, сколько вы хотите, разрешая больше промежуточных вершин. Таким образом, он, естественно, довольно быстро найдет маршруты, по которым проходят автомагистрали между штатами или автомагистрали.