Carambole Summer Challenge

Page 1 of 1

13 Replies - 2945 Views - Last Post: 25 July 2019 - 01:08 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=416495&amp;s=ee1572d19ef4877006d362c93e719f3f&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

#1 DK3250

• Pythonian

Reputation: 551
• Posts: 1,721
• Joined: 27-December 13

Carambole Summer Challenge

Posted 15 June 2019 - 07:31 AM

Normally, Carambole Billiard is played on a rectangular table without pockets (holes that the ball can fall into).
In this challenge the table is still four-sided, but the angles are not straight; furthermore, there are pockets in the four corners.

As I want to use graphics for the challenge, dimensions/positions are given in pixels.
The four corners are located:

```p1 = (100, 730)
p2 = (700, 700)
p3 = (500, 400)
p4 = (50, 190)

```

The ball is simply a single (decimal-)point, graphically represented as a single pixel.
The starting point for the ball is (172, 520)

The pockets are a single pixel wide; i.e. if the position of the ball is less than 0.5 pixels from a corner, the ball is considered to be in the pocket.

We think of a board with no friction and perfect elastic bounces. Angle of incidence equals angle of reflection.

Now, a billiard board with ‘random’ angles is known to behave chaotic. If two shots are made with even a minute difference in starting angle, they will end up following completely different trajectories after a few bounces. It is really amazing to see.

A starting task in this challenge is to make a program that can simulate a ball on such a table. If you start a ball in a random direction it will end up in a pocket – but it might require several hundreds of bounces, sometimes more than 1000 bounces.

A popular form of carambole is the three-cushion game. This requires the player to be able to calculate/predict the ball position after four bounces (one cue and three cushions); demanding, but still doable on a normal table.
But more difficult on the table in this challenge.

So, here is the challenge:
Make a program that can calculate the starting angle such that the ball ends up in a pocket after exactly four bounces on the table sides.
The picture below shows one possible solution. There are many solutions; it will be great if you find (minimum) one for each corner.
You can report ‘Mission Accomplished’ by uploading a picture of one of your solutions.
I use a red dot to mark the starting point and all bounce points.

Closing remark:
I have made many games involving bounces. But they were all bounces on either horizontal or vertical surfaces for which the math is very simple. Reflection on skewed lines was a little more complicated than I expected; I was probably seduced by the simplicity of “Angle of incidence equals angle of reflection”. So, don’t despair if this part takes longer than you expect.

The tricky part of this challenge is about ending up in a pocket after 4 bounces.

Happy Coding.

A special Post Scriptum for snoopy11:
Turtle graphics will be great….

Is This A Good Question/Topic? 3

Replies To: Carambole Summer Challenge

#2 albert003

Reputation: 36
• Posts: 735
• Joined: 15-December 14

Re: Carambole Summer Challenge

Posted 24 June 2019 - 11:59 PM

I want to make sure I understand this challenge. The challenge is to make a billiard table using turtle that doesn't have a rectangle shape?. Can I use pygame?

#3 DK3250

• Pythonian

Reputation: 551
• Posts: 1,721
• Joined: 27-December 13

Re: Carambole Summer Challenge

Posted 25 June 2019 - 02:46 AM

Sure, you can use pygame - I did myself!

The post scriptum comment is more a joke directed specifically to snoopy11 because he made a quite unusual solution to the pi challenge using turtle graphics.

Otherwise you are right, the billiard table here should have no right angles and no parallel sides.
For easier comparison of solutions you can use the same corner and start coordinates as I did, but that's not a prerequisite.

The challenge has two major parts:
1. Figure out the math of “Angle of incidence equals angle of reflection”. This is well described on the internet in terms of linear algebra. But you need to convert the linear algebra to code.
2. Find a way to calculate the starting angle such that the ball ends up in a pocket after exactly 4 bounces. In my solution this is an iterative process, but one that converges quite rapidly.

Once first point is made, you can enjoy the simulation of 'endless' bounces until the ball finally reach a pocket - sometimes after more than 1000 bounces. I do recommend a bounce counter just for the fun of it.

Happy Coding

#4 albert003

Reputation: 36
• Posts: 735
• Joined: 15-December 14

Re: Carambole Summer Challenge

Posted 03 July 2019 - 12:15 AM

So just to make sure I understand, the challenge is to make a shape which doesn't have 90 angles and animate a ball bouncing off each wall?.

#5 DK3250

• Pythonian

Reputation: 551
• Posts: 1,721
• Joined: 27-December 13

Re: Carambole Summer Challenge

Posted 03 July 2019 - 06:18 AM

Typing on mobile.
Yes, the first step is to code a Ball bouncung on a board with no right angles and no parallel sides.
The 4 bounce task builds on the general solution.

#6 DK3250

