Discussion :

[Aspic]

Bonjour à tous,

J'espère que je suis sur le bon forum

Je recherche un algorithme (pseudo-code m'irait très bien) permettant de détecter une "pièce" dans une matrice 2D. La matrice 2D représente un terrain de jeu (le jeu Sokoban) composé de murs, de caisses, de goals et du sol.
Un pièce est une zone entourée de murs (peu importe ce qu'il y a à l'intérieur de la zone) et comportant UNE SEULE entrée d'une SEULE case.

On pourrait éventuellement partir de la case en (6; 17) qui est un goal pour démarrer l'algo.

Par exemple, dans l'image en pièce jointe, je souhaite trouve un algo permettant de détecter la zone en rouge qui est une pièce remplit de goals formée d'une seule entrée située en (7; 13) (la case haut-gauche est en (0;0) ).

Auriez vous des pistes ?

Merci d'avance

[tbc92]

Avant de parler algo, il faut s'assurer que le besoin est totalement défini.

A partir d'un emplacement, on cherche à définir une pièce...
Si on part de la case qui est en diagonale (au dessus à gauche) du personnage Mario, quelle est la pièce autour de cette case ?

On peut choisir la pièce avec toute la partie droite du puzzle, ou bien la 'pièce' avec les 3 branches qui partent vers le centre ou le bas du puzzle.

En définissant mieux le besoin, ça peut aider à réfléchir à l'algorithme.

[dourouc05]

En réfléchissant « à voix haute »… J'aurais tendance à penser sous forme de graphe : un élément de ta matrice est un nœud, relié à toutes les cases directement accessibles ; l'étiquette de chaque nœud correspondrait à son remplissage (vide, caisse, bouton-poussoir de destination ; les murs ne sont simplement pas représentés). Ainsi, tu représentes l'information la plus importante : les zones accessibles (la connexité du graphe). Ensuite, tu peux agréger les cases en pièces : si une case a strictement plus de deux voisins, alors ces trois ou quatre cases font partie d'une pièce (cas particulier : les coins, indistinguables d'un couloir en comptant simplement les nœuds connectés). À voir ce que ça donne en y réfléchissant plus.

[picodev]

Bonjour,

Considère ton sol comme un graphe, les noeuds étant les cases de ton damier. Deux noeuds sont reliés par une arrête s'ils représentent deux cases sols côte à côte. Si tu cherches «Un pièce est une zone entourée de murs (peu importe ce qu'il y a à l'intérieur de la zone) et comportant UNE SEULE entrée d'une SEULE case» cela revient à chercher les points d'articulation de ce graphe. La composante biconnexe de ce graphe contenant les goals à laquelle tu ajoutes un ou plusieurs points d'articulation consécutifs sera une telle pièce. Cela fonctionnera si tous tes goals sont dans une seule pièce ...
Par exemple en rouge les points d'articulations et en bleu la plus grande des zones qui correspondrait à ta définition :

[tbc92]

.../...
si une case a strictement plus de deux voisins, alors ces trois ou quatre cases font partie d'une pièce (cas particulier : les coins, indistinguables d'un couloir en comptant simplement les nœuds connectés). À voir ce que ça donne en y réfléchissant plus.

Non, ça ne marche pas.
Prend les 5 cases en haut du dessin proposé par Aspic.
Ces 5 cases forment une pièce, mais pourtant, on n'a pas de cas avec moins de 3 voisins, à part les coins bien sur.

[Aspic]

Avant de parler algo, il faut s'assurer que le besoin est totalement défini.

Oui tu as raison, pour être plus précis :
1) L'entrée d'une pièce comme je l'ai défini, ne peut se faire que par UNE SEULE direction (Haut, bas, gauche ou droite). Ce qui implique que la case (7; 9) ne peut pas être l'entrée car on pourrait y accéder par la droite et par le haut (losange noir sur le schéma).

2) Si on considère la case en haut-gauche de Mario donc la (7; 10), alors la pièce associée est dessinée jaune

3) Pour simplifier, tous les goals seront dans la même pièce mais c'est vrai qu'il se peut qu'il y ait 2 pièces avec par exemple 4 goals dans la 1ère et 2 goals dans la 2nd.

=> Le but ultime est donc de détecter la chambre qui contient tous les goals (en vert sur le schéma). Pour la représenter au niveau du code, j'ai besoin des coordonnées de son entrée ainsi que :
a) soit les coordonnées du coin haut-gauche de la pièce ET le nombre de lignes et de colonnes de la pièce
b) soit les coordonnées du coin haut-gauche ET du coin bas-droite de la pièce
(les murs étant compris car j'en ai besoin pour la suite...)

Dans mon exemple, la pièce recherchée est en jaune : l'entrée de la pièce des goals est effectivement en (7; 10). Le coin haut gauche est en (5;10), le coin bas-droite en (9; 18). Sa taille est de 5 lignes par 9 colonnes. Mea culpa, je me suis trompé dans mon premier post

Ensuite, tu peux agréger les cases en pièces : si une case a strictement plus de deux voisins, alors ces trois ou quatre cases font partie d'une pièce (cas particulier : les coins, indistinguables d'un couloir en comptant simplement les nœuds connectés). À voir ce que ça donne en y réfléchissant plus.

Effectivement, je suis d'accord avec ta solution mais on fait comment justement avec les coins ? Impossible de les détecter en regardant les voisins...

La composante biconnexe de ce graphe contenant les goals à laquelle tu ajoutes un ou plusieurs points d'articulation consécutifs sera une telle pièce. Cela fonctionnera si tous tes goals sont dans une seule pièce ...

Je ne suis un pro en théorie des graphes, j'ai des notions de base. Je ne comprends pas ce qu'est une composante biconnexe et en quoi elle va permettre de détecter la pièce.

J'ai bien compris qu'il fallait représenter le niveau comme un graphe avec pour les noeuds, les cases du niveau mais je sèche pour la détection de toutes les cases appartenant à la pièce des goals.

J'espère avoir pu être plus précis sur mon problème.

Merci d'avance.

[picodev]

...
Je ne suis un pro en théorie des graphes, j'ai des notions de base. Je ne comprends pas ce qu'est une composante biconnexe et en quoi elle va permettre de détecter la pièce.

J'ai bien compris qu'il fallait représenter le niveau comme un graphe avec pour les noeuds, les cases du niveau mais je sèche pour la détection de toutes les cases appartenant à la pièce des goals.
...

C'est juste une question de modélisation et de vocabulaire.

Les nœuds de ton graphe seront les cases sols.

Sur ton image, ton graphe possède 2 composantes connexes : l'extérieur et l'intérieur du labyrinthe. L'intérieur du labyrinthe est la composante connexe qui contient les goals (parcours en profondeur à partir d'une case contenant un goal, tous les nœuds visités seront l'intérieur de ton labyrinthe).

Un point d'articulation est un nœud qui si on le retire du graphe scinde le graphe en plusieurs parties indépendantes (= pour aller de l'une à l'autre tu es obligé de passer par ce point d'articulation). Cela correspond à l'entrée d'une pièce (=si on bouche l'entrée tu ne peux plus ni sortir ni entrer dans ta pièce).

Si tu trouves tous les points d'articulation de ton graphe, les nœuds qui n'en sont pas peuvent se regrouper en composantes connexes qui auront la propriété (pour simplifier) que de chaque nœud tu peux atteindre n'importe quel autre nœud par au moins deux chemins différents. Cela signifie que même si tu rajoutes une cloison entre deux cases sols (=retirer l'arrête qui les lie) tu pourra toujours aller d'une à l'autre (=une définition possible d'une pièce). C'est ce qu'on appelle une composante biconnexe. D'ailleurs je me suis trompé sur le dessin, la case où se trouve Mario est une pièce ne faisant pas partie de la pièces des goals.

Je pense que tu pourras trouver pas ma de littérature sur les algorithmes permettant de trouver et les points d'articulation et les composantes biconnexes d'un graphe. Il faudra évidemment les adapter à ton cas (par exemple ici).

...
3) Pour simplifier, tous les goals seront dans la même pièce mais c'est vrai qu'il se peut qu'il y ait 2 pièces avec par exemple 4 goals dans la 1ère et 2 goals dans la 2nd.
...

