I'm terrible at basketball and I wanted to improve my skills. I could have taken the boring approach and simply improved my skills through practice, but where is the fun in that? Instead I was inspired by Stuff Made Here. He made a curved backboard that would make it easier to shoot a ball into a hoop. The basic idea is to optimize the shape of the backboard so it is more likely to bounce shots into the hoop. You end up with a shape like a concave mirror. Concave mirrors focus light into a single point. Similarly the backboard focuses ball bounces towards the center of the hoop. 

The optimization for this project is done using a computer simulation that generates a backboard shape and tests shooting a ball from a bunch of different positions and angles. It sort of keeps trying different backboards until it either runs out of time or stops improving the shape. This is a complex optimization problem that could be solved in a number of different ways. I solved it using something called a Genetic Algorithm.

Sources
Stuff Made Here Video: https://www.youtube.com/watch?v=vtN4tkvcBMA
Github Repo: https://github.com/JoeyShotts/OptimizedBasketballHoop 
Thingiverse Printable Model: https://www.thingiverse.com/thing:7386237 
CAD: https://cad.onshape.com/documents/86306989aa1c30e44a7d12f8/w/0b1b638670a97f9a8d33990a/e/202dbd67a0fa8fff18fc6649 

The End Product
Before getting into the details, I want to share the results. I am publishing a printable 3D model of the backboard, so anyone can make it and play with it. This model is limited to be useful for one specific situation, shooting a mini basketball indoors. The backboard is optimized for that specific situation, and while it could probably be used for other situations, it likely won't work as well. However I am also publishing the code, so someone with some coding knowledge can generate a backboard to fit their needs. I'm sure the code and algorithm could be improved. If you have a GPU running the simulation it might take somewhere in the ballpark of 3-10 hours to run. 

The simulation that determines the percentage of shots that make it into the hoop initially had only around 0.5% of shots making it into the hoop. The final shape allowed around 10.5% of shots to make it into the hoop. To test the effectiveness of the hoop I made a flat backboard and hoop of the same size as the optimized backboard and hoop. I can only very rarely make a shot into the flat backboard, while with the optimized hoop I can pretty consistently make it in.

This kind of optimized backboard and hoop has real applications. The first use case is similar to pickleball. Pickleball has experienced a recent rise in popularity, and one reason why is the sports design. As compared to tennis, it's much easier to play, making it more fun. In a similar vein this basketball backboard makes it easier to shoot hoops, and thus more fun. There is nothing wrong with making something more fun by making it easier. I'm sure kids would find something like this really fun.

The other use case that comes to mind is to help people with disabilities. If someone has experienced some loss of motor abilities, this might provide a way to make basketball a little more doable. A backboard could be optimized for different situations. Maybe it's someone in a wheelchair who is only shooting from one spot. Maybe it's someone who is older and can still stand, but might use a non-standard basketball form. Maybe it's someone who can only shoot from close up, or needs to use a tool or prosthetic to help shoot the ball.

This backboard also provides a valuable learning opportunity for collegiate level computer science students. A lot of focus has been put on Machine Learning and Data Science recently. The modern computing revolution hardly relies on only these techniques. While this project specifically relies on a Genetic Algorithm to optimize the hoop, it would be completely possible to take this project and optimize the backboard using a long list of different computer science techniques. 

Genetic Algorithms
Using a Genetic Algorithm to optimize the shape of the backboard made a lot of sense. As the name suggests, Genetic Algorithms take inspiration from nature and evolution. In nature, genetics partially determine a species' speed, camouflage, heat/cold tolerance, etc. By changing their genes over time species adapt to better suit their environment. These genes get changed by random variation and by crossing the genes of successful parents. Over time species slowly become optimized for their specific situation. A genetic computer algorithm works similarly, but at a faster rate and with way less complexity and variables. In nature evolution is really slow, and species just have to be "good enough" to survive, not necessarily ideal. The classic example is the way rabbits sometimes eat their own poop. Needless to say, I'm not sure they would in an ideal world. In a genetic algorithm, things work a little differently.

