next »

[zarovv]

Hi.
I have a blue box that collides with array of red boxes.



The question is how do I push the blue box.
I know that I need to push it first right and then up, but how, if there is a way, I can loop through the red boxes and afterwards know that I need to push first right and then up.

It's not a single direction push, its multiple push so I was wondering if there is a way to solve it.

[raigan]

I'm not sure why this approach isn't better known, but try this:

1) calculate the penetration vector between the blue box and all red boxes it's overlapping; if there's no penetration (or, it's tiny, eg <0.00001), you're done.

2) find the *deepest* penetration (longest vector) from (1), and move the blue box by this vector

3) go to (1); you might want to limit the number of iterations: 4 is usually enough (if your red boxes are all axis-aligned, 2 should be enough), more than 8-16 and your blue box is probably stuck in an impossible situation and you need to take more drastic measures (eg back up to the previous position and step forward by half as much as you did the first time).

This will depenetrate the blue box from an arbitrary set of overlaps *and* give you smooth sliding over tile seams without any precomputation. Hopefully someday I'll write this up so more people will be aware of it.


(This assumes you have some method to calculate the penetration vector between two boxes (ie the vector which, when you move the blue box by this vector, it no longer penetrates the other box); there is tons of code floating around the internet for this, sadly all the stuff I can find is convoluted, over-complicated crap! I'd recommend trying to understand "the separating axis theorem", but anyway you're looking for Oriented Bounding Box (the blue one) vs Axis Aligned Bounding Box (the red ones), in 2D. I can recommend Christer Ericson's "Real-Time Collision Detection". Otherwise I might have time to sketch an OBB-vs-AABB query tomorrow, but googling "2D obb vs aabb" will hopefully get you somewhere. (Note that you can use obb-vs-obb and just set one of the obbs to align with the world axes, in a pinch.))

actually, this thread is okay, hopefully it will give you the gist of the SAT: https://gamedev.stackexchange.com/questions/25397/obb-vs-obb-collision-detection

[zarovv]

Thanks for the reply)

Though, I am not sure about deepest or max penetration. Lets call it max push distance.

If for example we have only the left boxes, max push for the bottom box can be in up direction and thats incorrect because we dont want to push the box up if we have only left boxes.

[raigan]

It's a bit confusing, but you want the "maximum of the minimums", ie for each pair of boxes, you want to find the *shortest* way to push them out of each other, but then once you have that "shortest way" for every pair, you want to select the single *longest* one and then actually push out using that, then repeat the process iteratively.

So for your example of the two left boxes, the top box will want to push out to the right by a long amount, and the bottom box will want to push up by a short amount. So you'll pick the top box first (because it's longer than the bottom push), then push the blue one out by that amount, then re-test everything and find no remaining overlaps.

It might sound ad-hoc but "push out of the deepest penetration iteratively" is actually a pretty good way to find the global solution (blue box vs union-of-all-red-boxes) using only local solutions (blue box vs individual red boxes). It's not perfect but it's as perfect as you can get without doing a true global search.

The other thing is, this problem gets easier and easier the closer to the surface you get -- IME it's almost always better to just run your updates at a faster rate (smaller step size) rather than getting fancy with complex collision handling. This way you're making the problem a lot easier to solve, which means you can solve it using simpler methods. So if you're running your sim at 60hz and getting some glitches from deep penetration, try running it at 120hz. For most 2D games on modern PCs, you can use incredibly tiny steps and have plenty of CPU left over. IIRC one of Bennett Foddy's games uses a 500hz tick!

A good rule of thumb is that nothing should move more than half its radius per tick; this way things will never get too deep into penetration.

[zarovv]

Ok.

So in this case:



We have up box min penetration is right.
down box min penetration is up.

maxmium of all is up. so it pushes up no?

[raigan]

I think you're getting confused because you don't have the "box vs box" separating axis code working.
While it's true you can shift the blue box up to make it stop overlapping the bottom red box, the SAT won't find that result because it considers the projection of each shape along the axes, and in that case the shapes will still overlap along the up-down axis. (Sorry, this is hard to explain in words!)

For Blue vs Bottom-Red, the "minimum translation vector" would be to push the blue box up+right (ie push out of the bottom-left edge of the blue box), ie the axis would be one of the Blue box's two rotated axis, not one of the two axis-aligned Red box axes.

If you only accept axis-aligned movement, pushing right will be the "minimum translation vector".

Here's a pic that shows what the SAT code would consider the Blue box to look like if you're only interested in axis-aligned movement: https://imgur.com/9il7LKt

You can see that pushing to the right is shorter than pushing up or down, so right would be the Minimum Translation Vector for blue vs either box.

(sorry, embedding isn't working for me, I'm a noob)

[raigan]

here are examples of how the full SAT (not limited to only axis-aligned movement) would choose to push the Blue box -- it would use one of Blue's axes in both cases:

top red box: https://imgur.com/QvIIzDC

bottom red box: https://imgur.com/CTdASI1

[raigan]

