Circle collisions with physics

totebo · August 2017

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 · August 2017

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 · August 2017

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 · August 2017

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 · August 2017

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

antix · August 2017

@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 · August 2017

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 · August 2017

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 · August 2017

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

totebo · August 2017

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 · August 2017

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 · August 2017

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 · August 2017

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 · August 2017

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

totebo · August 2017

Makes sense. Performance wise there is just no comparison.

totebo · August 2017

@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 · August 2017

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)

Howdy, Stranger!

Categories

In this Discussion

Top Posters

Circle collisions with physics

Comments

Howdy, Stranger!

Quick Links

Categories

In this Discussion

Top Posters

Circle collisions with physics

Comments