In general, a genetic algorithm needs a genome, a population, and a fitness test. For a genetic algorithm the genome is the variable you want to optimize. In this project, the genome is a grid of points that define the shape of the backboard. These points will be moved around slightly randomly, and they will be ultimately determined by the parent genomes that were crossed to create the child genome. The genome variables have to be carefully selected, if there are too many the genetic algorithm will struggle to converge on a solution. 

For a genetic algorithm, the population is a number of genomes with different values. This is like how in nature a species might have a large population with a bunch of different individuals with different genes. In this case the population is around 500 backboards with different shapes. The population of a genetic algorithm is typically created with a high diversity. Initializing the population to include a bunch of different options will help the algorithm find the best solution.

Finally, you need a fitness test. In nature, this is a species ability to survive and reproduce. In a genetic algorithm, you typically create some way of scoring an individual genome in a population. In this project the fitness test is simply the percentage of shots that make it in when shooting at a bunch of points on a backboard from a bunch of positions. This process is summarized in the image below.

A key issue for genetic algorithms is diversity and size. In nature evolution takes a long time, and  produces a greater diversity of species as the world progresses. A computer simply can't match that level of complexity (unless we're living in the matrix). A genetic algorithm typically starts with a large and diverse population, and slowly converges on one solution that works the best. To make a genetic algorithm work effectively, you need to maintain diversity throughout the process, so the algorithm doesn't converge early on a solution that is a local optimum. 

Program Speed
Another critical issue for the program was speed. Genetic algorithms require having a large population and a fitness test. In this case the fitness test requires a lot of tests. Specifically the fitness score of any given backboard shape is the percentage of shots that will make it into the hoop if you shoot at a range of points on the backboard from a range of positions and speeds. To get an accurate fitness score you have to test a lot of trajectories. Specifically I'm testing 42x72 faces on the backboard, shooting at each face from 75x75x11 positions and at 21 different speeds. This means every face requires 1.3 million trajectory tests and every backboard genome requires about 4 billion tests to determine the fitness. Every trajectory test involves calculating the bounce off the backboard face, then potentially testing the bounce off the rim depending on where the ball lands after bouncing off of the backboard.

To make this program run in a reasonable amount of time I wrote the program from the ground up using C++ and a NVIDIA GPU. I made a custom script to test the trajectories rather than using a more standard simulation library. I also used multithreading and careful memory management. The finished version of the program took around 4 hours and ran for over 200 cycles, replacing about half of the 500 member population each cycle. It uses around 90% of the GPU while it runs and around 20% of the CPU. The desktop it ran on became like a mini space heater.

Trajectory Math
The trajectory math for the simulation relies on simple kinematics. These are the same 3 classic equations that are taught all over the world in physics class. Some assumptions were made. Drag was completely ignored, and calculation of spin was greatly simplified. This was because the calculations for spin and drag are complicated and computationally expensive. The trajectory calculation has to run 4 billion times for every backboard, so it needs to be as fast as possible. 

Spin has a pretty significant effect for basketball players, and is important to include to keep the trajectory simulation relatively accurate. Typically basketball players are trained to shoot balls with backspin. When a ball bounces the angle it enters the bounce equals the angle it bounces away with. However, when a basketball has backspin, it increases the downward velocity of the ball after the bounce. This makes intuitive sense, a basketball player wants the ball to bounce down more, towards the basketball hoop.

To include some calculation of spin, a simple constant was used. An assumption was made that on average, the backspin would lower the vertical speed component of the bounce by 20%. That means that after the bounce if the ball had a negative speed, the ball would have that speed increased by 20%. The spin in the other directions was completely ignored because if you average the speed of all shots at the backboard, the average spin speed to the right, left, or other directions would be 0. It's assumed that a shooter is just as likely to randomly spin the ball to the right or left, but that a shooter is likely to have some amount of backspin on average.

The other consideration is what to do about the hoop. The first part of the basketball shot is from the shooter's hands to some point on the backboard. These are both chosen at the start of the trajectory calculation, and don't have to be determined. Using vectors and some basic kinematics, calculating the ball's movement from the player's hand, to the chosen point on the backboard (where the angle of the face is known), and getting a resulting speed vector is a fairly straightforward physics problem. There are two options for what to do next.

