Вычисление «диагонального расстояния» в 3-х измерениях для эвристического поиска A * - PullRequest
Новая
       67

Вычисление «диагонального расстояния» в 3-х измерениях для эвристического поиска A *

0 голосов
/ 02 ноября 2018

Я бегу A * Поиск пути по трехмерной сетке данных. Доступные перемещения - это 26 окружающих узлов (то есть вы можете перемещаться по диагонали). Я использовал евклидово расстояние в качестве эвристики, и это работает хорошо, но я также хотел бы попробовать «диагональное расстояние», чтобы увидеть, как это работает (и если есть любой прирост скорости)

Я нашел некоторую логику в Интернете, чтобы сделать это в двух измерениях ... 

function heuristic(node) =
dx = abs(node.x - goal.x)
dy = abs(node.y - goal.y)
return D * (dx + dy) + (D2 - 2 * D) * min(dx, dy)

.., где D - расстояние север / восток / юг / запад (например, 1 м), а D2 - диагональное расстояние (например, sqrt (2))

Я не совсем уверен, как преобразовать это в 3 измерения - поэтому любая помощь будет принята с благодарностью

В качестве дополнительного вопроса (поскольку это то, сколько сетки в действительности ...) предположим, что узлы на оси x и y находятся на расстоянии 5 м друг от друга, но на расстоянии 2 м друг от друга на оси z ... как тогда будет работать формула?

Спасибо за любую помощь!

1 Ответ

0 голосов
/ 07 ноября 2018

Он может быть легко расширен до 3D. Требуется найти «середину» из 3 значений, для этого есть хитрость, учитывая, что у нас есть минимум и максимум. 

dx = absdiff(node.x, goal.x)
dy = absdiff(node.y, goal.y)
dz = absdiff(node.z, goal.z)
dmin = min(dx, dy, dz)
dmax = max(dx, dy, dz)
dmid = dx + dy + dz - dmin - dmax

Это работает для целых чисел в стиле Python и даже для стиля Java int, хотя для чисел с плавающей запятой это может вызвать некоторое округление.

Объедините их так: 

return (D3 - D2) * dmin + (D2 - D1) * dmid + D1 * dmax
...