What about geometry multi-collision and collision?

[itzpr3d4t0r]

Context

Following our discussion in #2208 regarding multi-draw functions, it's evident that having numerous APIs for multi-operation tasks doesn't align with our goal of optimizing performance. This was particularly apparent with drawing functions, where faster looping couldn't compensate for the computational time required to render large shapes covering much of the screen.

Now, with the upcoming addition of numerous shapes and corresponding collision methods in the geometry module (#2267), we face a similar challenge. Unlike multi-draw functions, these collision methods' runtime isn't solely determined by pixel count but rather by the complexity of involved shapes. Thus, optimizing runtime and ensuring stability with longer collision sequences becomes more feasible.

The current plan

The current plan entails:

• 6 multi-collision methods (collidelist/all, collidedict/all, collideobjects/all)
• 6 single collision methods (point, circle, line, rect, polygon, collideswith)

Calculating for the 3 shapes, we'll have a total of: 6 * 3 + 6 * 3 + 3 = 39 functions. This presents a considerable number of collision methods, which could pose usability challenges.

It's worth noting that single collision functions like colliderect() also allow passing a quick tuple to represent the shape, although this doesn't provide a speed benefit. Additionally, with the introduction of shapes like Line, passing a tuple like (10, 10, 20, 10) to a general .collide() method would cause ambiguity between a line and a rectangle.

My alternative

PS. These ideas could also be expaded to the Rect class for pygame 3.0 in #2760.
The alternative proposal is based on two main ideas:

Generalize the Collision Interface

This involves two sub-ideas:

• Consolidate specific collision functions into a single .collide() function, which would streamline the interface but might limit possibilities since tuples can't be passed anymore.
• Extend multi-collision functions to accept all types of shapes, eliminating the need for shape-specific functions. However, tuples can't be accepted here due to conflicting representations.

Implementing both of these ideas would reduce the total number of collision functions from 48 (considering every collision function) to 4 + 24 = 28. This approach simplifies maintenance and testing, although it would require some programs to be rewritten, hence the proposal for pygame 3.0.

Accept a Variety of Input Types (Single and Sequence)

This idea stems from our earlier discussion and suggests retaining single collision functions while allowing them to accept sequences of shapes (both classes and tuples) as input and return a sequence of booleans.

This implementation would be relatively straightforward and would spare us from creating specific multi-collision functions for each shape. Moreover, given the nature of collision calculations compared to pixel drawing, performance improvements are predictable. For instance, testing one implementation for Circle.collidepoint yielded a consistent 3X performance improvement, which can be expected for other collision methods as well.

[dr0id]

I know two approaches: double dispatch and lookup.

I'm no expert but my experience in implementing collision detection in python has shown me these two approaches. These methods are good for the narrow phase of collision detection where the primitive collision happen. Broad phase is probably a topic of itself.

double dispatch

I have implemented it once I think.
Each shape class has a collide method where another shape class instance can be passed in, e.g.

circle1 = Circle(...)
circle2 = Circle(...)
rect1 = Rect(...)
rect2 = Rect(...)

circle1.collide(rect1)
circle1.collide(cirlce2)
rect1.collide(circle1)

But this leads to many methods to be implemented. Each shape will have to implement a method for each other shape and itself, e.g.

class Circle:

  def collide(self, other):
    other.collide_circle(self)

  def collide_circle(self, other):
   # collision code for circle vs circle
    pass

  def collide_rect(self, rect):
    # collision code for circle vs rect
    pass

  def collide_line(self, line):
    # collision code for circle vs line
    pass

class Rect:
  def collide(other):
    other.collide_rect(self)

  def collide_circle(self, other):
   # collision code for circle vs circle
    pass

  def collide_rect(self, rect):
    # collision code for circle vs rect
    pass

  def collide_line(self, line):
    # collision code for circle vs line
    pass

When adding a new shape then all classes need to be changed/updated.

lookup

I have used this many times now, My preferred way.
For the lookup method some identifiers are needed for each shape (type, class, special property, ...). The for each collision pair a method is registered in a lookup table, e.g. in python using a dict:

lookup = dict() # {(type1, type2) : coll_fun}

# write a collision function only once for each pair
def collide_circle_rect(circle, rect):
  # collision code
  pass

def collide_circle_line(circle, line):
  # collision code
  pass

# register
lookup[(circle_type, rect_type)] = collide_circle_rect
lookup[(circle_type, line_type)] = collide_circle_line

# usage
# either directly
lookup[(circle1.type_id, rect1.type_id)](circle1, rect1)

# or embedded in the classes

class Circle:

  def collide(other):
    lookup[(self.type_id, other.type_id)](self, other)

The challenges here are: the lookup key and the order of the arguments

Lookupkey: in python I use tuples, but here other ideas could be used like bit masks to combine the values into some value. Also for the lookup table it does not have to be a dict (might be slow), but maybe it could be a simple array (if the number of collision functions is fixed but then the key has to be an index).

order of arguments: the code can be written such that always the correct order is used. For convenience a re-ordering method could be registered, e.g.:

lookup = dict()

def collide_circle_rect(circle, rect):
  # collision code
  pass

lookup[(circle_type,rect_type)] = collide_circle_rect # normal registration

def re_order(r, c):
  lookup[(c.type_id, r.type_id)](c, r)

lookup[(rect_type, circle_type)] = re_order # convenience, adds an additional method call

The lookup table has the advantage that adding a new collision function is pretty easy and could even be done at runtime.

Notes

Overall I would recommend to write the collision methods to process lists of objects at once for performance and loop within the function instead of calling a collision method for each pair, e.g.:

# provide this
def collide_circles_rects(circles, rects):
  for circle in circles:
    for rect in rects:
      # collision code
      pass


def collide_circle_rect(circle, rect):
  # collision code
  pass

# don't do this, method call overhead
for c in circles:
  for r in rects:
    collide_circle_rect(c, r)
  

If there is still the need for a collision function for single objects then call the one taking lists from within the single object function.