JeuWeb - Crée ton jeu par navigateur
[Résolu] Problème d'algo de remplissage - Version imprimable

+- JeuWeb - Crée ton jeu par navigateur (https://jeuweb.org)
+-- Forum : Discussions, Aide, Ressources... (https://jeuweb.org/forumdisplay.php?fid=38)
+--- Forum : Programmation, infrastructure (https://jeuweb.org/forumdisplay.php?fid=51)
+--- Sujet : [Résolu] Problème d'algo de remplissage (/showthread.php?tid=5361)

[Résolu] Problème d'algo de remplissage - popayan - 18-04-2011

Bonjour à tous,

Voici un petit problème auquel je suis confronté, j'ai une solution pour le moment mais elle est vraiment bancalle et très moche :malade:

Entrée de l'algo :

une table à 2 dimensions remplies de la façon suivante:
Code :
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0
0 0 0 1 1 0 1 0 0 1 0 1 1 1 0 1 0 0 0 0
0 0 0 1 0 0 0 1 1 0 1 0 0 0 0 0 1 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
0 0 1 0 1 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0
0 0 0 1 0 0 1 1 0 1 0 1 1 1 1 0 1 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

En regardant bien, on peut voir une forme dessinée avec des 1 dans ce tableau de 0.
La forme est obligatoirement fermée.

Sortie de l'algo :

le même tableau mais avec tous les 0 qui sont dans la forme remplacées par des 2.

Je donnerais mon algo après avoir eu quelques idées histoire de pas trop influencer.
Donc si vous avez des idées de comment faire ca proprement, je suis preneur Smile

RE: Problème d'algo de remplissage - Myrina - 18-04-2011

Il n'est pas nécessaire de réinventer la roue; après avoir trouvé un point de départ contenu à l'intérieur de ta figure, il suffit d'utiliser l'algorithme de la fonction fill : http://en.wikipedia.org/wiki/Flood_fill.

PS: c'est aussi le même algorithme à utiliser dans le démineur pour dévoiler l'ensemble des cases avec zéro mine aux alentour Tongue

RE: Problème d'algo de remplissage - Sephi-Chan - 18-04-2011

Par contre, ça implique de lancer l'algo en utilisant une case à l'intérieur du tracé.

RE: Problème d'algo de remplissage - niahoo - 18-04-2011

j'ai déjà donné sur ce forum du code php qui prend en entrée une map comme ça et qui donne en retour l'ensemble des zones enfermées, regroupées par tache. Tu devrais facilement pouvoir l'adapter et l'optimiser.

Tu saura par avance que tu n'as qu'une tache.

RE: Problème d'algo de remplissage - popayan - 18-04-2011

Merci Myrina! Je vais regarder de ce coté mais c'est exactement ce que je cherchais (du coup pas assez :p)

Pour partir de l'intérieur, je n'aurais pas de soucis puisque c'est moi qui dessine la forme et que ces contours sont "bornés".
ca marche nickel!
un petit rendu de test:
[Image: mini_417340Sanstitre.png]