👩‍👩‍👧 🙇🏻 👷🏼 Création d'un générateur de puzzle procédural 🌹 👩🏾‍💼 🐰

Cet article décrit le générateur de niveau pour mon jeu de puzzle Linjat . Un article peut être lu sans préparation, mais il est plus facile à assimiler si vous jouez sur plusieurs niveaux. J'ai posté le code source sur github ; tout ce qui est discuté dans l'article se trouve dans le src/main.cc

Exemple de plan de publication:

Linjat est un jeu de logique dans lequel vous devez fermer tous les nombres et points de la grille avec des lignes.
Les puzzles sont générés de manière procédurale en utilisant une combinaison de solveur, de générateur et d'optimiseur.
Le solveur essaie de résoudre les énigmes comme le ferait une personne et attribue à chaque puzzle une note d'intérêt.
Le générateur de puzzle est conçu de sorte qu'il est possible de changer facilement une partie du puzzle (numéro) et en même temps toutes les autres parties (points) changent de sorte que le puzzle reste résoluble.
L'optimiseur de casse-tête résout à plusieurs reprises les niveaux et génère de nouvelles variations par rapport aux plus intéressantes du moment.

Les règles

Pour comprendre le fonctionnement du générateur de niveau, vous devez malheureusement comprendre les règles du jeu. Heureusement, ils sont très simples. Le puzzle se compose d'une grille contenant des carrés vides, des nombres et des points. Un exemple:

Le but du joueur est de tracer une ligne verticale ou horizontale à travers chacun des nombres, sous réserve de trois conditions:

Une ligne passant par un numéro doit avoir la même longueur que le numéro.
Les lignes ne peuvent pas se croiser.
Tous les points doivent être fermés par des lignes.

Exemple de solution:

Hourra! La conception du jeu est prête, l'interface utilisateur est implémentée et il ne reste plus qu'à trouver plusieurs centaines de bons puzzles. Et pour de tels jeux, il n'est généralement pas logique d'essayer de créer de tels puzzles manuellement. Ceci est un travail informatique.

Prérequis

Qu'est-ce qui rend le puzzle de ce jeu bon? J'ai tendance à croire que les jeux de réflexion peuvent être divisés en deux catégories. Il y a des jeux dans lesquels vous explorez un espace d'état complexe du début à la fin (par exemple, Sokoban ou Rush Hour ), et dans lesquels il peut ne pas être évident quels états existent dans le jeu. Et il y a des jeux dans lesquels tous les états sont connus dès le début, et nous façonnons progressivement l'espace d'état en utilisant le processus d'élimination des états inutiles (par exemple, Sudoku ou Picross ). Mon jeu tombe définitivement dans la deuxième catégorie.

Les joueurs ont des exigences très différentes pour ces différents types de puzzles. Dans le second cas, ils s'attendent à ce que le casse-tête ne puisse être résolu que par déduction, et qu'ils n'auront jamais besoin de revenir en arrière / deviner / essayer et l'erreur ^[0] ^[1] .

Il ne suffit pas de savoir si un puzzle ne peut être résolu que par la logique. De plus, nous devons en quelque sorte comprendre à quel point les puzzles créés sont bons. Sinon, la plupart des niveaux ne seront que des scories triviales. Dans une situation idéale, ce principe pourrait également être utilisé pour créer une courbe de progression fluide, de sorte que, à mesure que le joueur progresse dans le jeu, les niveaux deviennent progressivement plus difficiles.

Solveur

La première étape pour répondre à ces exigences est de créer un solveur de jeu optimisé à cet effet. Le solveur de retour arrière vous permet de déterminer rapidement et avec précision si le puzzle est résoluble; en outre, il peut être modifié pour déterminer si la solution est unique. Mais il ne peut pas donner une idée de la complexité du puzzle, car les gens les résolvent différemment. Le solveur doit imiter le comportement humain.

Comment une personne résout-elle ce casse-tête? Voici quelques mouvements évidents que le didacticiel en jeu enseigne:

Si un point peut être atteint à partir d'un seul numéro, pour fermer un point, vous devez tracer une ligne à partir de ce numéro. Dans cet exemple, le point ne peut être atteint que par les trois, mais pas par les quatre:

