Вам нужно использовать расстояние Манхэттена для алгоритмов поиска путей A *?

Question

Я работаю над алгоритмом поиска пути A * с видео из Себастьяна Лиги (yt). Но я не знаю, нужно ли мне использовать манхэттенское расстояние или я могу использовать обычную теорему Пифагора для измерения расстояния. Кто-нибудь знает это?

Я работаю в c#, единство, если это уместно

Answer 1

Предполагая, что вам разрешено совершать диагональные движения, затем используйте теорему Пифагора для измерения диагонального расстояния, поэтому у вас будет стоимость 1 для перемещения по горизонтали / вертикали и стоимость 1,4 для перемещения по диагонали. Если вы используете Манхэттенское расстояние для измерения диагональных перемещений, вы никогда не будете перемещаться по диагонали, потому что стоимость каждого диагонального перемещения будет суммой горизонтального и вертикального перемещения.

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