Collision detection algorithm

Question

This is my second algorithm and I will try to make it as simple for you to understand how it works. It is pretty expensive and I'd like to make it more efficient.

Visual picture of the valid points where the direction of collision is calculated at.

It works by splitting a square into 4 sides and then by determining if an edge is within a side (which is a triangle). Then collision can respond by using collision direction as a tool to reduce velocity in the y or x axis.

from vector import Vector
from math_extra import Math
from utilities import util
import random
class Collisions():
 def Detect(me, ent):
 me_Pos = Vector.Add(me.GetPos(), [me.GetVelocity()[0], -me.GetVelocity()[1]]) # first entity with a predicted pos
 ent_pos = Vector.Add(ent.GetPos(), [ent.GetVelocity()[0], -ent.GetVelocity()[1]]) # second entity with a predicted pos
 y_max, y_min, x_max, x_min = me_Pos[1] + (me.Entity.h * 0.5), me_Pos[1] - (me.Entity.h * 0.5), me_Pos[0] + (me.Entity.w * 0.5), me_Pos[0] - (me.Entity.w * 0.5) # defining edge coordinates for the first entity
 y_max2, y_min2, x_min2, x_max2 = ent_pos[1] + (ent.Entity.h / 2), ent_pos[1] - (ent.Entity.h / 2), ent_pos[0] - (ent.Entity.w/2), ent_pos[0] + (ent.Entity.w/2) # defining edge coordinates for the second entity
 isColliding = ((x_max >= x_min2 and x_max <= x_max2) or (x_min <= x_max2 and x_min >= x_min2)) and ((y_min <= y_max2 and y_min >= y_min) or (y_max <= y_max2 and y_max >= y_min2)) # are two entitities interceting at all?
 y_range = Math.Clamp((abs(me_Pos[0] - ent_pos[0])) / (0.5 * ent.Entity.w) * ent.Entity.h, 0, ent.Entity.h) * 0.5 # y range (refer to the picture) This defines valid y coordinate range for left and right edge
 y_range_2 = (y_range*0.5) # y range (refer to the picture) This defines valid y coordinate range for top and bottom range
 left = (x_max >= x_min2 and x_max <= ent_pos[0]) and ((y_min <= ent_pos[1]+y_range and y_min >= ent_pos[1]-y_range) or (y_max <= ent_pos[1]+y_range and y_max >= ent_pos[1]-y_range)) # is something hitting me from the left
 right = (x_min <= x_max2 and x_min >= ent_pos[0]) and ((y_min <= ent_pos[1]+y_range and y_min >= ent_pos[1]-y_range) or (y_max <= ent_pos[1]+y_range and y_max >= ent_pos[1]-y_range)) # is something hitting me from the right
 top = ((x_max >= x_min2 and x_max <= x_max2) or (x_min <= x_max2 and x_min >= x_min2)) and ((y_min <= y_max2 and y_min >= ent_pos[1] + y_range_2) or (y_max <= y_max2 and y_max >= ent_pos[1] + y_range_2)) # is something hitting me from the top
 bottom = ((x_max >= x_min2 and x_max <= x_max2) or (x_min <= x_max2 and x_min >= x_min2)) and ((y_max >= y_min2 and y_max <= ent_pos[1] - y_range_2) or (y_min >= y_min2 and y_min <= ent_pos[1] - y_range_2))# is something hitting me top
 Collisions.Response(me, ent, [isColliding, left, right, top, bottom]) # respond to the collision
 return isColliding, left, right, top, bottom # return data about the collision
 def Response(me, ent, physdata):
 isColliding, left, right, top, bottom = physdata[0], physdata[1], physdata[2], physdata[3], physdata[4]
 me_Pos = me.GetPos()
 ent_Pos = ent.GetPos()
 me_Velocity = me.GetVelocity()
 if left == True:
 me.SetVelocity([me_Velocity[0] * -0.2, me_Velocity[1]])
 if right == True:
 me.SetVelocity([me_Velocity[0] * -0.2, me_Velocity[1]])
 if top == True:
 me.SetVelocity([me_Velocity[0], me_Velocity[1] * -0.2])
 if bottom == True:
 me.SetVelocity([me_Velocity[0], me_Velocity[1] * -0.2])
 y_max, y_min, x_max, x_min = me_Pos[1] + (me.Entity.h * 0.5), me_Pos[1] - (me.Entity.h * 0.5), me_Pos[0] + (me.Entity.w * 0.5), me_Pos[0] - (me.Entity.w * 0.5) # again defining coordinates for edges
 for x in [x_max, x_min]: # looping through all edges and seeing if the distance between them and center of entity two is less than the radius
 for y in [y_max, y_min]:
 colliding, byDistance = util.isInSphere([x,y], ent.GetPos(), ent.Entity.w * 0.5 )
 if colliding:
 me.Entity.move_ip(Vector.Multiply(Vector.Normalize(Vector.Sub(me.GetRealPos(),ent.GetRealPos())), 1+byDistance)) # if so then move the entity in other direction
 Collisions.Stuck_Response(me, ent)
 def Stuck_Response(me,ent):
 if Vector.Distance(me.GetRealPos(), ent.GetRealPos()) < me.Entity.w * 0.7:
 me.Entity.move_ip(random.randint(1,2), random.randint(1,2))
 me.Entity.move_ip(Vector.Sub(me.GetRealPos(), ent.GetRealPos()))
 def Translate(table): # loops through all entities and checks for collision with all of them
 for k, v in enumerate(table):
 for k2, v2 in enumerate(table):
 ent_one = table[k]
 ent_two = table[k2]
 if ent_one != ent_two: # don't collide myself with myself
 Collisions.Detect(ent_one, ent_two)