Et cela conduit à cette situation:
Si la ligne ne rentre pas dans une direction, elle doit être placée dans une autre. Dans l'exemple ci-dessus, les quatre ne peuvent plus être positionnés verticalement, nous savons donc que ce sera horizontal:
S'il est connu que la ligne de longueur X doit être dans une certaine position (verticale / horizontale) et qu'il n'y a pas assez d'espace vide pour placer une ligne de X cellules vides des deux côtés, alors vous devez couvrir plusieurs carrés au milieu. Si les quatre étaient trois dans l'exemple ci-dessus, nous ne saurions pas s'il s'étend complètement à droite ou à gauche. Mais nous saurions que la ligne devrait couvrir deux carrés du milieu:

Un raisonnement similaire est la base même du jeu. Le joueur cherche des moyens d'étirer une petite ligne, puis examine à nouveau le champ, car il peut lui donner des informations pour faire une autre conclusion logique. Créer un solveur qui suit ces règles sera suffisant pour déterminer si une personne peut résoudre le puzzle sans revenir en arrière.

Cependant, cela ne nous dit rien sur la complexité ou l'intérêt du niveau. Outre la solvabilité, nous devons en quelque sorte quantifier la complexité.

Une première idée évidente pour la fonction de notation: plus vous avez besoin de mouvements pour résoudre le puzzle, plus il est difficile. C'est probablement une bonne métrique dans d'autres jeux, mais le mien, très probablement, est plus important que le nombre de coups autorisés qu'un joueur a. Si un joueur peut tirer 10 conclusions logiques, il en trouvera très probablement une très rapidement. S'il n'y a qu'un seul coup droit, cela prendra plus de temps.

C'est-à-dire que, en première approximation, nous avons besoin que l'arbre de décision soit profond et étroit: il y a une longue dépendance des mouvements du début à la fin, et à chaque instant il n'y a qu'un petit nombre de façons de remonter la chaîne ^[2] .

Comment détermine-t-on la largeur et la profondeur d'un arbre? Une solution unique au casse-tête et à l'évaluation de l'arbre créé ne donnera pas de réponse exacte. L'ordre exact dans lequel les mouvements sont effectués affecte la forme de l'arbre. Nous devons considérer toutes les solutions possibles et faire avec elles quelque chose comme l'optimisation pour les meilleurs et les pires cas. Je suis familier avec la technique de recherche grossière des graphiques de recherche dans les jeux de puzzle , mais pour ce projet, je voulais créer un solveur en un seul passage, et non pas une recherche exhaustive. En raison de la phase d'optimisation, j'ai essayé de m'assurer que le temps d'exécution du solveur n'était pas mesuré en secondes, mais en millisecondes.

J'ai décidé de ne pas le faire. Au lieu de cela, mon solveur ne fait pas un mouvement à la fois, mais résout le puzzle en couches: en prenant un état, il trouve tous les mouvements valides qui peuvent être effectués. Il applique ensuite tous ces mouvements en même temps et recommence dans un nouvel état. Le nombre de couches et le nombre maximum de déplacements trouvés sur une couche sont ensuite utilisés comme valeurs approximatives de la profondeur et de la largeur de l'arbre de recherche dans son ensemble.

Voici comment résoudre l'un des énigmes difficiles avec ce modèle. Les lignes pointillées sont des lignes étirées sur cette couche du solveur, les lignes pleines sont celles qui n'ont pas changé. Les lignes vertes ont la bonne longueur, les rouges ne sont pas encore terminées.

Le problème suivant est que tous les mouvements effectués par le joueur sont créés égaux. Ce que nous avons énuméré au début de cette section n'est que du bon sens. Voici un exemple de règle de déduction plus complexe, dont la recherche nécessitera un peu plus de réflexion. Considérez le champ suivant:

Les points en C et D ne peuvent être couverts que par les cinq et les quatre du milieu (et pas un seul numéro ne peut couvrir les deux points en même temps). Cela signifie que les quatre au milieu doivent couvrir un point sur deux et ne peuvent donc pas être utilisés pour couvrir A. Par conséquent, le point A doit fermer les quatre dans le coin inférieur gauche.

