L’objectif est d’utiliser la détection de cycles pour optimiser Lenia.
En exécutant le Jeu de la Vie à la main, on remarque qu’il est souvent possible de réduire les calculs en identifiant des structures stables, comme les oscillateurs. Il est donc raisonnable de se demander si une optimisation similaire peut être appliquée à Lenia.
- Implémentation du Jeu de la Vie
- Version naïve
- Version avec détection de cycle
- Optimisation de Lenia
- Version naïve
- Version avec FFT
- Version parallélisée sur GPU
- Version avec détection de cycle
- Complétude de Lenia (bonus)
- Écrire un algorithme génétique pour trouver un glider gun
- Trouver un glider gun
On appelle simulation ce qui est défini par :
- Un champ scalaire,
$A : L \mapsto [0, 1]$ , où$L$ est un espace euclidien muni de la distance$d$ (cette implémentation utilise un espace euclidien en deux dimensions, mais Lenia peut être implémentée dans n’importe quelle dimension) - Une fonction de croissance,
$G : [0, 1] \mapsto [-1, 1]$ - Un noyau de convolution,
$K : \mathbb{R} \mapsto [0, 1]$ , tel que
$$ \int_{0}^{2\pi}\int_{0}^{+\infty} K(r) ,dr , d\theta = 1 $$
où
- Un pas de temps
$\Delta t$
La formule pour calculer l’état de
où
Dans le cas du Jeu de la Vie de Conway :
-
$ K(r) = \begin{cases} \frac{1}{9}, & \text{si } r = 1 \text{ ou } \sqrt{2} \ 0, & \text{sinon} \end{cases} $
-
$ G(s) = \begin{cases} 1, & \text{si } s = 2 \ 0, & \text{si } s = 3 \ -1, & \text{sinon} \end{cases} $
-
$\Delta t = 1$ -
On prendra un champ scalaire
$A^0$ initialement aléatoire.
On atteint difficilement les 30 générations par seconde.
Après recherche, il apparaît que parmi toutes les structures oscillantes qui émergent naturellement avec une probabilité supérieure à une sur un milliard, la majorité oscille en seulement deux générations.
On choisit alors de les détecter pour ne pas les recalculer.
Cette optimisation permet un gain significatif en termes de performances, augmentant la vitesse de génération de 30 à 300 générations par seconde.
Lenia est une version continue du Jeu de la Vie.
Pour passer à un modèle continu, on utilise des fonctions gaussiennes :
-
$ \text{bell}(x) = \exp\left(-\frac{(x - m)^2}{2s^2}\right) $
-
$ G(v) = 2 \cdot \text{bell}(v, 0.15, 0.015) - 1 $
-
$ K_R(r) = \text{bell}\left(\frac{r}{R}, 0.5, 0.15\right) \cdot \frac{1}{S_R} $
avec $ S_R = \int_0^{2\pi} \int_0^{+\infty} \text{bell}\left(\frac{r}{R}, 0.5, 0.15\right) , dr , d\theta $
$\Delta t \rightarrow 0$
Absurdemment lente, même pour des simulations très petites.
Le gain est considérable : on peut alors augmenter la résolution de la simulation par un facteur 16 tout en conservant la même fréquence de rafraîchissement.
Pour effectuer les convolutions, on utilise l’algorithme FFT 2D qui permet de les calculer en
(explication détaillée à ajouter)
Pour qu’une cellule passe à un état non nul (vivant), elle doit avoir au moins une voisine active dans son voisinage. Or, en pratique, de nombreuses cellules sont recalculées inutilement.
Une solution possible consiste à ne calculer que les cellules susceptibles d’être modifiées à l’état suivant.
Sur une grande zone vide, la simulation devrait être rapide. On va donc définir des zones d’intérêt.
Ces zones seront de taille
On atteint ainsi l’état de l’art actuel, mais les performances pour une simulation en
(À compléter)