Collision Detection

[Ingulit]

I hear you guys have a physics engine that supports collision detection of polygons. I'm trying to make a (currently 2D, soon to be 3D) physics engine myself, and I have everything working except for the collision detection. I've searched for many a tutorial on teh intarwebs, but the tubes are clogged with a massive amount of jargon and advanced concepts. Therefore, I was wondering if I could hear how you guys go about realistic (read: by physics laws) collision detection so that I may have insight on a real-life example that was executed by my peers. I'm about halfway through AP Physics right now, and I read my textbook in my spare time (I honestly love physics that much). I'm also a very talented (to toot my own horn) C and C++ programmer, and I am using the latter along with the Allegro Game Library for my engine. I'm going to be entering this engine in a competition very soon, so any help would be greatly appreciated.

[Ingulit]

I should mention I'm not asking for hand-holding, but rather a point in the right direction. If I could get a *brief* description of how you handled this, and perhaps a link to a more detailed, recommended tutorial, that'd be sufficient for me. I'm also hoping to use this thread as a question board if I encounter trouble with this, in the hopes you guys might have an answer (duh).

[Falco Girgis]

I'm not using anything "realistic" for collision detection. At the moment it's just a simple bound box colliding against another. It also assumes every collision is elastic.

The system treats every collision like a particle, rather than a larger object. It is much cleaner and more predictable this way. It works much better in a 2D game than a more advanced system.

I'm just not exactly sure how you wanted to check for collision. If you wanted per pixel accuracy, you wouldn't want to use our simple bound box method.

[MarauderIIC]

It's a shame my hd failed. It sounds like you might be looking for a per-pixel collision detection. One way to do such iirc is to reserve certain colors for sprites that you want to test collision on; for instance, I had a terrain destruction demo; shot a purple bullet and the bullet did not collide with white since that was the player's color so the demo wouldn't shoot itself. :P

With a point object it's relatively simple, I "blew up" a map from a 32x32 grid to a 640x480 grid, stored which grid squares had collision (true or false) in a 2d array and modified such values and the associated colors (transparent or no) when the terrain was shot.

With a 'real' object, such as a player, I would recommend bounding-boxes, they are effective and work perfectly fine. If you want finer tuned collision, use more bounding boxes. You could use infinitely many (per-pixel collision) but the more per-pixel collision tests you do the more processing power you use.

As to collision reactions, F=ma. Assign a scale to your game, assign a mass to each object, multiply to see how much force would be applied to your object. Then you can solve for acceleration on your 2nd object, since every action has an equal and opposite reaction.
F.1=m.1*a.1
F.1 =m.2*a.2
F.1/m.2 = a.2

Also, sorry, I've only screwed around with 2d detection. For 3d detection, instead of bounding boxes, use bounding spheres or bounding cubes. nehe.gamedev.net, if it's still around, had such a tutorial iirc.

[Falco Girgis]

Starting today, I'm rewriting our physics system to bind circles. I also have many other ambitious ideas that I can only hope to pull off this weekend. I'll show you guys when I'm done.

[Ingulit]

Oh, my goodness, no. I knew full well how to use bounding boxes, circles, and per-pixel already, but none of them are suitable for realistic real-time physics simulation. I'm looking for full-blown convex (and soon to be concave) collision interaction, for none of the other methods suited my purpose when implemented. When I heard you had a physics engine, I'd assumed you were using something more... advanced. Sorry, but I'm honestly (apparently) well ahead of you guys; my current engine far surpasses simple F=ma and elastic collision. My bad :X

[Tvspelsfreak]

I don't have anything to add about 2D collisions. But if you do jump to 3D take a look at some existing solutions. ODE is a full-blown physics engine in its own right, and afaik it's good for both 2D and 3D. As far as collision goes look at stuff like opcode, ozcollide, newton, etc...

[Falco Girgis]

If he's entering that into a competition, that might be illegal to use outright. I recommend having a look at that stuff to learn the math and theory behind it, because you'll probably have to write your own code.

