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

Question

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

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

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

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

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

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

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

это занимает 4 шага, чтобы пойти туда.

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

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

Answer 1

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

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

---

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

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)}