Странное поведение в A * pathfinding

Question

Пожалуйста, посмотрите этот GIF для лучшего понимания .

Я сталкиваюсь с этим странным поведением при поиске путей *. Я должен сказать, что моя формула G-стоимости просто

distance(this, startNode)

. У меня проблема с пониманием правильной формулы G-стоимости. Пожалуйста, поправьте меня, потому что я, вероятно, ошибаюсь. Таким образом, G-стоимость текущего узла должна быть

this.gCost = parent.gCost + distance(this, parent);

, где distance (this, parent) возвращает либо 10, либо 14. Таким образом, gCost будет рассчитываться по пути, проложенному родителями, а не кратчайший путь? Я прав?

Кроме того, после установки родительского я не обновляю его - я думаю, что это главная проблема. Не могли бы вы объяснить мне в псевдокоде, когда менять родителя узла?

Answer 1

Да, это правильный способ расчета g-стоимости. Что касается обновления родителя, вы делаете это, когда рассчитанная вами стоимость g ниже, чем предыдущая стоимость g для этого узла.

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