next »

[akuryo]

Hello everybody!

This is simple, I'm creating an RTS involving circle units. Every unit should push the other, since i want to make a dynamic moving RTS(instead of tile based).

I did some basic algorythm, checking collisions with every other circle, and eventually pushing it away but that doesn't seem to be very accurate, and not well optimized at all(when i see what my computer is able to do with hundreds of barrels under cryengine...).

Do you guys have an idea?

The problem is simple :

No gravity, no velocity needed, lots of circle overriding.

[powly]

I'd just test collisions while I move them; when I've moved one, I test it's not inside the others - if it is, move it back until it's not. (or make a recursive system that moves the other circles and again, tests them against every circle and so on) It would be fairly sufficient for a game, especially if the maps aren't too crowded.

Or then you could introduce a separate loop where you go through all the pairs and test them against each other - this is a lot slower and harder though.

(I've worked with the problem when I made a rigid body physics simulation with gravity for the bodies related to each other with a friend; it still starts rotating, slowly gaining more and more speed, because of the overlapping prevention system..)

[Mikademus]

I too am trying to figure out a similar algo. I am doing this atm by moving overlapping circles away from each other, and relying on fast enough update rates that the resulting cascade overlaps will be resolved. Needless to say, it is inelegant and sometimes ugly, so a better solution is needed.

This is in fact a non-trivial problem. I know there are physics solutions, but that feels overkill...

[akuryo]

#msqrt : This couldn't work. that means you couldn't be able to move a single circle surrounded by others, or you could be blocked by 3 circles and you couldn't spawn circles...

#Mikademus : Totally, it feels jerky and using a complex physic method would kill my proc even harder.

Maybe i should do some chain collision reaction, i'll think about that(this could also send you in an infinite loops in closed spaces.

[Tycho Brahe]

Some stuff I've done:
http://polytheneproductions.blogspot.com/2009/11/another-processing-thing.html
or
http://polytheneproductions.blogspot.com/2009/11/circle-physics.html

theese may not be exactly what you're looking for but if they are, contact me for some code...

[Zaphos]

Re speed -- are you doing any broadphase collision detection at all?  Eg quadtrees, spatial hashing, etc, instead of just doing O(n^2) pairwise checks?

Re accuracy -- what do you mean by accuracy here?  Do you mean the circles are interpenetrating on some frames?

[Draknek]

I am doing this atm by moving overlapping circles away from each other, and relying on fast enough update rates that the resulting cascade overlaps will be resolved.

This is the right direction to go in; you just need to run the collision resolution multiple times per frame. More iterations => more accurate (but more time spent).

If it's not running fast enough, you probably need a better broadphase algorithm.

[Tycho Brahe]

I'm doing nothing on the speed front, it's all very early days for it. On the accuracy side, it should be fairly accurate but not at high velocitys due to lack of ccd.
Ignore 90% of what I've written in those posts, it's mostly bulshyte

[nikki]

i would go about this way : for many many objects

first make the circles either rects or points (in a non visible way)
divide the area in a few smaller areas (so you dont have to check thousands to thousands circles) , and a collision could only happen within a small area anyway
then for every object (rect) check all other objets in the same area , rect overlap. 
if they overlap then check for circle to circle.

do this for all areas,
hope it makes sence,

as a side effect you get pretty nice data about the game area wich could be used in a multitude of ways.

bye

[brog]

prcomputing a sqrt lookup table for the ranges of values you'll need can give a surprising amount of speed increase, at the cost of a bit of accuracy and memory.

[Zaphos]

prcomputing a sqrt lookup table for the ranges of values you'll need can give a surprising amount of speed increase, at the cost of a bit of accuracy and memory.

You could also try the sqrt approximation found in the middle of this article -- http://www.teknikus.dk/tj/gdc2001.htm :

We now discuss how to get rid of the square root operation. If the constraints are all satisfied (which they should be at least almost), we already know what the result of the square root operation in a particular constraint expression ought to be, namely the rest length r of the corresponding stick. We can use this fact to approximate the square root function. Mathematically, what we do is approximate the square root function by its 1st order Taylor-expansion at a neighborhood of the squared rest length r*r (this is equivalent to one Newton-Raphson iteration with initial guess r). After some rewriting, we obtain the following pseudo-code:

// Pseudo-code for satisfying (C2) using sqrt approximation
delta = x2-x1;
delta*=restlength*restlength/(delta*delta+restlength*restlength)-0.5;
x1 += delta;
x2 -= delta;

Notice that if the distance is already correct (that is, if |delta|=restlength), then one gets delta=(0,0,0) and no change is going to happen.

(where in your case you only apply this if the circles are colliding, and restlength is just the sum of the radii of the two circles you're testing)

edit: I would guess optimizing the broad phase stuff will be much more important than optimizing the sqrt though!

[Will Vale]

I am doing this atm by moving overlapping circles away from each other, and relying on fast enough update rates that the resulting cascade overlaps will be resolved.

This is pretty much the way constraints are resolved in Thomas Jakobsen's paper which popularised the use of Verlet integrators in games:

http://www.teknikus.dk/tj/gdc2001.htm

If you do it right, it will converge on the correct solution. You could try running (say) four updates for every one display update to get it to come out smoother.

Advantages of this approach: It will converge and it's stable.

Disadvantages: It's sort of 'squidgy', although the more constraint iterations you run, the less obvious this will be.

Will

[Zaphos]

If you do it right, it will converge on the correct solution.

"The correct" solution is kind of a funny way to say it?  It will usually converge on a solution to the constraints (though, I'm guessing you could construct cases where it doesn't ...), but it's not a unique solution and probably wouldn't satisfy any other notion of correctness (eg, things could probably teleport through each other, etc) ...

[Will Vale]

Yeah, fair point about the uniqueness. Although I reckon any stable solution is the correct one