Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (499)
Games in Android Showcase (118)
games submitted by our members
Games in WIP (567)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Circle collision response  (Read 3824 times)
0 Members and 1 Guest are viewing this topic.
Offline theagentd
« Posted 2011-12-18 13:31:11 »

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.

Myomyomyo.
Offline Danny02
« Reply #1 - Posted 2011-12-18 13:53:14 »

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
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 801
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #2 - Posted 2011-12-18 13:56:32 »

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.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline delt0r

JGO Knight


Medals: 27
Exp: 18 years


Computers can do that?


« Reply #3 - Posted 2011-12-18 15:34:04 »

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.

I have no special talents. I am only passionately curious.--Albert Einstein
Offline theagentd
« Reply #4 - Posted 2011-12-18 15:50:35 »

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!

Myomyomyo.
Offline Chromanoid

Junior Member


Medals: 3



« Reply #5 - Posted 2011-12-18 16:54:00 »

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
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 801
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #6 - Posted 2011-12-18 17:11:28 »

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.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Chromanoid

Junior Member


Medals: 3



« Reply #7 - Posted 2011-12-18 17:20:53 »

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...
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 801
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #8 - Posted 2011-12-18 17:23:04 »

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

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Chromanoid

Junior Member


Medals: 3



« Reply #9 - Posted 2011-12-18 17:55:49 »

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!
Legends of Yore - The Casual Retro Roguelike
Offline theagentd
« Reply #10 - Posted 2011-12-18 17:58:20 »

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.


Myomyomyo.
Offline Roquen
« Reply #11 - Posted 2011-12-18 20:05:46 »

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/
Offline Danny02
« Reply #12 - Posted 2011-12-19 14:03:21 »

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
Offline delt0r

JGO Knight


Medals: 27
Exp: 18 years


Computers can do that?


« Reply #13 - Posted 2011-12-19 14:06:28 »

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

I have no special talents. I am only passionately curious.--Albert Einstein
Offline Danny02
« Reply #14 - Posted 2011-12-19 14:12:57 »

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.
Offline Abuse

JGO Knight


Medals: 12


falling into the abyss of reality


« Reply #15 - Posted 2011-12-19 14:18:39 »

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.

Make Elite IV:Dangerous happen! Pledge your backing at KICKSTARTER here! https://dl.dropbox.com/u/54785909/EliteIVsmaller.png
Offline theagentd
« Reply #16 - Posted 2011-12-19 15:01:23 »

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.

Myomyomyo.
Offline Roquen
« Reply #17 - Posted 2011-12-20 11:10:12 »

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.
Offline theagentd
« Reply #18 - Posted 2011-12-20 11:29:07 »

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.

Myomyomyo.
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

Pippogeek (39 views)
2014-09-24 16:13:29

Pippogeek (30 views)
2014-09-24 16:12:22

Pippogeek (19 views)
2014-09-24 16:12:06

Grunnt (44 views)
2014-09-23 14:38:19

radar3301 (27 views)
2014-09-21 23:33:17

BurntPizza (63 views)
2014-09-21 02:42:18

BurntPizza (32 views)
2014-09-21 01:30:30

moogie (40 views)
2014-09-21 00:26:15

UprightPath (50 views)
2014-09-20 20:14:06

BurntPizza (54 views)
2014-09-19 03:14:18
List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!