Не могу понять алгоритм A* Pathfinding, когда кажется, что два пути возвращают одинаковую длину, но один ведет меня в совершенно неверном направлении.

Стоимость G суммируется.

Из начальной точки движение на юго-восток стоит 14. С юго-восточного квадрата (ваш квадрат «здесь и сейчас») движение на юг стоит 10, это составляет совокупную стоимость G 10 + 14 = 24.

Опять же, от юго-восточного квадрата (ваш квадрат «здесь и сейчас») движение на запад будет стоить 10 очков (G), что дает нам снова 24 (поскольку мы уже заплатили 14, чтобы добраться до этого квадрата). Но этот квадрат уже находится в вашем открытом списке, поэтому вы проверяете, лучше ли полученный результат. Ваш открытый список показывает G 10 для этого квадрата, и поскольку 24 хуже, вы не обновляете его. (вот что значит выделенное жирным шрифтом)

Да вы что-то упускаете. Хотя я не уверен, что именно.

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

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

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

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

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

Это то, что, по вашему мнению, описывает алгоритм:

 ___ ___ ___ ___ ___
|   |   |xxx|   |   |  p = parent
|___|___|xxx|___|___|  c = current
| p |   |xxx|   | e |  e = end
|___\___|xxx|___|___|
| <---c |xxx|   |   |
|___|_|_|xxx|___|___|
|   | v |   |   |   |
|___|___|___|___|___|

Но вот что происходит на самом деле:

 ___ ___ ___ ___ ___
|   |   |xxx|   |   |  p = parent
|___|___|xxx|___|___|  c = current
| p |   |xxx|   | e |  e = end
|_|_\___|xxx|___|___|
| v | c |xxx|   |   |
|___|_|_|xxx|___|___|
|   | v |   |   |   |
|___|___|___|___|___|

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

Судя по описанию, следующий ход такой:

 ___ ___ ___ ___ ___
|   |   |xxx|   |   |  p = parent
|___|___|xxx|___|___|  c = current
| p |   |xxx|   | e |  e = end
|_|_\___|xxx|___|___|
| c |\  |xxx|   |   |
|_|_\_|_|xxx|___|___|
| v | v |   |   |   |
|___|___|___|___|___|

Что, как вы можете видеть, приведет к тому же выводу, что и угловой квадрат. На самом деле, стоимость движения сначала по диагонали или сначала вниз одинакова — требуется два шага в любом направлении, чтобы добраться до углового квадрата.