Python QuadTree

Question

我向QuadTree添加2個對象，但是當我查看對象的整個列表時，我只能找到1個對象。爲什麼會這樣，我能做些什麼來解決它？

from pygame import draw 

class QuadTree(object): 
    def __init__(self, box, current_level, max_level=3):# box (top_left_x, top_left_y, size_x, size_y) 
     self.location = (box[0], box[1]) 
     self.size = (box[2], box[3]) 
     self.current_level = current_level 
     self.max_level = max_level 

     self.objects = [] 
     self.__setupchirldren__() 

    def __setupchirldren__(self): 
     self.top_right =  None 
     self.top_left =   None 
     self.bottom_right =  None 
     self.bottom_left =  None 

    def elements(self): 
     if self.current_level == self.max_level: 
      for x in self.objects: 
       print x, x.rect 
     else: 
      if self.bottom_left != None: 
       self.bottom_left.elements() 
      if self.bottom_right != None: 
       self.bottom_right.elements() 
      if self.top_left != None: 
       self.top_left.elements() 
      if self.top_right != None: 
       self.top_right.elements() 

    def add_object(self, new_object, rect): 
     if self.current_level == self.max_level: 
      #print new_object, rect 
      self.objects.append(new_object) 
      #print self.objects 
     else: 
      half_size = (self.size[0]/2, self.size[1]/2) 
      if rect.colliderect(self.location, half_size): 
       self.top_left =   QuadTree((self.location[0], self.location[1], half_size[0], half_size[1]), self.current_level+1, self.max_level) 
       self.top_left.add_object(new_object, rect) 
      if rect.colliderect((self.location[0]+half_size[0], self.location[1]), half_size): 
       self.top_right =  QuadTree((self.location[0]+half_size[0], self.location[1], half_size[0], half_size[1]), self.current_level+1, self.max_level) 
       self.top_right.add_object(new_object, rect) 
      if rect.colliderect((self.location[0], self.location[1]+half_size[1]), half_size): 
       self.bottom_left =  QuadTree((self.location[0], self.location[1]+half_size[1], half_size[0], half_size[1]), self.current_level+1, self.max_level) 
       self.bottom_left.add_object(new_object, rect) 
      if rect.colliderect((self.location[0]+half_size[0], self.location[1]+half_size[1]), half_size): 
       self.bottom_right =  QuadTree((self.location[0]+half_size[0], self.location[1]+half_size[1], half_size[0], half_size[1]), self.current_level+1, self.max_level) 
       self.bottom_right.add_object(new_object, rect) 

    def draw(self, screen): 
     #if self.current_level == self.max_level: 
     draw.line(screen, (255, 0, 0), self.location, (self.location[0]+self.size[0], self.location[1])) 
     draw.line(screen, (255, 0, 0), self.location, (self.location[0], self.location[1]+self.size[1])) 
     draw.line(screen, (255, 0, 0), (self.location[0]+self.size[0], self.location[1]+self.size[1]), (self.location[0]+self.size[0], self.location[1])) 
     draw.line(screen, (255, 0, 0), (self.location[0]+self.size[0], self.location[1]+self.size[1]), (self.location[0], self.location[1]+self.size[1])) 
     if self.current_level != self.max_level: 
      if self.bottom_left != None: 
       self.bottom_left.draw(screen) 
      if self.bottom_right != None: 
       self.bottom_right.draw(screen) 
      if self.top_left != None: 
       self.top_left.draw(screen) 
      if self.top_right != None: 
       self.top_right.draw(screen) 

    def get_elements(self, rect): 
     #ret = self.objects 
     if self.current_level == self.max_level: 
      #print self.objects 
      return self.objects 
     else: 
      half_size = (self.size[0]/2, self.size[1]/2) 
      if self.top_left!= None and rect.colliderect((self.location, half_size)): 
       return self.top_left.get_elements(rect) 
       #for x in self.top_left.get_elements(rect): 
       # ret.append(x) 
      if self.top_right!= None and rect.colliderect(((self.location[0]+self.size[0]/2, self.location[1]), half_size)): 
       return self.top_right.get_elements(rect) 
       #for x in self.top_right.get_elements(rect): 
       # ret.append(x) 
      if self.bottom_left!= None and rect.colliderect(((self.location[0], self.location[1]+self.size[1]/2), half_size)): 
       return self.bottom_left.get_elements(rect) 
       #for x in self.bottom_left.get_elements(rect): 
       # ret.append(x) 
      if self.bottom_right!= None and rect.colliderect(((self.location[0]+self.size[0]/2, self.location[1]+self.size[1]/2), half_size)): 
       return self.bottom_right.get_elements(rect) 
       #for x in self.bottom_right.get_elements(rect): 
       # ret.append(x) 
      #print ret 
     return [] 

