Приблизительное расстояние?

Я занимаюсь поиском пути в 2D-сетке.

Мне нужно рассчитать расстояние как одну из моих эвристик.

Кроме того, мне нужно вернуть ближайшее место, если полный путь не найден.

Вычисление точного расстояния с двойной точностью кажется ненужным. Есть ли какое-либо быстрое приближение, которое я могу использовать, которое все еще будет достаточно точным, чтобы удовлетворить мои потребности? (с точностью округления до 1)

Кстати, длина пути обычно составляет всего около 5-30 узлов, поэтому использовать более точную функцию в конце не стоит.


performance distance algorithm
person user1012037    schedule 27.10.2011    source источник
comment
Какие движения являются законными? (и почему никто еще не спросил об этом? Знание ходов имеет решающее значение для поиска хорошей эвристики)   -  person harold    schedule 27.10.2011

Ответы (3)


arrow_upward
10
arrow_downward

Мне нужно вернуть ближайшее место, если полный путь не найден.

В этом случае вы можете пропустить операцию квадратного корня при вычислении расстояния, т.е. сравнить квадраты расстояний, используя только dy * dy + dx * dx.

Это работает, поскольку a2 ‹ b2 тогда и только тогда, когда a ‹ b для двух произвольных расстояний а и б.

В 2D-сетке это будет реализовано исключительно с целыми числами.

Если вам нужны нецелые значения, я бы, вероятно, использовал doubles, пока это не окажется узким местом.

person aioobe    schedule 27.10.2011
comment
Это самая требовательная функция программы. Рассчитал их. Это вызовет отставание, так что да, я микрооптимизирую. :) - person user1012037; 27.10.2011
comment
Хе-хе.. Рад слышать :) У меня нет лучшего варианта, чем dy*dy + dx*dx. Это, однако, позволит избежать двойников в любом случае. - person aioobe; 27.10.2011
comment
@aioobe. Обязательно ли использовать dy*dy + dx*dx или просто dy + dx будет работать? Есть ли что-то, что мне не хватает? - person KK.; 27.10.2011
comment
dy + dx даст ближайшую точку с точки зрения расстояния до Манхэттена. Я бы не сказал, что это на самом деле ближайшая точка. Рассмотрим, например, если мой юнит перемещается в позицию (1,1) от своей цели (то есть dx = dy = 1), то я бы сказал, что он ближе чем если бы он сдвинулся (2, 0) от своей цели. (Поскольку фактическое расстояние от цели равно √2.) - person aioobe; 27.10.2011
comment
Спасибо, проголосовал за это как ответ. Я реализовал это, и поиск пути стал в 3 раза быстрее, на всякий случай, если кто-то подумал, что это ненужная оптимизация. ;) - person user1012037; 27.10.2011
comment
Решение верное, но объяснение, поскольку a² ‹ b², недостаточно информативно. что такое а, что б? - person AlexWien; 25.10.2013
comment
@AlexWien, уточнил. - person aioobe; 26.10.2013
comment
Спасибо, я бы добавил: два расстояния, a, b, и это всегда верно для декартовых и географических расстояний. - person AlexWien; 28.10.2013

arrow_upward
2
arrow_downward

Если это двухмерная сетка, вы можете использовать манхэттенское расстояние. Это позволит вам все время работать в единицах сетки и избегать квадратного корня. Как предполагает aioobe, это, вероятно, микрооптимизация.

person Jeff Foster    schedule 27.10.2011

arrow_upward
2
arrow_downward

Чуть лучше, чем расстояние Манхэттена, и почти такое же быстрое:

unsigned int fastDist(unsigned int dx, unsigned int dy) {
    if ( dy < dx ) return (dx + (dy >> 1));
    else return (dy + (dx >> 1));
}

Это точно, когда либо dx, либо dy равны нулю. Ошибка по диагонали составляет около 6%, а максимальная ошибка составляет около 12%.

И это можно улучшить, добавив еще один термин:

unsigned int fastDist(unsigned int dx, unsigned int dy) {
    unsigned int w;
    if ( dy < dx ) {
        w = dy >> 2;
        return (dx + w + (w >> 1));
    }
    else {
        w = dx >> 2;
        return (dy + w + (w >> 1));
    }
}

Это имеет максимальную ошибку менее 7%, а ошибка по диагонали менее 3%.

person pjheink    schedule 19.06.2013
comment
Это хороший механизм со странными свойствами, которые я все еще пытаюсь понять. Здесь есть запись с выводом и некоторыми уточнениями: flipcode.com/archives/Fast_Approximate_Distance_Functions.shtml - person phord; 04.11.2013