2D Elastic Collision Spheres

[Operator]

Snippet of 2D collision detect and response...
Please let me know how to speed this up or
how to avoid flickering if ball/sphere gets too fast.

Code: Select all

rem 2D elastic collision with spheres v1
rem based on:
rem http://www.vobarian.com/collisions/2dcollisions2.pdf
rem http://blogs.love2d.org/content/circle-collisions
rem SB 3.4 / iPad mini 1.gen  / iOS 7.0.4 / Operator

graphics
option base 1
draw color 1,1,1
fill color 1,1,1

sch = screen_height()
scw = screen_width()
init_speed = 5
max_balls = 25
dim balls(max_balls,5)
x = 1
y = 2 
vx = 3
vy = 4
m = 5
ball_r = 15

'preload balls array x,y,vx,vy,mass
for i = 1 to max_balls
  balls(i,x) = ball_r + rnd(scw - ball_r)
  balls(i,y) = ball_r + rnd(sch - ball_r)
  balls(i,vx) = (-1 + 2*rnd(2))*rnd(init_speed)
  balls(i,vy) = (-1 + 2*rnd(2))*rnd(init_speed)
  balls(i,m) = 1
next i


do
'timer reset
t = timer()
graphics lock
graphics clear 0,0,0

'draw balls
for i = 1 to max_balls
  'draw balls
   ab_v = sqr(balls(i,vx)^2+balls(i,vy)^2)
   fill color ab_v/8,ab_v/8,ab_v/8
   fill circle balls(i,x),balls(i,y) size ball_r

  'move balls
   balls(i,x) += balls(i,vx)
   balls(i,y) += balls(i,vy)

  'wall (screen margin) collision detect & react
   if balls(i,x) <= ball_r Then
     balls(i,x) = ball_r
     balls(i,vx) = -1 * balls(i,vx)
   end if
   if balls(i,x) >= scw - ball_r Then
     balls(i,x) = scw - ball_r
     balls(i,vx) = -1 * balls(i,vx)
   end if
   if balls(i,y) <= ball_r Then
     balls(i,y) = ball_r
     balls(i,vy) = -1 * balls(i,vy)
   end if
   if balls(i,y) >= sch - ball_r Then
     balls(i,y) = sch - ball_r
     balls(i,vy) = -1 * balls(i,vy)
   end if


  'ball to ball collision detect and react
   for j = i + 1 to max_balls
     
     if (balls(i,x)-balls(j,x))^2 + (balls(i,y)-balls(j,y))^2 <= (2*ball_r)^2 Then
       'col_str$ = "ball "&str$(i)&" colliding ball "&str$(j)
       'draw text col_str$ at 10,10
       
       'resolve collision of ball(i) with ball(j)
       'colission vector = normal vector
       
       'calculate normal vector of collision: _n
        vec_n_x = balls(i,x) - balls(j,x)
        vec_n_y = balls(i,y) - balls(j,y)
       
       'normalize L=1 normal vector of collision
       'distance (vec_n_L) should be 2*ball_r
        vec_n_L = sqr(vec_n_x^2 + vec_n_y^2)
        
       'separate balls penetration along the
       '"line of collision".
        
        midptx = (balls(i,x) + balls(j,x))/2
        midpty = (balls(i,y) + balls(j,y))/2

        balls(i,x) = midptx + ball_r / vec_n_L * (balls(i,x) - balls(j,x))
        balls(i,y) = midpty + ball_r / vec_n_L * (balls(i,y) - balls(j,y))
        balls(j,x) = midptx + ball_r / vec_n_L * (balls(j,x) - balls(i,x))
        balls(j,y) = midpty + ball_r / vec_n_L * (balls(j,y) - balls(i,y))

       '.. continue normalization..
        vec_nn_x = vec_n_x / vec_n_L
        vec_nn_y = vec_n_y / vec_n_L
      
       'calculate normalized tangent vector to
       'normal vector
        vec_tn_x = -vec_nn_y
        vec_tn_y = vec_nn_x

       'resolve the velocity vectors, v1 and v2
       'into normal and tangential components 
       ' --> dot product
        v1_n = vec_nn_x * balls(j,vx) + vec_nn_y * balls(j,vy)
        v2_n = vec_nn_x * balls(i,vx) + vec_nn_y * balls(i,vy)
        v1_t = vec_tn_x * balls(j,vx) + vec_tn_y * balls(j,vy)
        v2_t = vec_tn_x * balls(i,vx) + vec_tn_y * balls(i,vy)
     
       'find the "new" tangential velocities 
       'after the collision (remain the same)
        v1_t_ac = v1_t
        v2_t_ac = v2_t
        
       'find the new normal velocities after
       'collision _ac
        v1_n_ac = (v1_n * (balls(j,m) - balls(i,m)) + 2 * balls(i,m) * v2_n) / (balls(j,m) + balls(i,m))
        v2_n_ac = (v2_n * (balls(i,m) - balls(j,m)) + 2 * balls(j,m) * v1_n) / (balls(j,m) + balls(i,m))

       'convert the scalar normal and tangential 
       'velocities into vectors
        vec_v1_n_ac_x = v1_n_ac * vec_nn_x
        vec_v1_n_ac_y = v1_n_ac * vec_nn_y
        vec_v1_t_ac_x = v1_t_ac * vec_tn_x
        vec_v1_t_ac_y = v1_t_ac * vec_tn_y

        vec_v2_n_ac_x = v2_n_ac * vec_nn_x
        vec_v2_n_ac_y = v2_n_ac * vec_nn_y
        vec_v2_t_ac_x = v2_t_ac * vec_tn_x
        vec_v2_t_ac_y = v2_t_ac * vec_tn_y

       'final velocity vectors by adding the
       'normal and tangential components
        vec_v1_ac_x = vec_v1_n_ac_x + vec_v1_t_ac_x
        vec_v1_ac_y = vec_v1_n_ac_y + vec_v1_t_ac_y
    
        vec_v2_ac_x = vec_v2_n_ac_x + vec_v2_t_ac_x
        vec_v2_ac_y = vec_v2_n_ac_y + vec_v2_t_ac_y
       
        balls(j,vx) = vec_v1_ac_x
        balls(j,vy) = vec_v1_ac_y
   
        balls(i,vx) = vec_v2_ac_x
        balls(i,vy) = vec_v2_ac_y

     end if
   next j
   
