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.

[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 :

[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

[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.

[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.