Исследуемый изометрический Pathfinder

Question

У меня проблема с попыткой выяснить, как реализовать систему поиска траектории для шахматной изометрической карты.

Я прочитал алгоритм A * и попытался посмотреть, как он будет отображаться на изометрической карте, и результаты привели меня сюда.

Таким образом, проблема лежит здесь (я сожалею о дешевом дисплее)

Итак, я в настоящее время на зеленой черепицей (2,3), и я пытаюсь найти путь к красной плитке (3,1).

Основываясь на алгоритме A *, я пытаюсь вычислить значение F соседних плит (я сделал это только для этих 3 плиток).
Поскольку изображение отображает значение F (2,1) ниже (2,2), и это является матерью всех проблем, диагональные плитки с j + 2 и j-2 будут иметь (почти) каждый раз более низкое значение F, чем «логический» выбор.
Итак, вместо того, чтобы идти (2,2), он перейдет к (2,1).

Как я могу решить эту проблему? Может кто-нибудь подскажет мне, что мне делать?

Answer 1

Основываясь на данных значениях, похоже, что ваш H не admissible. Так как для получения от (2,3) до (2,2) требуется 10, я полагаю, что он должен взять 10, чтобы получить от (2,2) до (3,1), но ваш H говорит, что требуется 20 (т.е. вы переоценивать).

Один из возможных H - это прямое расстояние до цели (или что-то вроде Manhattan distance или евклидова).

На нашем первом этапе мы исследуем всех соседей. Наши G значения будут выглядеть следующим образом: (G = зеленый, R = красной)

14 
    10 10 
14 R 14 
    10 10 
G 14 

Давайте H, как что-то вроде Манхэттена расстояния, где 14 является диагональным прыжком и 10 является переходом к непосредственному соседу. На самом деле это идеальная эвристика для этого примера, поскольку она точно такая же, как и фактическое расстояние. Это будет отличаться, если на пути есть препятствия.

Тогда мы получим значения Н как:

34 
    24 30 
14 R 34 
    10 24 
G 14 

Таким образом, наши значения F (= G + H) являются:

48 
    34 40 
28 R 48 
    20 34 
G 28 

Затем найти минимум, который 20, исследовать все это (неизведанных) соседей и найти минимум, что будет целью в этом случае.

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