next i
draw font name "Chalkduster"
draw font size 50
draw text "Smart Basic" AT scw*.65,sch*.9
draw font size 20
draw text "Frames per Second "&str$(int(1000/(timer()-t))) AT 0,5

graphics unlock

until sch = 0

[Mr. Kibernetik]

If you want maximum speed from your program, very important rule is: never calculate the same thing twice. Calculation is always slower than taking already calculated value from a variable.
Especially important are parts of code inside cycles. Always try to move calculation out of cycle if this value is not changing inside the cycle (like setting font name and size).

Good example is:
fill color ab_v/8,ab_v/8,ab_v/8

can be done faster with:
x=ab_v/8
fill color x,x,x

or here:
balls(i,x) = midptx + ball_r / vec_n_L * (balls(i,x) - balls(j,x))
balls(i,y) = midpty + ball_r / vec_n_L * (balls(i,y) - balls(j,y))
balls(j,x) = midptx + ball_r / vec_n_L * (balls(j,x) - balls(i,x))
balls(j,y) = midpty + ball_r / vec_n_L * (balls(j,y) - balls(i,y))

you calculate ball_r / vec_n_L unnecessarily many times.

Also using sprites instead of drawing balls should be faster. Balls color may be simulated by sprites transparency.

[Operator]

Thx. for the hints
avoiding double calculations makes
it a bit, bit faster,
but if I avoid using, graphics lock/unlock,
graphics clear by painting a bigger
black circle before the white circle
i get about 2 times the frame rate...
doesn't look nice but is much faster...??

Will try to follow up your suggestion using
sprites...

[Mr. Kibernetik]

Regarding GRAPHICS LOCK/UNLOCK.
You will understand why they may slow down if you know how they operate.
smart BASIC has default screen refresh rate. When you use screen locking/unlocking - you set your own refresh rate. In your program you refresh screen at the end of each calculation cycle. If you see slowing down with screen locking/unlocking this just means that your forced screen refresh rate is faster than default refresh rate. If your forced refresh rate is lower than default refresh rate (say, there will be more balls) then locking/unlocking will give better fps.
The faster you refresh the screen - the slower program goes, because screen refreshing takes time.

Actually I found some issues with graphics while experimenting with your code. Probably I will be able to speed it up.
Currently I can suggest you to use "fill rect scw,sch" instead of "graphics clear" - you will get back your 2x speed

[Henko]

Talking about speed, i personally would not like a higher speed in this app. It's nice like it is. You've got the time to observe upcoming collisions.

However, there is something very strange going on. The fps rate is about 8 (iPad3) for max_balls =2 and still 6 fps for 50 balls. As the amount of calculations is of order O(n^2), one would expect a dramatic decrease in fps. At first glance i cannot explain that. This is the first problem to investigate when optimizing for speed.

Mr. Kybernetik already suggested to avoid superfluous calculations.
There is more: you use a lot of indexing (the array indices) within the nested for loops. For each loop, only two balls are processed, each ball having 5 variables. You could copy the 10 ball variables from the arrays into single variables, do all calculations with these single variables (without indexing!) and copy them back to the arrays at the end of the loops.
Copying ball i can be done between the for i and the for j statement, ball j of course within the for j loop.

A minor gain is to replace statements like var = -1 * var simply by var = -var.

I also was a bit puzzled by the end statement of the do - until loop : UNTIL sch = 0
Apparently you wanted to use the var SCH to shift the text "SMART BASIC" upwards to the top of the screen during the simulation and stop the simulation if it arrives there. But the value of SCH may not be altered, because it is used to check for wall collisions. In effect it is not altered in the AT clause of the DRAW TEXT command. .95*sch doesn't alter the value of SCH. you should use a seperate variable for that purpose, which can be decreases each do_until loop until it is 0.

Nice simulation. In fact, you simulate the behaviour of a quantity of gas in a closed container. The balls are the gas molecules. The pressure of the gas originates of the number of wall collisions of the molecules. The average velocity of the balls is a measure for the temperature of the gas. (But maybe you know these things better than me )

Last remark: the code is already ready (no pun intended) for different masses among the balls. Using the volume formula of a sphere, the diameters of the balls could be varied accordingly (calculated outside the for loops of course!)

My 2 cents

[Mr. Kibernetik]

I checked this program for superfluous calculations - this gives really insignificant increase of speed.
Currently graphics commands are so slow in comparison with other math that there is no sense to optimize code.

If there were no graphics commands involved and if it was only math, then speed increases approx. 10 times (from 3.6 fps to 30 fps).
In this case code optimizations may give some result.

[Operator]

Thx for the feedback and for analizing this
behaviour deeper...
I'm working on the sprite version and will also
try Henko's hints&tricks...

What is the fixed refresh rate of smart basic ?
( ... concerning speed, more wouldn't harm )
( ... and one could allways delay the programm )
( ... to observe details ...)

[Operator]

Sprite version now implemented, looks nice and 53-56 fps
with 20 marbles is ok

@Henko
Please give me some hints to calculate all this avoiding indexing

Marble @ https://www.dropbox.com/s/fvu405zeqkb7wu0/marble.png

Code: Select all

rem 2D elastic collision with spheres v1.2
rem 1.1 avoiding double calculations : ) to speed a bit
rem 1.2 using sprites, 53-56 fps with 20 marbles
rem based on:
rem http://www.vobarian.com/collisions/2dcollisions2.pdf
rem http://blogs.love2d.org/content/circle-collisions
rem 
rem SB 3.4 / iPad mini 1.gen  / iOS 7.0.4 / Operator


graphics
graphics clear 0,0,1
option sprite pos central
option base 1
draw color 1,1,1
fill color 0,0,1
draw font name "Chalkduster"

endd = 0
sch = screen_height()
scw = screen_width()
init_speed = 5
max_balls = 20
dim balls(max_balls,5)
dim marb$(max_balls)
sprite "marble" load "/Sprites/marble.png" 
x = 1
y = 2 
vx = 3
vy = 4
m = 5
ball_r = 15

'preload balls array x,y,vx,vy,mass and marbles (sprites)
for i = 1 to max_balls
  balls(i,x) = ball_r + rnd(scw - ball_r)
  balls(i,y) = ball_r + rnd(sch - ball_r)
  balls(i,vx) = (-1 + 2*rnd(2))*rnd(init_speed)
  balls(i,vy) = (-1 + 2*rnd(2))*rnd(init_speed)
  balls(i,m) = 1
  sprite "marble" copy "marble"&str$(i)
  marb$(i) = "marble"&str$(i)
  sprite marb$(i) show
next i


do
t = timer()
'graphics lock
'graphics clear 0,0,0

'draw balls
for i = 1 to max_balls
  'draw balls
    'ab_v = sqr(balls(i,vx)^2+balls(i,vy)^2)/2
    'fill color ab_v,ab_v,ab_v
    'fill circle balls(i,x),balls(i,y) size ball_r

   'sprite marb$(i) alpha ab_v 'un mark but cost some fps!
   sprite marb$(i) at balls(i,x),balls(i,y)

  'move balls
   balls(i,x) += balls(i,vx)
   balls(i,y) += balls(i,vy)

  'wall (screen margin) collision detect & react
   if balls(i,x) <= ball_r Then
     balls(i,x) = ball_r
     balls(i,vx) = -balls(i,vx)
   end if
   if balls(i,x) >= scw - ball_r Then
     balls(i,x) = scw - ball_r
     balls(i,vx) = -balls(i,vx)
   end if
   if balls(i,y) <= ball_r Then
     balls(i,y) = ball_r
     balls(i,vy) = -balls(i,vy)
   end if
   if balls(i,y) >= sch - ball_r Then
     balls(i,y) = sch - ball_r
     balls(i,vy) = -balls(i,vy)
   end if


  'ball to ball collision detect and react
   for j = i + 1 to max_balls
     
     if (balls(i,x)-balls(j,x))^2 + (balls(i,y)-balls(j,y))^2 <= (2*ball_r)^2 Then
       'col_str$ = "ball "&str$(i)&" colliding ball "&str$(j)
       'draw text col_str$ at 10,10
       
       'resolve collision of ball(i) with ball(j)
       'colission vector = normal vector
       
       'calculate normal vector of collision: _n
        vec_n_x = balls(i,x) - balls(j,x)
        vec_n_y = balls(i,y) - balls(j,y)
       
       'normalize L=1 normal vector of collision
       'distance (vec_n_L) should be 2*ball_r
        vec_n_L = sqr(vec_n_x^2 + vec_n_y^2)
        
       'separate balls penetration along the
       '"line of collision".
        
        midptx = (balls(i,x) + balls(j,x))/2
        midpty = (balls(i,y) + balls(j,y))/2

        factor = ball_r/vec_n_L
        balls(i,x) = midptx + factor * (balls(i,x) - balls(j,x))
        balls(i,y) = midpty + factor * (balls(i,y) - balls(j,y))
        balls(j,x) = midptx + factor * (balls(j,x) - balls(i,x))
        balls(j,y) = midpty + factor * (balls(j,y) - balls(i,y))

       '.. continue normalization..
        vec_nn_x = vec_n_x / vec_n_L
        vec_nn_y = vec_n_y / vec_n_L
      
       'calculate normalized tangent vector to
       'normal vector
        vec_tn_x = -vec_nn_y
        vec_tn_y = vec_nn_x

       'resolve the velocity vectors, v1 and v2
       'into normal and tangential components 
       ' --> dot product
        v1_n = vec_nn_x * balls(j,vx) + vec_nn_y * balls(j,vy)
        v2_n = vec_nn_x * balls(i,vx) + vec_nn_y * balls(i,vy)
        v1_t = vec_tn_x * balls(j,vx) + vec_tn_y * balls(j,vy)
        v2_t = vec_tn_x * balls(i,vx) + vec_tn_y * balls(i,vy)
     
       'find the "new" tangential velocities 
       'after the collision (remain the same)
        v1_t_ac = v1_t
        v2_t_ac = v2_t
        
       'find the new normal velocities after
       'collision _ac
        v1_n_ac = (v1_n * (balls(j,m) - balls(i,m)) + 2 * balls(i,m) * v2_n) / (balls(j,m) + balls(i,m))
        v2_n_ac = (v2_n * (balls(i,m) - balls(j,m)) + 2 * balls(j,m) * v1_n) / (balls(j,m) + balls(i,m))

       'convert the scalar normal and tangential 
       'velocities into vectors
        vec_v1_n_ac_x = v1_n_ac * vec_nn_x
        vec_v1_n_ac_y = v1_n_ac * vec_nn_y
        vec_v1_t_ac_x = v1_t_ac * vec_tn_x
        vec_v1_t_ac_y = v1_t_ac * vec_tn_y

        vec_v2_n_ac_x = v2_n_ac * vec_nn_x
        vec_v2_n_ac_y = v2_n_ac * vec_nn_y
        vec_v2_t_ac_x = v2_t_ac * vec_tn_x
        vec_v2_t_ac_y = v2_t_ac * vec_tn_y

       'final velocity vectors by adding the
       'normal and tangential components
        vec_v1_ac_x = vec_v1_n_ac_x + vec_v1_t_ac_x
        vec_v1_ac_y = vec_v1_n_ac_y + vec_v1_t_ac_y
    
        vec_v2_ac_x = vec_v2_n_ac_x + vec_v2_t_ac_x
        vec_v2_ac_y = vec_v2_n_ac_y + vec_v2_t_ac_y
       
        balls(j,vx) = vec_v1_ac_x
        balls(j,vy) = vec_v1_ac_y
   
        balls(i,vx) = vec_v2_ac_x
        balls(i,vy) = vec_v2_ac_y

     end if
   next j
   