De toute évidence, il serait insensé de considérer cette chaîne de raisonnement comme la simple conclusion "ce point ne peut être atteint qu'à partir de ce nombre". Est-il possible de donner plus de poids à ces règles plus complexes dans la fonction d'évaluation? Malheureusement, dans un solveur basé sur des couches, cela n'est pas possible, car il n'est pas garanti de trouver une solution au moindre coût. Ce n'est pas seulement un problème théorique - en pratique, il arrive souvent qu'une partie du champ puisse être résolue soit par un seul argument complexe, soit par une chaîne de mouvements beaucoup plus simples. En fait, un solveur basé sur les couches trouve le chemin le plus court et non le moins coûteux, et cela ne peut pas être reflété dans la fonction d'évaluation.

En conséquence, je suis arrivé à cette décision: j'ai changé le solveur de sorte que chaque couche se compose d'un seul type de raisonnement. L'algorithme contourne les règles de raisonnement dans un ordre approximatif de complexité. Si la règle trouve des mouvements, ils sont appliqués et l'itération se termine et l'itération suivante démarre la liste depuis le tout début.

Ensuite, la décision se voit attribuer une évaluation: chaque couche se voit attribuer des coûts en fonction d'une règle qui y a été utilisée. Cela ne garantit toujours pas que la solution sera la plus économique, mais si les pondérations sont sélectionnées correctement, l'algorithme ne trouvera pas au moins une solution coûteuse si elle est bon marché.

De plus, cela ressemble beaucoup à la façon dont les gens résolvent les énigmes. Ils essaient d'abord de trouver des solutions faciles et ne commencent à bouger activement leur cerveau que s'il n'y a pas de mouvements simples.

Générateur

La section précédente a déterminé si un niveau particulier était bon ou mauvais. Mais cela ne suffit pas, nous devons toujours générer des niveaux pour que le solveur puisse les évaluer. Il est très peu probable qu'un monde généré aléatoirement soit résoluble, sans parler d'intéressant.

L'idée principale (ce n'est en aucun cas nouveau) est l'utilisation alternative du solveur et du générateur. Commençons par un puzzle, qui est probablement insoluble: placez simplement deux à cinq nombres dans des carrés aléatoires de la cellule:

Le solveur fonctionne jusqu'à ce qu'il puisse se développer davantage:

Ensuite, le générateur ajoute plus d'informations au puzzle sous la forme d'un point, après quoi l'exécution du solveur continue.

Dans ce cas, le point ajouté au solveur n'est pas suffisant pour un développement ultérieur. Ensuite, le générateur continuera d'ajouter de nouveaux points jusqu'à ce qu'il satisfasse le solveur:

Et puis le solveur continue son travail habituel:

Ce processus se poursuit soit jusqu'à ce que le puzzle soit résolu, soit jusqu'à ce qu'il reste plus d'informations à ajouter (par exemple, lorsque chaque cellule qui peut être atteinte à partir du nombre contient déjà un point).

Cette méthode ne fonctionne que si les nouvelles informations ajoutées ne peuvent rendre incorrectes les conclusions formulées précédemment. Cela serait difficile à faire lors de l'ajout de nombres à la grille ^[3] . Mais l'ajout de nouveaux points au champ a cette propriété; au moins pour les règles de raisonnement que j'utilise dans ce programme.

Où l'algorithme doit-il ajouter des points? Au final, j'ai décidé de les ajouter à l'espace vide, qui peut être fermé dans l'état initial avec autant de lignes que possible, afin que chaque point cherche à donner le moins d'informations possible. Je n'ai pas essayé de placer spécifiquement le point à l'endroit où il serait utile de progresser dans la résolution du puzzle au moment où le solveur se coince. Cela crée un effet très pratique: la plupart des points au début du puzzle semblent complètement inutiles, ce qui rend le puzzle plus difficile qu'il ne l'est vraiment. Si tout cela est beaucoup de mouvements évidents qu'un joueur peut faire, mais pour une raison quelconque, aucun d'entre eux ne fonctionne pas correctement. En conséquence, il s'est avéré que le générateur de puzzle se comportait un peu comme un cochon.

