QuadTree Collision Detection - 0.2

Can you please re-host the example source code, now that Geocities is down? I'd like to see how using Quadtrees can help optimize collision detection. Thanks in advance!

right, ok... version 0.2 now..., formulas fixed
my version system, so lazy, no cvs for this :p, its only a test after all
the balls now move smoother, not as much vibration when they are pulled to a corner by gravity.

now using

v1f = (m1-m2) * v1i / (m1+m2) + 2*m2*v2i / (m1+m2)
v2f = (m2-m1) * v2i / (m1+m2) + 2*m1*v1i / (m1+m2)

v1f: final velocity of ball 1
v2f: final velocity of ball 2
v1i: initial velocity of ball 1
v2i: initial velocity of ball 2
m1: mass of ball 1
m2: mass of ball 2

the formula comes from solving for v1f and v2f in the conservation of energy and conservation of momentum formulas.

i.e. (1/2).m1.(v1f^2) + (1/2).m2.(v2f^2) = (1/2)m1.(v1i^2) + (1/2).m2.(v2i^2) [Conservation of Energy]
m1.v1f + m2.v2f = m1.v1i + m2.v2i [Conservation of Momentum]

Does it also use vectors to change the x/y speeds?

yeap kinda, it brakes down the velocity component, and uses the 1D collision formula to change the velocity in the direction equal to the subtraction of the two position vectors.

impact_normal = (ball2.pos - ball1.pos).setLength(1.0)

the impact normal being the direction of the velocity we wanna extract and use the 1D formula on, the velocity in the direction perpendicular to the impact_normal is unchanged.

sorry for over post. back to this one

May 30, 2008 8:21am - Dylan J. Raub - nickname: (raubana)
That's a lot like my collision detection thing I made... does it set the amount and direction of the bounce based on how much they're intercecting? Does it also use vectors to change the x/y speeds?

nope, no matter how much they intercept, they r treaded the same as any other collision.
like one that intercepts 7 pixels deep into the other one is treated the same as another one that may only intercept 3 pixels deep. There is actually no deformation of the objects, its like steel ball berings hitting one another, very little to no morphing of objects.

It uses the basic one dimension formula for 100% elastic collisions (theres a modified one for slightly inelastic ones). Also forgot to note, the balls may slow down on their own, there is a damping formula to similar air resistance, a force is applied in the reverse direction of velocity proportional to its own speed.

the formula is.

v1f = v1i + 2*m2*v2i / (m1+m2)
v2f = v2i + 2*m1*v1i / (m1+m2)

ops... just realised my formula is wrong :p
its ment to be the following

v1f = (m1-m2) * v1i / (m1+m2) + 2*m2*v2i / (m1+m2)
v2f = (m2-m1) * v2i / (m1+m2) + 2*m1*v1i / (m1+m2)

i'll fix that in the code :p

Consider the lighter objects (red) like oxygen and the blue heaver objects water particles. The oxygen particles sit mostly above the water (opposite side of gravity vector) bcuz less dense than the water, but slightly dissolve in the water also. And the few water particles in the air, consider as the humidity of the air. A object is less effect when it gets hit by a light particle than a heavy particle for a given speed, so the red ones go flying when the blue ones hit them :p

i know not very user friendly :p... but if ya wanna see w/o gravity, change the two occurances of

g = Vec2(math.cos(a), math.sin(a)) * 20.0
to
g = Vec2(0.0, 0.0)

Also note, the QuadTree class isn't even used in the code :p.
Only the function detect_collisions_quadtree is used, originally i used the class
and realized i just kept rebuilding the tree and destroying in a single line, thought it was
pointless so i changed it into a recursive function.

Yes its possible to do w/o rebuilding tree. They do it in some games for doing collision detecting between dynamic objects and static objects (the dynamic objects players, monsters, bullets, ..., the static objects being the world / scenery (stuff thats still)). And then they dynamic objects r traced within the tree to detect their collisions against statics ones, like detecting collisions of players/monsters against the ground. As for dynamic objects i think its faster to re-develop the tree each time as all dynamic objects move, not too sure, depends on what ya building i guess. Monsters could stay still at moments. Maybe even possible for the objects to store the node/nodes they exist in the tree and edit the tree when they move for more speed. This programing here is just a test thing thats for something else im making, thought it was interesting to put here. The responses to the collisions r physically correct for perfect elastic collisions between (2d circles lol.. consider 3d cylinders for correct mass.) I haven't documented it well... the line in the middle represents the gravity vector.

I think it's just collision detection: you'll have to do the response yourself.

On another note, is it possible to avoid rebuilding the entire tree if only a few of your objects actually move? That would seem like a way to speed things up even more.

That's a lot like my collision detection thing I made... does it set the amount and direction of the bounce based on how much they're intercecting? Does it also use vectors to change the x/y speeds?

Just wondering, because that's how mine works.

So that's pretty neat what you've made here. even though it runs fast...very fast, it seems like the bounce is over 100%, so their flying all over the place. I think it's because they're pushed together by 'gravity'.