• Pythonian

Reputation: 551
• Posts: 1,721
• Joined: 27-December 13

Re: Carambole Summer Challenge

Posted 05 July 2019 - 11:37 AM

@albert003:
What about developing the code in a co-operation form.
Step by step we can build and improve the code.

I suggest the first step is a simple static 'picture'.
No ball, yet; just the board based on corner points. This will provide a nice feeling of progress.
If you agree to the idea, I hope you will make an attempt of this first step.

For info:
Next step is to apply the ball and develop the bounce.
But even this step we can break down in smaller parts.

Just to be clear:
This co-development is open to all - I'm sure that we will end up with something better the more participants we are.

#7 albert003

Reputation: 36
• Posts: 735
• Joined: 15-December 14

Re: Carambole Summer Challenge

Posted 06 July 2019 - 04:53 PM

This is what I have so far with just the picture. I drew a pool table without 90 angles. The part I think will be difficult will be to calculate the ball bounce inside of the table.

```import pygame

# Define some colors
black = (0, 0, 0)
white = (255, 255, 255)
green = (0, 255, 0)
red = (255, 0, 0)

pygame.init()

# Set the width and height of the screen [width, height]
size = (800, 600)#x y
screen = pygame.display.set_mode(size)

pygame.display.set_caption("Bouncing challenge")

# Loop until the user clicks the close button.
done = False

# Used to manage how fast the screen updates
clock = pygame.time.Clock()

while not done:
# --- Main event loop
for event in pygame.event.get():
if event.type == pygame.QUIT:
done = True

screen.fill(green)
pygame.draw.line(screen, black, [50, 50], [50, 350], 5)
pygame.draw.line(screen, black, [50, 50], [650, 300], 5)
pygame.draw.line(screen, black, [50, 350], [700, 550], 5)
pygame.draw.line(screen, black, [650, 300], [700, 550], 5)#

pygame.display.flip()

clock.tick(60)

# Close the window and quit.
pygame.quit()
```

This post has been edited by albert003: 06 July 2019 - 04:54 PM

#8 DK3250

• Pythonian

Reputation: 551
• Posts: 1,721
• Joined: 27-December 13

Re: Carambole Summer Challenge

Posted 07 July 2019 - 01:31 AM

@albert003: Great that you want to play along!

Even this small code raises several comments.
1. The colors are constants and as such they should be named with CAPITALS by convention.
2. The choice of GREEN as (0, 255, 0) is too bright for my eye. A more 'billiard-green' would be (97, 153, 59) - this is RAL 6018.
3. You re-draw the table/board at every pass of your main-loop, line 32-36. But we want to show the ball trajectory as it develops so the board should only be drawn once and for all. Only the ball movement should be added in the main-loop.
4. You prepare for use of pygame.time.Clock(). This is relevant for screen update several times per second. Actually we don't need to see the ball roll, adding new lines from one bounce to the next is sufficient to see the path. To see the ball movement at such slow pace is better obtained by pygame.time.wait().

Pewh, that was a lot of comment for such small code. I hope you dont mind. Your code with my comments implemented:
```import pygame
pygame.init()

# Define some colors
BLACK = (0, 0, 0)
WHITE = (255, 255, 255)
GREEN = (97, 153, 59)
RED = (255, 0, 0)

# Set the width and height of the screen [width, height]
size = (800, 600)  #x y
screen = pygame.display.set_mode(size)
pygame.display.set_caption("Bouncing challenge")

# Draw the board, - once and for all.
screen.fill(GREEN)
pygame.draw.line(screen, BLACK, [50, 50], [50, 350], 5)
pygame.draw.line(screen, BLACK, [50, 50], [650, 300], 5)
pygame.draw.line(screen, BLACK, [50, 350], [700, 550], 5)
pygame.draw.line(screen, BLACK, [650, 300], [700, 550], 5)

done = False

# Loop until the user clicks the close button.
while not done:
# --- Main event loop
for event in pygame.event.get():
if event.type == pygame.QUIT:
done = True

# calculate ball movement here

pygame.display.flip()

# Quit.
pygame.quit()

```

