A * Эвристика поиска путей для статических узлов

#c #path-finding #a-star

#c #поиск пути #a-star

Вопрос:

Я пытаюсь написать свой собственный алгоритм поиска пути A * и сталкиваюсь с проблемой; при поиске кратчайшего пути возникает следующая ошибка:

введите описание изображения здесь

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

Это, конечно, не самый короткий путь, и я уверен, что проблема связана с моей эвристической функцией (расстояние до Манхэттена):

 int Map::manhattanDistance(Node evaluatedNode, Node goalNode)
{
    int x = evaluatedNode.xCoord - goalNode.xCoord;
    int y = evaluatedNode.yCoord - goalNode.yCoord;
    if(x   y < 0)
        return (x   y) * -1;
    else
        return x   y;
}

Мне кажется, что формула расстояния Манхэттена здесь не идеальна, и поэтому мой вопрос таков: какой другой алгоритм измерения расстояния будет работать для меня здесь?

РЕДАКТИРОВАТЬ: для наглядности ширина каждого узла определяется количеством узлов в строке / ширина экрана = 640, а высота каждого узла определяется количеством узлов в столбце / высота экрана = 480.

Ответ №1:

Отрицательная стоимость будет означать, что маршрут свободен или более того, что он учитывает предыдущие ходы. Похоже, вы пытались учесть это, умножив на -1 совокупное значение, однако ущерб уже был нанесен. Вот почему в решении использовались диагонали, (1 — 1) * -1 по-прежнему равен нулю и, следовательно, считается свободным.

Я бы заменил оператор if следующим, который использует величину каждого компонента, применяя abs к нему отдельно:

возвращает Math.abs(x) Math.abs(y);