Stick-Physics

Discuss programming in the QuakeC language.
Urre
Posts: 1109
Joined: Fri Nov 05, 2004 2:36 am
Location: Moon
Contact:

Stick-Physics

Post by Urre »

Sometime in 2005, I caught a discussion involving LordHavoc among others, about something known as "stick-physics". They discussed an article by Thomas Jakobsen, which covered his work on the physics engine in the original Hitman game. It described the process of creating rigid body objects using particles and virtual "sticks" controlling the distance between two particles. Usually I let tech-heavy discussions pass by, but this one caught my attention because what was described, sounded to me like it should theoretically work in QuakeC. Jumping into the discussion, presenting this preposterous idea, I was surprised to find the response was "why not", which got me hooked bad. After a good ol' while of embarrassment and general misunderstanding of the concept on my part, LordHavoc decided it was more sane to simply code it himself than to explain the concepts of movement to someone who doesn't understand what a frame or gametick is, let alone walk him through the process of making a full-blown physics engine. Once LordHavoc's implementation of the physics was mostly done, I adopted it and began work on my multiplayer FPS featuring vehicles. What I discovered during development, was that the system to align the visible model to the physics-particles had a flaw. While doing what it was supposed to, it was a pain to create objects with more than three particles to align properly to the particles. The model was most often aligned in a strange manner, making me think there should be some way to offset this rotation to match the particles properly. After a while of experimentation with this on my own, I realised I was going to need matrices controlling the orientation of the model, for this particular rotation offset feature. Soon I discovered code which I believed would be of use for me, once again written by LordHavoc. It was an implementation of Rodriguez vector (aka Axis-Angle), an interesting take on rotation around a directional vector. As the code contained object alignment using matrices, I combined that with my stick-physics code, and used Rodriguez vector to calculate the offset rotation. While the matrices worked, the latter, more important part, didn't work at all. Fighting frustration over the whole rotation offset deal for well over a year, I attempted to implement all kinds of arcane ways to extract functionality out of the Rodriguez vector code it clearly wasn't meant to be used for. Once I admitted my defeat and came to LordHavoc for help, he slapped me silly for attempting what I did, and agreed to help out. He stripped out all of the Rodriguez vector code, and replaced the parts that used it with simple matrix transforms. It seemed like the QC physics-lib might actually see the light of day very soon. I gleefully posted a youtube video featuring some tossing of crates, promising more soon. This turned out to be a premature assessment. Fate played such a trick on us, that all of the five test cases I had constructed for LordHavoc to test against, worked by mere coincidence. Once I began making new objects, the code began to fail. Somehow the offset rotation code still wasn't working, even though the combined efforts of both LordHavoc and me had made very sure that it indeed was correct. Baffled by this recent development, we decided to put the project on ice until any one of us had time to continue the debugging. Fast-forward a few months, and you'll find both me and LordHavoc generally too busy with either life, or other projects, which admittedly are related to life (tm). You don't make money from something as obscure as a QC physics-lib, so it's rather low priority right now. I recently realised that it's very unlikely that any one of us would get more time as the months or even years go by, so instead of letting the code rot away on my harddrive, I figured it might as well do more good to be released, hopefully triggering some form of community effort. Just think about how cool it'd be with a QC physics-engine capable of (mostly) rigid bodies, and even vehicles with some further development.

This is how it's supposed to work:

Imagine a stick. Toss the stick, and it'll bounce around happily until laying down flat to the ground. Now imagine three sticks, stuck together forming a triangle. This acts very much the same way, but resembles something with more of a shape than a line. Imagine sticking together enough sticks that they form a cube, with a stick between each and every corner of the cube, making it feel really sturdy, so it won't bend under its own weight if dropped to the ground. This obviously makes for a good deal of many sticks. Each and every side of a cube uses 4 sticks to get the square shape of the edges, and 2 sticks for a cross in the middle for extra stability. The connecting edges between sides can obviously share sticks. On top of this, there are 4 sticks in the middle of the cube, connecting the corners together. This makes 28 sticks for a cube. All this is required to make the cube feel rigid. This is the basic idea of a stick-physics-engine.

