La marche aléatoire est un concept fondamental en probabilités. À chaque pas, un agent se déplace dans une direction choisie aléatoirement. Dans cette expérience, nous appliquons ce concept à la génération procédurale de niveaux : les plateformes sont placées selon un processus pseudo-aléatoire, et vous devez naviguer à travers le résultat.
Chaque plateforme est placée à une position X et Y déterminée par :
La question mathématique : quelle est la probabilité que le parcours soit complétable ? C’est-à-dire, existe-t-il toujours un chemin de sauts valides du début à la fin ?
Ce problème peut être modélisé comme un graphe orienté : chaque plateforme est un nœud, et une arête existe entre deux plateformes si un saut est physiquement possible (distance horizontale ≤ portée maximale, distance verticale ≤ hauteur de saut). Le parcours est complétable si et seulement si un chemin existe du premier au dernier nœud.
Avec les paramètres typiques (portée = 120px, hauteur de saut = 100px), la probabilité de complétude est d’environ 92%%. Les 8%% restants contiennent un « gouffre » infranchissable quelque part dans le parcours.
Les jeux vidéo résolvent ce problème en vérifiant la complétude après génération (par un BFS/DFS sur le graphe) et en regénérant si nécessaire. C’est un cas classique de rejet en échantillonnage (rejection sampling).