Collision with CIRCLES?

[Xoria]

I was trying my best to learn about collision, ( http://love2d.org/forum/viewtopic.php?f ... lide#p8490 ) but how can I formulate colision suitable for circles? As you can tell I have no intention of using love.physics.

TIA

[Jasoco]

Well, you could check for the distance from the center of the circle and see if it's less than the radius.

Code: Select all

function distanceFrom(x1,y1,x2,y2)
	return math.sqrt((x2 - x1) ^ 2 + (y2 - y1) ^ 2)
end

Where x1, y1 is the center of the circle and x2, y2 is the point you are checking. If the result is less than the radius then the point is inside the circle.

Don't know how fast this is in practice though.

[nevon]

Don't know how fast this is in practice though.

Fast enough, unless you have like a bazillion circles, or really, really tiny ones.

[kikito]

If you want to optimize the number of checks, you could always try reducing the number of objects checked by using a QuadTree... just give me a couple days so I can test the query() method.

[vrld]

You can also square the whole equation and thus save the square-root. You will only benefit by a quadtree, if you do lot's off collision tests in a frame or do other stuff with it - the thing needs time to build itself.

[Robin]

You can also square the whole equation and thus save the square-root.

You only benefit from that if radii are constant (even more if all circles have the same radius).

Code: Select all

circle = {x = 0, y = 100, r = 10}
circle.r2 = circle.r^2

[vrld]

You only benefit from that if radii are constant (even more if all circles have the same radius).

A square root takes more time to compute than computing a multiplication, so it would save time even if it was done at every timestep.

Code: Select all

> sqrt = math.sqrt  
> pow = math.pow
> s = os.clock() for i=1,1000000 do t = sqrt(i) end print(string.format("sqrt: %f ms", (os.clock() - s)*1000))
sqrt: 130.000000 ms
> s = os.clock() for i=1,1000000 do t = pow(i,2) end print(string.format("pow: %f ms", (os.clock() - s)*1000))
pow: 150.000000 ms
> s = os.clock() for i=1,1000000 do t = i^2 end print(string.format("^: %f ms", (os.clock() - s)*1000))
^: 70.000000 ms
> s = os.clock() for i=1,1000000 do t = i*i end print(string.format("mul: %f ms", (os.clock() - s)*1000))
mul: 50.000000 ms

[Robin]

Making sqrt and pow locals shaves about 50 ms off, but yeah, i*i is still definitely the fastest.

[rhezalouis]

per 10000 iteration * 100 sample,

Code: Select all

local b = math.sqrt;
a = b(2);

average exec time = 4921.17µs [control]

Code: Select all

a = math.sqrt(2);

average exec time = 1874.78µs [approx. 62%faster]

Code: Select all

a = 2^0.5;

average exec time = 976µs [approx. 80%faster]

I used the application posted on the topic [RLC]"Regarding Time Measurement" and simply average it using MsExel. Is there something wrong with the data collection method?

[Robin]

How does the outer code look like?

A few things to consider:

• If the local b ... part was inside the loop, it is logical it is slower: it gives something like GETGLOBAL, GETDOTTED, SETLOCAL, GETLOCAL, CALL in byte code rather than GETGLOBAL, GETDOTTED, CALL. There should be an improvement in performance if you move the local b = math.sqrt outside the loop.
• I'm not sure about this, but the Lua compiler might optimize constant expressions like 2^0.5. Change it to x^0.5 (where x is defined earlier to be a local with value 2) to see if it changes the outcome.