Circle collisions with physics

totebo

I'm planning to use Box2D to create a game with only circle collisions. Hundreds of circles all changing sizes all the time.

Box 2D is not ideal because you can't resize fixtures. You have to remove them and recreate them. This is slow. Pooling is unlikely to work, because there will be hundreds of different sizes.

Is there an alternative physics engine that allows changing size of a circle collision object?

totebo

Here is a quick (and dirty, oh so dirty) test, which went slightly better than I thought. The limit seems to be around 100 circles. Any more than that and it starts lagging on slower devices.

Open for suggestions on how to make this more efficient!

-- Localize math functions local random = math.random   -- Start up Box2D require "box2d" local world = b2.World.new( 0, 10, true ) local sprite_debug_draw = b2.DebugDraw.new() world:setDebugDraw( sprite_debug_draw ) stage:addChild( sprite_debug_draw )     -- Create walls to contain the circles local body_floor = world:createBody{ type = b2.STATIC_BODY } local poly = b2.PolygonShape.new() poly:setAsBox(400, 10) local fixture_definition1 = { shape = poly, density = 1.0, friction = 0.1, restitution = 0.9 } local fixturez = body_floor:createFixture( fixture_definition1 ) body_floor:setPosition( 0,400 ) local body_left_wall = world:createBody{ type = b2.STATIC_BODY } local poly = b2.PolygonShape.new() poly:setAsBox(10, 400) local fixture_definition1 = { shape = poly, density = 1.0, friction = 0.1, restitution = 0.9 } local fixturez = body_left_wall:createFixture( fixture_definition1 ) body_left_wall:setPosition( 0,0 ) local body_right_wall = world:createBody{ type = b2.STATIC_BODY } local poly = b2.PolygonShape.new() poly:setAsBox(10, 400) local fixture_definition1 = { shape = poly, density = 1.0, friction = 0.1, restitution = 0.9 } local fixturez = body_right_wall:createFixture( fixture_definition1 ) body_right_wall:setPosition( 300,0 )   local bodies = {} local fixtures = {}   -- Destroy and recreate a fixture local resizeFixture = function( body, fixture )   if fixture then body:destroyFixture( fixture ) fixtures[body] = nil end   if body.radius > 40 then body.size_diff = -1 elseif body.radius < 1 then body.size_diff = 1 end   body.radius = body.radius + body.size_diff   local circle = b2.CircleShape.new( 0, 0, body.radius )   local fixture_definition = { shape = circle, density = 1.0, friction = 0.1, restitution = 0.2 }   local fixture = body:createFixture( fixture_definition ) fixtures[body] = fixture   end     -- Create 100 bodies, each with one circle fixture for i=1, 100 do   local body = world:createBody{ type = b2.DYNAMIC_BODY } body.radius = random(40) body.size_diff = 1 body:setPosition( random(300),random(300) ) resizeFixture( body )   end   -- Resize all fixtures local resizeFixtures = function() for body,fixture in pairs(fixtures) do resizeFixture( body,fixture ) end end   -- Gameloop local enterFrame = function()   resizeFixtures() world:step(1/60, 8, 3)   end stage:addEventListener(Event.ENTER_FRAME, enterFrame )

antix

I suppose it depends on how these circles will move and stuff. Will all circles always be moving? If not then you can make some sleep so they aren't needing to do collision checking. The real problem however is when you get too many circles onscreen at one time, that's when the CPU grinds to a halt

HubertRonald

Hi @totebo if you're thinking make a game like agar.io
Here there is a sample on javascript

https://codepen.io/adrian_po_11235/pen/NqXyvq

Maybe you can take some ideas from there

In the case Box2D I had a similar problem than you (because I needed 700 circles per level ) so like @antix said you, you can make some sleep.. if these isn't on your screen for example like a google maps (if you're thinking multiplayer) only wake up circles those than you need show on your screen

totebo

Cheers guys! Yeah, like Agario, but with physics. I also think the key will be to disable stuff outside of view, good call.

antix

@HubertRonald, nice link, that's pretty cool. Basically that's acting just like Bump.lua

With my own prototype that used circles I used bump.lua. Each frame I would use queryRect() to get the circles in view and process those. Each time a circle left the screen I would start a counter and after 2 seconds it would go to sleep and not be processed if it did not come back onto the screen.

This worked pretty good and I was able to have many circles (thousands). Unfortunately I could never figure out how to stop circles clumping together.

And again there was the an issue when too many circles came onscreen

totebo

Thousands! That's advanced.

Box2D is pretty good at stopping overlapping objects, I suppose that's what a physics engine is for. As long as you don't create objects (fixtures) on top of each other you're pretty safe.

Too many circles on screen would be a problem, unless their behaviour were predictable and simple, in which case you could use PARTICLES!

antix

Particles would be good but I don;t think they are very good at resizing on the fly, which is what you wanted right?

pie

non physic Particles can be resized individually, but they won't handle collisions http://docs.giderosmobile.com/reference/gideros/Particles/setParticleSize

