[HN Gopher] 2D Rigid Body Collision Resolution
___________________________________________________________________
2D Rigid Body Collision Resolution
Author : atan2
Score : 414 points
Date : 2024-05-24 07:23 UTC (15 hours ago)
(HTM) web link (www.sassnow.ski)
(TXT) w3m dump (www.sassnow.ski)
| ecaradec wrote:
| If you want to go further and go for rigid body dynamics and
| constraint, I found that series of blog post very useful:
| https://www.toptal.com/game/video-game-physics-part-i-an-int...
| buzzcut_ wrote:
| Thanks for sharing!
| ksassnowski wrote:
| 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 wrote:
| It's a really good explanantion !
|
| Pardon my curiosity, but what tools did you use to build that
| page ?
| ksassnowski wrote:
| 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 wrote:
| 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!
| nox101 wrote:
| Thank you! looking forward to the rest
| aa-jv wrote:
| 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 wrote:
| 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 wrote:
| 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.
| kibbi wrote:
| 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
| lern_too_spel wrote:
| Feedback: You should explain or link to why the two
| formulations of the dot product are equivalent.
| unshavedyak wrote:
| 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!
| pmarreck wrote:
| I love anything having to do with matrices. This is great!
| gustavopezzi wrote:
| 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.
| rrr_oh_man wrote:
| I wish we had had this type of explanation in algebra on what to
| do with dot products.
| samlinnfer wrote:
| I always enjoyed the explanation from the N game:
| https://www.metanetsoftware.com/technique/tutorialA.html
|
| Back when flash was everywhere.
| nj5rq wrote:
| 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.
| smusamashah wrote:
| 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 wrote:
| 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 wrote:
| I'm thinking of changing my surname to Gambettski so I can
| also make cool online demos, so you're probably fine :)
| sph wrote:
| 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 wrote:
| For a brief moment, I thought this would be a Ciechanow blog
| and clicked quickly, only to return here to participate in
| discussions.
| isoprophlex wrote:
| Huh. I always remembered it as being _s_ because of French
| _sentier_ , meaning "path".
|
| Besides that... Beautiful page, well done!
| 33a wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| Neat! do you have a resource that explains this perspective
| further?
| buzzcut_ wrote:
| I second this. I would love to learn more.
| 33a wrote:
| 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_Unders
| tandingConstraints_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 wrote:
| 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.
| alanbernstein wrote:
| 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.
| JoeyJoJoJr wrote:
| Did you come across Verlet Integration [1]? It is quite
| convincing and usable for a lot of use cases, and is actually
| quite simple. I surprised myself when I was able to create a
| basic physics systems in a couple of hours with this great
| tutorial [2].
|
| [1]https://m.youtube.com/watch?v=lS_qeBy3aQI&pp=ygUSVmVybGV0IGl
| ...
|
| [2]https://m.youtube.com/watch?v=3HjO_RGIjCU&pp=ygUSdmVybGV0IGl
| ...
| kibbi wrote:
| 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 wrote:
| 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 wrote:
| 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
| iKlsR wrote:
| This will be a useful reference for later on if not now as
| well. http://www.jeffreythompson.org/collision-
| detection/table_of_..., it covers collision between points,
| circles, rectangles, lines, polygons, and triangles.
| willvarfar wrote:
| 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.
| NKosmatos wrote:
| Young high school and university students aspiring to become game
| designers should give some focus on their algebra, trigonometry
| and geometry :-)
| CooCooCaCha wrote:
| 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 wrote:
| That makes no sense. Kinematic rigid bodies are still...rigid
| bodies, and most games use dynamic and static rigid bodies not
| just kinematic ones.
| swayvil wrote:
| 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
| aDyslecticCrow wrote:
| 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 wrote:
| Yes! "Part 3: Collision Response" is basically what I'm using
| as a reference for these articles.
| filleduchaos wrote:
| 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.
| mort96 wrote:
| 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?
| maccard wrote:
| 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 wrote:
| 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.)
| TheRealPomax wrote:
| 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.
| mydriasis wrote:
| 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.
| mike31fr wrote:
| I had fun building a TypeScript demo about this topic, involving
| balls that can bounce and collide. I learned a lot.
|
| Code: https://github.com/vandrieu/canvas-bouncing-ball (the
| collision logic is in src/collision.ts)
|
| Result/Demo: https://vandrieu.github.io/canvas-bouncing-ball/
| redbell wrote:
| 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
| kurrrrrak wrote:
| There is very simple reason for this: "ski" it the most common
| suffix of Polish surnames, of which the most popular is
| Kowalski. There are a lot of people out there either Polish or
| with Polish origins.
|
| Author of https://ciechanow.ski - the site we all love here -
| is Polish programmer working for Apple.
| iKlsR wrote:
| On the same note there are some names that no matter the
| domain you know you're going to get a wizard, anyone named
| Thiago is a beast and I've chanced on several.
| redbell wrote:
| Well explained, +1. Didn't knew Ciechanowski is working for
| Apple. Such a genius!
| liuxiaopai wrote:
| awesome article glad to read
| danbmil99 wrote:
| Guess this is a Shameless plug but I wrote an interesting program
| over 12 years ago using even then very old three Js which is not
| quite the metal but much less abstract than today's tools. I'm
| always amazed when I check it and it's still running
|
| http://busyboxes.org
| Terr_ wrote:
| To dredge up a related oldie-but-goodie memory of blog posts:
|
| https://gafferongames.com/categories/game-physics/
| pkaler wrote:
| This is great. This reminds me of Chris Hecker's Rigid Body
| Dynamics series from GDMag/Gamasutra that I read (checks watch)
| almost 30 years ago! This is the classic/canonical set of
| articles.
|
| https://chrishecker.com/Rigid_Body_Dynamics
___________________________________________________________________
(page generated 2024-05-24 23:00 UTC)