Résoudre des labyrinthes avec Photoshop, c’est possible

J’ai récemment découvert qu’on pouvait utiliser Photoshop pour résoudre des labyrinthes. Quelle surprise ! Cela prend moins d’une minute (sauf si on se perd dans les menus de Photoshop…) et ne requiert que des fonctionnalités basiques. Vous vous demandez comment c’est possible ? Ça tombe bien, on va expliquer tout ça.

Pour nous aider, il faut se demander ce qu’est un labyrinthe — ne paniquez pas, cette question n’a rien de philosophique (pour une fois). C’est un bloc qui a une entrée, une sortie, et des tas de culs-de-sac. Bien. À quoi cela nous mène d’écrire une telle évidence ? À prendre conscience qu’on peut dire qu’en somme, un labyrinthe, c’est un chemin principal (de l’entrée à la sortie, donc la « solution ») entouré par deux blocs de murs qui vont un peu dans tous les sens.

Et là c’est intéressant : quand on traverse le chemin principal, on peut faire comme si on était entouré à gauche et à droite par un mur — auquel cas le labyrinthe serait évident, il suffirait d’aller « toujours tout droit ». Bien sûr ce mur a plein de trous, qui mènent vers d’autres chemins, mais ce sont des distractions. On pourrait même s’imaginer qu’ils n’existent pas, qu’on est entouré de deux blocs solides (et non percés de plein de chemins).

Cela se comprend si on s’imagine comment on crée un labyrinthe. Le plus simple est de partir d’un carré plein, de « percer » la solution puis de lui rajouter des tas d’embranchements qui ne mènent nulle part.

Labyrinthe de départ. Sauriez-vous le résoudre sans la solution ?
Si on traverse le chemin solution du labyrinthe en ignorant les autres, c’est comme si on était entouré par un gros bloc massif sur notre gauche, et un sur notre droite ; les autres chemins ici sont floutés pour montrer qu’ils ne sont pas pertinents.

Et c’est exactement ceci qui va nous aider à résoudre notre labyrinthe sur Photoshop : on va boucher les trous qui ne mènent nulle part.

Poser les fondations

On doit d’abord séparer les deux « blocs massifs » à droite et à gauche. Comment on le fait ? Il suffit de remarquer qu’ils tiennent chacun en un seul bloc et ne se touchent pas : évidemment qu’ils ne se touchent pas, car sinon le chemin solution serait bloqué ! Sur Photoshop, il suffit d’utiliser l’outil Baguette Magique en activant l’option « Pixels contigus ». Cela aura pour effet, en cliquant sur un mur, d’étendre la sélection dans toutes les directions, jusqu’à rencontrer une autre couleur — ici, du blanc.

Regardons donc ce qui se passe si l’on clique à n’importe quel endroit d’un mur :

Ici, le mur sélectionné reste toujours sur notre gauche lorsqu’on va de haut en bas

Tiens donc, on retrouve un des fameux blocs dont j’ai parlé ! Chose intéressante : il touche l’entrée (en haut à droite) et la sortie (en bas à droite) que d’un seul côté (du côté gauche). Du coup ce qu’on va faire, c’est remplir cette sélection en rouge, puis sélectionner l’autre côté des murs (toujours avec la Baguette Magique) et la remplir en bleu :

Hehe, on voit presque la solution apparaître, à la frontière entre le rouge et le bleu. Surprenant ? C’est en fait cohérent avec l’explication vue plus haut : la partie rouge et la partie bleue correspondent chacune à un bloc qui contient des culs-de-sac. Si seulement on pouvait boucher les trous…

Colmater

Et bien oui, on peut ! On va avoir besoin des options Dilater et Contracter la sélection. Dilater, c’est étendre la sélection dans toutes les directions, avec une certaine taille. Observons sur un nouvel exemple ce qui se passe si on Dilate une sélection avec des tailles de plus en plus grandes (au lieu d’utiliser du rouge, on va directement remplir la sélection en noir) :

C’est comme un objet qui… se dilate. À un moment donné, les régions qui étaient trop proches finissent par fusionner. Alors, si on Contracte la sélection pour revenir à la taille initiale, les régions restent connectées :

On a en quelque sorte bouché les trous qui ne sont pas trop gros. Et c’est ce qu’on va faire pour remplir les murs rouges et bleus : faire grossir la sélection d’une taille suffisante pour que tous les chemins internes (= faux chemins) soient « avalés », puis lui faire retrouver sa taille originale. Illustrations sur le mur rouge, en n’affichant que lui pour plus de clarté :

Et donc si on fait ça aussi pour le bleu, et qu’on met un peu de transparence pour voir le labyrinthe, voici le résultat :

TADA !

Tuto labyrinthe #DIY

Vous avez Photoshop ? Super, vous pouvez suivre ces instructions pour essayer vous-mêmes !

  1. Prendre l’outil Baguette magique et cocher l’option « Pixels contigus ».
  2. Cliquer sur une partie du mur, et la remplir en rouge sur un nouveau calque.
  3. Cliquer sur la partie restante, et la remplir en bleu sur un autre calque.
  4. Obtenir la sélection du calque rouge (Ctrl/Cmd + clic) ; puis Dilater la sélection de 4 pixels (Menu Sélection > Modifier > Dilater) ; puis la Contracter de 4 pixels.
  5. Remplir le calque rouge avec cette nouvelle sélection.
  6. Répéter les opérations 4 et 5 sur le calque bleu.
  7. Et voilà !

Ce qui est assez remarquable, c’est que cette technique marche sur une très grande variété de labyrinthes — il faut juste adapter la taille des dilatations et contractions pour qu’elles correspondent à notre image. Ce qui compte c’est que les murs forment deux blocs qui ne se touchent pas. Il y a de quoi s’amuser.

Par contre, telle quelle, cette technique ne pourra pas fonctionner sur les labyrinthes circulaires où l’arrivée se situe au centre (les murs forment un seul bloc). Avec suffisamment de motivation, et pas mal de bricolage, on peut quand même y arriver — mais cela demanderait encore trop d’explications. Je le laisse en challenge aux plus motivés (« preuve laissée au lecteur ») 😉


Supplément technique (traitement d’images) #engineersonly

Il faut considérer que l’image est binaire, où les murs valent 1 et le fond 0. Ce qu’on fait avec la baguette magique, c’est extraire et isoler les composantes connexes. Par exemple, un algorithme exploitant la structure de données Union Find marche très bien. Ensuite, ce qu’on fait avec les sélections relève du champ appelé Morphologie mathématique. En l’occurrence, l’option Dilatation correspond à une… dilatation, et l’option Contraction à une érosion. La composition des deux, dans cet ordre, est l’opérateur qu’on appelle Fermeture morphologique.

Donc une description haut niveau de l’algorithme que j’ai expliqué avec Photoshop serait :

  1. Extraire les composantes connexes.
  2. On note e = l’épaisseur des chemins (en pixels).
  3. Sur chaque composante connexe, appliquer une fermeture morphologique de rayon e/2.
Partager l'article

Une réponse sur “Résoudre des labyrinthes avec Photoshop, c’est possible”

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *