3 ms·
Some annotations of my own, all coming from memory and experience. The theoretical basis for most collision algorithms is the separating axis theorem(SAT). It
by chipsy 12y ago
Some annotations of my own, all coming from memory and experience.
The theoretical basis for most collision algorithms is the separating axis theorem(SAT). It simply states that for any two convex shapes there exists an axis partitioning them - and as a consequence, deriving this axis(the algorithm of which will depend on what kinds of shapes you're working with) gives you the collision boundary of the shapes.
What SAT does not do is specify how to resolve shapes that start in an overlapping position, how to resolve turning more than one axis of movement into a _single_ axis of separation, and how to resolve overlaps of more than one shape. Those things are all where a lot of collision code goes astray. Some solutions to these problems include:
Maintain either a "lookahead" of where shapes will be in the future based on their physics parameters, or a "timeline" of previous shape positions; then the collision resolution can incorporate this information to determine direction of travel prior to the moment of collision(and thus accurately approximate pushout, bounce, etc.)
Perform collision resolution in a buffered fashion: before changing position state, create "plans" for movable objects. Test the plans in multiple passes to ensure that they satisfy all the potentially colliding shapes.
Step along the axes of movement in independent collision steps; e.g. first you test to go up, then you test to go up and right, finally you move. Stacking each axis on top of the previous in a fixed order ensures that at no point is the colliding object "squashing" one of the tests when another passes(which causes typical stuck-in-walls glitches). It causes a distortion to appear when travel is diagonal, but its impact depends on the speed of movement and whether "cutting corners" matters.
Alternately, one may test each ordering and choose a "best" one heuristically so that diagonal movement is consistent in all cases.