next i

draw font size 50
draw text "Smart Basic" AT 650,600
fill rect 0,0 to 280,40
draw font size 20
draw text "Frames per Second "&str$(int(1000/(timer()-t))) AT 0,5

'graphics unlock

until endd = 1

[Mr. Kibernetik]

What is the fixed refresh rate of smart basic ?
( ... concerning speed, more wouldn't harm )
( ... and one could allways delay the programm )
( ... to observe details ...)

Default refresh rate is 0.1 second.

[Mr. Kibernetik]

This version is shorter and faster, using built-in complex numbers.

Code: Select all

rem 2D elastic collision with spheres v1.2
rem 1.1 avoiding double calculations : ) to speed a bit
rem 1.2 using sprites, 53-56 fps with 20 marbles
rem based on:
rem http://www.vobarian.com/collisions/2dcollisions2.pdf
rem http://blogs.love2d.org/content/circle-collisions
rem 
rem SB 3.4 / iPad mini 1.gen. / iOS 7.0.4 / Operator
rem mod by Mr.K.


graphics
graphics clear 0,0,1
option sprite pos central
option base 1
draw color 1,1,1
fill color 0,0,1
draw font name "Chalkduster"

endd = 0
sch = screen_height()
scw = screen_width()
init_speed = 5
max_balls = 20
dim balls_xy(max_balls), balls_v(max_balls), balls_m(max_balls)
dim marb$(max_balls)
sprite "marble" load "/Sprites/marble.png"
ball_r = 15
ball_d = ball_r * 2

'preload balls array x,y,vx,vy,mass and marbles (sprites)
for i = 1 to max_balls
  balls_xy(i) = ball_r + rnd(scw - ball_d) + (ball_r + rnd(sch - ball_d)) * 1i
  balls_v(i) = (-1 + 2*rndc(2))*rnd(init_speed)
  balls_m(i) = 1
  sprite "marble" copy "marble"&i
  marb$(i) = "marble"&i
  sprite marb$(i) show
next i

draw font size 50
t$ = "smart BASIC"
draw text t$ AT scw - text_width(t$),sch - text_height(t$)

draw font size 20

do
timer reset
'graphics lock
'graphics clear 0,0,0

