Le petit monde de Pac-man

En 1980 sortait un des jeux les plus mythiques de l’univers des jeux vidéos: Pac-man. Le principe de ce jeu est plutôt simple: vous incarnez une personnage qui ressemble à une petite pastille jaune et vous vous déplacez dans un labyrinthe dans lequel sont disposées des petites gommes que vous devez toutes gobé sans jamais vous faire attraper par 4 terrifiants fantômes. Bon, inutile que je décrive plus ce jeu mythique car vous y avez sans doute déjà joué. Si ce n’est pas le cas, vous allez réparer toute de suite cette faute grave en jouant à la version que Google avait créé et mise sur sa page d’accueil à l’occasion de l’anniversaire des 30 ans de ce jeu (attention, ce jeu est plus addictif que Flappy bird et 2048 réunis).

Écran de jeu du tout premier Pac-Man (image issue de l’article Pac-Man Wikipédia anglais)

Mais quel est le rapport entre ce jeu vidéo et les mathématiques ? C’est simple: tel M. Jourdain, Pac-man fait de la topologie sans le savoir.

Téléportation

Il faut se souvenir qu’une des caractéristiques du déplacement de Pac-Man dans le labyrinthe, c’est que sur la gauche de l’écran de jeu, il y a un tunnel qui, lorsqu’il est emprunté par Pac-Man, le téléporte sur la droite de l’écran du jeu (et vice-versa) ! D’un point de vue du jeu, cela donne plus de possibilités d’échapper aux fantômes, mais d’un point de vue mathématique, cette propriété nous permet d’affirmer que Pac-man vit sur un cylindre ! (ou sur un rouleau de PQ, c’est selon…). Afin de comprendre ce fait, nous allons d’abord donner une explication visuelle, puis une explication mathématique dans laquelle nous ferons un peu de topologie.

Explication visuelle

Étant donné que le bord gauche de l’écran est directement relié au bord droit de l’écran, on peut donc les identifier. Imaginez donc que l’écran soit une feuille de papier, et imaginez qu’on mette de la colle (segments verticaux bleus ci-dessous) sur le bord gauche et sur le bord droit de cette feuille puis qu’on colle le bord gauche sur le bord droit en les superposant. Voici ce qu’on obtiendrait:

Ainsi, après collage des extrémités, on se rend compte que Pac-man se déplace bel et bien sur un cylindre !

Explication mathématique

L’explication mathématique est moins évidente et requiert, comme dit plus haut, quelques notions de topologie que je vais essayer d’esquisser ici. Une démonstration rigoureuse du fait que Pac-Man vit sur un cylindre est disponible plus bas dans un fichier PDF pour les plus courageux d’entre vous.

Pour montrer que Pac-man vit sur un cylindre, on va procéder en deux étapes:
1) On commence par définir un ensemble qui représente le monde de Pac-man, c’est-à-dire dans lequel le bord gauche et le bord droit sont « identiques ».
2) On montre ensuite que cet ensemble est semblable à un cylindre du point de vue topologique. Une autre façon de le dire est qu’on peut obtenir un cylindre à partir de cet ensemble juste en le déformant « continûment ».

Étape n°1: On commence par modéliser l’écran sur lequel se déplace Pac-man en considérant qu’il s’agit du carré . Pour exprimer mathématiquement le fait que les points du bord gauche sont identiques à ceux du bord droit, on utilise la notion de relation d’équivalence. On définit sur la relation notée telle que pour tout , :

Les points P et Q sont équivalents. L’ensemble {P,Q} correspond donc à un point de l’ensemble quotient.

Le monde de Pac-man est alors l’ensemble (dit quotient) des classes d’équivalences pour cette relation, c’est-à-dire l’ensemble qu’on note dont chaque élément est un paquet qui regroupe tous les points du carré qui sont équivalents entre eux. Dans l’ensemble quotient, les points du bord gauche et du bord droit sont donc confondus.

Étape n°2: L’espace quotient est muni d’une topologie naturelle, appellée topologie quotient. Muni de cette topologie, on peut montrer que cet espace est alors compact.

On définit le cylindre comme étant l’ensemble des points de tels que et qu’on munit de la topologie induite par celle de .

Nous avons donc deux objets: d’un côté le monde de Pac-man et de l’autre un cylindre . Il s’agit de montrer que ces deux objets sont identiques d’un point de vue topologique (on dit homéomorphes). Pour cela, il faut montrer qu’il existe une bijection de l’un dans l’autre qui est continue et dont l’application inverse est elle aussi continue (on parle d’homéomorphisme). On définit la fonction suivante:

