Search code examples
pythonrecursionpygamequadtree

What is wrong with this recursive quadtree/subdivision algorithm?

this function is supposed to find if there is above a set number of points within the window, and if there is draw a rectangle around it and then subdivide by recursively calling the same function on all four quadrants of the previous rectangle. The behaviour seems almost right for the first 2 recursions and then seems to go a bit awry.. I also set a max depth so that it dosn't recurse too long. Im using pygame to draw the rectangles on the screen. Im assuming I have got muddled in my logic somewhere.

def recursion(x,x2,y,y2,max):
    #draws a square
    pygame.draw.rect(screen,(0,255,255),(x,y,x2,y2),1)

    currentMax = 0
    total_points = 0
    if max >= 30:
        return None
    currentMax = max + 1
   
    for i in range(len(xlist)):
        if xlist[i] in range(x,x2) and ylist[i] in range(y,y2):
            total_points += 1
    if total_points > 3:
      recursion(int(x),int(x2/2),int(y),int(y2/2),currentMax)#top_left
      recursion(int(x2/2),int(x2),int(y),int(y2/2),currentMax)#top_right
      recursion(int(x),int(x2/2),int(y2/2),int(y2),currentMax)#bottom_left 
      recursion(int(x2/2),int(x2),int(y2/2),int(y2),currentMax)#bottom_right

I also call it once to start the recursion with:

recursion(int(0),int(1000),int(0),int(1000),0)

The points are generated using:

for i in range(5):
    xlist.append(random.randint(0,1000))
    ylist.append(random.randint(0,1000))
Solution

  • When drawing a rectangle with pygame.draw.rect you have to specify the top, left point and the width and height instead of the bottom right point.
    Furthermore, the computation of the center is wrong. A maximum depth of 30 (2^30) is far too much and you can use the // (floor division) operator.

    Start with max >= 5 and total_points >= 1:

    def recursion(x,x2,y,y2,depth):
    if depth >= 5:
        return
    depth += 1
   
    total_points = 0
    for i in range(len(xlist)):
        if x < xlist[i] <= x2 and y < ylist[i] <= y2:
            total_points += 1

    if total_points >= 1:
        pygame.draw.rect(screen, (0,255,255), (x, y, x2-x, y2-y), 1)
        centerx = (x+x2) // 2
        centery = (y+y2) // 2
        recursion(x,       centerx, y,       centery, depth)
        recursion(centerx, x2,      y,       centery, depth)
        recursion(x,       centerx, centery, y2,      depth)
        recursion(centerx, x2,      centery, y2,      depth)

    Minimal example:

    import pygame, random

pygame.init()
screen = pygame.display.set_mode((500, 500))
clock = pygame.time.Clock()

def recursion(x,x2,y,y2,depth):
    if depth >= 5:
        return
    depth += 1
   
    total_points = 0
    for i in range(len(xlist)):
        if x < xlist[i] <= x2 and y < ylist[i] <= y2:
            total_points += 1

    if total_points >= 1:
        pygame.draw.rect(screen, (0,255,255), (x, y, x2-x, y2-y), 1)
        centerx = (x+x2) // 2
        centery = (y+y2) // 2
        recursion(x,       centerx, y,       centery, depth)
        recursion(centerx, x2,      y,       centery, depth)
        recursion(x,       centerx, centery, y2,      depth)
        recursion(centerx, x2,      centery, y2,      depth)

xlist = []
ylist = []
for i in range(5):
    xlist.append(random.randrange(screen.get_width()))
    ylist.append(random.randrange(screen.get_height()))

screen.fill(0)
recursion(0, screen.get_width(), 0, screen.get_height(), 0)
for p in zip(xlist, ylist):
    pygame.draw.circle(screen, (255, 0, 0), p, 8)
pygame.display.flip()
#pygame.image.save(screen, "grid.png")

run = True
while run:
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            run = False 

    pygame.display.flip()
    clock.tick(60)

pygame.quit()
exit()