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

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

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

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 и наоборот не работает.

Макет карты


search algorithm a-star heuristics isometric
person Electro    schedule 12.08.2009    source источник
comment
Вы сказали, что хотите исправить эвристику; Вы можете разместить код, относящийся к эвристике? Или, в качестве альтернативы, достаточно кода, чтобы мы могли определить решение?   -  person CoderTao    schedule 12.08.2009
comment
Ваша эвристика ... основана на пикселях? Расстояние Манхэттена типично для карты с квадратной сеткой и должно быть легко переведено в изометрическое, поскольку вы, вероятно, все равно храните карту в квадратной матрице. Тем не менее, размещение подсказки о том, как работает ваша текущая эвристика и как вы представляете карту внутри, было бы весьма полезно. Я думаю, что у CoderTao есть правильная идея в своем ответе, но я тоже не понимаю, почему его предложение потребует полной переписывания.   -  person agorenst    schedule 12.08.2009
comment
Моя эвристика не основана на пикселях, и моя карта не хранится в квадратной матрице, отсюда и перезапись. Карта была бы сохранена в квадратной матрице, если бы она была, например ромбовидной формы. Карта проецируется в виде прямоугольника.   -  person Electro    schedule 12.08.2009
comment
Да; но каждый квадрат на карте по-прежнему представляет собой набор двух координат. Мы не предлагаем полностью переписать все; просто немного обработки данных при вычислении эвристики. В конечном итоге нам все еще нужно более подробное описание, чтобы мы могли лучше посоветовать вам, какой курс выбрать. (Пример: я говорил о том, как исправить часть алгоритма «расстояние до завершения»; при повторном чтении кажется, что у вас проблемы только с частью «расстояние, чтобы добраться сюда»)   -  person CoderTao    schedule 12.08.2009
comment
Часть «расстояние, чтобы добраться сюда» является эвристическим. И что мне нужно, так это эвристика, которая учитывает неравномерность компоновки карты.   -  person Electro    schedule 13.08.2009
comment
Пересмотренный ответ лучше? Или альтернативно; Какие у него недостатки? (Нам очень нравится помогать ... просто попасть на одну и ту же страницу может быть сложно)   -  person CoderTao    schedule 13.08.2009
comment
Хорошо, еще раз, чего вы ожидаете в результате эвристики? это расстояние (3,2; 3,3) ‹расстояние (3,1; 3,3)‹ расстояние (3,2; 3,3)?   -  person CoderTao    schedule 13.08.2009
comment
представьте, что последним было расстояние (3,2; 3,3) ‹расстояние (3,1; 3,3)‹ расстояние (2,3; 3,3)   -  person CoderTao    schedule 13.08.2009
comment
Это почти верно. Первая стоимость 10, вторая и третья 14. Но перечитайте обновленный вопрос, если хотите.   -  person Electro    schedule 13.08.2009
comment
Хорошо; тогда я думаю, что это может быть новое решение; приведенная формула расстояния дает значения 10, 20 и 10 для вышеуказанных случаев; формула в моем ответе имеет 10, 14, 14. За исключением части обновления, которое я пропустил.   -  person CoderTao    schedule 13.08.2009

Ответы (2)


arrow_upward
4
arrow_downward

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

Скажем, 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 находится при x = 2; поэтому становится 2,5); математически найти sourceX оказывается труднее.

[Поток сознания; 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));
}

Обновление на основе новых вопросов:

Предполагая, что вы пытаетесь получить расстояние (3,2; 3,3) ‹(distance (2,3; 3,3) = distance (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);
}

РЕДАКТИРОВАТЬ: Исправлена ​​ужасная опечатка .... снова.

person CoderTao    schedule 12.08.2009
comment
Мне нужно исправить эвристику, а не сам алгоритм, а это потребует полного изменения системы. - person Electro; 12.08.2009
comment
В конечном итоге это должно изменить только эвристику; если вы попробуете эвристику для оставшегося расстояния как distance (squareCoords (current), squareCoords (dest)); Вам не нужно вносить никаких других изменений в систему. - person CoderTao; 12.08.2009
comment
Две вещи: A) есть опечатка B) это не дает мне лучшего пути, чем моя текущая эвристика, по уважительной причине: он не принимает во внимание диагональное движение - person Electro; 13.08.2009
comment
Я не беру на себя ответственности за ужасное правописание. Тем не менее; что значит «без учета диагонального движения»? Был бы полезен явный пример того, что он делает с вашей стороны. - person CoderTao; 13.08.2009
comment
Он не делает никаких диагональных ходов, если только вы не двигаетесь к соседней плитке. - person Electro; 13.08.2009
comment
Это ... бессмысленно. Не должно быть случая, когда алгоритм просто остановится ... в какой-то момент он должен исчерпать все возможности и сдаться; но это не должно задерживаться. - person CoderTao; 13.08.2009
comment
Ну вот что я имел в виду. Но на это нужно время. - person Electro; 13.08.2009
comment
Хорошо; Вероятно, здесь была еще одна ужасная опечатка. Я подозреваю, что мне следовало опубликовать код C #; gy = position.y + cy должно было быть gy = position.y + gx - person CoderTao; 13.08.2009
comment
Спасибо за код! Я настроил return 14 * diagonal... на return 11 * diagonal... и добился лучших результатов, чего это стоит. - person Clay; 08.05.2012

arrow_upward
-1
arrow_downward

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

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

Изменить: поменял синтаксис гиперссылок, упс.

person agorenst    schedule 12.08.2009
comment
К сожалению, плитки на гексагональной сетке движутся только в 6 направлениях, и стоимость перемещения одинакова для всех направлений, поэтому я не могу это использовать. - person Electro; 12.08.2009
comment
Боже мой, я совершенно неправильно понял твой вопрос. Каким-то образом изометрия стала шестиугольной. Извини за это. - person agorenst; 12.08.2009