1

我将 2 个对象添加到 QuadTree，但是当我查看整个对象列表时，我只能找到 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 对象位于 0x0236FAB0 对象 platform.FAB0236 平台对象位于 0x023P6

这很好我想要可变树中有两个不同的对象但是当我调用它时它只有列表中的第二个

所以我做了一个函数

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 rect(350, 630, 110, 110) platform.Platforms 对象位于 0x02320A70 rect(350, 630, 110, 110) platform.Platforms 对象位于 0x02320A70 rect(350, 630, 110, 110) 平台。平台对象位于 0x02320A70 rect(350, 630, 110, 110)

4

1 回答 1

2

您的add_object班级每次都会创建一个新的较低级别的四叉树，即使那里已经有一个。

我打算在你之前的四叉树问题上提出这个建议（很确定是你），但你在我有机会之前就删除了它：如果 QuadTree 类有一个找到或创建适当的方法的方法，你可能会更好给定位置的子树（您rect在add_objects和中调用的内容get_elements）。请注意，这假设每个对象都完全存在于一个子树中，这对于点是正确的，但对于任意矩形则不然。（最明显的情况是一个非常大的矩形——一个覆盖整个字段的矩形——占据了任何给定级别四叉树的所有四个子树。）

假设 in 中的逻辑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

这为您提供了一种查找包含四叉树的方法（如果不存在则返回 None），或者，为了添加对象，创建它（返回现有的最大级别四叉树，或在适当的象限中创建一个新的最大级别四叉树）。

和操作让您可以使用您计算的来获取getattr和设置 self.top_left、self.top_right 等。setattrname

然后添加一个对象非常简单：

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

还有一种更好的方法来处理位置计算和测试，但我把它留作练习。（当然，如果rects 可以跨越多个子树（如果它们不是点），则您需要计算所有适当子树的列表，而不是单个适当的 top-left / top-right /左下/右下子树。）

于 2012-04-22T03:18:55.280 回答