Welcome, guest | Sign In | My Account | Store | Cart

Dynamical Billiards Simulation (Python recipe) by FB36
ActiveState Code (http://code.activestate.com/recipes/577445/)

It simulates reflections of a ball on a billiards table that has one or more circular obstacles. (This can also be thought as a 2d ray-tracing.)

Most of the time the path of the ball would be chaotic (meaning, if another ball started from any slightly different location or direction then its path would be very different after a short while).

See Wikipedia for more info: http://en.wikipedia.org/wiki/Dynamical_billiards

Python, 89 lines
Download
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
# Dynamical Billiards Simulation
# FB - 201010295
# See Wikipedia for more info:
# http://en.wikipedia.org/wiki/Dynamical_billiards
import math
import random
from PIL import Image, ImageDraw
imgx = 800
imgy = 600
image = Image.new("RGB", (imgx, imgy))
draw = ImageDraw.Draw(image)

# Only 1 ball is used!
maxSteps = 20000 # of steps of ball motion (in constant speed)

n = random.randint(1, 7) # of circular obstacles
crMax = int(min(imgx - 1, imgy - 1) / 4) # max circle radius
crMin = 10 # min circle radius

# create circular obstacle(s)
cxList = []
cyList = []
crList = []
for i in range(n):
    while(True): # circle(s) must not overlap
        cr = random.randint(crMin, crMax) # circle radius
        cx = random.randint(cr, imgx - 1 - cr) # circle center x
        cy = random.randint(cr, imgy - 1 - cr) # circle center y
        flag = True
        if i > 0:
            for j in range(i):
                if math.hypot(cx - cxList[j], cy - cyList[j]) < cr + crList[j]:
                    flag = False
                    break
        if flag == True:
            break
    draw.ellipse((cx - cr, cy - cr, cx + cr, cy + cr))
    cxList.append(cx)
    cyList.append(cy)
    crList.append(cr)

# initial location of the ball must be outside of the circle(s)
while(True):
    x = float(random.randint(0, imgx - 1))
    y = float(random.randint(0, imgy - 1))
    flag = False
    for i in range(n):
        if math.hypot(x - cxList[i], y - cyList[i]) <= crList[i]:
            flag = True
            break
    if flag == False:
        break
    
# initial direction of the ball
a = 2.0 * math.pi * random.random()
s = math.sin(a)
c = math.cos(a)

for i in range(maxSteps):
    image.putpixel((int(x), int(y)), (255, 255, 255))
    xnew = x + c
    ynew = y + s

    # reflection from the walls
    if xnew < 0 or xnew > imgx - 1:
        c = -c
        xnew = x
    if ynew < 0 or ynew > imgy - 1:
        s = -s
        ynew = y

    # reflection from the circle(s)
    for i in range(n):
        if math.hypot(xnew - cxList[i], ynew - cyList[i]) <= crList[i]:
            # angle of the circle point
            ca = math.atan2(ynew - cyList[i], xnew - cxList[i])
            # reversed collision angle of the ball
            rca = math.atan2(-s, -c)
            # reflection angle of the ball
            rab = rca + (ca - rca) * 2
            s = math.sin(rab)
            c = math.cos(rab)
            xnew = x
            ynew = y

    x = xnew
    y = ynew
    
image.save("Dynamical_Billiards.png", "PNG")
Tags: chaos, graphics, math, pil, random

2 comments

FB36 (author) 13 years, 5 months ago  # | flag

Since the path of the moving ball is chaotic, x and/or y coordinates of the ball at consecutive reflection points can be used as a pseudo-random number generator.

In that case the initial location and direction of the ball, as well as the location and radii of the circles would function as the seed values of the generator.

FB36 (author) 13 years, 3 months ago  # | flag

This version uses a grid of n by m circular obstacles w/ all same radius:

# Dynamical Billiards Simulation
# http://en.wikipedia.org/wiki/Dynamical_billiards
# Only 1 ball is simulated.
# FB - 201101027
import math
import random
from PIL import Image, ImageDraw
imgx = 700
imgy = 700
image = Image.new("RGB", (imgx, imgy))
draw = ImageDraw.Draw(image)

maxSteps = 20000 # of steps of ball motion (in constant speed)

# create a grid of n by m circular obstacles
n = random.randint(1, 9) # horizontal grid size
m = random.randint(1, 9) # vertical grid size
crMax = int(min(imgx / (n + 1) / 2, imgy / (m + 1) / 2)) - 1 # max radius
crMin = 10 # min radius
cr = random.randint(crMin, crMax) # circle radius (same for all grid circles)
cxList = []
cyList = []
crList = []
for j in range(m):
    cy = int((j + 1) * imgy / (m + 1)) # circle center y
    for i in range(n):
        cx = int((i + 1) * imgx / (n + 1)) # circle center x
        cxList.append(cx)
        cyList.append(cy)
        crList.append(cr)
        draw.ellipse((cx - cr, cy - cr, cx + cr, cy + cr))

# initial location of the ball must be outside of the circle(s)
while(True):
    x = float(random.randint(0, imgx - 1))
    y = float(random.randint(0, imgy - 1))
    flag = False
    for i in range(n * m):
        if math.hypot(x - cxList[i], y - cyList[i]) <= crList[i]:
            flag = True
            break
    if flag == False:
        break

# initial direction of the ball
a = 2.0 * math.pi * random.random()
s = math.sin(a)
c = math.cos(a)

for i in range(maxSteps):
    image.putpixel((int(x), int(y)), (255, 255, 255))
    xnew = x + c
    ynew = y + s

    # reflection from the walls
    if xnew < 0 or xnew > imgx - 1:
        c = -c
        xnew = x
    if ynew < 0 or ynew > imgy - 1:
        s = -s
        ynew = y

    # reflection from the circle(s)
    for i in range(n * m):
        if math.hypot(xnew - cxList[i], ynew - cyList[i]) <= crList[i]:
            # angle of the circle point
            ca = math.atan2(ynew - cyList[i], xnew - cxList[i])
            # reversed collision angle of the ball
            rca = math.atan2(-s, -c)
            # reflection angle of the ball
            rab = rca + (ca - rca) * 2
            s = math.sin(rab)
            c = math.cos(rab)
            xnew = x
            ynew = y

    x = xnew
    y = ynew

image.save("Dynamical_Billiards.png", "PNG")