Howdy-doody-doodle-doo?
Collision detection and collision reactions are something game developers are constantly having to find ways to do. I'm going to explain the basic calculations needed to write efficient point-to-line collision reactions for all y'all who either don't know that much about physics, just want to brush up on some kinetics, or are just too lazy to do the calculations yourself.

THE BASICS OF COLLISIONS

Point-to-line? What's that mean?
When I say "point-to-line" (or "point-line") I am referring to a collision in which a specified point on an object collides with a solid line.

The point:
When I say "a specified point on an object" I am referring to ANY point (P) whose coordinates lie within the boundaries of your object. Obviously calculating collision with every single point in your object would be completely absurd, so collision objects are usually made up of a few keypoints to which the collision detection is applied. Those points are usually vertices and a few points that lie within longer lines. The calculations that I talk about in this explanation would be applied to these keypoints.

When a rotational force is applied to an object, the object will want to rotate around its center of mass. Every object has a center of mass. The simplest calculation for the center of mass is to assume the mass of every point in your object is the same, then you just take the average of the x-coordinates of all the points, and the average of the y-coordinates of all the points. That gives you your center of mass (x_c, y_c).

The line:
The line has a much shorter explanation: It's a line segment. It has endpoints, a slope, a y intercept, and angle, etc. All you really need is the endpoints and you can find the rest.


Detecting a collision
This is just a quick and dirty explanation of how you would go about determining if there was a collision between a line and a point on an object. Sorry for the lack of actual calculations. This is more about theory.

In order for a collision to take place at all, the point must be moving in some way. In order for it to move, it needs to have some sort of a vector representing velocity. Because your points are rigidly attached to this object's center of mass, the velocity of the object's center of mass can be used to represent the velocity of the point. (This doesn't take into account any velocity created by the object's rotation, but that calculation is a bit much for a lot of what we're doing, so we we'll just ignore that for now. Unless you're looking for a really, really accurate physics engine, this shouldn't have a tremendous effect on your end result.)

Using this velocity, we can calculate the trajectory (again ignoring rotation around the center of mass) of the point (P) between this frame and the next frame. The trajectory will just be a line between the current location of the point (x₁, y₁) and the location of the point (x₂, y₂). From there we can calculate the equation of the line segment between those two points and check if that line segment intersects with the line segment we're testing for collision.

Line to line intersection is fairly simple:
y=m₁x+b₁
y=m₂x+b₂
Then you solve the parametric equation for x and y to find the collision.

