itch.io

Je comprends bien ce que tu me décris, c’était la première approche que j'ai tentée :-) J'avais deux problèmes majeurs avec les résultats qu'elle me donnait :

• ça ressemble de très près à une technique de marche aleatoire, et comme les images de Wikipédia l'illustre bien le chemin qui en résulte a tendance à s'amasser en certains endroits tout en laissant d'autre pans de la carte complètement vides
• je ne pouvais pas garantir que le chemin fabrique était le plus court, et finir en deux-trois mouvements un niveau qui aurait du en prendre une vingtaine ça me signifiait que je n'avais pas bien le contrôle de la difficulté des niveaux générés

Le deuxième point était le plus important pour moi, et sans faire de raisonnements et preuves mathématiques sur mon processus de construction je ne me voyais pas pouvoir créer cette garantie de manière constructive. Je suis donc passé par la solution de secours du bidouillage algorithmique qui consiste à faire un parcours en largeur de la carte à chaque modification pour s'assurer de ne pas avoir réduit la longueur de la solution sans le vouloir.

Vu que ça me donnait facilement accès à tous les chemins existant depuis un point de la carte, j'ai aussi pu me débarrasser de la marche aléatoire et me contenter de placer des rochers au hasard de manière uniforme, ce qui a fortement augmenter la probabilité d'utiliser toute la map ou presque. Une bonne façon de s'en assurer pourrait être de considérer un chemin en plusieurs étapes plutôt qu'une solution en un seul segment, mais le coût en calcul et complexité de code dépasse surement le temps que j'avais à consacrer à ce problème pendant la Procjam...

(et pas de raycasting non plus dans ma première approche parce que si c'est un outil utile quand on vit dans un monde continu, moi je travaillais sur une grille discrète qui est facile à explorer de manière exhaustive)