Also, to be honest I've only ever used this approach for circles, capsules, and axis-aligned rectangles -- ie as part of a character controller for a character that's supposed to smoothly slide along tiles, where the character's shape can't rotate. It does seem like this approach could result in "snags" at the seams between tiles, if you're using a rotated box -- it will still be depenetrated, but it might not be depenetrated to the closest point on the surface.

If you want to find the correct global solution, the "brute-force" approach is to consider the combinatorial explosion of all possible projections. So if your Blue box is overlapping Red boxes A, B, and C, then you need to consider the following cases:

-push out of A, then push out of B, then push out of C
-push out of A, then push out of C, then push out of B
-push out of B, then push out of A, then push out of C
-etc (6 cases total)

you can try all the cases, remember all of them which end with the Blue box not overlapping anything, and then choose the one where the Blue box's final position is closest to its starting position. This should find the correct global solution, however it scales very poorly (eg imagine if there are 5 overlapping red boxes). In your case, if you only ever want axis-aligned pushes, then there should be a way to simplify things (since the pushes will never "fight", they're all orthogonal to each other), but I don't know since I've never done that. Computers are so fast these days that this might be a viable approach.

The heuristic I suggested of pushing out of the deepest first is a way to short-cut this process, however I only know that it works with circles, axis-aligned boxes, and capsules. In your case, it might work better if you changed the ordering heuristic so that instead of "deepest first", you find the red box **closest to the center point of the blue box**, and push out of that first.

Another approach for finding a global solution using only local information (pairs of boxes in isolation) is to use "Jacobi relaxation", where you calculate the push vectors for each box in isolation, then average them (add them together then scale the result by 1/N, where N is the number of push vectors) and iterate until there's no overlap. This will also converge, however it converges more slowly than push-deepest-first, and definitely doesn't behave as smoothly around seams.

[raigan]

Another strategy to consider is: don't allow penetration to occur. This makes your life a lot easier, and is probably the way to go if this is for an action game.

I don't know the context of your problem; if it's for a physics simulation, you'll probably have to deal with penetration, but if this is for a 2D arcade-style game, you should be able to avoid ever allowing things to overlap.

For example, one popular approach (seen in eg Celeste) is to step your shape in 1-pixel increments until it touches something, then stop it. This way you're guaranteed to never be in an overlapping state.

(Celeste steps the movement vector (x,y) one pixel at a time, first in X (until all x movement is done), and then in Y -- or maybe vice versa, I forget! This is a common approximation (AFAIK Super Mario did this too). You can also step it in both simultaneously by using this algorithm to determine, at each pixel, whether you want the next step to be in X or Y: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.42.3443&rep=rep1&type=pdf )

[zarovv]

thanks for the replies)

unfortunately i need to deal with penetration so it wont be so easy.

also that sat maybe a bit problematic for me. like if i move the box it will push at the direction the box moved no? so its like the box can get stuck?

if i wanted to push the box only in aligned axises. like X,Y of the red boxes only, there was a way to do that?

for example, if i know all the intersect points of corners, and edges intersect with edges.
There can be a way that with that information i can push only in aligned axises?

[raigan]

If you only want axis-aligned movement, then the easiest thing is to consider the Blue box to be axis-aligned (like in the first pic I showed, which is what the SAT code would do).

SAT is pretty much the best solution for 2D collision, I'm not aware of a better approach. Given two overlapping polygons, it will find the Minimum Translation Vector, which is guaranteed to be perpendicular to one of the faces of one of the polygons -- ie you'll push the objects out of each other, along one of their surface normals. In your case there are 4 possible axes it will pick: the two world x,y axes of the red boxes, or the two local (rotated) x,y axes of the blue box.

If what you want is axis-aligned movement (to resolve the collision) while still treating the Blue box like a rotated rectangle, this is also possible, however it becomes a trickier raycasting problem. Specifically, you can form the Minkowski sum of "Red Box + Blue Box", then cast axis-aligned rays out from the origin to find the closest intersection on the surface of the Minkowski sum. The shortest intersection is the vector you want to use to push things out of penetration.

This presentation will give you an idea of what Minkowski sums are all about: basically, you shrink your Blue box down to a point, and inflate/sweep the Red box "by" the Blue box. This results in a problem that's geometrically identical to your initial problem, but a lot easier to solve (because one of the objects is a point). https://www.slideshare.net/crowdscontrol/minkowski-sum-on-2d-geometry

Note that this only solves the local problem (a pair of boxes) at a time, you'll still need to combine it with some sort of global iteration similar to what I've outlined in previous posts.

IMO it would be better to use SAT, it's as simple as you can get, but even better would be to avoid penetration or keep it shallow enough that you can just brute-force things. I'm curious why you need to deal with penetration, it should be something you can design around.

Or, if you only want axis-aligned movement, the Celeste approach is definitely the easiest solution. If you have the position of the Blue box at the start of the frame (ie before it overlaps anything) and its final overlapping position, you can simply test every point between the start and end of the movement to find the result you want "from the outside" a-la Celeste. I'd suggest that as the simplest solution since you don't need a complex geometry query like SAT (which returns a vector), you just need a boolean "are these two boxes overlapping, yes/no?" query. It will be at most a few dozen of such tests, very simple for today's computers to chew through.