edit: Do you have any sort of rotational system implemented? Are you calculating moment of inertia and center of mass for complicated shapes then using a pixel perfect collision system? I'm just curious as to what you're doing that's so "advanced" (but more interested in why it's worth the additional trouble). For most every 2D application bounding a circle or something would be fine, but I guess if you're going 3D...

Chill out also, saying that you're way ahead of us isn't fair judgement. Our systems don't need that kind of precision for the kinds of games we're making.

edit2: thanks for the Youtube subscription.

edit3: You live in Alabama? Do you got to Bob Jones? Have we met? I just think it's weird that we live in the same state.

[Ingulit]

If he's entering that into a competition, that might be illegal to use outright. I recommend having a look at that stuff to learn the math and theory behind it, because you'll probably have to write your own code.

edit: Do you have any sort of rotational system implemented? Are you calculating moment of inertia and center of mass for complicated shapes then using a pixel perfect collision system? I'm just curious as to what you're doing. For most every 2D application bounding a circle or something would be fine, but I guess if you're going 3D...

Yeah, I've got rotation. I'm not actually writing a game, but rather a physics engine; I'm more of a "I make your game work" kind of guy. Currently, I've got a hierarchy like the following (though I've recently discovered it'll work upteen times faster if I completely redo it, so this has already changed considerably):

Coordinate
Sprite public Coordinate
Object public Coordinate
Facing public Object
Particle public Object, Sprite
Character/Weapons/Everything else public Facing, Sprite

I should mention I also have a (mathematical) Vector class that isn't part of the above hierarchy, and that this is a top-down physics engine (IE, gravity is perpendicular to the screen).

The Coordinate is what it sounds like; it's an x and y point. Currently you can only apply a vector to it, but I'm concepting more functions I've yet to implement.

The Sprite is a sprite handler that contains all the functions to draw objects to the screen and the functions for pixel-perfect collision (with underlying bounding boxes for speed).

The Object is a Coordinate point with mass, a velocity vector, and two friction constant values (kinetic and dynamic). Friction is handled in this engine in a very basic way: to determine the friction between the world and an object, the engine multiplies the object's appropriate constant with a friction constant defined by what the object is "standing" on. My engine relies on the Impulse-Momentum theorem to bypass acceleration entirely and to allow me to change an object's velocity directly using forces and time intervals; this sped up the engine considerably from when I had both Velocity and Acceleration vectors for each Object.

A Particle is an Object you can create and draw on the screen (Coordinates, Objects, and Facings are all abstract). They follow the laws of particle dynamics.

The Facing class is the one I'm currently revising the most, so practically all of this will change very soon. A Facing is essentially an Object with a direction, rotational velocity, and moment of inertia. Currently, my engine assumes all Facings to be spheres (again, I'm revising Facing the most), and therefore calculate the Moment of Inertia by using Facing's fourth (unnecessary) data member, its radius. By again using the Impulse-Momentum theory, my engine allows you to apply a torque on an object by giving it a magnitude and a time interval; my first revision to this class will be to combine the Force application function and the Torque application function into a single Force application function, for all forces will apply torques. The engine also takes into account the rotational friction of spinning objects by treating Facings (in this situation only) as though they were circular disks on the ground.

