У меня есть тороидальное эвклидово отображение. То есть поверхность является плоским евклидовым прямоугольником, но когда точка движется к правой границе, она будет появляться на левой границе (при одном и том же значении y), заданной x_new = x_old% width
В принципе, точки строятся на основе: * см. править
(x_new, y_new) = ( x_old % width, y_old % height)
Think Pac Man - выйдя с одного края экрана, вы окажетесь на противоположном краю.
Какой лучший способ рассчитать кратчайшее расстояние между двумя точками? Типичная реализация предполагает большое расстояние для точек на противоположных углах карты, когда на самом деле реальное завернутое расстояние очень близко.
Лучше всего я могу рассчитать классическую Delta X и Wrapped Delta X, а также классическую Delta Y и Wrapped Delta Y и используя нижнюю из каждой пары в формуле расстояния Sqrt (x ^ 2 + y ^ 2).
Но это потребует многих проверок, вычислений, операций - некоторые, которые, как я считаю, могут оказаться ненужными.
Есть ли лучший способ?
изменить
Когда объект перемещается, он перемещается в позицию (x_old, y_old), запускает его по вышеуказанной формуле и сохраняет (x_new, y_new) в качестве своей позиции. Вышеприведенная формула была добавлена только для выяснения того, что происходит, когда объекты перемещаются по границе; в действительности только одна (x, y) пара хранится в каждом объекте за раз.
Лучше всего я могу рассчитать классическую Delta X и Wrapped Delta X, а также классическую Delta Y и Wrapped Delta Y и используя нижнюю из каждой пары в формуле расстояния Sqrt (x ^ 2 + y ^ 2).
Это, я не думаю, что есть более быстрый путь. Но это не слишком сложно вычислять; вы могли бы сделать что-то вроде
dx = abs(x1 - x2);
if (dx > width/2)
dx = width - dx;
// again with x -> y and width -> height
(надеюсь, вы сможете перевести это на предпочитаемый вами язык)
Самое короткое расстояние между двумя точками в периодической области может быть вычислено следующим образом без использования каких-либо петель.
dx = x2-x1
dx = dx - x_width*ANINT(dx/x_width)
Это даст подписанное кратчайшее расстояние. ANINT - это внутренняя функция FORTRAN, для которой ANINT (x) дает ближайшее целое число, величина которого меньше абс (x) +0,5, с тем же знаком, что и x. Например, ANINT (0.51) = 1.0, ANINT (-0.51) = - 1.0 и т.д. Подобные функции существуют для других языков.
Найти наименьшую дельту в оси a для новых координат со значениями a1 и a2, где aBoundary - граница на оси a:
def delta(a1, a2, aBoundary):
return min(abs(a2 - a1), abs(a2 + aBoundary - a1))
Итак, если у вас есть две точки с новыми координатами x1,y1 и x2,y2, вы можете просто сделать:
sumOfSquares(delta(x1,x2,width), delta(y1,y2,height))
Это эффективно то, что вы предлагаете, но я бы не сказал, что это "много проверок, вычислений и операций".
(delta_x, delta_y)=
(min(width - abs(x_new - x_new), abs(x_new - x_old)),
min(height - abs(y_new - y_old), abs(y_new - y_old)))
Расстояние не может быть больше ширины /2 и высоты /2. Если вы получите разницу (X1-X2) больше ширины /2, вычитайте ширину /2, чтобы получить короткое расстояние. Вычислите расстояние, как обычно.
Человек, я сделал что-то ПУТЕМ другое...
здесь немного дополнительной функции, но ядром является расстояние на обернутом экране...
from math import sqrt
import pytweening
class ClosestPoint_WD(object):
def __init__(self, screen_size, point_from, point_to):
self._width = screen_size[0]
self._height = screen_size[1]
self._point_from = point_from
self._point_to = point_to
self._points = {}
self._path = []
def __str__(self):
value = "The dictionary:" + '\n'
for point in self._points:
value = value + str(point) + ":" + str(self._points[point]) + '\n'
return value
def distance(self, pos0, pos1):
dx = pos1[0] - pos0[0]
dy = pos1[1] - pos0[1]
dz = sqrt(dx**2 + dy**2)
return dz
def add_point_to_dict(self, x, y):
point = x, y
self._points[point] = 0
def gen_points(self):
max_x = self._width * 1.5 - 1
max_y = self._height * 1.5 - 1
# point 1, original point
self.add_point_to_dict(self._point_to[0], self._point_to[1])
# add the second point: x-shifted
if self._point_to[0] + self._width <= max_x:
self.add_point_to_dict(self._point_to[0] + self._width, self._point_to[1])
else:
self.add_point_to_dict(self._point_to[0] - self._width, self._point_to[1])
# add the third point: y-shifted
if self._point_to[1] + self._height <= max_y:
self.add_point_to_dict(self._point_to[0], self._point_to[1] + self._height)
else:
self.add_point_to_dict(self._point_to[0], self._point_to[1] - self._height)
# add the fourth point: diagonally shifted
if self._point_to[0] + self._width <= max_x:
if self._point_to[1] + self._height <= max_y:
self.add_point_to_dict(self._point_to[0] + self._width, self._point_to[1] + self._height)
else:
self.add_point_to_dict(self._point_to[0] + self._width, self._point_to[1] - self._height)
else:
if self._point_to[1] + self._height <= max_y:
self.add_point_to_dict(self._point_to[0] - self._width, self._point_to[1] + self._height)
else:
self.add_point_to_dict(self._point_to[0] - self._width, self._point_to[1] - self._height)
def calc_point_distances(self):
for point in self._points:
self._points[point] = self.distance(self._point_from, point)
def closest_point(self):
d = self._points
return min(d, key=d.get)
def update(self, cur_pos, target):
self._point_from = cur_pos
self._point_to = target
self._points = {}
self.gen_points()
self.calc_point_distances()
self.shortest_path()
def shortest_path(self):
path = pytweening.getLine(self._point_from[0], self._point_from[1], self.closest_point()[0], self.closest_point()[1])
#path = pytweening.getLine((self._point_from)
ret_path = []
for point in path:
ret_path.append((point[0] % self._width, point[1] % self._height))
self._path = ret_path
return self._path
вы не можете использовать функцию "abs" с оператором mod!
xd =(x1-x2+Width)%Width
yd=(y1-y2+Height)%Height
D=sqrt(xd^2+yd^2)