Resolving penetration between a convex shape and a union of convex shapes (for example, a set of tiles) is, AFAIK, an open problem that there exists no "perfect" solution to, so don't feel bad if this isn't as easy to solve as you thought it would be. I definitely think that stepping pixel-by-pixel is the easiest approach to give a solid, robust feel, and it's been used in countless games so you know it works. Otherwise, SAT and a more geometric approach is also another tried and tested solution (however it will result in an iterative approximation which may not be quite as smooth).)

[zarovv]

Thanks a lot) I am looking at GJK solution maybe it will help.

What i am trying to do is actually in 3d, so no pixel handling solution are relevant.
The images are to simplify.

I need to deal with penetration because i am moving the red cube through an array of blue cubes and i need the movement to be fluent.

I also need to handle impulse, which i already solved, but doesnt need to handle physics, i dont care about gravity.

I think I once looked at SAT but something didnt work out. But GJK from videos I saw maybe be a good solution I hope so I am looking at it.

Thanks)

[zarovv]

well thats a bummer it seems that those solutions dont work...

the problem with sat or GJK is that they are good for checking collision for multiple objects but those objects need to be seperated.

in my case, the box array is one unit and even though i go through each box to check collision i cant for left red boxes push right and for the other red box push up just because its min penetration because its incorrect. i need for left red boxes only push right.


If i try sat of gjk with min penetration i get push up as i suspected when i hit the corner of the red boxes, and thats incorrect.

it seems weird that there isnt a solution for this anywhere that i looked.

the only solution i kinda thought about is based on the local position of the blue box in the array and the red boxes around it i can know how to push it but its a bit problematic..

[SamSerious]

I would cut the blue box by all red boxes and fit a plane along the cut area (just approximate).
The normal of that plane would be the direction I'd push the blue box.

There are many ways to approximate the plane e.g.
1. store the plane of every cut contact point, in the end, average these.
2. calculate the centroid of all remaining contact points and use that and the center of the blue boxs to calculate a plane
3. run 10 iterations: take 3 random conact points,  calculate a plane, calculate the delata of min/max distances of all contact points and keep the plane with the smallest delta.

Cutting might sound complex, but if you cut with one plane/side of the box at a time, dividing into an "inside" and "outside" part, keeping only the "outside", it's manageable.

[zarovv]

A plane? I am not sure how it work, or do you mean axis aligned plane along the red boxes array?

My idea after thinking is checking the local center position along the red boxes array of the blue box.
Based on this local position and array i can know that red boxes that are down i need to push the blue box up, and those the are left i need to push right.

This can work maybe if the the center of the blue box in the array has no red box in it.
If it does I can check previous center position of the blue box, which in assumption suppose to be empty and check line collision with a red box from the previous center to the current center. This will find me first empty center in the red boxes array that i can check collision based on that method.



hopefully it works. Currently i dont see major issues with that

[Action Tad]

Well if ultimately what you want to happen is that the blue box ends up in line with the others,
then you don't really have to push it, you can get the location that it should end up in, when a collision happens,
based on which section in the array is empty, and then either just set the x and y of the blue box to that location,
or tween the blue box to that known collision result location. I hope that makes sense.

[qMopey]

it seems weird that there isnt a solution for this anywhere that i looked.

Did you look here? https://github.com/RandyGaul/cute_headers/blob/master/cute_c2.h

I wrote that code and am quite sure something in there will be good enough for your game, or at the very least for you to learn from

To be clear, just because you are using boxes does not mean this problem is simple. It is not simple. Calculating the overlap and separating rotated boxes is a very complicated problem. The only way this problem can be simple is if all boxes are strictly limited to axis-alignments.

[raigan]

it seems weird that there isnt a solution for this anywhere that i looked.

Did you look here? https://github.com/RandyGaul/cute_headers/blob/master/cute_c2.h

It's not obvious from the question but sadly this is all in 3D. :/

Also, AFAICT the OP doesn't want to use minimum-translation-vector -- they don't want to consider blue's axes as separating, they only want to slide the blue box along a world axis to end penetration -- so SAT-type tests aren't a great fit.

I believe this means that a raycast approach is needed (ie to determine how much to slide the blue box in order to end penetration with a red box, you form the minkowski sum of blue+red then cast rays outward from the origin along cardinal directons to find the closest intersection).

[zarovv]

well, after failing with my idea of local position (the solution has flaws) i came across this thread:
https://gamedev.stackexchange.com/questions/69339/2d-aabbs-and-resolving-multiple-collisions

the solution they give to him is rather very simple and may just work.
first you move in x direction, push in x and then you move y direction (and in my case also z direction).

i am still thinking about it and thinking if there is an issue but right now it seems legit.

[Raptor85]

depending on how complicated your game will be an easy way is to do triangle/box intersections against the new tick's position and if there's a collision roll back to the previous frame and test smaller steps, I've done this for a few ludum dare games, it's super quick to program and gives pretty solid feeling collision in platformers, it's also really easy to implement slopes.