This was a lot of fun to play! I was surprised by how challenging the puzzles generated by this algorithm can be. I had plenty of moments where I had to really think about how to solve the puzzle, and those "a-ha!" moments felt very satisfying!
Content que ça ait plu :-) Je ne suis pas assez bon en pixel art pour sortir des designs de ma tête, donc j'ai effectivement gardé la map de la route de glace de Crystal ouverte pour me servir d'inspiration.
Oui, tous les niveaux sont générés durant le fondu au noir qui les précède. Je viens de rajouter une explication du fonctionnement dans la description ; mais en quelques mots l'algorithme place des rochers au hasard, calcule le chemin le plus long et essaye d'ajouter ou de retirer des obstacles tant que ça rallonge la solution la plus courte.
(donc pas de raycasting, mais beaucoup de pathfinding pour essayer de s'assurer un niveau jouable et intéressant)
Ok, je vois, c'est hyper intéressant ce que tu as rajouté en description. J'aurai jamais pensé c'etait aussi complexe sous le "capot".
Perso je pensai que tu utilisais du raycasting car tu aurais pu :
-choisir une case de départ
-lancer un rayon a partir de celle ci
-placer un bloc "virtuel" sur la trajectoire du rayon qui le ferait dévié de 90°
-faire apparaitre un "vrai" bloc juste a côté du bloc virtuel en conséquence
-recommencer X fois jusqu'a placer la sortie
-le tout saupoudré de magie noir procédurale pour déterminer l'angle du rayon et l'endroit ou il doit dévier
Je sais pas si jme fait bien comprendre...
Voila ! Un dessin vaut milles mots :) Je dit pas que c'est la solution idéale, mais j'ai immédiatement cru que tu avais procédé ainsi. Un problème, de multiples solutions...
edit: j'ai mal placé l'un des rochers sur le dessin... je suis pas encore reveillé
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)
Waw tu m'apprend des tonnes de trucs la. Hmm, je crois qu'il serait possible de réduire le chaos qu'implique la méthode raycasting en lui imposant un certains nombre de contraintes, pour obtenir une répartition la plus homogène possibles des blocs de glaces. Tu me donne presque envie d'essayer de coder un proto...
En tout cas ta méthode de génération actuelle marche du tonnerre de dieu, et c'est plaisant a jouer, ça ne fait aucuns doutes. Même si elle semble un peu trop issue de l'esprit tordu d'un diplômé de polytechnique : )
← Return to game
Comments
Log in with itch.io to leave a comment.
I like to press the "solve this level automatically" button and watch the little blob zip around.
This was a lot of fun to play! I was surprised by how challenging the puzzles generated by this algorithm can be. I had plenty of moments where I had to really think about how to solve the puzzle, and those "a-ha!" moments felt very satisfying!
These puzzles are suprisingly tricky, great results for such a simple algorithm.
Bon sang j'ai eu des flashbacks de Pokémon cristal, bien joué :)
Du coup c'est généré procéduralement ? Tu utiliserai pas du raycasting des fois ?
Content que ça ait plu :-) Je ne suis pas assez bon en pixel art pour sortir des designs de ma tête, donc j'ai effectivement gardé la map de la route de glace de Crystal ouverte pour me servir d'inspiration.
Oui, tous les niveaux sont générés durant le fondu au noir qui les précède. Je viens de rajouter une explication du fonctionnement dans la description ; mais en quelques mots l'algorithme place des rochers au hasard, calcule le chemin le plus long et essaye d'ajouter ou de retirer des obstacles tant que ça rallonge la solution la plus courte.
(donc pas de raycasting, mais beaucoup de pathfinding pour essayer de s'assurer un niveau jouable et intéressant)
Ok, je vois, c'est hyper intéressant ce que tu as rajouté en description. J'aurai jamais pensé c'etait aussi complexe sous le "capot".
Perso je pensai que tu utilisais du raycasting car tu aurais pu :
-choisir une case de départ
-lancer un rayon a partir de celle ci
-placer un bloc "virtuel" sur la trajectoire du rayon qui le ferait dévié de 90°
-faire apparaitre un "vrai" bloc juste a côté du bloc virtuel en conséquence
-recommencer X fois jusqu'a placer la sortie
-le tout saupoudré de magie noir procédurale pour déterminer l'angle du rayon et l'endroit ou il doit dévier
Je sais pas si jme fait bien comprendre...
Voila ! Un dessin vaut milles mots :) Je dit pas que c'est la solution idéale, mais j'ai immédiatement cru que tu avais procédé ainsi. Un problème, de multiples solutions...
edit: j'ai mal placé l'un des rochers sur le dessin... je suis pas encore reveillé
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 :
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)
Waw tu m'apprend des tonnes de trucs la. Hmm, je crois qu'il serait possible de réduire le chaos qu'implique la méthode raycasting en lui imposant un certains nombre de contraintes, pour obtenir une répartition la plus homogène possibles des blocs de glaces. Tu me donne presque envie d'essayer de coder un proto...
En tout cas ta méthode de génération actuelle marche du tonnerre de dieu, et c'est plaisant a jouer, ça ne fait aucuns doutes. Même si elle semble un peu trop issue de l'esprit tordu d'un diplômé de polytechnique : )