Answer 1

1. Review

1. There are no docstrings. What do these functions do? What arguments do they take? What do they return?

2. The long lines mean that we can't read the code here without scrolling it. The Python style guide (PEP8) recommends sticking to 79 characters.

3. In Python it's good practice to use object attributes instead of getter functions. Using me.pos and me.velocity would make the code easier to read.

4. The code start with objects called me and ent, computes positions me_Pos and ent_pos (consistent apart from the capitalization), but then goes on to compute x_min and x_min2. Later on there are ent_one and ent_two. It is hard to remember which of these goes with me and which with ent. More consistency in naming would help.

5. The predicted position is computed like this:

   Vector.Add(me.GetPos(), [me.GetVelocity()[0], -me.GetVelocity()[1]])
   

   Why is the y component of the velocity inverted? It would be better to store it the other way round so you could write:

   Vector.Add(me.GetPos(), me.GetVelocity())
   

6. It's wrong to add a position to a velocity: the dimensions don't match. Velocity is the rate of change of position: it needs to be multiplied by a timestep in order to get a change of position. Presumably your code happens to work because your velocities are measured per frame and so the timestep is always 1. But this is inflexible: it means that if you ever need to change your framerate then you have to change all the velocities. Better to measure velocities per second.

7. The code would be much easier to read if the Vector class supported arithmetic operations (which is easy to do in Python using __add__, __mul__ and other special methods. You'd then be able to compute the predicted position like this:

   me.pos + me.velocity * timestep
   

8. The code could make more use of vectors. If an object's size were stored as a vector (instead of a pair of attributes w and h) then you could compute the axis-aligned bounding box more simply, perhaps like this:

   halfsize = me.size / 2
   bounding_box = me.pos - halfsize, me.pos + halfsize
   

9. This code repeatedly computes each object's axis-aligned bounding box before each collision. This is a waste of effort: better to compute this information once per frame and remember it.

10. The code in Stuck_Response relies on the objects having square bounding boxes (it only uses w). So why have h at all?

11. The strategy you're following here is to move the objects and then test to see if they intersect in their updated positions. This has a problem, which is that objects can pass through each other. Consider a timestep like this, with two objects in their initial positions and their movement vectors shown:

    The updated positions of the objects don't intersect:

    But a look at the swept paths of the two objects shows that at some point during the timestep they must have collided:

    See this answer on Stack Overflow for some advice on finding collisions between moving convex polygons.

12. The code in Translate compares every pair of objects. This means that it won't be able to handle very many objects before it starts to slow down due to the \$Θ(n^2)\$ runtime. Better to use some kind of spatial lookup structure like a quadtree to quickly find candidate collisions.

Answer 2

The main issue with your code is that you are using a class only as a container of methods. There is no state associated. In such conditions, using plain methods is less confusing.

However, looking at your Translate method, you could use your class as an extension of a list that perform collision detection on its own items. Something along the lines of:

class Collisions(list):
 def Translate(self):
 for elem in self:
 # do something with elem.

Talking about Translate, you should have a look at the itertools.permutation generator. However, considering two elements A and B contained in the list of collisionable items, I don't think it is efficient to perform collision detection between A and B to update A and then, latter on, perform collision detection between B and A to update B. You might want to iterate over each couple only once and call

Collision.Response(me, ent, [isColliding, left, right, top, bottom])
Collision.Response(ent, me, [isColliding, left, right, top, bottom])

or whatever parameters you see fit. In the meantime, you'd want to use itertools.combinations_with_replacement.

---

Some remarks on your style:

• As @Kai suggested, try to reduce the length of your lines; on way of doing it is condensing a > b_min and a < b_max kinds of tests by b_min < a < b_max;
• Some names sounds badly chosen; try perform_detection instead of Translate or save_new_position instead of Stuck_Response; avoid title case for function names;
• Why using a list to pass parameters around to Response if you are just unpacking them right after?
• You are computing isColliding but never using it...

---

Proposed improvement:

import random
from itertools import permutations
from vector import Vector
from math_extra import Math
from utilities import util
class Collisions(list):
 def perform_detection(self): # loops through all entities and checks for collision with all of them
 # Use combinations_with_replacement(self) if you see fit.
 for entity1, entity2 in permutations(self,2):
 Collisions.detect(entity1, entity2)
 @staticmethod
 def detect(me, ent):
 # first entity with a predicted pos
 me_Pos = Vector.Add(me.GetPos(), [me.GetVelocity()[0], -me.GetVelocity()[1]])
 # second entity with a predicted pos
 ent_pos = Vector.Add(ent.GetPos(), [ent.GetVelocity()[0], -ent.GetVelocity()[1]])
 # defining edge coordinates for the first entity
 y_max = me_Pos[1] + (me.Entity.h/2)
 y_min = me_Pos[1] - (me.Entity.h/2)
 x_max = me_Pos[0] + (me.Entity.w/2)
 x_min = me_Pos[0] - (me.Entity.w/2)
 # defining edge coordinates for the second entity
 y_max2 = ent_pos[1] + (ent.Entity.h/2)
 y_min2 = ent_pos[1] - (ent.Entity.h/2)
 x_min2 = ent_pos[0] - (ent.Entity.w/2)
 x_max2 = ent_pos[0] + (ent.Entity.w/2) 
 # does two entities intersect at all?
 isColliding = ((x_min2 <= x_max <= x_max2) or (x_min2 <= x_min <= x_max2)) and
 ((y_min2 <= y_min <= y_max2) or (y_min2 <= y_max <= y_max2)) 
 # valid y coordinate range for left and right edge
 y_range = Math.Clamp(abs(me_Pos[0] - ent_pos[0]) / (ent.Entity.w/2) * ent.Entity.h, 0, ent.Entity.h) / 2
 y_range_2 = y_range / 2
 # is something hitting me from the left
 left = (x_min2 <= x_max <= ent_pos[0]) and
 ((ent_pos[1]-y_range <= y_min <= ent_pos[1]+y_range) or
 (ent_pos[1]-y_range <= y_max <= ent_pos[1]+y_range))
 # is something hitting me from the right
 right = (ent_pos[0] <= x_min <= x_max2) and
 ((ent_pos[1]-y_range <= y_min <= ent_pos[1]+y_range) or
 (ent_pos[1]-y_range <= y_max <= ent_pos[1]+y_range))
 # is something hitting me from the top
 top = ((x_min2 <= x_max <= x_max2) or (x_min2 <= x_min <= x_max2 )) and
 ((ent_pos[1] + y_range_2 <= y_min <= y_max2) or (ent_pos[1] + y_range_2 <= y_max <= y_max2)) 
 # is something hitting me from the bottom
 bottom = ((x_min2 <= x_max <= x_max2) or (x_min2 <= x_min <= x_max2)) and
 ((y_min2 <= y_max <= ent_pos[1] - y_range_2) or (y_min2 <= y_min <= ent_pos[1] - y_range_2))
 Collisions.compute_movement(
 me, ent,
 (x_max, x_min), (y_max, y_min),
 isColliding, left, right, top, bottom)
 @staticmethod
 def compute_movement(me, ent, x_bounds, y_bounds, isColliding, left, right, top, bottom):
 me_Pos = me.GetPos()
 ent_Pos = ent.GetPos()
 me_Velocity = me.GetVelocity()
 if left or right:
 me.SetVelocity([me_Velocity[0] * -0.2, me_Velocity[1]])
 if top or bottom:
 me.SetVelocity([me_Velocity[0], me_Velocity[1] * -0.2])
 radius = ent.Etity.w / 2
 for x in x_bounds: # looping through all edges and seeing if the distance between them and center of entity two is less than the radius
 for y in y_bounds:
 colliding, byDistance = util.isInSphere([x,y], me_pos, radius)
 if colliding:
 me.Entity.move_ip(Vector.Multiply(
 Vector.Normalize(Vector.Sub(me.GetRealPos(),ent.GetRealPos())),
 1 + byDistance)) # if so then move the entity in other direction
 if Vector.Distance(me.GetRealPos(), ent.GetRealPos()) < me.Entity.w * 0.7:
 me.Entity.move_ip(random.randint(1,2), random.randint(1,2))
 me.Entity.move_ip(Vector.Sub(me.GetRealPos(), ent.GetRealPos()))

However compute_movement does not really need to be a method unless you use it several times in conjunction with combinations_with_replacement as stated above.

• HDalton: Thanks for your feedback! The computational time nearly decreased by 200%.

Answer 3

I think you could improve code style by limiting the line length.

e.g.

 bottom = ((x_max >= x_min2 and x_max <= x_max2) or (x_min <= x_max2 and x_min >= x_min2)) and ((y_max >= y_min2 and y_max <= ent_pos[1] - y_range_2) or (y_min >= y_min2 and y_min <= ent_pos[1] - y_range_2))

is really hard to read you have to scroll it (even in any IDE) horizontally. My suggestion is to break it at and and or

Moreover, adding comments to your code would help a lot to understand what's going on ;-)

• HDalton: I added comments now!