où représente la classe d’équivalence de . On peut montrer que est bijective et continue sans trop de difficultés. Pour montrer que est bicontinue, c’est-à-dire que son inverse  est aussi continue, on utilise le lemme classique suivant:

Soit une application continue. Si est un espace compact et si est un espace séparé, alors l’image d’un fermé de par est un fermé de .

Comme est compact et que est séparé, alors l’image de tout fermé par est un fermé. Puisque est bijective, cela veut dire que l’image réciproque d’un fermé par est encore un fermé et donc que est continue ! Ainsi, est un homéomorphisme et le monde de Pac-man est bien homéomorphe à un cylindre.

Pour les lecteurs familiers avec cette si belle branche des mathématiques qu’est la topologie (les autres, laissez tomber… je vous aurai prévenus !), les détails de cette preuve sont disponibles dans le fichier suivant:

Démonstration mathématique du fait que Pac-man vit sur un cylindre

Variante

On pourrait imaginer que lorsque Pac-man traverse le bord gauche de l’écran, il soit téléporté sur le bord droit et qu’en plus il soit renversé (symétrie centrale par rapport au centre de l’écran). Voici ce qu’on aurait (j’ai ajouté un oeil à Pac-man pour mieux voir le renversement):Pour représenter cela schématiquement, on mettra des flèches en sens opposés sur chacun des bords :Lorsqu’on colle le bord gauche sur le bord droit de façon à ce que les flèches se superposent dans le même sens, on obtient alors un ruban de Möbius !D’un point de vue mathématique, cela reviendrait à définir sur le carré la relation d’équivalence telle que pour tout , . On peut montrer que l’ensemble quotient obtenu est bel et bien homéomorphe à un ruban de Möbius.

Pac-man change de monde

Il y a eu de nombreuses versions de Pac-man, mais en 2007, le créateur du Pac-man originel développa une suite qui s’appelle Pac-man Championship Edition.

La particularité de cette nouvelle version est, qu’en plus d’être téléporté sur le bord droit quand il traverse le bord gauche, Pac-man est téléporté sur le bord du haut quand il traverse le bord du bas. Voici la représentation de l’écran avec les identifications des bords de cette nouvelle version de Pac-man:

On peut montrer que ce monde est alors équivalent (homéomorphe) à un tore:Pac-man a donc changé de monde: il ne vit désormais plus sur un cylindre, mais sur un tore !

Remarque: Pour voir géométriquement que ce monde est bien un tore, faites comme ce qu’on avait fait plus haut pour le cylindre: imaginez que le carré est une feuille de papier, collez les flèches bleues l’une sur l’autre, ce qui donne un cylindre, puis collez ensuite les flèches rouges l’une sur l’autre et vous obtenez bien un tore:

Animation extraite de l’article Wikipedia anglais sur le tore.

Autres variantes

On peut s’amuser à imaginer toutes les possibilités de téléportation sur l’écran. Les voici résumées ci-dessous, avec pour chaque configuration l’objet topologique qui lui est homéomorphe:

(Je n’ai pas pu/su dessiner le plan projectif réel, ne m’en voulez pas, mais vous pouvez le visualiser ici… déjà que j’en ai chié avec le ruban de Möbius et la bouteille de Klein, même en m’inspirant d’un code déjà existant…)

Les jeux vidéo et la topologie

Il n’y a pas que Pac-man qui vit sur un cylindre ou un tore. Il y a de nombreux jeux vidéos dans lesquels les bords de l’écran communiquent entre eux. Par exemple, dans le (très ancien) jeu Asteroïds, le monde est un tore. Dans le jeu super Mario Bros 2, il y a certains tableaux verticaux où les bords gauche et droit de l’écran communiquent: ce sont donc des cylindres (regardez par exemple les 25 premières secondes de cette vidéo. On voit clairement Luigi passer de gauche à droite comme Pac-Man !).  Dans le jeu de course F-Zero GX, l’un des circuits est un ruban de Möbius !

Il y a de nombreux autres exemples de mondes cylindriques, toriques ou sphériques dans l’univers du jeu vidéo mais, à ma connaissance, il n’y a pas encore eu de jeu vidéo qui se déroule sur une bouteille de Klein…

A quand un jeu vidéo qui se déroule sur une bouteille de Klein ?

Pour finir, une petite anecdote: dans le jeu vidéo Minecraft, l’écran d’accueil comporte une phrase différente à chaque lancement. Voici ce qu’on peut lire parfois:

C’est amusant car d’un point de vue topologique, le monde de Minecraft n’est pas homéomorphe à une sphère puisque, par exemple, il existe des trous (cavernes, etc.) !