return to table of content

2D Rigid Body Collision Resolution

ksassnowski
10 replies
10h47m

Hey everyone, author here!

To give some context, this is only part one in a series of blog posts I plan on writing about rigid body physics.

The post is aimed at people like myself, who aren't game devs and don't necessarily have a strong math background. Which is why I spend so much time explaining concepts that would appear almost trivial to someone who has experience in this area.

Happy to answer any questions you might have.

wiz21c
1 replies
10h32m

It's a really good explanantion !

Pardon my curiosity, but what tools did you use to build that page ?

ksassnowski
0 replies
10h24m

Thanks!

Most of the physics-based example are written in WebGL using three.js. Using three.js is a little bit overkill for this because all the examples are in 2D but it's what I was familiar with. For the actual physics simulations, I'm using matter.js.

The diagrams use a library I wrote while working on the post [1].

Everything runs inside a Vue app which serves as the glue between things like the sliders and the three.js scenes and diagrams.

[1] https://ksassnowski.github.io/vueclid-docs/

wingerlang
0 replies
10h8m

Very nice. The section "A word about math" really is important. I am admittedly not good at math, but I was able to build a VERY (extremely, even) rudimentary physics simulation many years ago by really really simplifying the math concepts. I was essentially iterating on the building blocks, points, lines, etc. With a lot of small steps and a lot of visual debugging lines, it ended up extremely janky and slow, but it did kinda work!

unshavedyak
0 replies
30m

Sounds intriguing! I’m probably your ideal audience, given a large coding background, low math background, and current writing 2D focused games.

If I may ask a question, in your mind what’s the benefit of more deeply understanding these implementations when physics frameworks handle a lot of the really mathy logic behind collisions and simulations.

Either way I’m putting this in my read queue. Thanks!

nox101
0 replies
9h46m

Thank you! looking forward to the rest

lern_too_spel
0 replies
3h43m

Feedback: You should explain or link to why the two formulations of the dot product are equivalent.

kibbi
0 replies
3h49m

Feedback: Your introduction "From Mario bouncing off a Goomba..." might be a bit misleading IMO because most games like the classic Super Mario titles on NES and SNES do not require and did not use most of these calculations.

Game development beginners often have the wrong impression that they need rigid body collision calculations or a 2D physics engine like Box2D to handle collisions. That's true if you want to make a game like Pool or something with collapsing stacks of crates like Angry Birds.

But for a 2D platformer you only need to detect collisions by comparing (axis-aligned) rectangles and to handle collisions by changing the moving character's X and Y coordinates (to undo an overlap) or setting the character's Y velocity (after using the jump button, or after landing on a Goomba's head).

This also makes it easier for the developer to finetune exactly how moving the character should feel like. (This includes inertia, but this inertia is usually not physically realistic.) Trying to use realistic physics as a gamedev beginner can easily lead to floaty and unsatisfying movement.

An example tutorial to start with this simple physics-free approach: https://www.love2d.org/wiki/Tutorial:Baseline_2D_Platformer

aa-jv
0 replies
8h23m

I'm curious whether you've considered using Box2D[1] as a reference, since it is a pretty complete implementation of rigid body physics? Or is it more that you want to re-implement things from scratch as part of this tutorial?

[1] - https://box2d.org/documentation/

Coolbeanstoo
0 replies
6h46m

I really enjoyed the article :) Made it very understandable for me a person who struggled with some similar things in school.

Would really appreciate the inclusion of an RSS feed so I can continue to follow along!

CaptainOfCoit
0 replies
5h42m

Great article and very fun to read, as someone who also doesn't have a strong math background, so thank you for explaining these "trivial" concepts :)

