Нахождение направления движения в мире с обернутыми краями

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

Кратчайшее расстояние определяется как:

int rows = MapY;
int cols = MapX;

int d1 = abs(S.Y - T.Y);
int d2 = abs(S.X - T.X);
int dr = min(d1, rows-d1);
int dc = min(d2, cols-d2);

double dist = sqrt((double)(dr*dr + dc*dc));

Пример мира

                   :         
                   :  T    
                   :         
    :--------------:---------
    :              :
    :           S  :
    :              :
    :              :
    :  T           :
    :              :
    :--------------:

На диаграмме ребра показаны с помощью: и -. Я показал завернутый повтор мира в правом верхнем углу тоже. Я хочу найти направление в градусах от S до T. Таким образом, кратчайшее расстояние - до верхнего правого повтора T. Но как рассчитать направление в градусах от S до повторного T в правом верхнем углу?

Я знаю позиции как S, так и T, но я полагаю, что мне нужно найти позицию повторного T, но там больше 1.

Система координат миров начинается с 0,0 в верхнем левом углу и 0 градусов для направления, которое может начинаться с запада.

Кажется, что это не должно быть слишком сложно, но я не смог найти решение. Я надеюсь, что Сомоне может помочь? Любые сайты будут оценены.

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

int dx = T.X - S.X; // difference in position
int dy = T.Y - S.Y;

if (dx > MapX / 2) // if distance is bigger than half map width, then looping must be closer
    dx = (dx - MapX) * -1; // reduce distance by map width, reverse 
else if (dx < -MapX / 2) // handle the case that dx is negative
    dx = (dx + MapX) * -1;

//Do the same for dy
if (dy > MapY / 2)
    dy = (dy - MapY) * -1;
else if (dy < -MapY / 2)
    dy = (dy + MapY) * -1;

double dist = sqrt(dy*dy+dx*dx); // same as before
double angle = atan2(dy,dx) * 180 / PI; // provides angle in degrees

В таком мире существует бесконечное количество путей от S до T. Обозначим координаты T через (Tx, Ty), координаты S через (Sx, Sy)и размер мира через (Wx, Wy). Обернутые координаты T являются (Tx + i * Wx, Ty + j * Wy), где iи jявляются целыми числами, то есть элементами множества {..., -2, -1, 0, 1, 2, ...}. Векторы, соединяющие S с T, являются (Dx, Dy) := (Tx + i * Wx - Sx, Ty + j * Wy - Sy). Для данной (i, j)пары расстояние - это длина вектора sqrt(Dx * Dx + Dy * Dy), а направление в радианах - atan(Dy / Dx). Кратчайший путь является одним из 9 путей, где iи jнаходятся в {-1, 0, 1}:

Значения iи jдля кратчайшего пути могут быть определены напрямую:

int i = Sx - Tx > Wx / 2 ? 1 : Sx - Tx < -Wx / 2 ? -1 : 0;
int j = Sy - Ty > Wy / 2 ? 1 : Sy - Ty < -Wy / 2 ? -1 : 0;

Спасибо @IlmariKaronen, @SamHocevar и @romkyns за вашу помощь!

Вычислите один возможный вектор направления, даже если он не самый короткий, затем оберните его координату X так, чтобы он находился в [-MapX/2,MapX/2]диапазоне, и то же самое для Y:

int DirX = (T.X - S.X + 3 * MapX / 2) % MapX) - MapX / 2;
int DirY = (T.Y - S.Y + 3 * MapY / 2) % MapY) - MapY / 2;

Это оно! Вы также получите расстояние без дальнейших расчетов:

double dist = sqrt((double)(DirX*DirX + DirY*DirY));

Я думаю, что есть несколько способов сделать это. Вот 2, которые я могу думать вне головы:

# 1: обрабатывать дела вручную

Возможны ровно 10 случаев:

• Это в той же плитке, что и S
• Это в любой из 8 окружающих плиток
• Это не найдено вообще.

Однако для каждой из окружающих плиток они представляют собой перестановки различных вычислений для компонента расстояния X или Y. Поскольку это конечное число случаев, вы можете просто жестко написать, как рассчитать их, и найти кратчайшее расстояние между ними.

Вот иллюстрация 2 случаев для поиска dx. Случай 1, где Tнаходится в той же плитке, что Sи DX просто S.x - T.x. Для плитки справа, dxбудет рассчитываться как TileWidth - S.x + T.x.

               :         
               :  T    
               :         
:--------------:---------
:              :
:           S  :
:  |--------|--:--|
:dx=(S.x-T.x) dx=(TileWidth-S.x+T.x)
:  T           :
:              :
:--------------:

В качестве небольшой оптимизации найдите минимальное расстояние, прежде чем брать квадратный корень. Тогда вы экономите до 7 sqrtзвонков.

# 2: Аннотация координат

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

Для простого расчета расстояния не беспокойтесь об этом.

Не беспокойтесь о «9 направлениях». Причина в том, что среди этих 9 случаев есть 5 вырожденных случаев: «прямо на север», «прямо на запад», «прямо на юг», «прямо на восток» и «идентично». Например, прямой север является вырожденным, потому что он представляет собой случай, когда северо-запад и северо-восток соединяются и дают одинаковый результат.

Таким образом, у вас есть 4 направления для расчета, и вы можете просто выбрать минимум.

Спасибо за все ответы, в конце концов я использовал Toomai под редакцией Скотта Чемберлена. Я также сделал несколько изменений из-за того, что моя система координат начинается с y в верхнем левом углу и увеличивается при перемещении вниз (в основном инвертировано по сравнению с обычными координатами графика для y).

Я отправил сообщение на тот случай, если кто-то еще найдет эту страницу и использует такую ​​же обратную систему.

  int dx = T.X - S.X; // difference in position
int dy = S.Y - T.Y;

if (dx > MapX / 2) // if distance is bigger than half map width, then looping must be closer
    dx = (dx - (MapX / 2)) * -1; // reduce distance by half map width, reverse 
else if (dx < -MapX / 2) // handle the case that dx is negative
    dx = (dx + (MapX / 2)) * -1;

//Do the same for dy
if (dy > MapY / 2)
    dy = (MapY - dy)) * -1;
else if (dy < -MapY / 2)
    dy = (dy + MapY);

double angle = atan2(dy,dx) * 180 / PI; // provides angle in degrees

angle = 180 - angle; //convert to 360 deg