Ce processus ne crée pas toujours une solution, mais il est assez rapide (environ 50-100 millisecondes), donc pour générer un niveau, vous pouvez simplement le répéter plusieurs fois. Malheureusement, il crée généralement des puzzles médiocres. Dès le début, il y a trop de mouvements évidents, le champ se remplit très rapidement et l'arbre de décision s'avère plutôt superficiel.

Optimiseur

Le processus décrit ci-dessus a créé des puzzles médiocres. À la dernière étape, j'utilise ces niveaux comme base pour le processus d'optimisation. Cela fonctionne comme suit.

L'optimiseur crée un pool qui contient jusqu'à 10 options de puzzle. Le pool est initialisé avec un nouveau puzzle aléatoire généré. À chaque itération, l'optimiseur sélectionne un puzzle dans le pool et effectue sa mutation.

La mutation supprime tous les points, puis modifie légèrement les nombres (c'est-à-dire diminue / augmente la valeur d'un nombre sélectionné au hasard ou déplace le nombre vers une autre cellule de la grille). Vous pouvez appliquer plusieurs mutations au champ en même temps. Ensuite, nous exécutons le solveur dans le mode de génération de niveau spécial décrit dans la section précédente. Il ajoute suffisamment de points au puzzle pour qu'il redevienne résoluble.

Après cela, nous redémarrons le solveur, cette fois en mode normal. Pendant cette exécution, le solveur surveille a) la profondeur de l'arbre de décision, b) la fréquence du besoin de différents types de règles, c) la largeur de l'arbre de décision à différents moments. Le puzzle est évalué sur la base des critères décrits ci-dessus. La fonction d'évaluation préfère les solutions profondes et étroites, et les niveaux de complexité accrue ajoutent également plus de poids aux énigmes dans lesquelles des règles de raisonnement plus complexes sont nécessaires.

Ensuite, un nouveau puzzle est ajouté à la piscine. Si la piscine contient plus de 10 puzzles, le pire est éliminé.

