Page 1 of 2
Collision with CIRCLES?
Posted: Mon Apr 19, 2010 2:37 am
by 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
Re: Collision with CIRCLES?
Posted: Mon Apr 19, 2010 2:51 am
by 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.
Re: Collision with CIRCLES?
Posted: Mon Apr 19, 2010 5:41 am
by nevon
Jasoco wrote:Don't know how fast this is in practice though.
Fast enough, unless you have like a bazillion circles, or really, really tiny ones.
Re: Collision with CIRCLES?
Posted: Mon Apr 19, 2010 6:57 am
by 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.
Re: Collision with CIRCLES?
Posted: Mon Apr 19, 2010 7:22 am
by 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.
Re: Collision with CIRCLES?
Posted: Mon Apr 19, 2010 3:36 pm
by Robin
vrld wrote: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
Re: Collision with CIRCLES?
Posted: Mon Apr 19, 2010 4:18 pm
by vrld
Robin wrote: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
Re: Collision with CIRCLES?
Posted: Mon Apr 19, 2010 5:00 pm
by Robin
Making sqrt and pow locals shaves about 50 ms off, but yeah, i*i is still definitely the fastest.
Re: Collision with CIRCLES?
Posted: Thu Apr 29, 2010 1:54 pm
by rhezalouis
per 10000 iteration * 100 sample,
average exec time = 4921.17µs [control]
average exec time = 1874.78µs [approx. 62%faster]
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?
Re: Collision with CIRCLES?
Posted: Thu Apr 29, 2010 3:04 pm
by 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.