As simulações de física têm um recurso incrível - podem ser interrompidas, rebobinadas e reproduzidas. Esta é uma ferramenta muito poderosa que pode ser usada para gerar mundos incomuns. Neste post, vou descrever como usei isso para sincronizar o som das bolas batendo em músicas famosas. Peço aos interessados sob o corte!
Introdução
Adoro criar todos os tipos de visualizações sofisticadas, simulações de física e todo esse tipo de coisa. E então, dois ou três anos atrás, quando eu estava desenvolvendo minha próxima ideia , eu tive uma ideia, mas e se gerarmos o mundo físico de forma que os processos que ocorrem nele criem uma melodia? De fato, em uma simulação por computador, podemos sempre reverter, percorrer as opções, escolher a melhor e ao mesmo tempo ter todas as informações sobre a melodia: notas, tempo de execução de uma nota. Então eu tive essa ideia de viver na minha cabeça até tempos melhores, até ter tempo de escrever algo em quarentena, daí surgiu esse projeto com esse artigo.
Modelo
Decidi começar com um modelo bastante simples. No meu modelo, existem apenas dois tipos de objetos: mármores e plataformas ou pranchas. As plataformas têm coordenadas estritamente fixas, são definidas por dois pontos finais e têm largura constante. As bolas caem sob a influência da gravidade e podem quicar nas plataformas de acordo com as leis da física. Além disso, decidi usar apenas colisões absolutamente elásticas para que a energia do sistema permaneça sempre inalterada. Mas o mais importante é que quando a bola e a plataforma colidem, um som é tocado, cada plataforma tem seu próprio som e pode consistir em várias notas ao mesmo tempo.
Assim, nosso mundo consiste em muitas plataformas, cada uma delas com um som atribuído. E as bolas que caem neste mundo podem criar uma sequência de sons e, no nosso caso, até uma melodia.
Algoritmo
Nós descobrimos o modelo, mas como gerar tal mundo de forma que os sons de bolas batendo se alinhem em uma melodia conhecida ?
Decidi usar o mais desajeitado, no entanto, que se mostrou bastante bom, força bruta recursiva e força bruta de gente comum . Mas para que tudo funcionasse como deveria, tive que usar alguns truques. Todas as etapas subsequentes são realizadas dentro de uma função recursiva:
- Simulamos o mundo, até o próximo momento em que você precisa tocar uma nota.
- Se durante a simulação houve uma colisão indesejada, voltamos ao nível superior.
- , , , . , . . «» ( , , ).
- 4. .
- 5. ,
- 6. , , , , .
Na foto você pode ver a visualização de uma etapa deste algoritmo:
Nota
, , , . , , . , . , .
Recursão travada
Como qualquer algoritmo de força bruta , este tem uma desvantagem na forma de "recursão travada", isso acontece quando alguma plataforma "ruim" não permite que o mapa seja gerado no futuro, mas ao mesmo tempo permite que você gere uma parte grande o suficiente dele, mas não completamente ... Nesse caso, a recursão ficará paralisada até que enumere todas as opções na subárvore de recursão que essa plataforma "ruim" gera. Não há problema quando a altura desta subárvore não excede 4-8 níveis de recursão, mas às vezes pode atingir 20-30 níveis, o que torna simplesmente impossível iterar por todas as variantes desta subárvore.
Portanto, em minha implementação, decidi usar uma heurística para superar o travamento. A ideia é reduzir parte da recursão quando tais casos são detectados. Pareceu-me o mais óbvio voltar a os níveis de recursão são maiores se durante iterações, não foi possível melhorar o comprimento máximo do caminho gerado nas plataformas. No meu caso, eu escolho como 10% do número de notas, e como em 2000.
Você pode ver o resultado dessa heurística na demonstração, quando o progresso da geração do mapa às vezes será redefinido em 10%. Mas, ao mesmo tempo, permite que você conclua a geração do cartão em um tempo razoável.
Geração iterativa
Agora vamos resolver o seguinte problema: após o início da geração do mapa, a página congela por 10-30 segundos e é impossível entender o que está acontecendo, tudo caiu, ou apenas leva muito tempo para gerar o mapa. Portanto, decidi escrever também uma implementação iterativa do algoritmo de geração para que você possa construir um mapa consistentemente em pequenas partes.
Não tive que inventar algo novo, apenas reescrevi o algoritmo recursivo em uma pilha explícita. Assim, uma barra de progresso apareceu na página que irá ajudá-lo a entender que o código não caiu, apenas leva muito tempo para encontrar um local adequado de plataformas para sua faixa.
Em alguns casos, a geração pode demorar muito, para isso adicionei o botão Play , que interrompe a geração e inicia a simulação do mundo.
Baixar toque
Para baixar a melodia, eu uso arquivos midi, mas antes disso passei por tonejs.github.io/Midi para transformá-la em json compatível com o navegador (mas no momento não há funcionalidade para baixar meu arquivo no demo, apenas uma escolha de uma lista preparada está disponível).
Também é importante notar que frequentemente haverá várias trilhas paralelas dentro do arquivo midi, mas como meu algoritmo até agora só funciona com uma bola, apenas uma trilha será carregada com o maior número de notas.
resultados
Depois de adicionar alguns efeitos, gravei o primeiro vídeo:
Depois de revisá-la várias
O vídeo pode mostrar uma dessincronização, percebi isso mais tarde. Se você for para a página com a demonstração , não deverá haver nenhuma fora de sincronia (o som é reproduzido apenas quando a batida é registrada).
Qual é o próximo?
Tenho planos de adicionar a capacidade de gerar esses mapas para várias bolas de uma vez. Tenho ideias de como fazer isso, testei várias opções, mas até agora todas funcionam extremamente devagar para gerar uma faixa completa.
Outra ideia minha foi adicionar novos objetos: botões, trampolins, canhões (?), Anéis ... a lista pode ser complementada :) Eles podem diversificar muito o mundo.
O código
Você pode encontrar todo o código-fonte em meu repositório.
Todas as sugestões, solicitações de pull, questionários são bem-vindos!