totebo

You could technically use particles like sprites and control them individually. So may work with my game, but I have a feeling I would hit another bottleneck somewhere else, it doesn't feel like the "right thing to do".

But I love a bit of a hack, so may just try that!

SinisterSoft

Here is something I figured out...

function collision(x1,y1,r1,x2,y2,r2) local x,y,r=x2-x1,y2-y1,r1+r2 if ((x*x)+(y*y))<(r*r) then return true else return false end end

SinisterSoft

Just modded my old code to now use particles:

application:setBackgroundColor(0)     frameRate=application:getFps()   local bit = require("bit")   local sub=string.sub local random,floor,sin,cos,pi,abs,rad,pi,sqrt=math.random,math.floor,math.sin,math.cos,math.pi,math.abs,math.rad,math.pi,math.sqrt local bnot,band,bor,bxor,lshift,rshift,rol,ror=bit.bnot,bit.band,bit.bor,bit.bxor,bit.lshift,bit.rshift,bit.rol,bit.ror math.randomseed(os.time())   width=application:getContentWidth() height=application:getContentHeight() orientation=application:getOrientation()   function collision(x1,y1,r1,x2,y2,r2) local x,y,r=x2-x1,y2-y1,r1+r2 if ((x*x)+(y*y))<(r*r) then return true else return false end end   particles=Particles.new() stage:addChild(particles)   function circle(r,c1,c2,a) p=particles:addParticles(0,0,-r,0,0) if p then particles:setParticleColor(p,c2,a) end return p end   local frameCounter=0 circles={}   repeat   local x,y,r=random(0,width),random(0,height),random(2,20) local collide=false for loop=1,#circles do local c=circles[loop] if collision(x,y,r,c.x,c.y,c.r) then collide=true break end end if not collide then local c1,c2,c3=random(0x40,0xff),random(0x40,0xff)*0x100,random(0x40,0xff)*0x10000 local p=circle(100,0xffffff,c1+c2+c3,1) if p then circles[#circles+1]={} local c=circles[#circles] c.x=x c.y=y c.r=r c.wr=r c.particle=p particles:setParticleSize(p,r*2) particles:setParticlePosition(p,x,y) end end   until #circles==100   function gameLoop(event) local skip=event.deltaTime*frameRate if skip>1.5 then skip=2 else skip=1 end   local usage=(application:getTextureMemoryUsage()/1024) if usage~=oldUsage then oldUsage=usage print("Texture usage: "..usage.."MB") end local fps = 1/event.deltaTime if fps<40 then print("FPS: "..floor(fps))   end   frameCounter=frameCounter+1   for loop=1,#circles do c=circles[loop] local x,y,r=c.x,c.y+1,c.wr if y>height then y=height end local pos=false if r>0 then local collide=false   for loop2=1,#circles do if loop~=loop2 then local c2=circles[loop2] if collision(x,y,r,c2.x,c2.y,c2.wr) then local a,a2=pi*r*r,pi*c2.wr*c2.wr local d=20--abs(a-a2)/50 if a<a2 then a=a-d if a<0 then r=0 else r=sqrt(a/pi) end a2=a2+d c2.wr=sqrt(a2/pi) else a=a+d r=sqrt(a/pi)   a2=a2-d if a2<0 then c2.wr=0 else c2.wr=sqrt(a2/pi) end end c.wr=r collide=true break end end end if not collide then if y>height then y=height end c.y=y pos=true end end local r=c.r if r~=c.wr then local d=(c.wr-r)/4 r=r+d if r<1 then r=random(2,20) c.wr=r c.y=-random(height*3) pos=true end c.r=r particles:setParticleSize(c.particle,r*2) end if pos then particles:setParticlePosition(c.particle,c.x,c.y) end end end   stage:addEventListener(Event.ENTER_FRAME,gameLoop)

totebo

That's pretty darn sweet. One question I had about particles was their lifespan. If you don't specify a TTL, do they live forever?

SinisterSoft

yes, I even use them for the 3D stars and particle effects in RetroStar!

totebo

Makes sense. Performance wise there is just no comparison.

totebo

@SinisterSoft could this be turned into a super-fast Gideros version of Bump, but with circles instead of axis-aligned rectangles? Your code is way to efficient for me to follow, but it feels like it's begging to be turned into a reusable class.

SinisterSoft

It's not really that efficient. It still has a sqrt to find real distances. The easiest way to optimise things I've found is to look how people used to do this on integer based machines - like the amiga, etc in assembly language. There is usually some math trick to do things much faster than you would think.

The collision is pretty simple & fast though - that could be done inline with the main code to speed things up.

The x*x (square) is used quite a lot in my code. I'm sure we could add an new operator to Lua to do this really common operation - it would shave time off a lot of code all over the place as gideros wouldn't need to look up the variable twice - just once. Maybe this ^^var would work?

Maybe ^% could be used to give a very fast LUT based sqrt ?

so that would been to find a distance would be:

distance=^%(^^dx+^^dy)