Alors il va falloir se creuser les méninges pour bien modéliser tout ça ...

[Aspic]

Désolé pour l'absence de 3 jours, je suis pas mal occupé en ce moment

C'est juste une question de modélisation et de vocabulaire.

Les nœuds de ton graphe seront les cases sols.

Sur ton image, ton graphe possède 2 composantes connexes : l'extérieur et l'intérieur du labyrinthe. L'intérieur du labyrinthe est la composante connexe qui contient les goals (parcours en profondeur à partir d'une case contenant un goal, tous les nœuds visités seront l'intérieur de ton labyrinthe).

Un point d'articulation est un nœud qui si on le retire du graphe scinde le graphe en plusieurs parties indépendantes (= pour aller de l'une à l'autre tu es obligé de passer par ce point d'articulation). Cela correspond à l'entrée d'une pièce (=si on bouche l'entrée tu ne peux plus ni sortir ni entrer dans ta pièce).

Si tu trouves tous les points d'articulation de ton graphe, les nœuds qui n'en sont pas peuvent se regrouper en composantes connexes qui auront la propriété (pour simplifier) que de chaque nœud tu peux atteindre n'importe quel autre nœud par au moins deux chemins différents. Cela signifie que même si tu rajoutes une cloison entre deux cases sols (=retirer l'arrête qui les lie) tu pourra toujours aller d'une à l'autre (=une définition possible d'une pièce). C'est ce qu'on appelle une composante biconnexe. D'ailleurs je me suis trompé sur le dessin, la case où se trouve Mario est une pièce ne faisant pas partie de la pièces des goals.

Merci pour l'explication, c'est très clair et j'ai bien compris

Je pense que tu pourras trouver pas ma de littérature sur les algorithmes permettant de trouver et les points d'articulation et les composantes biconnexes d'un graphe. Il faudra évidemment les adapter à ton cas (par exemple ici).

1) Alors si j'ai bien compris, la première étape est de représenter le labyrinthe (zone intérieure, la zone extérieure en fait n'existe pas pour le jeu...) sous forme de graphe non orienté ? Si oui, à partir de quel point dois-je partir pour établir le graphe ? N'importe quel goal ? ou n'importe quelle case ?

2) Ensuite, une fois le graphe établi, je dois trouver un algorithme permettant de détecter les composantes biconnexes du graphe

3) Et après, trouver les points d'articulation du graphe.

J'ai un doute car d'après ce que j'ai lu, il faut d'abord trouver les points d'articulation pour déterminer les composantes biconnexes du graphe. Je suis un peu perdu

Et, en admettant que j'arrive à trouver ces fameux points d'articulation, comment vais-je savoir lequel est le bon ? (en partant du principe qu'il n'y a qu'une seule pièce de goal mais potentiellement d'autre pièces dans le labyrinthe...)

Merci

[picodev]

1) Alors si j'ai bien compris, la première étape est de représenter le labyrinthe (zone intérieure, la zone extérieure en fait n'existe pas pour le jeu...) sous forme de graphe non orienté ? Si oui, à partir de quel point dois-je partir pour établir le graphe ? N'importe quel goal ? ou n'importe quelle case ?

J'imagine que lorsque tu charges un niveau tu n'as pas d'indications si une case appartient ou non à l'intérieur ou l'extérieur du jeu. Le seul moyen de les différencier est de connaître au moins un nœud/case qui est à l'intérieur. Ce nœud/case est forcément un nœud/case goal. Donc faire un parcours en profondeur à partir de ce nœud/case te permettra de déterminer la composante connexe qui contient les goals = l'intérieur. Les autres nœuds/cases seront soit des murs ou l'extérieur. Attention au cas où le plateau serait scindé en deux, deux parties indépendantes comportant chacune des goals.

2) Ensuite, une fois le graphe établi, je dois trouver un algorithme permettant de détecter les composantes biconnexes du graphe
3) Et après, trouver les points d'articulation du graphe.

J'ai un doute car d'après ce que j'ai lu, il faut d'abord trouver les points d'articulation pour déterminer les composantes biconnexes du graphe. Je suis un peu perdu