Now, to get slightly more detailed, the sticks are actually imaginary. The physics-engine is actually particle based, only using the "sticks" for information about how much space there should be between a given 2 particles. Every frame, after applying gravity, collision and bounce reaction on all the particles, the physics engine accesses the list of sticks for the current object, and moves the particles the stick points to either further away or closer together, depending on their current relation to eachother. Because sticks can share particles, it will end up resembling a rigid object as all the particles in an object will constantly struggle to stay away/close to eachother at the same time. Weird, I know, but it works.

The following will be very hard for me to explain, but I'll do my best!

Now when we have 8 particles forming the corners of a cube, and 28 imaginary sticks keeping the particles in check, we need to make it actually look like a cube! So we attach a model to it, by making it align with the particles, so it rotates correctly as the particles move around in the world. How to actually do this, is the tricky part. LordHavocs original idea, which as far as I know still exists in dpmod, was to align it to the first three particles of the object. First particle used as a base of origin, pointing to the second particle for direction, third particle for roll. This idea works very well, but it overlooks something essential. It either requires very simple physics-objects, or that the models are positioned and aligned with the physics engine in mind, something which is impossible to predict when you're the artist making the model. This is why I began work on the whole offset-rotation deal, which was actually supposed to be my smaller contribution to the lib, more like a necessity for future features. The idea was to create a common point of origin and rotation, which is required to attach objects to objects, to direct thrusters, calculate directional force, and all kinds of useful things which have to do with vehicles. Seeing as that part of the code isn't working, one can't even really create simple non-vehicle objects as it's not possible to even consistently attach a model to the particles.

Now, if we imagine that this offset thingy works, and we have a cube object with particles, sticks and a nice comprehensible orientation, I can explain another of my contributions which is quite a deal cooler. Another problem with the whole system was that objects couldn't collide with eachother. For this problem, I figured it should be perfectly possible to use pusher-entities, or in other words, BSP models using MOVETYPE_PUSH. They'd align themselves with the particles much in the same manner as the visible cube model as described earlier, except instead of simply setting the origin and angles each frame, the information is converted into euler directional and rotational velocity values, which means that we get the benefit MOVETYPE_PUSH provides, which simply put is, moving other non-BSP entities out of the way. At the same time, a particle of an object can collide with the BSP model of another object, and simply bouncing off, so it works both ways. On top of this, I added the ability to transfer force between objects, by simply dividing the force applied on the BSP model of an object between all of its particles, based on distance to impact, thus making it react realisticly. This also had a wonderful side-effect; when the BSP model of an object pushes a particle of another object, the imaginary sticks of that object will attempt to push the particle back to its previous position, which results in the particle not being able to travel very far, meaning that other particles requiring to move instead, causing movement on the whole object as if it was pushed, as well as the other object getting some of the initial force back upon itself, making it act as if it bounced off the object it hit, while none of its particles actually touched the opposing object. If that doesn't make sense, then never mind, it's just cool, and it works. It makes you able to push crates, among other things.

So where does the system break, you ask? As you might have noticed, I've talked a lot about the offset-rotation part breaking. But how does it break? Well, in one way, I might say I have no idea. The idea is simple enough (for anyone who's matrix-proficient, and that doesn't include the ability to fly or punch very fast). All the system needs is two matrix transforms, and it should work! The way it's designed, is as follows: In order to ease the process of creating these physics objects, I made an ingame editor for this specific task. As mentioned before, a model which aligns itself with the first three particles will in most cases look very odd, so it needs to be rotated to face forward, and this rotation needs to be saved for future reference, in order to rotate it in the same manner no matter the relationship between the particles of the object, so that it can appear upside down, or slightly to the side, however the game world might place it, and as we all know, physics objects in action games tend to spin in all kinds of crazy ways. Then on top of this, the user might want to rotate the model himself for whatever reason, so that rotation needs to be saved as well, which assuming the previous rotation works, shouldn't be a big deal. Once it works, it works in both cases, one should assume. This whole deal, for some reason, does not work. The model spins in mysterious ways ingame, while the particles are acting as one would expect them to. This is where I need help. It doesn't very much make sense why the transforms aren't working. LordHavoc apparently tried many approaches, to get the right combination for all the test cases that existed.