The easiest thing to do is to ignore the hoop. You want the ball to bounce to as close to the center of the hoop as possible. You can easily calculate what position the ball is at when the ball is at the height of the hoop. Then you can simply decide if the ball will likely make it in or not based on how close it is to the center of the hoop. This solution works, and is really fast to calculate, but it misses a lot of edge cases. What if the ball is moving really fast and would have hit the hoops rim? What if the ball is coming in at a weird angle? How do you decide what distance from the center of the target will count as the ball making it in?

The other option is do the calculation to see if the ball will hit the rim, and then determine if the trajectory after the rim bounce will bounce the ball in or out of the hoop. Calculating the exact point, speed and direction the ball is when it hits the rim is actually quite a hard problem, and it requires using computationally expensive trigonometric functions like sin and cos. Up to this point the most computationally expensive calculation has been calculating the square root. Furthermore, you can't calculate it directly, the most common approach is to calculate where it hits the rim numerically. You have to iterate through the ball's trajectory, checking each point to see if it has hit the rim yet.  

To get around this, a simplification is needed. Instead of calculating the exact point the ball hits the rim, you can assume that the ball will hit the rim when the ball is at the same height as the hoop. This is slightly inaccurate, but is way faster and easier to calculate, allowing the use of the same straight forward kinematics. If the ball is close to the rim's edge, it collides with the rim. If the ball is outside the rim the ball didn't make it in. If the ball is inside the rim it is made. If the ball hits the rim, some additional kinematic calculations can be done to determine if the ball will bounce into the hoop or if it will bounce out of the hoop.

By carefully considering the mathematical simplifications needed, the fitness test that resulted uses multiplication, division and square root calculations that can run extremely quickly on a GPU, allowing the entire algorithm to complete in a reasonable amount of time.

Backboard Smoothing
As previously mentioned, genetic algorithms need a relatively small genome to be effective. If there are too many variables, the genetic algorithm will struggle to converge on a solution. Specifically, a grid of 4x6 points was used to control the shape of the backboard. The x and z values of the points remained fixed, they were at the locations shown on the grid. The y values of these points were varied up and down to ultimately determine the shape of the backboard. 

There are a lot more faces on the backboard than these points. This is important for getting an accurate fitness test, as every face of the backboard is tested separately. This 4x6 grid was used to determine points that made a grid of 42x72 individual faces. In a 3D .stl file, the faces are triangles. For the backboard, the 42x72 faces are all squares. They are later split into triangles when the actual 3D .stl file is made. 

To actually smooth between the points, you have to use a 3D version of a spline. A spline is a commonly used interpolation function. All that means is it is sort of trying to determine a line of best fit. In algebra classes, it's pretty common to learn how to find the line of best fit for a scatterplot. On a graphing calculator, algebra classes might commonly teach how to make a polynomial function that best fits some data. A spline is a version of this best fit that is specifically designed to curve cleanly based on some given data points. A lot of drawing programs will allow users to control points to determine a curvy shape, these programs are really just using a spline.

There many different types of splines, this project specifically used a monotonic cubic spline to make a bicubic surface. What that really means is that  a specific type of spline was applied using the x values in direction and the z values in the other, along with the control points in y, to generate a smooth connection between all of the control points. There are specific functions called Hermite functions that are used to determine the exact y value at any given point on the backboard using the control points.

Room For Improvement
This project could and should be improved in the future. One improvement would be to add the ability to mirror both sides of the basketball hoop. Currently both sides are solved independently, but this is a huge waste of computation. 

The previous feature would need to be optional for this next feature to work. It would be nice to create backboards generated for individuals specific needs. Especially for people who are not able to generate a backboard themselves. For example, a backboard that is optimized to only be shot at from the left or from the right (for when the hoop is placed in the corner of a room) could be generated. It would also be nice to have backboards optimized to be placed at different heights and to have backboards optimized for shooters of different heights.

Another feature that would be useful is to add other variables into the genome. For example, the target point could be a part of the genome, and so could the backboard height. These values would need to be limited, but it's likely that a better optimization overall could be created.

Conclusion
This project demonstrates what is possible in the era of modern computing. It serves as an example of how everyday objects can be optimized to fit the needs of individuals, making a better world for everyone. It is my hoop that other makers will take this project and build on it to create new and interesting projects.