Et, en admettant que j'arrive à trouver ces fameux points d'articulation, comment vais-je savoir lequel est le bon ? (en partant du principe qu'il n'y a qu'une seule pièce de goal mais potentiellement d'autre pièces dans le labyrinthe...)

Non en premier lieu tu trouves les points d'articulation et ensuite tu détermines les composantes biconnexes.
Chaque nœud va devoir avoir un champ qui détermine à quelle composante biconnexe il appartient. Au départ tu initialises tous ces champs à indéterminé. Ensuite tant qu'il y a des nœuds indéterminé tu fais un parcours en profondeur à partir de ce nœud en t'arrêtant aux points d'articulations. À chaque fois que tu recommences un parcours à partir d'un nœud indéterminé tu crées une nouvelle pièce.
Si seule la pièce avec les goals t'intéresse (à supposer qu'il n'y en ait qu'une) alors tu ne t'intéresseras qu'aux nœuds/cases indéterminés contenant des goals ... si tu es obligé de faire plusieurs parcours alors tu auras plusieurs pièces goals.
Si tu n'as pas de points d'articulation alors tout ton plateau est la pièce goal ...
Une pièce goal peut avoir plusieurs entrées (autant que de points d'articulation différents rencontrés lors du parcours) ...

[Aspic]

D'accord, je pense avoir compris, je vais essayer de voir ce que je peux faire.
Et puis je reviendrais poster mes résultats et éventuels problèmes
Merci pour tes explications.

[Aspic]

Bonjour,

Je repasse par là pour dire que j'ai finalement réussi à récupérer les points d'articulation pour détecter la zone de goal mais je me demandais comment faire dans les deux cas suivants :

1) détecter plusieurs zones de goals avec une seule entrée par zone
2) détecter une zone de goal mais avec 2 entrées

Si jamais quelqu'un repasse par là, ca serait cool

Merci

[picodev]

Bonjour,

Je repasse par là pour dire que j'ai finalement réussi à récupérer les points d'articulation pour détecter la zone de goal mais je me demandais comment faire dans les deux cas suivants :

Bonjour,
cool ...

1) détecter plusieurs zones de goals avec une seule entrée par zone

Si seule la pièce avec les goals t'intéresse (à supposer qu'il n'y en ait qu'une) alors tu ne t'intéresseras qu'aux nœuds/cases indéterminés contenant des goals ... si tu es obligé de faire plusieurs parcours alors tu auras plusieurs pièces goals.

2) détecter une zone de goal mais avec 2 entrées

Si jamais quelqu'un repasse par là, ca serait cool

Merci

Si tu n'as pas de points d'articulation alors tout ton plateau est la pièce goal ...
Une pièce goal peut avoir plusieurs entrées (autant que de points d'articulation différents rencontrés lors du parcours) ...

[Aspic]

Si seule la pièce avec les goals t'intéresse (à supposer qu'il n'y en ait qu'une) alors tu ne t'intéresseras qu'aux nœuds/cases indéterminés contenant des goals ... si tu es obligé de faire plusieurs parcours alors tu auras plusieurs pièces goals.

Je t'avoue que je n'ai pas du tout compris...
Voilà un exemple avec 2 zones de goal :
http://webdocs.cs.ualberta.ca/~games.../screen.10.jpg

Et un autre avec une zone de goal mais avec 2 entrées qui sont des points d'articulation :
http://webdocs.cs.ualberta.ca/~games...s/screen.7.jpg

Pour ce 2ème cas, j'arrive bien à récupérer ces deux points d'articulation mais c'est après que je coince...

Mon algo pour trouver les cases appartenant à la zone de goal dans le cas où il y a UNE SEULE entrée est :
pour chaque point d'articulation trouvé,
retirer ce point du graphe
faire un BFS à partir d'un goal.
Toutes les cases trouvées pendant ce BFS appartiennent à la zone de goal. Évidemment , il faut aussi vérifier que tous les goals se trouvent parmi ces cases. Après je prends la zone qui a le plus de cases car ca m'arrange dans le cas du Sokoban.

Mais dans le cas avec 2 entrées, mon algo ne marche plus.

Merci d'avance