Home > Back-end >  efficiently calculate distance between multiple pygame objects
efficiently calculate distance between multiple pygame objects

Time:04-09

I have a pygame program where i wish to check if any of the rabbits are close enough to mate. In doing so i have to use two for loops where i use the distance between two points formula to calculate the distance. This is process consumes many of my computers resources and cause the games performance to drop dramatically.

What is the most efficient way to check each rabbits distance to one another?

def mating(rabbits):
    for i in range(len(rabbits)):
        for x in range(len(rabbits)):
            if math.sqrt(math.pow((rabbits[i].xpos - rabbits[x].xpos),2)   math.pow((rabbits[i].ypos - rabbits[x].ypos),2)) <= 20:
                #add a new rabbit
                rabbits.append(rabbit())

CodePudding user response:

In your algorithm, math.sqrt consumes most of the time. Calculating the square root is very expensive. Compare the square of the distance instead of the distance, so you don't have to calculate the square root.
You also calculate the distance from one rabbit to the other rabbit twice. Note that you even calculate a rabbit's distance from itself (when i is equal to x). This distance is always 0. The outer loop must go through all rabbits. However, the inner loop only needs to iterate through the subsequent rabbits in the list (rabbits[i 1:]).

def mating(rabbits):
    for i, rabbit1 in enumerate(rabbits):
        for rabbit2 in rabbits[i 1:]:
            dx = rabbit1.xpos - rabbit2.xpos
            dy = rabbit1.ypos - rabbit2.ypos
            if dx*dx dy*dy <= 20*20:
                #add a new rabbit
                rabbits.append(rabbit())
  • Related