You can also find the intersection point of two lines (not line segments) by finding the determinants of a series of matrices (which I won't really explain the specifics of at this time) and you can simplify it to a single equation as shown in pseudocode here:
function intersect(x1,y1,x2,y2,x3,y3,x4,y4){
x = ((x1*y2-y1*x2)*(x3-x4)-(x1-x2)*(x3*y4-y3*x4))/((x1-x2)*(y3-y4)-(y1-y2)*(x3-x4))
y = ((x1*y2-y1*x2)*(y3-y4)-(y1-y2)*(x3*y4-y3*x4))/((x1-x2)*(y3-y4)-(y1-y2)*(x3-x4))
return Point(x,y)
}
If one of the lines is vertical, then you can simply find the x of that line and solve the equation of the other line for y at that x coordinate.

Note that those will find the intersection point of two LINES, not line-SEGMENTS. In order to correct this, you just need to check whether the point of intersection is between the start and end points of both line segments. If so, a collision occurred between the current frame and the next frame.

NOTE: When doing the collision detection calculations, it is best to calculate the collisions of all keypoints on your object, and figure out which collision happened first. Then calculate the reaction based on that collision. Otherwise it can get messy if you object is moving at a high speed and multiple reactions are being calculated at once, when they really wouldn't have happened if you had calculated in order of time. Calculating the time of the collision is simple enough:
//where (x1,y1) and (x2,y2) are the start and end points (respectively) of the point's trajectory
//and (x,y) is the point of collision
time = sqrt((x-x1)^2-(y-y1)^2)/sqrt((x2-x1)^2-(y2-y1)^2)Assuming we already know that (x,y) lies on the line defined by (x1,y1)(x2,y2), this equation will return a value between 0 and 1. 0 means the objects are colliding on the current frame (which should have been handled during the last calculation) and 1 means they will collide exactly on the next frame. Anything in between means the collision occurred somewhere between the two frames.

For anyone programming in a language such as Axe or ASM that doesn't directly use decimals, think of the time value as a percent rather than 0 to 1. So instead of 1 you use a large integer value for 100%, and 0 for 0%.



COLLISION REACTIONS

Finally the good stuff. And by good, I mean there's a lot to cover.

A basic explanation of vector dynamics for collision objects:
"Vector dynamics" is pretty much a fancy way of saying "how objects move." A vector, for those who don't know, has two properties: a magnitude, and a direction. For example, velocity is a vector: its magnitude is the speed the object is traveling at, and its direction is...well, the direction the object is traveling.

Let's talk a bit about the properties of a moving object. There are many properties that we could talk about, but there are a few that we actually care about for these purposes:

• Mass (we'll use 1 for almost all calculations just for the sake of simplicity. )
• Position (relative to the center of mass)
• Linear velocity
• Linear acceleration
• Angular velocity
• Angular acceleration
• Moment of inertia (sort of...)

Hopefully you already know what most of those are, but I'll just briefly go over them all, just in case.
-Mass is mass. It's the mass of the object, and it is represented by the mass. All clear? Good! Moving on...
-Position is simply the x and y of the center of mass of the object. As I said earlier, the center of mass can be found by averaging all the x/y points within the bounds of the object....or just average the x and y of your extremes, because we're using a constant particle mass.
-Linear velocity, or just 'velocity', is simply the speed and direction in which the object is currently moving. If it's not moving, it has no velocity. The easiest way to express velocity in programming is by using individual xVel and yVel values.
-Linear acceleration, or just 'acceleration', is the rate at which the linear velocity changes from one frame to another. We'll also express this using individual xAccel and yAccel values.
-Angular velocity, also known as 'rotational velocity', is the speed at which the object is rotating. Like linear velocity, angular velocity is also a vector, it's what's called a "rotary vector." The magnitude is the speed, and the direction is the axis it rotates about. But we'll be using the center of mass as a rotational axis, so we only need to worry about the speed, which we'll call rotVel (for 'rotational velocity').
-Angular acceleration, like regular acceleration, is the rate at which the angular velocity changes from one frame to the next. We'll express this as rotAccel.
-Moment of inertia is probably a new term for you if you haven't taken a physics class. Put simply, Inertia is an object's resistance to a change in motion (Newton's First Law: Every body remains in a state of constant velocity unless acted upon by an external unbalanced force). The Moment if Inertia is its resistance to a change in rotational motion.

When I say "Moment of inertia (sort of...)" I mean that using the exact moment of inertia is not always possible in all situations. The calculation for moment of inertia requires that you integrate over the entire surface of the object the distance to the axis of rotation squared times the mass for each particle. This is not always a simple calculation if you're using irregular shapes. In that case we can cheat and use a more regular shape that is similar. Here's a list of the moments of inertia for many regular shapes: http://en.wikipedia.org/wiki/List_of_moments_of_inertia

For this example, I'll be using a "Thin rectangular plate of height h and of width w and mass m" (as defined in that wikipedia list), so our moment of inertia (usually represented as I) calculation will be (mass*(h*h+w*w))/12. For most calculations we'll use a mass of 1, because that makes things easy, but this answer will almost definitely have to be scaled down quite a bit in order for it to look good in our pseudo-physics environment.


Bodies colliding:
Okay, so now we finally have collision, let's take a look at what's going on.

As we know, change occurs when a force is applied to an object. Physics states that Force=mass*acceleration, but because we're using a mass of 1, we can say that Force=acceleration. Remember that acceleration is also a vector, so it must have magnitude and direction.

An object has a net force F_net acting upon it at any given time. "Net force" is as simple as the sum of all individual forces acting upon the object. From this point onward, please just understand that due to our mass being 1, any time we talk about a "force" being applied, it means an "acceleration" of equal magnitude is applied.

Gravity is a force that is acting on anything with mass at all times. So you can always assume your object has the force of gravity being applied straight down. Also, we know that "for every action there is an equal and opposite reaction." So, if an object is sitting on flat ground, the object has the force of gravity pulling it down against the ground, and the ground pushes back with an equal force in the opposite direction. For any surface of any angle, this force will be applied in a direction perpendicular to the angle of the ground. This perpendicular force is called the Normal Force (represented by F_Norm).

Let's look at some simple physics: a box is placed on an inclined plane at angle θ.



Gravity is pulling downward (as usual) with a force of F_g. The magnitude of the normal force can be calculated by F_Norm=mass*F_g*cos(θ). But that only accounts for cos(θ) of the force of gravity, so the object would still be accelerating straight down by F_gsin(θ), meaning it would fall through the surface of the plane! That's because when F_Norm is applied, the rest of the force of gravity is diverted to go PARALLEL to the surface of the plane. The magnitude of that parallel force can be calculated by F_||=F_g*sin(θ).

Okay, so now the box is sliding down the inclined plane at a velocity increasing by F_|| every frame. At least, it WOULD if the plane was made out of some sort of friction-less material. But since lack of friction can be assumed physically impossible, let's make this more realistic and add some in. The force of friction (F_fric) is applied in the OPPOSITE direction of F_||, with a magnitude found by F_fric=F_Norm*µ. Piece of cake, right? But wait...what's that "µ" symbol doing there? The Greek letter µ ("mu", pronounced "mew") represents the coefficient of friction. Oh, dear! What does THAT mean? µ is the ratio of the force of friction between two bodies, and the force pushing the two bodies together. µ changes based on what materials the two bodies are made of. In this case, F_Norm is the force pushing the two bodies together.

Wow, all this stuff with µ is getting really complex. Isn't there an easier way? Yep! Let's forget all about that µ stuff and assume that our materials will never change, so we can just make up a value to represent our µ. Just for the sake of examples, let's say our µ is 0.15. Based on that, we can say that F_fric=F_Norm*0.15 and it is applied in the opposite direction as F_||. If it's the exact opposite direction, why not just subtract F_fric from F_||? Our new equation for the parallel force with friction applied will be F_||=F_g*sin(θ)-F_Norm*-0.15.

Just to make sure we're on the same page now...
   F_Norm=F_g*cos(θ)[
    F_||=F_g*sin(θ)-F_Norm*0.15[/sub] (remember that 0.15 is just the example value for µ. Play around with it until you find something you like.)


Okay, so now we know the normal force and the parallel force applied to an object on a plane that at the angle θ_p. Let's look at what those forces mean for us.

Let's say a box is now dropped at an angle of 0 degrees from some height onto an inclined plane at angle θ_p. The corner of the box will hit the plane first, so that's where the collision is processed. F_Norm is now applied to the box at the point of collision P_c. This will cause the box to rotate, but we need to know how much it will rotate. Let's take a look:

First we look at the angle θ_a between P_c and the box's center of mass P_m. Now we look at F_Norm and find the angle that it is applied at (θ_N). The difference between these two angles (θ_c) is what we'll be looking at. Using this angle we can calculate both the linear and angular acceleration on the object.
accel=F_Norm*cos(θ_c)
But remember we're representing acceleration with xAccel and yAccel, so we have to use convert it to x and y.
xAccel=xAccel+accel*cos(θ_a)
yAccel=yAccel+accel*sin(θ_a)
The reason we use θ_a is that the force is applied to the center of mass, not just this specific point.
But now that only accounts for cos(θ_c of the force. The other sin(θ_c) turns into angular acceleration.
rotAccel=rotAccel+F_Norm*sin(θ_c)

Now we've dealt with what happens with F_Norm, but what about F_||? That force is still applied, but now we have to do the same calculations to it as we did to the normal.
First we take the difference between θ_a and θ_|| (we'll call it θ_d). Now we apply F_|| to the linear and angular accelerations the same way.
accel_||=F_||*cos(θ_d)
xAccel=xAccel+accel_d*cos(θ_a)
yAccel=yAccel+accel_d*sin(θ_a)
rotAccel=rotAccel+F_||*sin(θ_d)


So let's look at what we have now:
   accel=F_Norm*sin(θ_c)
    xAccel=xAccel+accel*cos(θ_a)+accel_d*cos(θ_a)
    yAccel=yAccel+accel*sin(θ_a)+accel_d*sin(θ_a)
    rotAccel=rotAccel+F_Norm*sin(θ_c)+F_||*sin(θ_d)


I know this is still incomplete, but I thought I'd update it to at least this much and I'll update again once the full explanation is done. After that I will add graphics for explanations (which will help a lot, I'm sure) and then I'll put together an example of implementation of all of this for the final version. Thanks for your patience!

Hey everyone! I'm Zippy. Or Taw. Either one.

I love words.
Words are awesome.
Anathema. Putrid. Spackle. Dank. Elbow. Gaggle. Pundit. Vivacious.....

You may look at words like that and just say "Okay...those are words. Cool story." But I look at words and see things like this:
STARTLING
STARTING
STARING
STRING
STING
SING
SIN
IN
I
Remove one letter each time and it is STILL a real word. Isn't that awesome?

Or how about this:
Therein, Therein, Therein, Therein, Therein, Therein, Therein, Therein, Therein, Therein, Therein.
All those words can be seen without rearranging any letters.
SO AWESOME.
Even just thinking about every-day words is awesome. Words like "banana" and "floss."

But enough about words, I've barely introduced myself!

I'm Zippy/Taw (as you already know), I'm a nerd (As you probably guessed), and I'm perfectly fine with that fact.
I like people. I like to talk. And I love talking to people...
I have ADHD and Tourette's Syndrome, along with a few other minor things, but hey, we all have our issues, right?
I like math. I hate math classes. I love to learn. I hate the educational system.
I love thinking. Specifically problem solving.

My love for learning inspires me to try all sorts of things, leading to the smorgasbord of activities and ideas that I refer to as my interests.

Programming, problem solving, psychology, building things, playing music, composing music, singing, acting, dancing, drawing, painting, marching band, colorguard, writing, stilt-walking, juggling, spinning poi, gymnastics, aerial acrobatics, teaching things to people, laughing, dreaming, meeting new people, just generally being around people, telling jokes (usually bad puns or obnoxiously witty remarks), correcting spelling/grammar, and obviously a lot more things.

I'm 18, I graduated high school a year ago, but I'm taking a year off before college. I am currently dancing 13 hours a week doing Jazz, Lyrical, Ballet, Ballroom, Hip-Hop, Breaking, and Popping/Locking. This year I'm dancing competitively in Jazz, Ballroom, Hip-Hop, and Popping/Locking.

I'm a self-taught programmer with plans to take actual CS courses in college. I started with VB4 when I was 7 (looking back at that always makes me laugh), then I learned Flash ActionScript 2.0, then 3.0, then TI-BASIC, then a liiiiiiiiiiiiiiiiiiiiittle bit of z80 ASM, then Java, then 4 days ago I started poking around with Axe, and now I'm here.

I play a lot of instruments. I won't list them all right now, but if you really want I can tell you.

I teach at a circus camp in the summer, hence the stilt-walking, juggling, poi, gymnastics, and aerial acrobatics in my list of interests.

I'm one of those people who starts a bunch of projects but is conveniently too ambitious to finish any of them before starting more and completely forgetting about the old ones. I wish that wasn't the case, but oh well.

That's basically me. If you have any questions about me or even about anything really, I'll be happy to answer them, at least to the best of my knowledge.
Glad to be on the forums

My apologies for writing so much,
-Zippy Dee

<-----noob here.

Can someone explain to me what an Axiom is?

Thanks!
-Zippy Dee

AXE/ASM noob here!

What's the ideal way to store large amounts of data (i.e. map data, sprites, large strings) for your programs? I'd expect that you'd just keep the data in your program, but is there a better way to do it?
Also, could I get some guidance on when to use temp ram areas/external variables rather than portions of program memory for data storage?

Any other data optimization tips would be greatly appreciated!

Thanks!
-Zippy Dee