The current state, available here (thanks shubhub!), features the ability to toss large crates when pressing E, and pushing them, as well as sort of "shooting" them with mouse1. I was hoping to atleast get time to make a gravity-gun like thing before making this release for laughs, but I figured there's not much point. It's not a hard thing to do though, really.

Note that there are many *other* bugs as well, but the fact that the transforms aren't working makes the whole project moot, so I haven't put very much weight in figuring those out. They also seem like significantly smaller tasks, looking at how complicated the transform problem turned out to be.

Enjoy, and please do help if you can.

NOTE: the lib is released with only the working crate enabled for presentations sake, you'll have to go into data/backup/ and move the files from there to data/ in order to see how it breaks, especially b_batt0.ubj
Last edited by Urre on Mon Oct 20, 2008 1:43 pm, edited 2 times in total.
I was once a Quake modder
Wazat
Posts: 771
Joined: Fri Oct 15, 2004 9:50 pm
Location: Middle 'o the desert, USA

Post by Wazat »

Sounds very cool. I'm afraid I cannot help much, but I'd love to see this working at some point.

The gravity gun could be fun to build, though. :D
When my computer inevitably explodes and kills me, my cat inherits everything I own. He may be the only one capable of continuing my work.
vicious1988
Posts: 16
Joined: Sun Oct 12, 2008 10:14 pm

Post by vicious1988 »

I did something like this a few years back in Irrlicht. Not as advanced though.
Urre
Posts: 1109
Joined: Fri Nov 05, 2004 2:36 am
Location: Moon
Contact:

Post by Urre »

Is the interest low because of the massive amount of text, or what? I mean, did anyone even check it out, although they might not believe they'd be of much help? Although I did this myself, I find it rather inspiring to toss the crates around, thinking how close it is to actually working. Imagine, a physics engine for your DarkPlaces based mods/games!
I was once a Quake modder
CocoT
Posts: 695
Joined: Tue Dec 14, 2004 5:39 pm
Location: Belly-Gum
Contact:

Post by CocoT »

Sorry if I didn't post earlier... I personally find it great! I mean, I saw a while ago the video you posted on youtube and was stunned! It's even more impressive to see it work on my own computer, and particularly to see how little it all affects frame rate. Now, that said, I'm afraid my coding skills are way inferior to what you would need in someone to be able to help you out :(
I'm wondering who would be best qualified (and interested in Quake1) to help you out. Maybe we can start by thinking about those people, alert them about the project, bring them here and see if and see how they could help.
We could also get Pappy-R involved and ask him if he could post a request on PQ (I think the idea of helping to create a physics engine for Quake1 could appeal to a lot of coders)
Neurotic Conversions - New location: Update your bookmarks!
Urre
Posts: 1109
Joined: Fri Nov 05, 2004 2:36 am
Location: Moon
Contact:

Post by Urre »

That does sound like a cool idea, even though I believe it'd need to be someone from the community, as I see most programmers would see it as a step back, sort of, or more like just not making very much sense. This because it's made in QC, and not a physics-engine for Quake in the sensible kind of way, which is doing it engine-side. Half the point was showing the strengths of this soon 13 years old, crude and simple, language. Seeing how far the project has gone, one could say I've already shown it, and thus continuing the project is moot, as it will never measure up to an engine-side physics-engine. The other reason why I did it, was because, well, I like using DarkPlaces for my gamedev needs, and I wanted a physics engine, and I only knew QC. As simple as that. It'd be cool to see what people would say, though. Who knows, I might be wrong!
I was once a Quake modder
MauveBib
Posts: 634
Joined: Thu Nov 04, 2004 1:22 am

Post by MauveBib »

I had a play around with an earlier version of this while doing ragdoll experients, but I couldn't solve the main issues with the code.

I also couldn't get joint limts working, so i stopped.

plus, 90ish entities for a single corpse was probably a little too many.
Apathy Now!
-z-
Posts: 19
Joined: Wed Mar 05, 2008 5:58 pm
Contact:

Post by -z- »

I too recall seeing this video on youtube a while back. Much to my dismay you had replied, "But it's sadly discontinued at the moment due to unforeseen bugs. I announced it too early." Which made me sad at the time because as you've described above, I too found it inspiring.

Coming across the news post on the front page, this dropped my jaw. It was very exciting to hear I could learn more about this project I assumed dead. Though heavy on the paragraphs, I reasoned through your article relatively painlessly. You do a very good job describing these concepts which, being only in a Physics I class, blow my mind a bit.

I hope you find someone to help because this really is amazing. A gravity gun would make this all the more fun. Your matrix comment gave me a chuckle.

Thanks for the read.
Nexuiz Ninjaz - Practicing the ninja arts of Nexuiz | Happy 1 Year Ninjaz! - Mapping Contest to celebrate!
Urre
Posts: 1109
Joined: Fri Nov 05, 2004 2:36 am
Location: Moon
Contact:

Post by Urre »

-z-: Your post warmed my heart very much :)

As did everyone elses, and the fact that there was a news post on both I3D frontpage and PlanetQuake! Seems your idea came to life CocoT :)

Mauve: I have many ideas for joint limits, but I can admit they're tough. The best idea I've had so far, is limiting by the use of planes which are attached to particles. I can see it working! Also, 90 entities is nothing for DP ;)

Thanks for the shown interest and support!
I was once a Quake modder
-z-
Posts: 19
Joined: Wed Mar 05, 2008 5:58 pm
Contact:

Post by -z- »

I3D and PlanetQuake aren't the only sites your article has been frontpaged on, I've shared the news with the ninjaz :). Beyond being awesome that you were able to get as far as you did, learning as much as you did, involving the different people that you did; you took the time to write about it.

People like yourself are building the future of these games, inspiring your colleagues and attracting new ones. Your tales help build an environment, a story, a deeper meaning to things we may otherwise take for granted.

Keep up the great work \m/ (-.-) \m/
Nexuiz Ninjaz - Practicing the ninja arts of Nexuiz | Happy 1 Year Ninjaz! - Mapping Contest to celebrate!
Electro
Posts: 312
Joined: Wed Dec 29, 2004 11:25 pm
Location: Brisbane, Australia
Contact:

Post by Electro »

-z-: yeah, and you should see what he can do with his clothes ON :o
Benjamin Darling
http://www.bendarling.net/

Reflex - In development competitive arena fps combining modern tech with the speed, precision and freedom of 90's shooters.
http://www.reflexfps.net/
Urre
Posts: 1109
Joined: Fri Nov 05, 2004 2:36 am
Location: Moon
Contact:

Post by Urre »

-z-: awesome to hear :)

Electro! How are things? PM me some time, I can rarely chat nowadays, should be able to in november.
I was once a Quake modder
Electro
Posts: 312
Joined: Wed Dec 29, 2004 11:25 pm
Location: Brisbane, Australia
Contact:

Post by Electro »

Urre: anything not work related is going awesome. Job hunt isn't going as good as I'd hoped, tough time finding work in this damn country at a place that doesn't totally suck.

Considering throwing in the towel with art, could very well be a dead end for me (in this country anyway, and where-ever I would want to live doesn't seem to be hiring atm). Going to revamp my portfolio one last time and see where that leads.

anyway.. yeah hurry up November ffs!
Benjamin Darling
http://www.bendarling.net/

Reflex - In development competitive arena fps combining modern tech with the speed, precision and freedom of 90's shooters.
http://www.reflexfps.net/
ceriux
Posts: 2230
Joined: Sat Sep 06, 2008 3:30 pm
Location: Indiana, USA

Post by ceriux »

yep finding a job sucks... iv applied at everyplace with in like.... 5 miles (considering i dont have a vehical) and still havnt gotten a job.
goldenboy
Posts: 924
Joined: Fri Sep 05, 2008 11:04 pm
Location: Kiel
Contact:

Post by goldenboy »

5 miles? Can I live where you live, please?
Post Reply