Circle collision response

[theagentd]

Okay, I have up to 1 000 circles on a 2D plane (no gravity, it's a top-down view). They can collide with each other and with axis-aligned square walls. All is fine when there are just a few objects colliding, but when too many objects start to pile up it starts to vibrate and eventually random circles are ejected from the center or fly around randomly. To prevent this I added a "smoothness" to collisions, which allows units to be compressed instead of completely pushing away other objects and themselves. This improved things, but too many circles stacked together can be very compressed, which looks like crap, since they start to melt together.

I had an idea of dynamically adapting the smoothness value depending on how many other things a circle is colliding with, but I realized that this would reduce the position correction when more circles are close together, leading to even more compression, and I would end up with the worst of both low smoothness and high smoothness. Clearly I need a different solution.

I've thought of using Box2D and just let it solve all collisions, but the problem is that I have potentially millions of static wall squares, and JBox2D just crashes when I go over 2048 shapes.

My current implementation does this:

1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26   27

for(Circle circle1 : allCircles){     List<Circle> nearbyCircles = getCollidingCircles(circle1, ...);     if(nearbyCircles.isEmpty()){         continue;     }     for(Circle circle2 : nearbyCircles){         double dx = circle1.x - circle2.x;    double dy = circle1.y - circle2.y;         double distance = Math.sqrt(dx*dx + dy*dy);                 double distanceToAdd = circle1.radius + circle2.radius - distance;         double multiplier = distanceToAdd / distance * SMOOTHNESS; //SMOOTHNESS is less than or equal to 1        circle1.deltaX += dx * multiplier;         circle1.deltaY += dy * multiplier;     }     movedCircles.add(circle1); } while(!movedCircles.isEmpty()){     Circle c = movedCircles.remove(movedCircles.size() - 1);     c.x += c.deltaX;     c.x += c.deltaY;     c.deltaX = 0;     c.deltaY = 0; }

THIS CODE IS COMPLETELY REWRITTEN FOR THIS THREAD FOR CLARITY!!! Please do not bash any performance problems or anything, as my actual code is completely different.

As you can see, I only update the position of one of the circles in a collision, but as the collisions will both collide with each other, they will both be pushed away by the same amount. This is not a performance problem either (getting around 300 FPS for 1000s of circles). I just need something with better collision response than what I have now.

[Danny02]

hi,
I took a look at your code and tried to understand what u were doing there.

I would suggest that your start with handling the collisions with propper physics first, take a look at  http://en.wikipedia.org/wiki/Momentum

[Riven]

The age old problem of correctness vs. performance.

You state in your post that it is not a performance problem, which is solely the case because you didn't take correctness into account. Once you do, you'll see it starts to become a performance problem. JBox2D is on the other end of the spectrum. It's up to you to find a balance.

The biggest problem is that you push two circles out of eachother, without checking whether there is actually space available at the new position. If not, you can push a center a circle so far into another circle that you'll have extreme forces pushing it out. So once you find there is no room at the new position, you have to move the all circles affected, recursively. You can see how you have to give up a lot of performance for this to be more correct.

Games published by our own members! Check 'em out!

[delt0r]

The multiple collision problem is a hard one to solve for a non real time simulation. To do it correctly you need to order every collision and process the next collision, then work out the new order, there are many papers on this sort of thing. However this is always too slow. Everything else has stiffness problems and accuracy trade offs. The classic method is to allow some penetration that provides a *force* not a displacement with damping. Its hard to get it all right, but most game physics libs use this method. However many objects, as in thousands and more, is very much a topic of current research even for offline methods.

[theagentd]

hi,
I took a look at your code and tried to understand what u were doing there.

I would suggest that your start with handling the collisions with propper physics first, take a look at  http://en.wikipedia.org/wiki/Momentum

I know what momentum is, I've played Portal. >_>

The age old problem of correctness vs. performance.

You state in your post that it is not a performance problem, which is solely the case because you didn't take correctness into account. Once you do, you'll see it starts to become a performance problem. JBox2D is on the other end of the spectrum. It's up to you to find a balance.

The biggest problem is that you push two circles out of eachother, without checking whether there is actually space available at the new position. If not, you can push a center a circle so far into another circle that you'll have extreme forces pushing it out. So once you find there is no room at the new position, you have to move the all circles affected, recursively. You can see how you have to give up a lot of performance for this to be more correct.

I'd guess this is spot on.

I am making a strategy game, and the circles are units. I don't want any fancy physics for now, just some basic collision solving. I figured a simple solution like this would be enough, but apparently it wasn't. I thought it would kind of solve all collisions by pushing away circles little by little in an order independent manner, but when several units are pushing in the same direction it just can't compensate. It all depends on how fast units are moving ( = how hard they can push). By limiting the maximum movement speed of units to a reasonable value I can improve the situation.

I remembered that JBox2D had this "iterations" variable in the update function which controlled quality in some way. For now, I'll just take multiple smaller steps get more accurate physics. Dividing the time step into 4 eliminates almost all artifacts in my test program while still running at around 100 FPS. It is also an easily thread-able solution; I don't mind if you need a dual-core or better to run my game with 1 000 units, which is a pretty extreme case in the first place.

Still I am very interested in solving collisions. Collision detection is one thing, but solving them seems to be the real problem in physics engines. How does JBox2D do it? What about recursively check every circle in the game on collision? Wouldn't that give a worse scenario of ridiculously bad performance? I mean:
1. Check collisions between all nearby circles (potentially n^2)
 2. For each collision, check collisions of new positions (potentially n^2)
  3. Recursively do the same thing potentially n times.

O(n^n)? >___>

The multiple collision problem is a hard one to solve for a non real time simulation. To do it correctly you need to order every collision and process the next collision, then work out the new order, there are many papers on this sort of thing. However this is always too slow. Everything else has stiffness problems and accuracy trade offs. The classic method is to allow some penetration that provides a *force* not a displacement with damping. Its hard to get it all right, but most game physics libs use this method. However many objects, as in thousands and more, is very much a topic of current research even for offline methods.

Ah, I see. For now, the solution I posted above does its job, but I will want to upgrade to more proper physics later. Thanks for the info!

[Chromanoid]

broadphase -> select potential collision pairs via sweep and prune or similar
narrowphase -> select actual collision pairs and create contact constraints
constraint solving -> solve contact constraints via impulses x-times in random order (see http://www.bulletphysics.org/mediawiki-1.5.8/index.php?title=Collision_Detection_and_Physics_FAQ#How_do_most_physics_engines_solve_constraints.3F) (edit: I think I misunderstood a bit of the processing, see Rivens post)

http://code.google.com/p/box2d/downloads/detail?name=GDC2006_ErinCatto.zip might be interesting for you

[Riven]

The random-order strategy is deeply flawed.

Let's imagine three circles in a row, slightly overlapping.
 - What would be the desired outcome? The central circle would stay put, the other circles would move out.
 - What is the actual outcome? The central circle will move, and one of the outer circles would move out way faster than the other one.

Solution:
 - Calculate the forces during solving the constraints, do NOT move the circles yet.
 - This ensures the central circle will cause/receive equal (opposing) forces and stay put.
 - This ensures the circles on the sides will receive equal (opposing) forces and move out.

[Chromanoid]

yeah I didn't want to imply that the positions of the circles should be moved. I just edited my previous post. just adjust velocities (linear and torque). I think solving via sequential impulses has better results with random order, at least in bullet you can enable random order processing...

[Riven]

Once you work with forces, the order of processing doesn't change anything.

[Chromanoid]

Ah ok, thx. Then I think the randomize order option in bullet is just for special cases. Somebody in the forum mentioned calculaltions related to restitution are improved by random order. I just saw this option is off by default.

Games published by our own members! Check 'em out!

[theagentd]

Once you work with forces, the order of processing doesn't change anything.

It does slightly in my case, as I need deterministic physics.

My current solution calculates a correction value instead of a force, but I will probably change that later. However, it still has the same characteristics as your proposed solution to the random order problem.

[Roquen]

TOI ordering is not a requirement, there are alternate methods.  Too lazy to do a web search but there are probably some starting points here: http://www.wildbunny.co.uk/blog/2011/03/25/speculative-contacts-an-continuous-collision-engine-approach-part-1/

[Danny02]

why not use something like the flow fields in supreme commander 2 http://www.viddler.com/explore/BigDownload/videos/1182/

try to google to find some papers about it

[delt0r]

Flow fields is for path planing and not collision detection and response.

[Danny02]

yes sure, but he is doing a rts game and he is using collision detection so that his units won't pile up all in one point.
So he is using collision dedection more as a mean for his pathfinding which can better be handled with flow fields.

[Abuse]

Last time I approached this problem, I made it so only 1 collision could occur per iteration by reducing the delta t of the timestep to equal the earliest collision that frame & resolved the collision.
I then continued the remainder of the frame as a new iteration (which might again be subdivided if further collisions are detected).

Thinking about it, there was a flaw in my implementation - I only ever calculated the collision response with two actors; when three or more actors intersected each other at precisely the same time there was a potencial it'd screw up. Not an insurmountable problem, it'd just have made my collision response calculation a bit more complicated.

[theagentd]

Flow fields are interesting, but I want my units to have pretty individual AI, so it's kind of not really applicable in my case. It's a very interesting technique though, and I'd love to read more about it just for the sake of it. I might add some kind of AI based collision reaction to avoid collisions.

[Roquen]

I'll state some obvious stuff.  It sounds from your desc that using region quad-trees should be a win.  Also distance squared is an equivalent metric to distance for yes/no questions.

[theagentd]

I'll state some obvious stuff.  It sounds from your desc that using region quad-trees should be a win.  Also distance squared is an equivalent metric to distance for yes/no questions.

I use a grid with an ArrayList for each "tile" in the grid. When a unit's position changes, I check to see if I also need to change his location in the grid (without using list.contains() obviously). This isn't a very good idea though, as I use the same grid for line-of-sight queries, which are about 5-10x as big areas, meaning that if I have a finer grid line-of-sight queries is going to suffer, but a coarser grid means collision detection is going to be a lot slower in worst case scenarios... >_< I've thought about using multiple grids (2 or maybe more), but a quad tree would be the best. I have no idea how to implement it with dynamic data though. If you know a good article or tutorial I'd love to read it...

I already use the distance trick too.