Physics simulations have one incredible feature - they can be stopped, rewound, and replayed. This is a very powerful tool that can be used to generate unusual worlds. In this post, I will describe how I used this to synchronize the sound of the balls hitting famous music. I ask those interested under the cut!
Introduction
I love to create all kinds of fancy visualizations, physics simulations and all that kind of stuff. And so two or three years ago, when I was developing my next idea , I had an idea, but what if we generate the physical world so that the processes taking place in it create a melody? Indeed, in a computer simulation, we can always roll back, go through the options, choose the best one and at the same time we have all the information about the melody: notes, playing time of a note. So I had this idea to live in my head until better times, until I had time to write something in quarantine, thus this project with this article appeared.
Model
To begin with, I decided to choose a fairly simple model. In my model, there are only two types of objects: marbles and platforms or planks. Platforms have strictly fixed coordinates, are set by two end points and have a constant width. The balls fall under the influence of gravity and can bounce off the platforms according to the laws of physics. Also, I decided to use only absolutely elastic collisions so that the energy of the system always remains unchanged. But the most important thing is that when the ball and the platform collide, a sound is played, each platform has its own sound and can consist of several notes at once.
Thus, our world consists of many platforms, each of which has an assigned sound. And the balls that fall in this world can create a sequence of sounds, and in our case, even a melody.
Algorithm
We figured out the model, but how to generate such a world so that the sounds of beating balls line up in a well-known melody ?
I decided to use the most clumsy, nevertheless, which proved to be quite good, recursive brute force, and in the common people bruteforce . But in order for everything to work as it should, I had to use a few tricks. All subsequent steps are performed inside a recursive function:
- We simulate the world, until the next moment when you need to play a note.
- If during the simulation there was an unwanted collision, we return to the higher level.
- , , , . , . . «» ( , , ).
- 4. .
- 5. ,
- 6. , , , , .
In the picture you can see the visualization of one step of this algorithm:
Note
, , , . , , . , . , .
Recursion stuck
Like any bruteforce algorithm, this one has a drawback in the form of "recursion stuck", this happens when some "bad" platform does not allow the map to be generated in the future, but at the same time allows you to generate a large enough part of it, but not completely ... In this case, the recursion will get stuck until it enumerates all the options in the recursion subtree that this "bad" platform spawns. There is no problem when the height of this subtree does not exceed 4-8 levels of recursion, but sometimes it can reach 20-30 levels, which makes it simply impossible to iterate through all the variants of this subtree.
Therefore, in my implementation, I decided to use a heuristic to overcome the stuck. The idea is to collapse some part of the recursion when such cases are detected. It seemed most obvious to me to return to levels of recursion are higher if during iterations, we were unable to improve the maximum length of the generated path across platforms. In my case, I choose as 10% of the number of notes, and like 2000.
You can see the result of this heuristic in the demo, when the progress of map generation will sometimes be reset by 10%. But at the same time, it allows you to complete the generation of the card in a reasonable time.
Iterative generation
Now let's solve the following problem: after the start of map generation, the page freezes for 10-30 seconds and it is impossible to understand what is happening at all, everything has fallen, or it just takes a very long time to generate the map. Therefore, I decided to write also an iterative implementation of the generation algorithm so that you can consistently build a map in small portions.
I didn't have to invent something new, I just rewrote the recursive algorithm onto an explicit stack. Thus, a progress bar appeared on the page that will help you understand that the code has not fallen, it just takes a long time to find a suitable location of platforms for your track.
In some cases, the generation can take too long, for this I added the Play button , which stops the generation and starts the simulation of the world.
Download ringtone
To download a melody, I use midi files, but before that I ran it through tonejs.github.io/Midi to turn it into a browser-friendly json (but at the moment the demo does not have the functionality of downloading my file, only a choice from a ready-made list is available).
It is also important to note that often there will be several parallel tracks inside the midi file, but since my algorithm so far only works with one ball, only one track will be loaded with the largest number of notes.
results
After adding some effects, I recorded the first video:
After reviewing it several
The video may show a desynchronization, I noticed this later. If you go to the page with the demo , there should be no out of sync (the sound is actually played only when the beat is registered).
What's next?
I have plans to add the ability to generate such maps for several balls at once. I have ideas on how to do this, I tested several options, but so far they all work extremely slowly to generate a full track.
Another idea of mine was to add new objects: buttons, springboards, cannons (?), Rings ... the list can be supplemented :) They can greatly diversify the world.
The code
You can find all the source code in my repository
Any suggestions, pull requests, quizzes are welcome!