Как это сделать для обнаружения столкновений?

Question

Я должен написать метод collide внутри класса Rectangle, который принимает в качестве параметра еще один объект Rectangle и возвращает True, если он сталкивается с прямоугольником, выполняющим метод, и False, если это не так. Моим решением было использовать цикл for, который выполняет итерацию через каждое значение x и y в одном прямоугольнике, чтобы увидеть, попадает ли он в другой, но я подозреваю, что могут быть более эффективные или изящные способы сделать это. Это метод (я думаю, что все имена довольно понятны, просто спросить, если что-то не понятно):

def collide(self,target): 
    result = False 
    for x in range(self.x,self.x+self.width): 
     if x in range(target.get_x(),target.get_x()+target.get_width()): 
      result = True 
    for y in range(self.y,self.y+self.height): 
     if y in range(target.get_y(),target.get_y()+target.get_height()): 
      result = True 
    return result 

Заранее спасибо!

Answer 1

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

if x in range(target.get_x(),target.get_x()+target.get_width()): 

Заслуга Пайтона, что такое очевидное выражение вашей идеи на самом деле преуспевает, как предполагалось. То, что вы, возможно, не осознаете, это то, что (в Python 2, в любом случае) каждое использование range() создает список (в Python 3 он создает генератор и вместо этого выполняет итерацию; если вы не знаете, что это значит, просто примите, что это немного лучше в вычислительных терминах). То, что я подозреваю, что вы, возможно, имел в виду,

if target.get_x() <= x < target.get_x()+target.get_width(): 

(я использую тестирование открытого интервала, чтобы отразить использование range()) Это имеет то преимущество, заменив N сравнения равенства двух сцепленных сравнений. При относительно простой математической операции (вычитание target.get_x() от каждого члена в сравнении), преобразует это в

if 0 <= x-target.get_x() < target.get_width(): 

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

Конечно, после этого контроля мы должны смотреть с удвоенной энергией в

for x in range(self.x,self.x+self.width): 

Это устанавливает нижнюю и верхнюю границу х, а неравенство Вы писали должно быть ложно для всех значений х , Тем не менее, стоит сделать вывод за пределы кода в целях алгоритма. Поскольку любое освещенное создание, которое могло бы сделать внутренний тест, теперь дублируется много раз (по ширине объекта, если быть точным). Я позволю себе перефразировать

for x in range(self.x,self.x+self.width): 
    if x in range(target.get_x(),target.get_x()+target.get_width()): 
     result = True 

в псевдокод: «если какое-либо х между self.x и self.x + self.width лежит между х целями и целями х + шириной, то объекты встречных» , Другими словами, перекрываются ли два диапазона. Но вы уверены, что много делаете, чтобы это выяснить.

Кроме того, только потому, что два объекта сталкиваются в измерении x, это не означает, что они сталкиваются в пространстве.В самом деле, если они также не сталкиваются в у размерности, то объекты не пересекается, иначе бы вы оценили эти прямоугольники как сталкивающиеся:

+----+ 
| | 
| | 
+----+ 

    +----+ 
    | | 
    | | 
    +----+ 

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

Поняв это, возможно, пора взглянуть на принципы в this YouTube video, что делает геометрию относительно ясной, но не выражает формулу вообще хорошо. Это объясняет принципы достаточно хорошо, пока вы используете одну и ту же систему координат. В основном два объекта A и B накладываются горизонтально, если левая сторона A находится между левой и правой сторонами B. Они также перекрываются, если право B находится между левым и правым слева. Оба условия могут быть правдой, но в Python вы должны подумать об использовании ключевого слова or, чтобы избежать ненужных сравнений.

Итак, давайте определим одномерную функцию перекрытия:

def oned_ol(aleft, aright, bleft, bright): 
    return (aleft <= bright < aright) or (bleft <= aright < bright) 

Я собираюсь обманывать и использовать это для обоих размеров, так как внутри моей функции не знает, какой размер свои данные я камерой Расширенный призывающую это с. Если я прав, то следующий состав должен сделать:

def rect_overlap(self, target): 
    return oned_ol(self.x, self.x+self.width, target.x, target.x+target.width) \ 
     and oned_ol(self.y, self.y+self.height, target.y, target.y+target.height 

Если вы настаиваете на использовании этих методов доступа вы должны заново отливать код, чтобы включить их. Я сделал отрывочное тестирование функции 1-D перекрытия, и ничего не на rect_overlap, поэтому, пожалуйста, дайте мне знать - caveat lector. Появляются две вещи.

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

2. Если вы используете выражения в качестве аргументов функции, они доступны по имени внутри тела функции без необходимости делать явное назначение.

Answer 2

def collide(self, target): 

    # self left of target? 
    if x + self.width < target.x: 
     return False 

    # self right of target? 
    if x > target.x + target.width : 
     return False 

    # self above target? 
    if y + self.height < target.y: 
     return False 

    # self below target? 
    if y > target.y + target.height: 
     return False 

    return True 

Нечто подобное (зависит от вашей системы коорда, то есть у положительно вверх или вниз)