Are you planning to read/explain through XPBD (Extended Position Based Dynamics - http://mmacklin.com/xpbd.pdf) as well in future posts? The concept seems to be gaining traction and I've used it with Bevy (via https://github.com/Jondolf/bevy_xpbd) with big success so far, seems more stable than the usual approach.

33a
7 replies
7h59m

Collisions are violations of the pairwise non-intersection constraint between bodies. Collision forces are Lagrange multipliers of these constraints. Collision normals are the (normalized) partial derivatives of the constraint function wrt one of the body's configurations.

mort96
3 replies
7h52m

That sounds like the kind of thing which works if you're doing physics at 1kHz+ with an integration algorithm with good numeric stability which honours conservation of energy, but in games, we're often running physics at down to 30Hz using some ad-hoc Euler-Chromer, which requires very different approaches

33a
2 replies
7h35m

It's still the same principle even in games. If you are trying to explain where forces come from and how resolution works, you need to ground it in something. Otherwise you are just adding extra assumptions onto assumptions.

mort96
1 replies
5h9m

In proper physics simulations, everything's about forces, most things are springs, and you never teleport stuff. In games, modelling the ground as a spring really doesn't work and teleporting entities when they collide with parts of the world often makes a lot of sense. It's just not the same.

EDIT: If I'm incorrect, please explain how. I've written some game physics systems and seen some proper physics sim systems and these comments reflect my understanding of the situation, and if I've said something wrong, please correct me instead of just downvoting.

33a
0 replies
3h35m

The principle of least constraint is the basis for rigid body mechanics based contact forces. This has been known since the days of Gauss and Hamilton, and is fundamentally how restitution and collision forces are derived in Lagrangian mechanics. There's a long literature on this going back more than a hundred years.

It's true that some commercial solvers like Ansys use spring/penalty methods, but this is due to the spring forces being easier to couple to other solvers. It's harder in the Ansys force/velocity formulation to combine things like elasticity and fluids to their rigid body solver. To deal with the instability of systems of many stiff springs they have to take many small timesteps to avoid convergence issues.

More recently techniques like XPBD have been gaining popularity, particularly in film, which use purely positional constraints and variational methods to combine many different types of physics simulations. There's a really great and approachable series of videos by Matthias Muller on youtube which goes through how to implement all this in JS https://matthias-research.github.io/pages/

Finally it's funny you should mention games, since many older games used spring methods for physics. It was only when constraint based solvers became popular after Havok/Half-Life 2 did we start to see games with real rigid body dynamics and stable stacking of boxes. Older physics games like Trespasser ( https://en.wikipedia.org/wiki/Trespasser_(video_game) ) had many bugs due to the use of hacky spring physics. For a good explanation of how games do it today look at Erin Catto's work on Box2D https://box2d.org/publications/

bollu
2 replies
6h56m

Neat! do you have a resource that explains this perspective further?

buzzcut_
0 replies
6h48m

I second this. I would love to learn more.

33a
0 replies
3h34m

Posted a reply here https://news.ycombinator.com/item?id=40466855

This is a specific reference on how constraints model contact between rigid bodies https://box2d.org/files/ErinCatto_UnderstandingConstraints_G...

Most games since Half Life 2 use constraint forces like this to solve collisions. Springs/penalty forces are still used sometimes in commercial physics solvers since they're easier to couple with other simulations, but they require many small timesteps to ensure convergence.

onetimeuse92304
5 replies
7h54m

One side project I am working on right now is a 2d space shooter I am developing with my son. The idea is to have top down look, have each player control some kind of ship and fly in an enclosed area filled with space debris and shot opponents. An important aspect of this game is that the space debris can be moved around the arena and used creatively to capture opponents, prevent them from achieving their goals, etc.

As part of the project I was thinking we will skip game engine altogether because I wanted to teach my son a bit more about how to structure the application, etc. I thought in future we would use a ready game engine but at least once we would go through the exercise of implementing everything.

Everything was fine until we approached the problem of collision detection and handling. That's when things went downhill pretty quickly. Even with my theoretical math background I was soon consumed with just enormous amount of corner cases and finally decided to relent and use Box2d for this.

I am not a professional game developer, but I have over 20 years of development experience + math background and I still made the mistake of underestimating the problem. It really seems easy problem when you state it and just becomes exponentially more and more complex as you start digging into details.

kibbi
2 replies
3h42m

Did your game require realistic physics collisions? If not, this might be unnecessary complexity. Almost no 2D shoot'em up game before 2000, and very few afterwards, go this route. Here's the common method to make a shmup with very simple rectangle comparisons:

https://kidscancode.org/blog/2016/08/pygame_shmup_part_3/

But if your space debris objects are supposed to collide and agglomerate realistically, and if the player ships are supposed to have difficulty pushing a cluster of heavy objects out of the way, then using a physics library is sensible.

onetimeuse92304
0 replies
1h27m

It does requires realistic collisions.

The point is you fly in a small spaceship in an arena, you hide behind obstacles, you shoot with a small variety of weapons and you use your weapons to either shoot the enemy directly or rearrange the map to make life difficult for your them. The collisions need to be realistic because you need to be able to predict what is going to happen when you hit things a certain way.

It is just a concept we are playing with.

Another part of that concept is that this game is meant for small kids that can't read. There is not a single letter or digit in the entire game. No menu. You just start the controller and get immediately pulled into the game.

And another feature is we wanted the game fun because the control feel fun and immediate. So we are experimenting a lot with what it means for the controls to be enjoyable.

lukan
0 replies
22m

I think it is waaaaay easier and likely more performant to just use a subset of Box2D or (rapier), than implementing simple physic yourself.

They are quite optimized and performant libaries already and there are tons of tutorials for box2d out there (thanks to iforce).

You just add some shapes of your liking and call world.step

alanbernstein
0 replies
6h12m

That still seems like a good lesson for your son; it's not always worth following the pure build-it-yourself dream for every part of a project.

smusamashah
4 replies
9h2m

The way this article is written with small simulations throughout the page and word highlights was reminding me of https://ciechanow.ski/ and then I noticed the domain name. It is very similar too https://www.sassnow.ski/

Couldn't be happier seeing more people going to same depths (or heights) to explain things to people. Will be looking forward to more articles like this as this just the very first one.

ksassnowski
1 replies
8h53m

Bartosz was definitely my biggest inspiration when writing this post. I was debating if I should actually use that domain because it might come across as a little too derivative but I couldn't resist!

ggambetta
0 replies
7h21m

I'm thinking of changing my surname to Gambettski so I can also make cool online demos, so you're probably fine :)

