Эффективное обнаружение столкновений

Я использую python и pyglet в 2D-игре, но столкнулся с проблемой при обнаружении столкновений. Мой код для проверки столкновения выглядит так:

def distance(self,target):
    return math.sqrt((self.x-target.x)**2 + (self.y-target.y)**2)
def check_collision(self):
    for i in list_of_mobs:
        if self.distance(i) < (self.width/2 + i.width/2):
            return True

Он проверяет расстояние от каждого спрайта, где «цель» - это другой спрайт. Я не уверен в том, что нужно ли мне проверять наличие столкновений между всеми спрайтами? У меня более 200 мобов (даже больше, надеюсь, в готовом продукте), и он становится неиграбельным, когда проверяются коллизии. Есть ли способ проверять спрайты только на определенном расстоянии без потери скорости?

РЕДАКТИРОВАТЬ:

Я почитал гугл и обнаружил, что большая часть скорости тратится на одни и те же столкновения. т.е. sprite1 проверялся с помощью sprite2, а sprite2 проверялся с помощью sprite1. Поэтому я внес несколько изменений в функцию проверки столкновений, и теперь она работает быстрее, но все еще менее 20 кадров в секунду.

def check_collision(self):
    global mobs_to_collide
    if mobs_to_collide == []:
        mobs_to_collide = list_of_mobs[:]
    if self in mobs_to_collide:
        mobs_to_collide.remove(self)
    for i in mobs_to_collide:
        if self.distance(i) < (self.width/2 + i.width/2):
            return True

(он может содержать какой-то неэффективный код / ​​бесполезные вещи. Я немного поигрался с ним)

РЕДАКТИРОВАТЬ2:

Я решил использовать rabbyt в качестве библиотеки спрайтов. Столкновения происходят быстро и легко. Я заменил приведенный выше код ^^ на:

rabbyt.collisions.collide(mobs_to_collide)

Это возвращает список списков (я не уверен, что это правильный термин) с объектами, которые столкнулись. Я все еще работаю над тем, как преобразовать это в оператор типа «если столкновение:», но я добиваюсь прогресса. Если кто-то находится в подобной ситуации, я бы рекомендовал использовать rabbyt.


python collision-detection pyglet game-ai
person user1237200    schedule 17.09.2012    source источник
comment
Зайдите в Google и прочтите о дереве квадратов и разделении двоичного пространства   -  person Aesthete    schedule 17.09.2012
comment
Они кажутся довольно сложными: / Я подумал, может быть, сетка может сработать, хотя я не уверен, как это можно сделать   -  person user1237200    schedule 17.09.2012
comment
@ user1237200, если rabbyt - это решение, вы должны добавить это как ответ, а не обновлять вопрос (вы даже можете принять свой собственный ответ).   -  person Andy Hayden    schedule 19.09.2012

Ответы (2)


arrow_upward
2
arrow_downward

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

for object_ in objects:
    if not object_.visible: # pyglet.sprite.Sprite() provides this flag
        continue
    # rest of your collision detection
person bx2    schedule 19.01.2015

arrow_upward
4
arrow_downward

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

def distancesq(self,target):
  return (self.x-target.x)**2 + (self.y-target.y)**2
def check_collision(self):
  for i in list_of_mobs:
    # Square this distance to compensate
    if self.distancesq(i) < (self.width/2 + i.width/2)**2: 
        return True
person Aesthete    schedule 17.09.2012
comment
спасибо за ответ, попробую :) сильно ли тормозит функция sqrt? - person user1237200; 17.09.2012
comment
Каждая команда во внутреннем цикле замедляет его, и в этом случае извлечение квадратного корня почти бесполезно; просто измените расстояние, на котором запускается событие. - person Douglas E Knapp; 24.05.2020