Ce processus est répété plusieurs fois (environ 10 000 à 5 000 itérations m'ont pris). Après cela, la version la mieux notée du puzzle est enregistrée dans la base de données du niveau du puzzle. Voici à quoi ressemble la progression du meilleur puzzle en un seul cycle d'optimisation:

J'ai essayé d'utiliser d'autres façons de structurer l'optimisation. Dans une version, un recuit simulé a été utilisé; d'autres étaient des algorithmes génétiques avec diverses opérations de croisement. Aucune des solutions n'a fonctionné aussi bien qu'un algorithme naïf avec un pool d'options remontant au sommet.

Solution unique unique

Lorsqu'un puzzle a une solution unique et unique, une difficulté intéressante se pose. Est-il possible de permettre au joueur de supposer qu'il existe une solution et de tirer des conclusions sur cette base? Serait-il juste que le générateur de casse-tête suggère que le joueur le fasse?

Dans un article sur HackerNews, j'ai dit qu'il y avait quatre options pour aborder cette situation:

Déclarez le caractère unique de la solution dès le début et forcez le générateur à créer des niveaux qui nécessitent ce type de raisonnement. C'est une mauvaise décision car elle complique la compréhension des règles. Et ce sont généralement les détails que les gens oublient.
Ne garantissez pas l'unicité d'une décision: prenez potentiellement de nombreuses décisions et prenez-les toutes. En fait, cela ne résout pas le problème, mais le repousse.
Supposons simplement qu'il s'agit d'un événement très rare, qui dans la pratique n'est pas important. (Il s'agit de la solution qui a été utilisée dans la mise en œuvre initiale.)
Modifiez le générateur de casse-tête afin qu'il ne génère pas de casse-tête dans lesquels la connaissance de l'unicité de la solution serait utile. (Probablement la bonne solution, mais nécessitant un travail supplémentaire.)

Au départ, j'ai choisi cette dernière option, et c'était une terrible erreur. Il s'est avéré que je n'ai pris en compte qu'une seule façon dont l'unicité de la solution a conduit à une fuite d'informations, et c'est en fait assez rare. Mais il y en a d'autres; l'un d'eux était en fait présent à tous les niveaux que j'ai générés et conduisait souvent au fait que la solution devenait triviale. Par conséquent, en mai 2019, j'ai changé les modes Hard et Expert en utilisant la troisième option.

Le cas le plus ennuyeux est un diable avec une ligne pointillée dans ce champ:

Pourquoi un joueur rusé peut-il tirer une telle conclusion? Un diable peut couvrir n'importe laquelle des quatre cases voisines. Aucun d'entre eux n'a de points, ils ne doivent donc pas être couverts par une ligne. Et le carré ci-dessous n'a pas de superpositions avec d'autres nombres. S'il n'y a qu'une seule solution, cela devrait être le cas lorsque d'autres nombres couvrent les trois carrés restants et que les deux ferment le carré en dessous.

La solution consiste à ajouter quelques points supplémentaires lors de la reconnaissance de tels cas:

Un autre cas courant est un tiret avec une ligne pointillée dans ce champ:

Les carrés à gauche et en haut des deux ne sont pas différents. Aucun d'entre eux n'a de point, et aucun ne peut être joint à partir d'un autre numéro. Toute solution dans laquelle un diable couvre le carré supérieur aura une solution correspondante dans laquelle il ferme le carré de gauche, et vice versa. S'il y avait une seule solution unique, cela ne pouvait pas être le cas, et le diable aurait dû couvrir le carré inférieur.

J'ai décidé ce type de boîtier de la manière suivante: "si ça fait mal, alors ne le touchez pas." Solver a appliqué cette règle à un stade précoce de la liste des priorités et a attribué un poids négatif à ces mouvements. Les puzzles avec cette fonctionnalité sont généralement ignorés par l'optimiseur, et les quelques restants sont ignorés au stade de la sélection finale des niveaux pour le jeu publié.

Ce n'est pas une liste complète. Pendant les tests de jeu avec une recherche délibérée d'erreurs, j'ai trouvé de nombreuses autres règles pour des solutions uniques. Mais la plupart d'entre eux semblaient rares et ils étaient suffisants à trouver, donc ils n'ont pas grandement simplifié le jeu. Si quelqu'un résout le puzzle en utilisant un tel raisonnement, je ne le blâmerai pas.

Conclusion

Initialement, le jeu a été développé comme une expérience dans la génération procédurale de puzzles. La conception et le générateur du jeu sont allés de pair, de sorte que les techniques elles-mêmes sont difficiles à appliquer directement aux autres jeux.

La question à laquelle je n'ai pas de réponse: l'investissement de tels efforts dans la génération procédurale s'est-il justifié?Les commentaires des joueurs sur la conception des niveaux ont été très controversés. Dans les commentaires positifs, on a généralement dit que certains trucs délicats se font toujours sentir dans les puzzles. Dans la plupart des critiques négatives, ils m'ont écrit que le jeu n'avait pas un gradient de complexité.

J'ai encore quelques puzzles à leurs balbutiements, et j'ai tellement aimé le générateur que j'utilise probablement une approche procédurale similaire pour eux. Je ne changerai qu'une chose: dès le début, je procéderai à des tests de jeu actifs avec la recherche d'erreurs.

Remarques

[0] Ou, du moins, il me semblait. Mais quand j'ai regardé les joueurs en direct, près de la moitié d'entre eux ont juste fait des suppositions, puis ont répété à travers eux. Oh bien.

[1] Les lecteurs de mon article devraient également lire l'article Résoudre le démineur et le rendre meilleur Magnus Hoff.

[2] Je préciserai que la profondeur / l'étroitesse d'un arbre est une métrique que je considérais comme importante pour mon jeu, et pas pour toutes les autres énigmes. Par exemple, il y a un bon argument selon lequel le casse-tête de l'heure de pointe est intéressant s'il a plusieurs chemins pour résoudre presque, mais pas exactement la même longueur. Mais c'est arrivé parce que Rush Hour est un jeu pour trouver la solution la plus courte, et pas n'importe quelle solution.

[3] Hors ajout d'unités. Il n'y avait pas de points dans la première version du puzzle, et le plan prévoyait que le générateur ajoute des unités si nécessaire. Mais cela semblait trop restrictif.

Création d'un générateur de puzzle procédural