sph
0 replies
8h15m

With a sample size of 2, I declare that the .ski domain is dedicated to very high-quality interactive education websites. I am now conditioned to click on any .ski domain that I come across on HN.

BOOSTERHIDROGEN
0 replies
6h11m

For a brief moment, I thought this would be a Ciechanow blog and clicked quickly, only to return here to participate in discussions.

filleduchaos
3 replies
5h10m

I know this post is focused on collision resolution, but I was still a little disappointed to see collision detection handwaved away. In my experience that's where the real headscratchers are.

maccard
1 replies
2h48m

Completely disagree - convex collision detection is a neatly solved problem. SAT [0] is implementable in a couple of hours, and GJK [1] is a really neat algorithm that takes a ltitle more than SAT to implement. For optimising collision detection there's some spatial partitioning [2] algorithms that work really well.

The gnarly stuff comes in when you're trying to figure out contact points and impulse responses and apply them without blowing everything up. I've written some of this stuff for a few games now, and the resources below have stood the test of time IMO

[0] https://dyn4j.org/2010/01/sat/ [1] https://realtimecollisiondetection.net/pubs/SIGGRAPH04_Erics... [2] https://allenchou.net/2013/12/game-physics-broadphase/

filleduchaos
0 replies
4m

Well yeah, people often assume that because they know how to tell if two shapes are currently intersecting, they've solved collision detection...and then their games turn out to have a bunch of detection-related bugs and glitches. Most notoriously, lots of homebrewed physics libraries suffer badly from tunnelling (i.e. when one or both bodies are moving so fast that they completely pass through another before the next time collision is naively checked, and so the checker fails to detect a collision at all).

