Расчет между 2 точками в 2D-массиве

Я делаю карту 2D-массива, например:

* 0 1 2 3 4 5 6
0 # # # # # P #
1 # # # # # # #
2 # # # # # # #
3 # # T # # # #
4 # # # # # # #

Это игра. «Т» — Тролль, а «П» — Игрок. Тролль преследует игрока в этой игре. Предположим, что игрок теперь не будет двигаться. Позиция (строка, столбец) Тролля (3,2) и Игрока (0,5)

Тролль может преследовать игрока, идя в правом верхнем направлении. Это означает, что для достижения позиции P требуется всего 3 шага:

(3,2)->(2,3)->(1,4)->(0,5)

Но когда я использую формулу евклидова расстояния:

    (int) Math.floor(Math.sqrt(Math.pow((0-3) , 2) + Math.pow((5-2) , 2))) ;

туда нужно сделать 4 шага.

Я так запутался в формуле Distance. Я не могу использовать его в этой ситуации? Но в некоторых случаях он делает правильные шаги.

Надеюсь, кто-то может объяснить эту проблему, спасибо.


java coordinates algorithm shortest-path
person annie    schedule 23.02.2015    source источник
comment
@LarsBlumberg Движение тролля (строка, столбец): (2,3) -> (1,4) -> (0,5)   -  person annie    schedule 23.02.2015

Ответы (1)


arrow_upward
6
arrow_downward

Я думаю, вы имеете в виду возможность двигаться по диагонали. Если вы двигаетесь по диагонали, вы на самом деле перемещаетесь на sqrt(2) «единиц», поэтому вы сможете «двигаться быстрее», потому что при использовании диагоналей вы делаете более одной единицы за шаг.

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

Если вы хотите избежать диагоналей, чтобы вы не могли совершать «более быстрые» перемещения, хорошей метрикой расстояния является манхэттенское расстояние., что в основном

manhattan_distance(a,b) = abs(a.x - b.x) + abs(a.y - b.y)

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

diffX = abs(a.x - b.x)
diffY = abs(a.y - b.y)
numSteps = max(diffX, dixxY) //max is returning the higher value of both.

Это работает, потому что вы собираетесь сделать столько диагональных ходов, сколько сможете, и это число равно min(diffX,diffY), а затем вам нужно двигаться только по одной оси для напоминания о ходах, вы «приблизились» по этой оси на min(diffX,diffY) шагов, так что вам осталось сделать max(diffX-diffY) - min(diffX,diffY) ходов, теперь суммируйте два «вида» ходов (диагональные/недиагональные), и вы получите:

numMoves = max(diffX-diffY) - min(diffX,diffY) + min(diffX,diffY) = max(diffX-diffY)

Пример на вашей матрице:

diffX = abs(3-0) = 3
diffY = abs(2-5) = 3
max(diffX,diffY) = 3

тл;др:

  • Классическое евклидово расстояние не работает, потому что длина диагонали равна sqrt(2), поэтому при его использовании вы двигаетесь быстрее.
  • Ее можно решить, избегая диагоналей и используя манхэттенское расстояние dist(a,b) = abs(a.x - b.x) + abs(a.y - b.y)
  • Или разрешив диагонали и используя метрику расстояния: dist(a,b) = max{abs(a.x-b.x),(a.y-b.y)}
person amit    schedule 23.02.2015
comment
Спасибо:) Впервые слышу манхэттенскую дистанцию. - person annie; 23.02.2015