Now, let's look at the ball movements.
If the ball position is (x, y) it will have two speed components in the x- and y-directions, say velocity = (dx, dy). This velocity can be seen as a vector.
Likewise, the sides of our board can be seen as vectors pointing from one end-point to another (we don't need to care about the direction).
Finding the intersection between two vectors is described on many sites - for now I'll leave it to you.
If you want, you can also solve this as intersection between a vector and a line - the math is almost the same.

You need to find the intersection to all four sides and then determine which is the right one.

Only then we can start thinking about the bounce.

I know that I am pushing you, but see if you can work out the hit between ball and table rim. Then we can look into the bounce in next post.

This post has been edited by DK3250: 07 July 2019 - 01:33 AM
Reason for edit:: Typo

#9 baavgai

• Dreaming Coder

Reputation: 7467
• Posts: 15,477
• Joined: 16-October 07

Re: Carambole Summer Challenge

Posted 07 July 2019 - 08:53 AM

This was fun. More a math problem than a graphics problem. I suck at math.

I don't really want to cough up my solution code just yet. There are more than one set of valid paths for this, of course. This was my favorite, I think:

Though, to show that the final bank doesn't always hit the same corner, this was also nice:

Big hint here, I included degrees in those screen shots. My final solution rotates through the winners, which I thought was nice. Extra credit?

Actually, degrees isn't that much of a hint. It's all about intersect and bounce and there's more than one way to skin that cat.

I mocked up a lot of tester code before moving on to the final problem. Raw values are nice, but even some math geeks break out a number line when things get messy. And, this gets messy.

Here's my final mockup, where I knew I had the math right:

You'll note those little perpendicular stubs where the ball meets the wall? Those are the normals to help visualize the math on those sloped walls. The field here is ((1,1), (19,3), (15,19), (2,15)), which you should be able to pick up from the graph.

Good luck to all.

#10 DK3250

• Pythonian

Reputation: 551
• Posts: 1,721
• Joined: 27-December 13

Re: Carambole Summer Challenge

Posted 07 July 2019 - 03:48 PM

Nice baavgai, I'm glad you liked the challenge.

I also made small test/sample code in the development, including markings of the normals; exactly as you have shown.
I hope to show this (and other sample code) in the 'co-operative tutorial' currently under development (post #8).

My first version was made with 'pure' python; later I made a version using numpy for the linear algebra.
What approach did you use?

#11 baavgai

• Dreaming Coder

Reputation: 7467
• Posts: 15,477
• Joined: 16-October 07

Re: Carambole Summer Challenge

Posted 08 July 2019 - 04:41 AM

DK3250, on 07 July 2019 - 05:48 PM, said:

What approach did you use?

Pure python. And an embarrassing amount of google-fu; I've honestly forgotten this kind of math more times than I can count. I wanted to to see how many tools were actually needed for the task. Pulling in anything more than something to render the graphics seems almost like cheating.

Admittedly, I did investigate how many applicable tools were baked into pygame, as I knew I'd go with that. While there is a promising Vector2 class, collusion detection seems more sprite oriented and for this you need projection. Though, admittedly, the thought occurred to me to make a ball sprite and just let it collide. This is certainly one kind of solution, though not the most efficient way to find a valid path.

#12 baavgai

• Dreaming Coder

Reputation: 7467
• Posts: 15,477
• Joined: 16-October 07

Re: Carambole Summer Challenge

Posted 17 July 2019 - 11:51 AM

I felt bad that I never put code out for this. Frankly, without some 2D library you kind of end up writing one yourself, which is kind of what I did. As a consequence, this is a rather large, ugly, code dump. I've played around with it long enough that I'm fed up and it probably ain't getting less ugly.

The 2D bit is about half of the 250 lines.
Spoiler

#13 DK3250

• Pythonian

Reputation: 551
• Posts: 1,721
• Joined: 27-December 13

Re: Carambole Summer Challenge

Posted 25 July 2019 - 06:33 AM

@baavgai:
As the author of this challenge, I feel inclined to comment on your solution.

Your 'silly 2D lib' is very thorough and impressive.
The very last method, "next_bounce" of class BoundVector; maybe this method doesn't belong in the 2D lib as it is directly related to the challenge and not part of a general library.

The rest of the code I find quite advanced and not always easy to understand.
You use generators and closures on a routine basis while I and other beginners still fight with fully understanding the concept.
I would love to see you turn this solution into a tutorial of generators and (especially) closures.

The general output and overall impression: Astonishing !!!

#14 baavgai

• Dreaming Coder

Reputation: 7467
• Posts: 15,477
• Joined: 16-October 07

Re: Carambole Summer Challenge

Posted 25 July 2019 - 01:08 PM

DK3250, on 25 July 2019 - 08:33 AM, said:

The very last method, "next_bounce" of class BoundVector; maybe this method doesn't belong in the 2D lib as it is directly related to the challenge and not part of a general library.

This is more the art, than science, of programming: how to organize the stuff. I figured a BoundVector is essentially a projectile, or anything that moves. And, if it moves, it will eventually hit something, so... I actually made a bouncing ball demo with it later, so it sort of seemed to fit outside the challenge.

Frankly, this is probably the 10th refactoring of the thing. I really, really, tried to not build a wee library, but without it things just seemed more confusing. In an earlier version I used no classes at all, just functions. Which is fun, but I thought the classes made it a little clearer what was going on.