Des règles formelles.
Des propriétés démontrables.
AURELIS articule géométrie discrète, théorie des graphes et modélisation par contraintes. Son objet d’étude est l’espace des configurations admissibles : ce qui constitue un état valide, les transformations autorisées et les propriétés que l’on peut établir sur leurs résultats.
Dans Pixaelo, la question centrale est dynamique : caractériser des transferts de pixels sous conservation des couleurs et capacité finie. Dans Tidilo, elle est combinatoire : qualifier des arrangements géométriques sous contraintes et leur unicité canonique.
Système de transitions à états finis
Problème de satisfaction de contraintes
Une propriété n’a de sens que relativement à un modèle. AURELIS distingue l’admissibilité d’une configuration, la légalité d’une transformation, l’existence d’une solution, son éventuelle unicité et la mesure de l’expérience de résolution. Ces questions se complètent et disposent chacune de critères explicites.
La dynamique discrète
des pixels.
Un puzzle Pixaelo associe une image cible à une répartition de pixels colorés et à une réserve de capacité fixe. L’analyse porte sur un système de transitions : les actions modifient la distribution spatiale sans créer de matière, sans changer la palette et sans déplacer les pixels déjà correctement positionnés.
Définir l’état avant de raisonner sur les gestes.
Le support du dessin est un ensemble fini Ω de cellules actives d’une grille entière. Sa cardinalité N mesure le nombre de pixels à placer. Les coordonnées décrivent la géométrie ; la palette K décrit les classes de couleurs. La valeur 0 représente une place vide et n’est pas une couleur à reconstituer.
- T
- La cible chromatique : la couleur attendue dans chaque cellule active.
- B
- La configuration courante du dessin : couleurs présentes et emplacements libres.
- 𝓡
- Le vecteur des cases physiques de réserve. C est sa capacité ; r désigne son nombre de cases occupées.
- σ
- La sélection d’interaction : une source, une couleur et un ensemble de pixels actuellement manipulables.
La configuration physique s et la sélection σ jouent des rôles distincts. Sélectionner change l’intention d’interaction ; cela ne retire aucun pixel. L’historique des actions décrit, lui, des états antérieurs. Il ne fait pas partie de l’image cible et ne modifie pas l’inventaire des couleurs.
Cette séparation permet de formuler des propriétés sans les confondre avec l’affichage. Le zoom, le déplacement de la caméra, la visibilité du coffre ou une animation d’arrivée changent la présentation du même état logique. Ils ne constituent pas des transferts supplémentaires.
L’admissibilité du départ est un problème de contraintes.
La définition d’un nouveau puzzle doit respecter simultanément son support, sa palette et ses quantités. À l’état initial, le masque des cellules actives correspond à celui de la cible, la réserve est vide et chaque couleur est présente dans la quantité attendue. Les nouveaux départs sont entièrement à résoudre : aucun pixel actif n’est déjà à sa bonne place.
Ces exigences ont des conséquences combinatoires. Si une couleur occupe n_c positions de la cible, ses pixels doivent pouvoir être répartis hors de ces positions au départ. Une condition nécessaire est donc n_c ≤ N − n_c. Une dominante chromatique trop forte peut rendre incompatible l’exigence d’inventaire exact avec celle d’un départ sans pixel correct.
La validité structurelle d’un état initial et l’existence d’une trajectoire de résolution sont deux questions logiques distinctes. La première décrit les conditions à satisfaire par une configuration. La seconde porte sur les transitions qui la relient à la cible. Une image visuellement plausible ne suffit pas à établir ces propriétés.
Deux voisinages pour deux fonctions différentes.
Le voisinage orthogonal relie deux cellules partageant un côté. Le voisinage à huit directions ajoute les contacts par les coins. Pour un même ensemble de pixels, ajouter les arêtes diagonales peut réunir plusieurs composantes orthogonales ; cela ne crée aucune cellule supplémentaire.
Les mêmes quatre cellules forment quatre composantes par les côtés et une seule composante lorsque les contacts diagonaux sont admis.
4 composantes connexes
Sélection : connexité à huit voisins.
La sélection initiale d’un groupe sur le dessin relie les pixels mobiles de même couleur par les côtés et les coins. Un pixel déjà correct est exclu de ce groupe ; il ne sert pas de liaison entre deux groupes sélectionnables. Après un transfert partiel, le reliquat peut rester sélectionné : il ne représente pas nécessairement une nouvelle composante maximale du plateau.
Destination : connexité à quatre voisins.
Pour une couleur c, une zone de destination se définit sur les cellules dont la cible vaut c et qui sont soit libres, soit déjà correctement remplies. Le déplacement peut traverser cette région par les côtés ; seules ses cellules libres reçoivent des pixels. Une cellule occupée par une mauvaise couleur interrompt ce passage. Les pixels corrects peuvent donc relier des destinations sans devenir des sources mobiles.
La topologie est une partie de la définition de la mesure. Un nombre de composantes calculé à quatre voisins et un nombre calculé à huit voisins ne caractérisent pas le même graphe. La comparaison de deux analyses exige de conserver cette convention, ainsi que l’ensemble des pixels considéré.
Un transfert est une transformation sous préconditions.
Une action effective associe une source sélectionnée à une destination explicite. Sur le dessin, la source ne contient que des pixels mal placés de la couleur choisie. Dans la réserve, elle correspond à des pixels réellement présents. Une destination sur le dessin doit être libre et demander cette même couleur ; une destination dans la réserve doit disposer de capacité.
Le nombre p de pixels transportés est strictement positif pour un transfert effectif. Il est borné par la quantité sélectionnée et par le nombre f d’emplacements compatibles disponibles. Lorsque la destination ne peut recevoir tout le groupe, le transfert porte sur une partie de celui-ci. Cette granularité permet de raisonner avec un espace de stockage réellement fini.
La réserve contient 36 cases dans la campagne et 12 dans le tutoriel. Son ouverture visuelle ne change pas C. Une tentative sans destination admissible ne constitue pas une transition physique ; elle ne crée ni place, ni pixel, ni progression. L’aperçu d’un déplacement et son application appartiennent à deux opérations distinctes.
La couleur se déplace ; l’inventaire se conserve.
Pour chaque couleur c, on compte les pixels présents sur le dessin et ceux présents dans la réserve. Leur somme doit rester égale à la quantité de cette couleur dans la cible. Ce bilan s’applique indépendamment à chaque classe chromatique : une quantité totale correcte ne compense pas un déficit d’une couleur par l’excédent d’une autre.
Notons L le nombre de pixels corrects sur le dessin, M le nombre de pixels non vides encore mal placés et r le nombre de pixels stockés. Les pixels constituent une partition de taille N. Si h désigne le nombre de cellules actives vides, les égalités suivantes caractérisent tout état valide du modèle.
L’égalité h = r exprime un couplage spatial précis : déplacer un pixel vers la réserve libère une case active, et remplir une case depuis la réserve consomme un pixel stocké. Le rangement de la réserve n’autorise donc aucune création de capacité abstraite. La forme des zones libres et la répartition des couleurs déterminent les usages possibles de cet espace.
L’application logique d’un transfert conserve ce bilan avant et après l’action. Son animation peut montrer plusieurs arrivées successives, mais l’état évalué ne dépend pas du nombre d’images affichées ni de la durée de la cascade. Cette distinction entre transformation et représentation évite qu’une interruption visuelle devienne une action supplémentaire.
Une dynamique orientée par une fonction de potentiel.
Les règles de transfert donnent une propriété de monotonie : pour une même définition, sans annulation ni remplacement d’état, un pixel correct reste correct. L’ensemble des positions acquises ne peut que grandir. Un transfert vers la réserve laisse L constant ; un placement sur la cible l’augmente du nombre de pixels reçus.
Le potentiel Φ pondère les pixels encore mal placés sur la grille et ceux qui attendent dans la réserve. Les trois types de transferts autorisés ont les variations ci-dessous. La variable p désigne toujours le nombre de pixels effectivement déplacés.
| Transfert | ΔL | ΔM | Δr | ΔΦ |
|---|---|---|---|---|
| Dessin → réserve | 0 | −p | +p | −p |
| Réserve → cible | +p | 0 | −p | −p |
| Dessin → cible | +p | −p | 0 | −2p |
Ainsi, chaque transfert effectif fait strictement décroître une quantité entière positive ou nulle. Le graphe des transferts dirigés ne contient pas de cycle tant qu’aucun état antérieur n’est réintroduit. Une sélection, un aperçu ou une tentative refusée laissent ce potentiel inchangé.
L’annulation possède une autre sémantique : elle restaure une configuration passée et peut donc augmenter Φ. Elle reste extérieure à cette propriété des transferts vers l’avant. Le potentiel décrit l’orientation du modèle ; l’atteignabilité de la cible et l’effort ressenti par le joueur constituent des questions supplémentaires.
Préciser ce que démontre un chemin de résolution.
La cible terminale exige le dessin exact et une réserve vide. Pour établir la résolubilité d’une configuration donnée, un témoin est une suite finie d’actions dont chaque transition respecte les règles et dont l’état final satisfait cette condition. Le certificat porte sur une relation entre un départ, une définition de puzzle et un chemin admissible.
Plusieurs propositions doivent rester distinctes. L’existence demande au moins un chemin. L’unicité du chemin demanderait que les autres suites possibles ne constituent pas des résolutions distinctes selon une équivalence explicitée. L’optimalité impose encore un objectif : minimiser le nombre de transferts, le volume de pixels transportés ou l’utilisation maximale de la réserve conduit à des critères différents.
Le dessin final peut être fixé de manière unique par T alors que les ordres de transfert demeurent nombreux. La détermination de l’image ne démontre donc pas l’unicité de la trajectoire. De même, une trace valide décrit un coût observé pour cette trace ; elle ne fournit pas automatiquement le minimum parmi toutes les trajectoires admissibles.
La validation d’un départ et la validation d’un témoin sont séparables : l’une établit les invariants de la configuration, l’autre vérifie des transformations successives. Leur concordance permet d’attacher une propriété de résolubilité au bon objet mathématique, sans la déduire de l’apparence de l’image.
Distinguer taille de l’espace et coût d’une vérification.
À support, palette et capacité fixés, l’espace des configurations physiques est fini. Une borne de comptage très large consiste à autoriser indépendamment chaque couleur ou le vide dans chacune des N cellules actives et des C cases de réserve. Les invariants d’inventaire et les contraintes de placement réduisent ensuite cet ensemble.
Cette borne mesure un univers de configurations, pas le nombre d’états réellement parcourus par un moteur. Elle ne classe pas, à elle seule, la difficulté algorithmique du jeu. Les propriétés de monotonie, les symétries, la structure des régions et les contraintes de conservation influencent fortement la géométrie des états admissibles.
Contrôler un témoin de k transitions consiste à établir la légalité de ses actions et la satisfaction de l’état terminal. Ce problème n’exige pas de compter toutes les résolutions. En revanche, démontrer une minimalité requerrait une information supplémentaire sur les chemins concurrents ou une borne inférieure atteinte par le témoin.
Le nombre de pixels, la longueur d’une trace et le coût d’une interaction tactile sont ainsi trois échelles différentes. Une analyse de performance doit préciser ce qu’elle mesure : calcul logique, traitement d’un événement, dessin d’une image ou durée globale sur un appareil donné.
Décrire le puzzle par un vecteur d’observables.
La structure d’un dessin ne se résume pas à sa résolution. AURELIS considère des familles de mesures portant sur le volume, la répartition chromatique, les régions cibles et la fragmentation des groupes. Les composantes isolées, la taille du groupe dominant et la distribution des tailles caractérisent des formes d’interaction différentes.
Ces mesures géométriques sont définies avec leur voisinage. Les analyses historiques à quatre voisins conservent cette signification ; elles ne deviennent pas des mesures à huit voisins par changement d’intitulé. Sur un même ensemble de pixels, le graphe et sa convention de connexité font partie de la donnée mesurée.
Des observables propres à un chemin.
Pour un témoin de k transferts, p_t est la quantité transportée à l’action t et r_t l’occupation de la réserve après cette action. Les grandeurs ci-dessous décrivent ce témoin. Elles peuvent différer entre deux résolutions du même dessin. Le maximum d’occupation inclut l’état initial r₀ ; pour un nouveau départ, r₀ = 0.
| Observable | Expression | Interprétation |
|---|---|---|
| Transferts par pixel | k / N | Granularité de la trace rapportée au volume du dessin. |
| Pixels transportés | Σ p_t | Volume total déplacé, qui peut dépasser N lorsque la réserve sert d’intermédiaire. |
| Transferts unitaires | #{t : p_t = 1} / k | Part des actions portant sur un seul pixel, même si la sélection de départ était plus grande. |
| Occupation maximale | max₀≤t≤k(r_t) / C | Pression maximale sur la capacité physique de la réserve. |
| États saturés | #{t : r_t = C} / k | Fréquence des configurations pleines après transfert ; il ne s’agit pas d’une proportion de temps. |
| Transferts partiels | p_t < |S_t| | Actions dans lesquelles la destination ne reçoit qu’une partie de la sélection. |
Un groupe isolé et un transfert unitaire désignent donc deux objets différents : le premier est une propriété de composante, le second une propriété d’événement. Cette distinction évite d’attribuer à la seule image un comportement provenant d’un chemin particulier ou d’une capacité de réserve.
Passer de l’instance à la progression d’ensemble.
Le catalogue Pixaelo rassemble 2 000 niveaux de campagne et 1 825 dessins journaliers. À cette échelle, une moyenne globale peut masquer une succession de petites actions pénibles, un changement brutal de palette ou une concentration locale de puzzles aux interactions similaires.
L’analyse multiscalaire distingue le pixel, le groupe, le puzzle, une fenêtre de niveaux et le catalogue. Les mesures normalisées facilitent la comparaison de dessins de tailles différentes. Les distributions et quantiles révèlent les extrêmes que la moyenne efface ; les voisinages de progression donnent un contexte aux écarts observés.
La diversité comporte aussi plusieurs dimensions. Deux images peuvent être différentes octet par octet tout en proposant un rythme de manipulation proche. À l’inverse, deux sujets visuellement voisins peuvent induire des régions et des groupes très différents. Identité exacte, proximité perceptuelle, structure du puzzle et variété des sujets restent des axes de lecture distincts.
Les observables de structure et de trajectoire renseignent le confort potentiel. Leur relation avec la difficulté ressentie demande une observation humaine : expérience du joueur, compréhension des gestes, choix de parcours, taille d’écran et habitudes de manipulation influencent l’effort réel.
La propriété reste attachée à sa définition.
L’identité d’un puzzle comprend sa cible, son support, ses couleurs, son état de départ et les règles qui donnent un sens aux actions. Changer une illustration ne doit pas conduire à attribuer silencieusement à une nouvelle définition la progression ou la preuve d’une ancienne.
Une partie en cours doit continuer à être interprétée selon la définition qui la rend cohérente. Les pixels déjà placés, les pièces de réserve et les états antérieurs doivent satisfaire le même inventaire. L’historique artistique, qui décrit ce qui a réellement été terminé, a une sémantique différente de l’aperçu d’un contenu courant.
Une empreinte de contenu sert à reconnaître une définition précise. Elle ne démontre pas à elle seule la légalité d’un transfert, l’authenticité d’une progression ou la qualité d’un dessin. La reconnaissance d’identité et la vérification de propriétés ont des fonctions complémentaires.
Relier la cohérence logique à l’expérience réelle.
Une technologie de puzzle doit maintenir la cohérence entre son modèle et ses interactions. Une sélection ne doit pas altérer la grille ; un aperçu ne doit pas consommer de réserve ; une opération refusée doit laisser l’état physique inchangé. La présentation d’un résultat et le geste qui l’a produit restent rattachés au même transfert effectif.
La comparaison de plusieurs implémentations peut établir qu’elles interprètent de la même façon des définitions et des traces données. Sa portée dépend des cas couverts et des versions concernées. Une conformité sur un ensemble de trajectoires ne se confond pas avec une équivalence formelle de tous les comportements possibles.
AURELIS distingue ainsi la validité d’état, la légalité des transitions, la résolubilité d’une instance et les mesures de son parcours. La performance d’affichage, l’ergonomie tactile et l’évaluation artistique complètent cette description au niveau de l’expérience de jeu.
Découvrir Pixaelo ↗La géométrie discrète
des placements.
Tidilo se formalise comme un problème de satisfaction de contraintes. Il faut choisir, pour chaque objet, une position et une orientation admissibles, puis établir la compatibilité simultanée de ces choix. L’étude porte sur les arrangements finaux et leurs classes d’équivalence.
Des objets physiques à un espace de choix discret.
Chaque objet possède une empreinte géométrique, un ensemble d’orientations autorisées et des ancrages compatibles avec le support. Son domaine D_i rassemble les placements légaux considérés pour cet objet. Les obstacles, compartiments, zones et relations de groupe participent à la définition de l’instance.
U_i désigne l’ensemble des cellules occupées par l’objet i pour un placement donné. L’absence de collision est une condition nécessaire. Les contraintes de groupe, de zone et d’objectif ajoutent leurs propres prédicats. Recouvrir exactement une zone est une exigence supplémentaire lorsqu’elle appartient aux règles du niveau ; elle ne se déduit pas de la seule absence de chevauchement.
Compter des solutions canoniques.
L’ordre dans lequel les objets ont été placés ne définit pas, à lui seul, un nouvel arrangement final. Certaines orientations ou permutations d’objets peuvent aussi représenter des configurations équivalentes, lorsque les règles l’autorisent. La canonicalisation fixe cette équivalence avant de compter les solutions.
L’équivalence doit conserver les contraintes de l’instance. Une transformation géométrique ou une permutation n’est pas admise uniquement parce que le dessin paraît symétrique. Cette précision évite aussi bien de multiplier artificiellement les solutions que de fusionner des arrangements réellement distincts.
Quatre statuts, quatre significations précises.
UNIQUE établit l’existence d’une seule classe de solutions canoniques. MULTIPLE établit au moins deux classes distinctes. UNSOLVABLE établit l’absence de solution dans le modèle évalué. UNKNOWN indique que le résultat disponible ne permet pas de conclure sur la propriété recherchée.
Le solveur a épuisé l’espace pertinent et prouvé une solution canonique unique.
UNKNOWN ≠ UNIQUEUne recherche incomplète reste un résultat incomplet.Trouver un arrangement valide établit l’existence ; l’unicité exige également d’écarter les autres classes pertinentes. À l’inverse, deux arrangements canoniquement distincts suffisent à établir la multiplicité. Le sens du résultat dépend de la question démontrée, pas de la seule présence d’une solution de référence.
Mesurer les interactions entre possibilités.
Les placements admissibles forment une structure de concurrence. Deux possibilités peuvent se disputer les mêmes cellules ou être incompatibles avec une relation de groupe. Un graphe de conflits décrit ces incompatibilités par paires ; les contraintes impliquant plusieurs objets peuvent demander une relation d’ordre supérieur. La densité ci-dessous concerne un graphe simple non orienté comportant au moins deux sommets.
Les tailles de domaines, leur recouvrement, la proportion de cellules disputées et la densité des interactions décrivent l’ambiguïté de l’instance. Les rotations ajoutent des alternatives lorsque leurs empreintes sont réellement différentes. La pression spatiale caractérise les zones dont l’occupation réduit les choix disponibles pour d’autres objets.
Les impasses retardées et les choix localement plausibles renseignent l’anticipation requise. La difficulté n’est donc pas identifiée au seul nombre d’opérations d’un solveur : un coût de calcul est sensible à la représentation et aux méthodes de résolution, tandis que l’effort humain dépend de la lisibilité des choix.
Relier la structure aux stratégies de résolution.
Des stratégies simples permettent d’observer comment une instance réagit à des décisions intuitives : tenir compte de la taille des objets, de leurs possibilités restantes, de la proximité des bords ou de la préservation d’espaces utiles. Elles constituent des modèles de comportement, distincts d’une observation directe de joueurs.
Leur réussite, les impasses rencontrées et l’écart avec une solution valide décrivent des profils de puzzle différents. Un arrangement mathématiquement unique peut rester évident visuellement ; une ambiguïté locale peut, au contraire, exiger de différer un choix sans modifier le nombre de solutions finales.
La qualité d’une instance est multidimensionnelle.
La résolubilité et l’unicité caractérisent l’espace des solutions. La qualité structurelle ajoute d’autres questions : les objets participent-ils réellement aux décisions, les rotations ont-elles un rôle, l’espace est-il utilement contraint et les ambiguïtés produisent-elles une réflexion cohérente avec le niveau visé ?
La difficulté, la diversité et la progression sont donc des dimensions complémentaires. Une valeur élevée sur un axe n’implique pas une bonne qualité d’ensemble. L’analyse distingue les propriétés de preuve des caractéristiques qui décrivent l’intérêt et le rythme de résolution.
Une campagne se lit à plusieurs échelles.
La campagne de Tidilo comprend 10 mondes de 100 niveaux, soit 1 000 puzzles. Une progression se décrit par des distributions locales de difficulté, des introductions de mécanismes, des variations de pression et des respirations. Une moyenne par monde ne décrit pas l’enchaînement vécu d’un niveau au suivant.
L’étude de fenêtres successives permet de caractériser les ruptures et les répétitions. La taille de grille, le nombre d’objets et le nombre d’orientations ne constituent pas, pris isolément, une échelle universelle de difficulté.
La diversité dépasse l’apparence des objets.
Deux niveaux peuvent employer des objets visuellement différents tout en imposant une structure de décision très proche. Les domaines, les conflits, les rotations pertinentes et les interactions spatiales offrent une autre description de leur parenté.
Comparer cette structure complète la variété visuelle. La diversité de contenus se lit alors comme une diversité de situations à résoudre : dispositions, contraintes dominantes, dépendances entre choix et rôle des zones critiques.
Qualifier le résultat dans le bon modèle.
La preuve d’unicité canonique de Tidilo porte sur des arrangements sous contraintes. La preuve de résolubilité de Pixaelo porte sur un chemin de transitions légales. Ces deux éditions partagent une exigence de cohérence formelle et conservent des objets de preuve différents.
La validation est attachée aux règles et à la définition étudiées. Un changement d’empreinte, de rotation, de zone ou de relation peut modifier l’espace des solutions. La propriété établie doit alors être considérée sur cette nouvelle instance, avec sa propre équivalence canonique.
Découvrir Tidilo ↗La propriété vérifiée
suit les règles du jeu.
États, transitions et conservation pour Pixaelo V5.4. Domaines, compatibilité et classes de solutions pour Tidilo V5.2. Une même précision dans la définition des problèmes, des mesures et des résultats.
Explorer INS PROD Games ↗