當我插入對象它打印出

platform.Platforms在0x0236F950 platform.Platforms對象對象在0x0236F950 platform.Platforms在 0x0236F950 platform.Platforms對象的對象在0x0236F950 platform.Platforms 對象0x0236FAB0 platform.Platforms object at 0x0236FAB0 platform.Platforms object at 0x0236FAB0 platform.Platforms object at 0x0236FAB0

這是很好的我想在可變樹 兩個不同的對象，但是當我把它稱爲它只有第二個列表

，所以我做了一個功能

def elements(self): 
    if self.current_level == self.max_level: 
     for x in self.objects: 
      print x, x.rect 
    else: 
     if self.bottom_left != None: 
      self.bottom_left.elements() 
     if self.bottom_right != None: 
      self.bottom_right.elements() 
     if self.top_left != None: 
      self.top_left.elements() 
     if self.top_right != None: 
      self.top_right.elements() 

打印出

platform.Platforms對象在0x02320A70矩形（350，630，110，110） platform.Platforms對象在0x02320A70矩形（350，630，110，110） platform.Platforms在0x02320A70對象矩形（350，630，110，110） platform.Platforms對象在0x02320A70矩形（350，630，110，110）

Answer 1

你add_object類使得每一次新的較低級別的四叉樹，即使有已經在那裏。

我打算在你之前的四叉樹問題上提出這個建議（很確定是你），但是在我有機會之前將它刪除了：如果QuadTree類有一個方法可以找到 - 或者 - 爲給定位置創建適當的子樹（在add_objects和get_elements中都稱爲rect）。請注意，這假定每個對象都完全位於一個子樹內，對於點而言是如此，但對於任意矩形不是。 （最明顯的例子是一個非常大的矩形酮覆蓋整個場佔據四叉樹的任一給定電平的所有子樹。）

假設在get_elements邏輯基本上是正確的，對於例如，您可以定義是這樣的：

def find_or_create(self, rect, create = False): 
    "find or create the sub-tree that contains the given point" 
    if self.current_level == self.max_level: 
     return self # we contain it 
    half_size = (self.size[0]/2, self.size[1]/2) 
    if rect.collide_rect((self.location, half_size)): 
     name = 'top_left' 
     location = self.location 
    else if rect.collide_rect(...): 
     name = 'top_right' 
     location = ... # top right location 
    else ... [as before, each time setting name and location] 
    # now, after deciding which sub-quadrant applies... 
    quad = getattr(self, name) 
    # if the sub-quadrant already exists, recurse 
    if quad: 
     return quad.find_or_create(rect, create) 
    # otherwise, if we are supposed to create it, do that 
    if create: 
     quad = QuadTree(...) # this is why you also have to compute "location" 
     setattr(self, name, quad) 
    return quad # return the new quadtree, or None, as appropriate 

這給你一個方法來找到含有四叉樹（返回無如果不存在的話），或者添加對象，創建它（返回現有的最高級別的四叉樹或者在適當的象限中創建一個新的最大級別的四叉樹）。

getattr和setattr操作讓您使用您計算的name來獲取和設置self.top_left，self.top_right等。

添加對象，然後很瑣碎：

quad = self.find_or_create(rect, True) 
    quad.objects.append(new_object) 

有一個更好的方式來處理位置的計算與測試，以及，但我離開這個練習。（當然，如果rect s可以跨越多個子樹 - 如果它們不是點 - 則需要計算所有適當子樹的列表，而不是單個合適的左上角/右上角/左下角/右下角的子樹。）