Точный A * поиск эвристический для изометрических карт?

Question

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

Update: После обширного каротажа и анализа (читается как тратит много времени, пытаясь выяснить банальность), я пришел к выводу, что моя нынешняя эвристика работает довольно хорошо, но с одним небольшим исключением: конечный результат отменяется для real прямое и диагональное движение.

inline int Pathfinder::calculateDistanceEstimate(const CellCoord& coord) const 
{ 
    int diagonal = std::min(abs(coord.x-goal->position.x), abs(coord.y-goal->position.y)); 
    int straight = (abs(coord.x-goal->position.x) + abs(coord.y-goal->position.y)); 
    return 14 * diagonal + 10 * (straight - 2 * diagonal); 
} 

Это означает, что прямой ход, который действительно стоит sqrt(2) раза больше, чем диагональное движение на в изометрической карты, рассчитываются, чтобы быть у диагонального. Возникает вопрос: как я могу изменить текущую эвристику, чтобы она давала правильные результаты для изометрической компоновки? Просто заменив diagonal на straight и наоборот не работа.

Answer 1

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

Скажите, что 0,0 остается корень карты. 0,1 остается неизменным, 1,2 становится 0,2; 1,3 - 0,3; 2,3 превращается в 1,4; 3,3 составляет 2,5; 0,2 превращается в -1,1; и т. д. Это возвращает вас в квадратную сетку, так что координаты и эвристика должны работать снова.

Координата Y - Y + смещение источника X (3,3 при х = 2, поэтому значение равно 2,5); поиск исходногоX математически оказывается более сложным.

[Поток сознания; ignore] Изометрические координаты при Y = 0 являются точными для источника X. Таким образом, для расчета источника X вам нужно «перемещать влево/вверх Y раз», что должно чистить изменение Y/2; округляется вниз, в X координат .... примерно предполагая, что квадратные координаты будут:

sourceX = X - Y/2 
sourceY = Y + sourceX 

Где sourceX и sourceY координаты в обычной квадратной сетки; и Y/2 - целочисленная арифметика/округленная вниз.

Таким образом, в теории, это становится:

double DistanceToEnd(Point at, Point end) 
{ 
    Point squareStart = squarify(at); 
    Point squareEnd = squarify(end); 
    int dx=squareStart.X-squareEnd.X; 
    int dy=squareStart.Y-squareEnd.Y; 
    return Math.Sqrt(dx*dx+dy*dy); 
} 
Point squarify(Point p1) 
{ 
    return new Point(p1.X-p1.Y/2, p1.Y+(p1.X-p1.Y/2)); 
} 

Update на основе новых битов вопроса:

Если предположить, что вы пытаетесь получить расстояние (3,2; 3,3) < (расстояние (2,3; 3,3) = расстояние (3,1; 3,3)); следующее должно работать: (в переводе с C#, опечаток не гарантируется не присутствует)

inline int Pathfinder::calculateDistanceEstimate(const CellCoord& coord) const 
{ 
    int cx=coord.x - coord.y/2; 
    int cy=coord.y + cx; 
    int gx=goal->position.x - goal->position.y/2; 
    int gy=goal->position.y + gx; 
    int diagonal = std::min(abs(cx-gx), abs(cy-gy)); 
    int straight = (abs(cx-gx) + abs(cy-gy)); 
    return 14 * diagonal + 10 * (straight - 2 * diagonal); 
} 

EDIT: Исправлена ​​опечатка ужасно .... снова.

Answer 2

Amit здесь вычисляет «расстояния на гексагоналях». Его код на C++, и я не могу ручаться за него, но Amit - это имя, которое я слышал раньше для разработки игры.

Манхэттенское расстояние для шестиугольников должно быть подходящим для правильной эвристики.

Редактировать: изменил синтаксис гиперссылки, кричит.