A * допустимая эвристика на сетке с телепортерами?

Предположим, что у вас есть 2D сетка ячеек, некоторые из которых заполнены стенами. Символы могут делать шаг от одного квадрата до любого квадрата, который является одним шагом по горизонтали или вертикали от него, но не может пересекать стены.

Учитывая начальную позицию и конечную позицию, мы можем найти кратчайший путь от начальной позиции до конечной позиции, используя алгоритм A * с допустимой эвристикой. В этой текущей установке расстояние Манхэттена было бы допустимым, поскольку оно никогда не переоценивает расстояние до пункта назначения.

Теперь предположим, что помимо стен, в мире есть пары телепортеров. Переход на телепорт немедленно переносит персонажа в связанный телепорт. Существование телепортеров нарушает допустимую эвристику, приведенную выше, поскольку можно было бы добраться до места назначения быстрее, чем принимать оптимальное расстояние в Манхэттене, используя телепорт, чтобы сократить расстояние. Например, рассмотрим этот линейный мир с телепортерами, отмеченными Т, начальное положение с пометкой S, а конечная позиция отмечена E:

T . S . . . . . . . . . . . . . E . T

Здесь лучший маршрут - прогулка к телепорту слева, затем сделать два шага влево.

Мой вопрос таков: какая хорошая допустимая эвристика для A * в мире сетки с телепортерами?

Спасибо!

Ответ 1

Создайте график телепортеров:

У вас есть node для каждого телепортера и node для конечной позиции.
У вас есть грани, соединяющие каждый node друг с другом node, образуя полностью связанный граф.
Для весов краев используйте расстояние Манхэттена между каждой ячейкой назначения node (той, куда вы входите, когда вы вводите телепорт) и всеми другими узлами.

Используйте алгоритм Дейкстра для вычисления кратчайшего расстояния от каждого node до конца.

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

Ответ 2

Если в вашем мире не так много телепортеров, я бы попробовал следующую эвристику, где MHD(a,b) - расстояние Манхэттена между ячейками a и b, а T(i) - телепорт, ближайший к ячейке i:

h(x,y) = min( MHD(x,y), MHD(x,T(x)) + MHD(T(y),y) )