l'algo FloodFill

Salut à tous

Voilà le projet sur lequel je travaille actuellement. Il s’agit d’un jeu de puzzle sur Amstrad CPC

L’idée est parti d’un jeu que j’ai trouvé sur le Net qui se base sur l'algorithme du FloodFill. Pour ceux qui ne connaisse pas, c'est un algo qui permet de remplir une zone délimitée par des contours. On l’utilise pour dans les logiciels de dessin pour remplir des zones par exemple. Mais il est également utilisé dans des jeux comme le démineur.

Voici un lien pour découvrir cet algo : https://fr.wikipedia.org/wiki/Algorithme_de_remplissage_par_diffusion#:~:text=L'algorithme%20de%20remplissage%20par,d'images%20matricielles%20comme%20Paint.

Et voici le jeu que j’ai découvert et qui m’a inspiré pour commencer mon projet : 

https://unixpapa.com/floodit/

L’idée c’est de remplir la grille du jeu avec une seule couleur. Le remplissage démarre toujours avec la case en haut à gauche.

J’ai alors attaqué de faire un proto en Lua/Love2d pour comprendre l’algo et tester un peu le gameplay.

J’ai fais deux versions de l’algo, en récursif et non récursif. L’idée était de pouvoir le reprogrammer sur le CPC. Or ici il est fortement déconseillé d’utiliser la récursivité sur des processeurs 8 bit avec très peu de ressources mémoire. J’ai donc essayé de porter l’algo en assembleur sur le Z80 et de tester si ça fonctionnait.

J’ai démarré le projet par le codage d’une routine pour afficher la grille du jeu qui est defini avec 2 parametre, sa largeur et sa hauteur.

Maintenant il fallait remplir la grille de façon aléatoire. Pour ça il a fallu coder un algo pour faire des nombres random entre 1 et nombre de couleurs à choisir (6 maximum dans le jeu). Je me suis bien cassé la tête dessus, mais je suis parvenu à faire une génération de grille aléatoire.

Puis il a fallu mettre en place un système pour interagir, notamment pour choisir la couleur de remplissage. Pour commencer, j’ai juste affiché les couleurs et je les ai associées à une touche. Comme on peut le voir sur le gif ci dessous.

Je peux maintenant changer la couleur de la case en haut à gauche. J’ai à présent tous les éléments pour me mettre à coder et tester l’algo de floodFill. J’ai commencé par tester la direction Nord. 

La difficulté ici à été de trouver un moyen de  stocker les coordonnées de la prochaine cellule à tester et à gérer une pile. C’est en même temps la partie la plus intéressante. Je suis donc partie sur plusieurs idées et celle que j’ai retenue est de gérer les coordonnées des cases sur un octet. J’utilise le premier quartet, c'est-à-dire les 4 premiers bits de l’octet (poids fort)  pour les coordonnées en x et il me reste les 4 derniers bits (poids faible) pour les coordonnées en y. Cette astuce me permet de stocker sur un octet les coordonnées et donc, c’est bien plus simple pour la gestion de l’algo. 

Mais il y a une contrainte, elle me limite dans la taille de la grille. je ne peux en effet afficher une grille de plus de 16*16, car avec 4 bits je suis limité à 16 en valeur par quartet. Pour mon cas c’est même largement suffisant car en réalité, on le verra un peu plus tard, je ne peux afficher à l’écran des grilles plus grande que 12*10 cellules (8 *16 pixels).

Après plusieurs jours à tester l’algo j’ai pu faire un premier prototype jouable. C’est une version très épurée, sans vraiment de boucle de jeu, mais permettant de tester le moteur , de générer et de remplir des grilles. C'était le minimum à faire pour savoir si c’était faisable sur CPC.

Maintenant que cette étape est validée je peux me lancer dans la réalisation plus poussée du jeu.

Ce sera la pour plus tard dans un prochaine devlog

Vous pouvez suivre l’évolution sur mon Trello ici : https://trello.com/b/XSxSzE2Q/pocky

et bien sûr tester la dernière version jouable sur ma page Itch.io