After these classes, everything else in the game is a combination of a Facing and a Sprite (characters, weapons lying on the ground, etc). This technique worked reasonably well for the most basic needs, but now I'm looking for quite a bit more realism. My primary impediment is collision detection that allows for realistic (read: obeys the laws of physics) collision, for I already have every other change written down (not typed) that assumes the collision works the way it should. The 3D engine will come much, much later; as for now, I'm sticking to 2D. If you'd like me to detail the changes I plan to make, I shall. It'll take me quite a while, however, for I truly, I plan to overhaul the entirety of what I just described (in retrospect, I've conceded it is laughably unrealistic).

Questions/Criticisms/Comments welcome; I hope this explanation was understandable. Remember, I read my Physics textbook in my spare time, so these physics concepts are as easy as breathing for me to comprehend; I may have oversimplified some aspects of the engine unwillingly, for which I apologize. However, I imagine most of you will know how this works.


EDIT 1: By claiming my engine to be "more advanced," I was looking at it from solely a physics standpoint. It's the only aspect of game programming I'm interested in, really (read: I couldn't even imagine coding half the shit your game can do, and I know it).

EDIT 2: I'm in an engineering class with your brother. He led me to this website.

[MarauderIIC]

Currently, my engine assumes all Facings to be spheres

Just throwing stuff out, since physics is not something I'm all that awesome at (but calculus is ok), if you have an equation describing the facing of the polygon, can't you find the slope at the pixel since you can find pixel-perfect collision? (Derivative)?

Or integral of moment of inertia of (an infinite number of infinitely small) (arbitrary objects, rings) over the area of the face/volume? That would get you the moment of inertia for an arbitrary (face/volume), right...? Assuming it's regular? Otherwise you'd have to take multiple integrals... Well, if you have the area or volume it shouldn't matter? Hurm. Of course if you're drawing it in the first place you can't draw a concave object, right? So you can take the integrals of each thing you draw as you draw them, right?

My calculus-based physics is weak since my physics is rather weak =p

[MarauderIIC]

The above post had a few edits in case someone got caught replying during all my edits.

[Arce]

Um. Sounds to me like you're going to want to be using Swept Spheres/Ellipsoids.

Google it; I haven't taken Physics yet and probably couldn't lay out the concepts with the correct terms and whatnot. Its fairly simple (I think) so you should be okay with it.

Edit: Aww ha. I knew I'd seen a nice tut a while back.
http://www.three14.demon.nl/sweptellips ... ipsoid.pdf

Tell me if it helps. Or is that not what you're looking for?

[Ingulit]

Um. Sounds to me like you're going to want to be using Swept Spheres/Ellipsoids.

Google it; I haven't taken Physics yet and probably couldn't lay out the concepts with the correct terms and whatnot. Its fairly simple (I think) so you should be okay with it.

Edit: Aww ha. I knew I'd seen a nice tut a while back.
http://www.three14.demon.nl/sweptellips ... ipsoid.pdf

Tell me if it helps. Or is that not what you're looking for?

Actually, this is the very thing that I've been planning to do with my physics engine during the overhaul; that is to say, I was going to get away from pixel-perfect and move to polygons (and I've already concepted all the functions that go with a polygon being a vector of vertexes), but I was still confused as to how I'd handle collision detection. This seems like a great starting point for my algorithm concepts! I also just did some searching for myself, and I came across the N Game website, which had tutorials on how it handles collision:

http://www.harveycartel.org/metanet/tutorials.html

Now I'm thinking I'll use a combination of a grid algorithm for speed (from above tutorials) and this ellipsoidal algorithm for accuracy. This is the kind of stuff I was hoping for when I signed up; thanks a ton already! :D

[Falco Girgis]

I think it's fascinating that somebody your age is so interested in physics, especially in programming a physics simulator with such precision.

I think you'll win whatever contest you want to enter.

What are you, 17 or 18?

[Ingulit]

What are you, 17 or 18?

Just turned the former, though I've been dabbling in this field since 14. Honors Physics/AP Physics has been a gift from God (or the higher power of your choice) for me. I absolutely adore figuring out how things work, so physics quickly became my favorite field of study! I'm not sure how to explain it, but I get a thrill from being able to reproduce the real world accurately in a computational environment. Of course, this is not the only reason I do this; after I have a suitably realistic simulator, I'll move on to what I really want to do: tweaking minor aspects of the laws of physics and seeing what the results thereof would be, and then creating new gameplay based on the rules I create for myself. You could call my computer my easel; that which I imagine I communicate through ones and zeros, my paintbrush the object-oriented languages of the day. But unlike paintings or books, you can blow up parts of my "art" and receive only positive repercussion!


EDIT: I edited this once. You'll be able to tell if you saw the first (3-sentence) version or not.