And on top of that there is more to collision detection than just code IMO - setting up hitboxes that both feel right for the player and aren't visually glitchy is not as straightforward as it might seem, especially with 3D.

(Also, figuring out contact points is part of competently implemented collision detection.)

mort96
0 replies
4h53m

I mean there's a lot of material out there already about collision detection though. This feels a bit like seeing a blog post about register allocation and being sad that it doesn't talk about parsing?

buzzcut_
0 replies
6h47m

Thanks for sharing!

aDyslecticCrow
1 replies
5h51m

Making a 2d rigid-body physics engine is a really fun project. I made one myself in javascript before learning about linear algebra. And I dug deep into the maths to get it working. Despite months of work, I barely scratched the surface beyond the widely known basics.

Making a stable engine where objects don't compress into one another or jitter is a rabbit hole without a bottom that even the most math-heavy articles I could find rarely touched.

I used a series of old articles by Christ Hecker to understand the maths myself. http://www.chrishecker.com/Rigid_Body_Dynamics

ksassnowski
0 replies
5h43m

Yes! "Part 3: Collision Response" is basically what I'm using as a reference for these articles.

CooCooCaCha
1 replies
6h11m

You probably don’t want rigid body collisions in most game mechanics. Player controllers, npc logic, etc. are hand crafted most of the time.

filleduchaos
0 replies
5h13m

That makes no sense. Kinematic rigid bodies are still...rigid bodies, and most games use dynamic and static rigid bodies not just kinematic ones.

willvarfar
0 replies
7h39m

My own attempts at 3d games failed to get good sweeping polygon polygon collision to work. IIRC I found one good demo video of a programmer demonstrating it on youtube but no code or articles or anything.

swayvil
0 replies
6h7m

If you constrain your geometry to a tesselation, it gets much more precise, simple and fast.

Like those old atari games where everything was little square tiles / pixels.

But little squares aren't the most expressive geometry.

How about kisrhombille?

https://en.m.wikipedia.org/wiki/Kisrhombille

rrr_oh_man
0 replies
9h39m

I wish we had had this type of explanation in algebra on what to do with dot products.

redbell
0 replies
2h53m

Oh! Look, a well-researched, deeply-explained, and interactive post.

Honestly, when I initially read the domain name and noticed the TLD is ".ski" I was thinking it is from the author who wrote about Mecanical Watch [1] and other cool stuff.. it turned out to be a totally different one but of similar quality. What's the secret sauce behind this ".ski" TLD :)

___________________

1. https://news.ycombinator.com/item?id=31261533

nj5rq
0 replies
9h16m

Wow, perfect timing. Some days ago I started to get interested in this, particularly in circle collisions. Keep it up, looking forward for the rest of the posts.

mydriasis
0 replies
3h52m

To learn JS I started with canvas, and without any game dev experience, made a couple of cute little browser games. One is a galaga clone that, for the most part, works OK. The hard part is the projectile collisions. Instead of taking the position of your bullet now, and where it would be in the next time step, and seeing if it would intersect with the enemy hitboxes taken in the same way, I _only_ checked on the current timestep, which means your bullets can magically go around the enemies! Silly stuff. Maybe some day I'll go back and fix it.

liuxiaopai
0 replies
2h44m

awesome article glad to read

isoprophlex
0 replies
8h17m

Huh. I always remembered it as being s because of French sentier, meaning "path".

Besides that... Beautiful page, well done!

gustavopezzi
0 replies
10h27m

This is really cool! Love the explanations, the interactions, and especially the friendly tone of voice of the article. Looking forward to the ones following.

TheRealPomax
0 replies
4h23m

I do wish this kept going and went "and as a last step, we need to add in torque" because pretty much everyone stops at regular force vectors, but torque transfer is so ridiculously important.

NKosmatos
0 replies
6h51m

Young high school and university students aspiring to become game designers should give some focus on their algebra, trigonometry and geometry :-)