4
\$\begingroup\$

First, some context

I'm currently implementing a (well, tiny) game engine using a predictive approach. The idea is to compute when a state change will occur, and only update state at time of the first state change, which can help save computing power. The problem is I have to implement predictive physics. And I'm fine for simple stuff (collision detection, basic collision responses, motions of isolated bodies) but I'm facing a big problem when it comes to more complicated interactions, especially constraint-like behavior.

I also made, few time ago, this post on physics.stackexchange

Problem restrictions

In my case, I restricted physics a lot in order to keep predictive collision detection simple:

  • Bodies have no rotation allowed, only translations.

  • Bodies have no animation allowed, they will not change shape over time.

  • Bodies are rigid, so they don't have any deformation.

  • Body can only be "roughly" shaped, they will never feature curves, only faces (even tho they can have lots of faces)

Problem: computing accelerations of several bodies constrained together

In order to achieve efficient a priori collision detection, I need to work with both speed and acceleration.

I have a collection of bodies, all in "possible" contact by pairs (their relative speed two by two is 0 on at least one direction).

Each of these bodies have a "initial" net force assigned, coming from interactions from bodies outside the collection for example.

I would like to allow theses bodies to have several relations between them, expressing how they should behave to each other. Relations may be:

  • constraints over acceleration for one body (example: no acceleration, or no acceleration along a certain direction)

  • constraints over relative acceleration for a pair of bodies, as non penetration constraints or stickiness.

  • forces opposing to relative movement of a pair of bodies, as friction

Finally, my goal to compute for each of these bodies the "final" net force satisfying constraints.

Example

The player (square on the pic) is pushing several boxes, with a triangular shape. Those boxes will "push" each other away, while still dragging along a bit their neighbors.

Problem 1 example, box pushing

What I've tried and what I'm looking for

For now I try to focus only on non-penetration constraints

First, I've tried to find an iterative approach, based on a graph representing interactions between objects, propagating base net forces through bodies one after another, and then "giving back" forces when a new force arrives on a body, but it quickly gets too complicated to picture, and I expected algorithmic complexity to be way too high anyways...

The problem feels like there is an equation system to solve somewhere.

Then, given this post, I tried to adapt it to my problem, but I don't know how to model non-penetration constraint, since I didn't found a way to express it other than one looking like an inequation between acceleration of a pair of object: \$ a1 - a2 >= 0 \$.

Therefore, I would appreciate a lot to get some help with either:

  • My entire problem obviously

  • Only non-penetration constraints

  • Advises on understanding how to model "constraints" to balance other forces

  • Any other ideas (I feel so lost)

  • Advises to improve formulation of this post

EDIT : Found a solution based on linear programming, I will take some time to check it's robustness and then will add it as an answer to the post.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ I would posit that there may be a good reason that no game physics engine in common use works the way you're describing. Iterative stepping, penetration, and resolution may be somewhat sloppy, but the approximations allow us to handle very complicated systems of interacting constraints without an explosion of algorithmic complexity. Keep in mind that Newtonian dynamics are Turing Complete, so exactly solving an arbitrary set of interacting physics constraints may be computationally equivalent to solving the Halting Problem. \$\endgroup\$
    – DMGregory ♦
    Commented Jul 18, 2019 at 16:12
  • \$\begingroup\$ @DMGregory True, that's why I've already removed rotations from the physics, otherwise movement equations would become way too complicated, and I didn't wanted to call a solver for collision detection x). I can eventually restrain constraints to a tiny set if needed. Thank's for pointing the possible insolvability of the problem ^^ Intuitively I thought that my problem would not be harder than solving a regular constraint system, but maybe I was wrong x) \$\endgroup\$
    – Felix Bertoni
    Commented Jul 18, 2019 at 18:32
  • \$\begingroup\$ If your solution checks out, please be sure to post it as an Answer, rather than as an edit to the Question. (Sorry if that was already obvious — we get a lot of questions sitting "unanswered" in our system because the solution was edited-in instead) \$\endgroup\$
    – DMGregory ♦
    Commented Jul 22, 2019 at 12:42
  • \$\begingroup\$ @DMGregory yes, don't worry, It will just take some time to check the solution :'( \$\endgroup\$
    – Felix Bertoni
    Commented Jul 23, 2019 at 13:23

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .