Как двигаться в декартовом пространстве по кардинальным направлениям, ограничивая повороты?

Question

Дана декартова система координат, исходная позиция A (X / Y) и промежуточная позиция B (X / Y). Я хочу перейти от A к B. Однако я могу двигаться только по восьми направлениям N, NE, E, SE, S, SW, W, NW.

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

Итак, я сейчас ищу алгоритм, который решает эту проблему - от A до B только с одним или макс. два направления для использования. Конечно, сейчас я игнорирую любые препятствия, так что теоретически я всегда могу добраться от А до Б с максимум двумя разными направлениями. Вероятно, я мог бы решить эту проблему с помощью множества операторов if, но я бы предпочел более элегантное решение ...

Надеюсь, это было несколько понятно:)

Заранее спасибо за любые идеи!

С уважением, Матиас

Answer 1

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

другими словами:

• проверьте, выровнены ли вы по горизонтали / вертикали.если это так, двигайтесь в этом направлении и закончите.
• в противном случае найдите наиболее близкое диагональное направление, используя метод, который у вас есть.
• двигайтесь вдоль диагонали, пока вы не выровнены по горизонтали или вертикали.затем двигайтесь в этом направлении и заканчивайте.

Answer 2

Вы можете начать с вычисления фактического количества шагов между любой заданной точкой и пунктом назначения;вероятно, это будет что-то вроде "геометрия такси" , но более сложное.Если все 8 шагов имеют одинаковое «реальное» (т. Е. Евклидово) расстояние, количество ваших шагов должно быть примерно таким:

dist(dx,dy) = |dx|+|dy| + sqrt(0.5)(|dx+dy|+|dx-dy|)

Тогда, как правило, будет два возможных шага с одинаковымНаименьшее расстояние до пункта назначения.Затем вы можете выбрать направление, которое совпадает с последним (где это возможно).

На самом деле, если вы выполните математику, как показано выше, вы, вероятно, столкнетесь с проблемами с точностью с плавающей точкой.Тем не менее, вы все равно сможете принять верное решение, предоставив небольшую «скидку» (скажем, 1% за шаг) в предпочтительном направлении.

Answer 3

Для случая двух максимумов это выглядит относительно просто:

1. Проецируйте линию из A -> B, а затем из B -> A.Выберите ближайшего к этой линии кардинала, округляя в направлении по часовой стрелке или против часовой стрелки .Быть последовательным.(Как только угол определен из A -> B, вероятно, лучше всего просто добавить Pi, чтобы минимизировать очень странные случаи с математикой ... не уверен, что это действительно может произойти.)
2. Перепроектировать линии изA -> B и B -> A вдоль выбранного кардинального направления.
   1. Если линии параллельны (требуется движение точно в одном кардинальном направлении и, таким образом, их также можно считать завершением на шаге № 1), то есть один сегмент A -> B.
   2. Если линиинепараллельно найдите пересечение линий, точка C.Тогда есть два сегмента A -> C и C -> B.

Я думаю, что более разумное решение будет давать веса для каждого поворота (относительно расстояния) - тогда путем настройкиweights - количество разрешенных ходов может быть увеличено или уменьшено.

Не уверен, что это имеет смысл / имеет смысл, но удачное кодирование!

Answer 4

Похоже, ваша проблема связана с переоценкой оптимального маршрута по пути. Это приведет к постоянным переключениям между, например, N и NE, затем N, затем NE и т. Д. Это оптимальный маршрут, основанный на расстоянии, но вам нужен оптимальный маршрут, основанный на изменениях направления.

Разрешение на это либо

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

Чтобы объяснить мое второе предложение, вы должны знать, что (без препятствий) любая точка может быть достигнута за два «хода». Начальное движение - это первое движение, и во время движения по этому пути допускается только еще одно изменение направления. Ваш алгоритм должен был бы учесть этот «еще один» - любой возможный маршрут к цели не должен быть выбран, если он не может быть достигнут за оставшееся количество ходов.

Похоже, что ваш алгоритм ориентирован на минимальное расстояние, а не на минимальные ходы - или это какая-то комбинация из двух?