'draw balls
for i = 1 to max_balls
  'draw balls
    'ab_v = abs(balls_v(i))/2
    'fill color ab_v,ab_v,ab_v
    'fill circle balls(i,x),balls(i,y) size ball_r

   'sprite marb$(i) alpha ab_v 'un mark but cost some fps!
   pos = balls_xy(i)
   sprite marb$(i) at real(pos),imag(pos)

  'move balls
   balls_xy(i) += balls_v(i)

  'wall (screen margin) collision detect & react
   x = real(balls_xy(i))
   y = imag(balls_xy(i))
   vx = real(balls_v(i))
   vy = imag(balls_v(i))
   if x <= ball_r Then
     balls_xy(i) = ball_r + y * 1i
     balls_v(i) = vy * 1i - vx
   end if
   if x >= scw - ball_r Then
     balls_xy(i) = scw - ball_r + y * 1i
     balls_v(i) = vy * 1i - vx
   end if
   if y <= ball_r Then
     balls_xy(i) = x + ball_r * 1i
     balls_v(i) = vx - vy * 1i
   end if
   if y >= sch - ball_r Then
     balls_xy(i) = x + (sch - ball_r) * 1i
     balls_v(i) = vx - vy * 1i
   end if

  'ball to ball collision detect and react
   for j = i + 1 to max_balls
     
     vec_n = balls_xy(i) - balls_xy(j)
     if abs(vec_n) <= ball_d Then
       'col_str$ = "ball "&str$(i)&" colliding ball "&str$(j)
       'draw text col_str$ at 10,10
       'resolve collision of ball(i) with ball(j)
       'colission vector = normal vector
       'calculate normal vector of collision: _n 
       'normalize L=1 normal vector of collision
       'distance (vec_n_L) should be 2*ball_r
        vec_n_L = abs(vec_n)
        
       'separate balls penetration along the
       '"line of collision".
        
        midpt = (balls_xy(i) + balls_xy(j)) / 2

        factor = ball_r / vec_n_L
        balls_xy(i) = midpt + factor * (balls_xy(i) - balls_xy(j))
        balls_xy(j) = midpt + factor * (balls_xy(j) - balls_xy(i))

       '.. continue normalization..
        vec_nn = vec_n / vec_n_L
      
       'calculate normalized tangent vector to
       'normal vector
        vec_nn_x = real(vec_nn)
        vec_nn_y = imag(vec_nn)
        vec_tn_x = -vec_nn_y
        vec_tn_y = vec_nn_x
        vec_tn = vec_tn_x + vec_tn_y * 1i

       'resolve the velocity vectors, v1 and v2
       'into normal and tangential components 
       ' --> dot product
       ix = real(balls_v(i))
       iy = imag(balls_v(i))
       jx = real(balls_v(j))
       jy = imag(balls_v(j))
        v1_n = vec_nn_x * jx + vec_nn_y * jy
        v2_n = vec_nn_x * ix + vec_nn_y * iy
        v1_t = vec_tn_x * jx + vec_tn_y * jy
        v2_t = vec_tn_x * ix + vec_tn_y * iy
     
       'find the "new" tangential velocities 
       'after the collision (remain the same)
        v1_t_ac = v1_t
        v2_t_ac = v2_t
        
       'find the new normal velocities after
       'collision _ac
        im = balls_m(i)
        jm = balls_m(j)
        imjm = im + jm
        jmim = jm - im
        v1_n_ac = (v1_n * jmim + 2 * im * v2_n) / imjm
        v2_n_ac = (-v2_n * jmim + 2 * jm * v1_n) / imjm

       'convert the scalar normal and tangential 
       'velocities into vectors
        vec_v1_n_ac = v1_n_ac * vec_nn
        vec_v1_t_ac = v1_t_ac * vec_tn

        vec_v2_n_ac = v2_n_ac * vec_nn
        vec_v2_t_ac = v2_t_ac * vec_tn

       'final velocity vectors by adding the
       'normal and tangential components
        balls_v(j) = vec_v1_n_ac + vec_v1_t_ac
        balls_v(i) = vec_v2_n_ac + vec_v2_t_ac

     end if
   next j
   
next i

fill rect 0,0 to 280,40
draw text "Frames per Second "&str$(int(1000/timer())) AT 0,5

'graphics unlock

until 0