How's this for collision detection?

Question

I have to write a collide method inside a Rectangle class that takes another Rectangle object as a parameter and returns True if it collides with the rectangle performing the method and False if it doesn't. My solution was to use a for loop that iterates through every value of x and y in one rectangle to see if it falls within the other, but I suspect there might be more efficient or elegant ways to do it. This is the method (I think all the names are pretty self explanatory, just ask if anything isn't clear):

def collide(self,target):
    result = False
    for x in range(self.x,self.x+self.width):
        if x in range(target.get_x(),target.get_x()+target.get_width()):
            result = True
    for y in range(self.y,self.y+self.height):
        if y in range(target.get_y(),target.get_y()+target.get_height()):
            result = True
    return result

Thanks in advance!

Answer 1

The problem of collision detection is a well-known one, so I thought rather than speculate I might search for a working algorithm using a well-known search engine. It turns out that good literature on rectangle overlap is less easy to come by than you might think. Before we move on to that, perhaps I can comment on your use of constructs like

if x in range(target.get_x(),target.get_x()+target.get_width()):

It is to Python's credit that such an obvious expression of your idea actually succeeds as intended. What you may not realize is that (in Python 2, anyway) each use of range() creates a list (in Python 3 it creates a generator and iterates over that instead; if you don't know what that means please just accept that it's little better in computational terms). What I suspect you may have meant is

if target.get_x() <= x < target.get_x()+target.get_width():

(I am using open interval testing to reflect your use of range())This has the merit of replacing N equality comparisons with two chained comparisons. By a relatively simple mathematical operation (subtracting target.get_x() from each term in the comparison) we transform this into

if 0 <= x-target.get_x() < target.get_width():

Do not overlook the value of eliminating such redundant method calls, though it's often simpler to save evaluated expressions by assignment for future reference.

Of course, after that scrutiny we have to look with renewed vigor at

for x in range(self.x,self.x+self.width):

This sets a lower and an upper bound on x, and the inequality you wrote has to be false for all values of x. Delving beyond the code into the purpose of the algorithm, however, is worth doing. Because any lit creation the inner test might have done is now duplicated many times over (by the width of the object, to be precise). I take the liberty of paraphrasing

for x in range(self.x,self.x+self.width):
    if x in range(target.get_x(),target.get_x()+target.get_width()):
        result = True

into pseudocode: "if any x between self.x and self.x+self.width lies between the target's x and the target's x+width, then the objects are colliding". In other words, whether two ranges overlap. But you sure are doing a lot of work to find that out.

Also, just because two objects collide in the x dimension doesn't mean they collide in space. In fact, if they do not also collide in the y dimension then the objects are disjoint, otherwise you would assess these rectangles as colliding:

+----+
|    |
|    |
+----+

  +----+
  |    |
  |    |
  +----+

So you want to know if they collide in BOTH dimensions, not just one. Ideally one would define a one-dimensional collision detection (which by now we just about have ...) and then apply in both dimensions. I also hope that those accessor functions can be replaced by simple attribute access, and my code is from now on going to assume that's the case.

Having gone this far, it's probably time to take a quick look at the principles in this YouTube video, which makes the geometry relatively clear but doesn't express the formula at all well. It explains the principles quite well as long as you are using the same coordinate system. Basically two objects A and B overlap horizontally if A's left side is between B's left and right sides. They also overlap if B's right is between A's left and right. Both conditions might be true, but in Python you should think about using the keyword or to avoid unnecessary comparisons.

So let's define a one-dimensional overlap function:

def oned_ol(aleft, aright, bleft, bright):
    return (aleft <= bright < aright) or (bleft <= aright < bright)

I'm going to cheat and use this for both dimensions, since the inside of my function doesn't know which dimension's data I cam calling it with. If I am correct, the following formulation should do:

def rect_overlap(self, target):
    return oned_ol(self.x, self.x+self.width, target.x, target.x+target.width) \
        and oned_ol(self.y, self.y+self.height, target.y, target.y+target.height

If you insist on using those accessor methods you will have to re-cast the code to include them. I've done sketchy testing on the 1-D overlap function, and none at all on rect_overlap, so please let me know - caveat lector. Two things emerge.

1. A superficial examination of code can lead to "optimization" of a hopelessly inefficient algorithm, so sometimes it's better to return to first principles and look more carefully at your algorithm.

2. If you use expressions as arguments to a function they are available by name inside the function body without the need to make an explicit assignment.

Answer 2

def collide(self, target):

    # self left of target?  
    if x + self.width < target.x:
        return False

    # self right of target?
    if x > target.x + target.width :
        return False

    # self above target?
    if y + self.height < target.y:
        return False

    # self below target?
    if y > target.y + target.height:
        return False

    return True

Something like that (depends on your coord system, i.e. y positive up or down)