CODEWITHSUNDEEP
pythoncomparisonsetiteration
JesseTG
JesseTG

Reputation: 2123

Python: Iterating through a set so we don't compare the same objects multiple times?

So I'm writing a game. Here's how the collision detection works; there's an invisible grid, and objects (or, rather, their references) are added and removed from cells based on where they are. Collision comparisons are only done between objects in the same cell.

The references are stored in a Python set that is owned by each cell. It has to be a set. When a collision is detected, it's stored in a Collision object with three attributes; the two objects that collided and the time the collision occurred. When all collisions are accounted for, they're sorted by time, then processed.

This is the loop that individual cells use to check for collisions;

#grid.collisions is a list of recorded collisions, and self.objects is the set
#of objects currently in this cell.

for i in self.objects:
    for j in self.objects:
        if id(i) != id(j) and pygame.sprite.collide_rect(i, j):
            grid.collisions.append(Collision(i, j))

The problem is, this compares the same two objects twice; if we had a set {1, 2, 3, 4}, we'd be comparing (1, 2) and (2, 1). Not only that, but these duplicate comparisons are being added into the total list of collisions and thereby breaking the entire system!

I know that I can't index sets, which means I can't do something like for j in range(i, len(self.objects)) where i and j are both integers. How can I get around this limitation to make sure that two objects in the same set are not compared twice? I can't remove the objects in these sets; they are only to be removed if the object leaves the grid cell.

Since these collisions are being handled every frame, I would prefer to avoid creating new objects (the real code doesn't create new Collisions as the sample does, I just simplified it for readability). I could just remove duplicate comparisons, but to compare every collision to every other would be a lot of overhead.

Upvotes: 3

Views: 4545

Answers (3)

HYRY
HYRY

Reputation: 97301

Change != to < in your code:

for i in self.objects:
    for j in self.objects:
        if id(i) < id(j) and pygame.sprite.collide_rect(i, j):
            grid.collisions.append(Collision(i, j))

Upvotes: 1

jdi
jdi

Reputation: 92577

If your goal is to just compare all the unique combinations of the set, you could make use of itertools.combinations

from itertools import combinations

for i, j in combinations(self.objects, 2):
    if pygame.sprite.collide_rect(i, j):
        grid.collisions.append(Collision(i, j))

Example:

aSet = set([1,2,3,4])
list(combinations(aSet, 2))
# [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]

combinations produces a generator which is pretty efficient, compared to managing multiple indexs and temporary lists

Upvotes: 7

Vaughn Cato
Vaughn Cato

Reputation: 64308

How about making a list?

objects=list(self.objects)
for i in range(len(objects)):
  for j in range(i+1,len(objects)):
     if pygame.sprite.collide_rect(objects[i], objects[j]):
       grid.collisions.append(Collision(objects[i], objects[j]))

Here's another alternative:

objects=[]
for i in range(self.objects):
  for j in objects:
    if pygame.sprite.collide_rect(i, j):
      grid.collisions.append(Collision(i, j))
    objects.append(i)

Upvotes: 1

Related Questions