Алгоритм Дейкстры предназначен для нахождения кратчайшего пути ко всем узлам (от одного начального узла). Программисты игр используют направленный поиск, такой как A *. Когда Дейкстра обрабатывает узел, который находится ближе всего к начальной позиции, A * обрабатывает тот, который оценивается как ближайший к конечной позиции
Способ, которым это работает, заключается в том, что вы предоставляете дешевую функцию «оценки» от любой заданной позиции до конечной точки. Хороший пример - как далеко пролетит птица, чтобы туда добраться. * Добавляет это к текущему расстоянию от начала для каждого узла и затем выбирает узел, который, кажется, находится на кратчайшем пути.
Чем лучше ваша оценка, тем меньше времени потребуется, чтобы найти хороший путь. Если это время все еще слишком велико, вы можете найти путь на простой карте, а затем другой путь на более сложной карте, чтобы найти маршрут между местами, которые вы нашли на простой карте.
Обновление
После долгих поисков я нашел статью на A *, которую вы можете прочитать