[DEVELOPMENT: Hell]
Hmmm... Archetype needs to take a little break (not that I haven't already put it on the back burner). I've thought this many times, but still, I'll say it... I need to work on smaller projects. To that end, I tried my hand at the pyweek challenge that just occurred. For those that don't know, the challenge is to write a game, either alone or in a team, within one week, based off a theme that isn't revealed until the moment the challenge begins. This challenge was "Nine Times".
So... did I succeed...
Ummm, not exactly.
Turns out, having to help move family from one apartment to another takes a hell of a lot of time (8 hours of day 1... lost).
Nine hours a day due to my full time job doesn't help much either.
Then, of course, my father's computer fails two days before the end of the challenge and who's the only one in the family that can fix it? Yeeeah...
None-the-less I still spent most of my free hours working on something, and while I didn't have anything playable until 5 minutes AFTER the end of the challenge, I learned a lot!
One thing I learned was that Android's SL4A is not a viable platform for writing games. I'm thrilled that there's a method for writing applications for the Android outside of Java and C++, but as I looked into the SL4A project, I soon realized that the Android graphics library was not exposed to the scripting languages. This is a HUGE oversite of the project, I think, and, as such, I lost a few hours of the pyweek challenge because I didn't realize this issue until I was preparing to develop my pyweek game on Android. DRAT! With any luck, SL4A will get a graphics hook and then we'll REALLY be cooking! HA!
[TUTORIAL: SATs]
Pyweek wasn't a total loss, though, as I learned and nailed Separate Axis Theorem collisions!! There's a bit of documentation out on SATs and it's all pretty good, but I figured I'd share my discoveries with my wide blog audience for no other reason than to solidify my understanding of the system.
- Firstly, I'd like to point out that this is for calculating collisions on 2D objects. While SAT works on 3D, I only really worked with 2D, and that's what I'm working with.
- Secondly... I haven't worked with sphere (or rounded) objects. It wasn't what I was focusing on when I was developing my application, and so, for the time being, I'm skipping rounded objects.
- Thirdly, SAT ONLY WORKS WITH CONVEX OBJECTS! These are objects that if you drew a strait line through them, the line could NEVER intersect the object in more than 2 locations regardless of where you drew the line.
To begin let's talk about projection. What is projection? It's a shadow. For a 3D object projected onto a plane, the result is a 2D shape (or, if you think of the real world... a shadow). For a 2D object, the projection is a line with a length long enough to encompass the entire 2D object when viewed from the axis in which one is projecting.
Huh?
Well... let's think of a rectangle. The axises of a rectangle are the X and Y axis, and the projection of a rectangle upon the X axis would be the same as the length of the rectangle.
Projection in regards to SATs:
Let's stick with the rectangle for a little while and start talking about SATs...
With the Separate Axis Theorem we can determine if two objects are colliding with one another if ALL of the axises of projection between the two objects in question overlap each other. If even a single projection doesn't, then there is no collision.
Think of the two rectangles... I dare you to try drawing two rectangles in such a way that the shadows on the X axis AND the Y axis for BOTH rectangles touch but the rectangles AREN'T colliding. Go ahead. I'll sit here and wait for you...
...
...
No? Couldn't do it? And that's the point. If all shadows for both objects are all overlapping each other, then your objects are colliding. If even a single pair of shadows ARE NOT colliding, then the objects ARE NOT colliding. That's the Separate Axis Theorem. Take your objects, find all axies in which you need to project upon. If even a single axis has a pair of projections that DO NOT overlap, then there is no collision and you're done.
Finding Axises to Project Upon:
Great! Now you may be wondering... "If I'm suppose to project upon some axises, what axises do I need to use?"... As it turns out, the axises you need to project against are simply the normal vectors for each side of your 2D object. Lets look at a little python code that does this...
Code Example: 1.0
# This is a 10x10 rectangle centered at the origin.
points = [[-5, 5], [-5, -5], [5, -5], [5, 5]]
axises = [] # an empty list at the moment
# We loop through the edges of the objects...
# which just so happens to be the same as
# the number of points.
for p in range(0, len(points)):
if p == len(points)-1:
edge = [points[0] - points[0][0], points
[1] - points[0][1]]
else:
edge = [points
[0] - points[p+1][0], points
[1] - points[p+1][1]]
# Now that we have the edge, we need to find it's normal... There're actually TWO
# normals you can use, depending on if you use the left handed or right handed
# normal. For the most part, it doesn't matter which you use, as long as you're
# consistent.
# I'm going to use Left Handed normals....
norm = [edge[1], -edge[0]] # Or... (y, -x)... it's that simple.
# At this point we've found our normal, which is more or less our axis. I say
# "more or less" only because, for simplicity, our axis should be a UNIT vector.
nlength = math.sqrt((norm[0]**2)+(norm[1]**2))
axis = [norm[0]/nlength, norm[1]/nlength] # <--- That's our axis for this edge!
axises.append(axis) # and we add it to our list of axises for this object.
HEY! HEY! You're example uses a rectangle and creates FOUR axises! When you were talking to us about projection, you said rectangles only have TWO!!!
Ummm... well, yeah, sort of. Because the rectangle has four sides, it technically has four axises in which to test... however, two of those axises parallel the other two. In essence, it's like we have the same axis twice (even though they may both be going in to different directions). To solve this problem, you can change the last line of code above to...
Code Example: 1.1
AddAxis = True
# We need to loop through our existing axises.
for a in axises:
# Calculating the dot product of the two axises...
dp = (axis[0]*a[0]) + (axis[1]*a[1])
# Now we get the arc-cosine of the dot product. If the two axises are parallel
# then the value of acos will be either a 1.0 or a -1.0 ... so we check the
# absolute value of the acos to see if we get a 1.0. If we do, we DON'T want
# to add the axis to the list, since a similar one already exists.
if abs(math.acos(dp)) == 1.0:
AddAxis = False
break
if AddAxis:
axises.append(axis)
Yes, it's a bit more complicated and eats more CPU cycles, but, depending on the complexity of your shape, it shouldn't effect you too much and doing the above would cut down on the number of tests you need to do in the upcoming examples.
One important thing to keep in mind is, we need to calculate the projections of BOTH objects over BOTH objects' axises! We'll see this in Code Example 3.0
Calculating Projections:
So... now that we have our axises in which to test against, how do we calculate out the projection of the object over an axis?
Well... we take the dot product of each point in our object against our axis, storing the minimum and maximum values.
Code Example: 2.0
# These are our minimum and maximum projection values.
# Initially, we don't have any.
proj_min = None
proj_max = None
# We loop through each point in our objects.
for p in points:
# Calculating the dot product.
# NOTE: While the axis should be normalized (as we did in Code example 1.0),
# we don't need to, nor should we normalize the point.
dp = (axis[0]*p[0])+(axis[1]*p[1])
if proj_min == None:
proj_min = dp
proj_max = dp
else:
if dp < proj_min:
proj_min = dp
if dp > proj_max:
proj_max = dp
projection = [proj_min, proj_max]
Keep in mind, we would have to do with for ALL axises from BOTH objects ON BOTH objects.
Huh?
I'll explain next...
Putting it All Together... Simply:
So now you see how we get our axises to test upon and how to calculate out projections... let's put it together!
Code Example: 3.0
# obj1 and obj2 are assumed to be a list of points like used in Example Code 1.0
def collides(obj1, obj2):
# Assume the CalculateAxises function does the same as Example Code 1.0
# and returns the axises list.
# Calculate the axises for the first object
o1axises = CalculateAxises(obj1)
for axis in o1axises:
# Assume the CalculateProjection function does the same as Example Code 2.0
# and returns the [min, max] projection.
# Get the projection of obj1 over the axis.
o1proj = CalculateProjection(axis, obj1)
# Get the projection of obj2 over the axis
o2proj = CalculateProjection(axis, obj2)
# Assume the Overlaps function returns true if the two projections
# overlap and false otherwise.
if not Overlaps(o1proj, o2proj):
# As soon as ONE pair of projections DON'T overlap
# we KNOW there's no collision. Done.
return False
# NOPE! Not done yet. We now have to do the SAME THING for the axises of the
# OTHER object.
# Calculate the axises for the second object and repeat the same as we did above.
o2axises = CalculateAxises(obj2)
for axis in o2axises:
# Assume the CalculateProjection function does the same as Example Code 2.0
# and returns the [min, max] projection.
# Get the projection of obj1 over the axis.
o1proj = CalculateProjection(axis, obj1)
# Get the projection of obj2 over the axis
o2proj = CalculateProjection(axis, obj2)
# Assume the Overlaps function returns true if the two projections overlap and false
# otherwise.
if not Overlaps(o1proj, o2proj):
# As soon as ONE pair of projections DON'T overlap
# we KNOW there's no collision. Done.
return False
# We've now looped over all axises for both objects. If we're still here, then
# ALL PROJECTIONS OVERLAP!
# We've COLLIDED!
return True
And now you know, using the Separate Axis Theorem, whether or not the two objects collide.
Of course, you usually want to know a little more than that... like, if they've collided, how do you break OUT of the collision? Turns out, that's not too much harder than what we've already done.
Putting it All Together... MTV Style:
No... not the TV station. In this case, MTV stands for Minimum Transition Vector... or, more simply... What's the quickest way out of here!!!
What we want is a vector showing us the way to non-collision safety. All we need for that is axis in which the minimum overlap was found. Lets go to code, shall we?
Code Example: 4.0
def collides(obj1, obj2):
# These will hold the information we need to find our MTV.
# For now, they're None... meaning we didn't find anything yet.
MTVOverlap = None
MTVAxis = None
# Calculate the axises for the first object
o1axises = CalculateAxises(obj1)
for axis in o1axises:
# Assume the CalculateProjection function does the same as Example Code 2.0
# and returns the [min, max] projection.
# Get the projection of obj1 over the axis.
o1proj = CalculateProjection(axis, obj1)
# Get the projection of obj2 over the axis
o2proj = CalculateProjection(axis, obj2)
# We're getting rid of the Overlaps function from before, and using the
# Overlap function (we dropped the 's'). Overlap will return a scalar
# value equal to the amount of overlap between the two projections.
# If there is no overlap, then Overlap will return a 0.0
ol = Overlap(o1proj, o2proj)
if ol == 0.0:
# We have no overlap... meaning we have no collision... meaning
# we have NO MTV. We're done.
return None
# Here's where we do some new stuff...
if MTVOverlap is None:
MTVOverlap = ol
MTVAxis = axis
elif ol < MTVOverlap:
MTVOverlap = ol
MTVAxis = axis
# Calculate the axises for the second object and repeat the same as we did above.
o2axises = CalculateAxises(obj2)
for axis in o2axises:
# Assume the CalculateProjection function does the same as Example Code 2.0
# and returns the [min, max] projection.
# Get the projection of obj1 over the axis.
o1proj = CalculateProjection(axis, obj1)
# Get the projection of obj2 over the axis
o2proj = CalculateProjection(axis, obj2)
# We're getting rid of the Overlaps function from before, and using the
# Overlap function (we dropped the 's'). Overlap will return a scalar
# value equal to the amount of overlap between the two projections.
# If there is no overlap, then Overlap will return a 0.0
ol = Overlap(o1proj, o2proj)
if ol == 0.0:
# We have no overlap... meaning we have no collision... meaning
# we have NO MTV. We're done.
return None
# Here's where we do some new stuff...
if MTVOverlap is None:
MTVOverlap = ol
MTVAxis = axis
elif ol < MTVOverlap:
MTVOverlap = ol
MTVAxis = axis
# Ok... we've gotten this far, which means all projections overlap between
# the two objects, so we want to return the MTV. We've already captured
# the MTV, so we return it as a single vector...
return [MTVAxis[0]*MTVOverlap, MTVAxis[1]*MTVOverlap]
And we're done... Yeah.. ummm... for the most part...
MTV Directionality:
This little bit caught me for a while when I was figuring this out. I had done everything right, but, when I tested two objects as certain angles, instead of the MTV moving the objects out of collision, it'd send them further IN! It had occurred to me, after a couple hours of frustration, that... What is the MTV was pointing in the same direction as the colliding object.
First thing I had to realize is that the winding of my object's points were important. Meaning, where they clock-wise or counter-clock-wise. For instance, for Code Example 1.0, the points in the "points" variable are counter-clock-wise. There's probably ways to determine this programatically, but, for simplicity, just say all objects must be drawn in the same winding. In my case, I was drawing in a CCW direction as well, so...
I thought to myself... "self", I said, "during the collision, one object has to be moving and the other not" (simple situation). So, I decided that I would calculate the vector between the two objects...
vector = collideeObj.position - colliderObj.position
...and normalize it...
vector.normalize()
Then I would get a normal vector of my MTV...
MTVNorm = MTV.normalize(returnCopy=True)
... find the dot product between my direction vector and my MTV vector...
dp = vector.dot(MTVNorm)
... and, for CCW winding...
if dp < 0.0:
# This inverts the vector. Same path, different direction
MTV = -MTV
... and finally, reposition the collider by the MTV
collider.position += MTV
And there you have it! OBJECTS COLLIDING PROPERLY!!
Caveats:
Like I said, this works for N-sided objects. I didn't even look at rounded objects because I wasn't focusing on those (I was pressed for time). Also, the objects MUST be CONVEX objects, but that's more a caveat with SAT than my code. Lastly, there's no compensation here for fast moving objects nor complete inclusion (one object totally within another).
If you want to do concave objects, simply create a group of convex objects and treat them as one object, except during collision testing.
Conclusion:
I hope at least someone finds this useful... but, at the very least, I can always look this back up if ever I need to code up SAT objects again. If anyone would like, I could post up a simple example program (in python), but for now, I need to eat dinner.
