[Prog] Mini-Instant Programmation : Bust-A-Move et la récursivité

Salut à tous! Aujourd'hui,  le temps de réalisation du prochain billet tend un peu vers +inf car mes vacances sont très chargées. Je vais par contre vous montrer un petit exemple pratique de la récursivité sur un problème qui m'est apparu lors de la programmation d'un projet.

Mon petit jeu, WIP, mais plus pour longtemps ^^

Je suis en train de programmer une adaptation de Bust-A-Move sur Casio Prizm (oui, une calculatrice ). Si vous voulez savoir à quoi il ressemble, c'est à côté. C'est un jeu précurseur, sorti sur arcade. On doit envoyer des bulles colorées afin de les regrouper par paquets de 3 ou plus pour les faire exploser, dans le but de vider la map.

J'ai déjà fini le placement de la bulle, la prochaine étape sera faire exploser ces dernières si j'ai formé un groupe de bulles suffisamment gros. Manque de bol, j'ai pas d'idées pour gérer lesdites bulles, c'est un type de problème jamais vu auparavant. J'avais trouvé une solution relativement peu aisée à gérer, et surtout bizarre : j'aurais recherché en suivant des cercles concentriques les bulles adjacentes. J'ai rapidement laissé tomber cette idée bancale pour une solution récursive, car je ne savais absolument pas comment gérer ces fameux cercles. Voici mon idée :

Je pars de la bulle lancée, je la marque, et je regarde ses voisines. Si une de ses voisines est de la même couleur et non marquée (cette condition est très importante, si vous l'omettez, vous ferez planter l'algorithme), je la marque, et je refais la même chose en partant de celle-ci. Si une bulle n'a pas de voisine de la même couleur non marquée, je reviens sur la bulle précédente. Si on revient sur la bulle lancée, on a fait le tour, on a fini la recherche, on peut vérifier si on doit effacer les bulles, et on agit.

Cette méthode est programmable de deux façons différentes: soit le backtracking ou la méthode récursive. Le backtracking est une méthode où dans une boucle on réitère nos opérations en ajoutant notre position dans une pile à chaque fois qu'on avance, et en récupérant la précédente si on doit reculer. La méthode récursive est un poil différente : on appèle la fonction recursive si on doit avancer, et on quitte l'appel actuel si on doit reculer. La pile d'appel sera similaire à celle du backtracking. Le backtracking étant déjà été fait pour un autre projet, je décide donc de faire la 2e option, cela sera ma première proche avec du récursif. Ca n'est pas forcément pas la meilleure solution, mais ici, ça marche, et j'étais content de voir que ça pouvait me donner le résultat escompté! A vrai dire, cette méthode peut paraître gourmande, mais j'pense avoir trouvé une alternative encore plus lente: je parcoure le tableau pour trouver des bulles adjacentes à celles déjà marquées jusqu'à que j'en trouve plus. Ca, c'est la pire idée que j'ai pu avoir! Ici, ca n'aurait pas trop de problèmes de lenteur car j'ai une map de 8*13 bulles, mais imaginez sur une map de 200*402!

Pour finir ce "mini-billet", je vous dirai que pour un problème, il ne faut pas hésiter à chercher des idées qui peuvent paraître farfelues, mais possibles!