Remue-méninges: comment regarder les tâches sous un angle différent

Remue-méninges avec transposition

Parfois, je suis coincé et je dois chercher des façons de penser la tâche sous un angle différent. Certaines tâches peuvent être affichées sous forme de matrice ou de tableau. Leur structure ressemble à ceci:


Les cellules avec lesquelles je travaille sont organisées en colonnes et en lignes. Prenons un exemple d'un jeu simple:


Les lignes sont des classes de personnages: guerrier, mage, voleur.

Les colonnes sont des types d'actions: attaque, défense, action spéciale.

La matrice contient tout le code pour traiter chacun des types d'actions pour chaque type de caractère.

À quoi ressemble le code? En règle générale, ces structures sont organisées en de tels modules:

1. Fighter contiendra un code pour gérer les coups d'épée, réduisant les dégâts avec une armure et un coup puissant spécial.
2. Mage contiendra un code de manipulation de boule de feu, une réflexion des dégâts et une attaque de gel spéciale.
3. Thief contiendra du code pour gérer les attaques de poignard, éviter les dégâts d'esquive et une attaque de désarmement spéciale.

Il est parfois utile de transposer la matrice. On peut l'arranger sur un autre axe :

1. Attack contiendra un code pour gérer les balançoires, les boules de feu et les attaques au poignard.
2. Defend contiendra un code pour gérer la réduction des dégâts, refléter les dégâts et éviter les dommages.
3. Special contiendra un puissant code de gestion de frappe, gel et désarmement.

On m'a appris qu'un style est «bon» et l'autre «mauvais». Mais je ne vois pas clairement pourquoi tout devrait être ainsi. La raison en est l' hypothèse que nous ajouterons souvent de nouvelles classes de caractères (noms), et ajouterons rarement de nouveaux types d'actions (verbes). De cette façon, je peux ajouter du code en utilisant le nouveau module sans toucher à tous ceux disponibles. Dans votre jeu, tout peut être différent. En regardant la matrice transposée, je suis conscient de l'existence de l'hypothèse et peux y mettre en doute. Ensuite, je penserai au type de flexibilité dont j'ai besoin, et alors seulement je choisirai la structure du code.

Regardons un autre exemple.

Les interprétations des langages de programmation ont différents types de nœuds correspondant aux primitives: constantes, opérateurs, boucles, branchements, fonctions, types, etc. Nous devons générer du code pour tous.


Super! Vous pouvez créer une classe pour chaque type de nœud, et ils peuvent tous hériter de la classe de base Node . Mais nous nous appuyons sur l'hypothèse que nous ajouterons des lignes et moins souvent des colonnes. Que se passe-t-il dans le compilateur d'optimisation? Nous ajoutons de nouvelles passes d'optimisation. Et chacun d'eux est une nouvelle colonne.


Si je veux ajouter une nouvelle passe d'optimisation, je devrai ajouter une nouvelle méthode à chaque classe, et tout le code de passe d'optimisation sera distribué dans différents modules. Je veux éviter une telle situation! Par conséquent, dans certains systèmes, une autre couche est ajoutée en plus de cela. En utilisant le modèle de visiteur, je peux stocker tout le code pour fusionner les boucles dans un module, plutôt que de le diviser en plusieurs fichiers.

Si vous regardez la matrice transposée, nous ouvrirons une autre approche:


Maintenant, au lieu de classes avec des méthodes, je peux utiliser l' union étiquetée et la correspondance de modèles (elles ne sont pas prises en charge dans tous les langages de programmation). Pour cette raison, le code entier de chaque passe d'optimisation sera stocké ensemble et peut se passer de l'indirectité du modèle de visiteur.

Il est souvent utile d'examiner le problème du point de vue de la matrice. Son application à une structure orientée objet à laquelle tout le monde pense peut me conduire à autre chose, comme un modèle de système entité-composant, des bases de données relationnelles ou une programmation réactive.

Et cela ne s'applique pas seulement au code. Voici un exemple d'application de cette idée aux produits. Supposons qu'il y ait des personnes ayant des intérêts différents:


Si je développais un site de réseautage social, je pourrais permettre aux gens de suivre les nouvelles des autres. Nick peut s'inscrire à Alice, car ils sont tous deux intéressés par les voitures, et sur Fenya, car ils sont tous deux intéressés par les voyages. Mais Nick recevra également les articles d'Alice sur les mathématiques et ceux de Fenya sur la politique. Si je considérais une matrice transposée, je pourrais permettre aux gens de s'abonner à des sujets . Nick pourrait rejoindre un groupe d'amateurs de voitures, ainsi qu'un groupe de voyageurs. Facebook et Reddit ont commencé à peu près au même moment, mais ce sont des matrices transposées l'une de l'autre. Facebook vous permet de suivre les gens; Reddit vous permet de vous abonner à des sujets.

Lorsque je m'immobilise ou que je souhaite envisager des alternatives, je regarde le problème et y cherche différents axes de commande. Parfois, regarder un problème sous un angle différent peut fournir une meilleure solution.

Remue-méninges sur la décomposition

J'utilise une autre technique appelée décomposition.

En algèbre, l'opération de décomposition transforme un polynôme de la forme 5x² + 8x - 21 en (x + 3) · (5x - 7). Pour résoudre l'équation 5x² + 8x - 21 = 0, nous pouvons d'abord la factoriser en (x + 3) · (5x - 7) = 0. Ensuite, nous pouvons dire que x + 3 = 0 ou 5x - 7 = 0. Expansion transforme une tâche difficile en quelques tâches plus faciles.


Prenons un exemple: j'ai six classes: File , EncryptedFile , GzipFile , EncryptedGzipFile , BzipFile , EncryptedBzipFile . Je peux les décomposer en une matrice:


En utilisant le modèle «décorateur» (ou impuretés), j'ai transformé six types de fichiers différents en quatre composants: plain, gzip, bzip, encrypt. Cela ne semble pas économiser beaucoup, mais si j'ajoute plus de variations, les économies augmenteront. La décomposition transforme les composants O (M * N) en composants O (M + N).

Un autre exemple: parfois les gens me posent des questions comme "comment écrire une interpolation linéaire en C #?" . Je peux écrire de nombreux tutoriels potentiels:


S'il y a M sujets et N langues, je peux écrire des tutoriels M * N. Cependant, cela représente beaucoup de travail. Au lieu de cela, j'écrirai un tutoriel sur l' interpolation , quelqu'un d'autre rédigera un tutoriel sur C #, puis le lecteur combinera la connaissance de C # avec la connaissance de l'interpolation et rédigera sa version d'interpolation en C #.

Comme la transposition, la décomposition n'aide pas toujours, mais le cas échéant, elle peut être très utile.

Remue-méninges en arrière

Dans les deux parties précédentes, j'ai parlé de la façon dont j'aborde parfois la tâche, en essayant de l'organiser en une matrice. Parfois, cela n'aide pas et j'essaie ensuite de regarder la tâche dans la direction opposée. Jetons un œil à la génération de cartes procédurales. Souvent, je commence par une fonction de bruit, puis j'ajoute des octaves, ajuste les paramètres et ajoute des couches. Je le fais parce que j'ai besoin de cartes qui ont certaines propriétés.


Il est tout à fait possible de commencer par des expériences avec des paramètres, mais l'espace des paramètres est assez grand, et on ne sait pas si je trouverai les paramètres qui conviennent le mieux à mes besoins. Par conséquent, après avoir expérimenté un peu, je m'arrête et commence à penser dans l'ordre inverse: si je peux décrire ce dont j'ai besoin, cela peut aider à trouver les paramètres.

C'est cette motivation qui m'a fait étudier l'algèbre. Si nous avons une équation de la forme 5x² + 8x - 21 = 0 , alors quel sera x ? Quand je ne connaissais pas l'algèbre, je résolvais cette équation, essayant de substituer différentes valeurs de x , en les choisissant d'abord au hasard, puis en les ajustant quand je sentais que j'étais proche de la solution. L'algèbre nous donne un outil pour aller dans une direction différente. Au lieu de deviner les réponses, elle me donne un appareil (décomposition, ou équations quadratiques, ou la méthode newtonienne de recherche itérative des racines), que je peux utiliser plus consciemment pour rechercher des valeurs x (-3 ou 7/5).

J'ai l'impression de me retrouver souvent dans ce genre de situation de programmation. Lorsque je travaillais sur la génération de cartes procédurales, après avoir expérimenté les paramètres pendant un certain temps, je me suis arrêté et j'ai compilé une liste de ce qui devrait être dans les mondes de jeu d' un projet :

1. Les joueurs doivent commencer le jeu loin de la côte.
2. En montant de niveau, les joueurs doivent monter.
3. Les joueurs ne devraient pas pouvoir atteindre le bord de la carte.
4. À mesure que le niveau augmente, les joueurs doivent se joindre à des groupes.
5. Il devrait y avoir de simples monstres sur les côtes sans grande variation.
6. Dans les plaines, il devrait y avoir une grande variété de monstres de difficulté moyenne.
7. Dans les zones montagneuses, il doit y avoir des monstres complexes.
8. Il doit y avoir une sorte de repère qui permet aux joueurs de rester au même niveau de difficulté, et un autre repère qui vous permet d'augmenter ou de diminuer le niveau de difficulté.

La compilation de cette liste a conduit à la création des restrictions suivantes:

1. Les mondes du jeu devraient être des îles avec de nombreuses côtes et un petit pic au centre.
2. L'altitude doit correspondre à la complexité des monstres.
3. Aux basses et hautes altitudes, il devrait y avoir moins de variabilité des biomes qu'aux altitudes moyennes.
4. Les routes devraient rester au même niveau de difficulté.
5. Les rivières devraient couler de grandes à petites hauteurs et offrir aux joueurs la possibilité de monter / descendre.

Ces limitations m'ont amené à concevoir un générateur de cartes. Et il a conduit à la génération d'un jeu de cartes bien meilleur que celles que j'ai reçues en ajustant les paramètres, comme je le fais habituellement. Et l' article résultant a intéressé de nombreuses personnes à créer des cartes basées sur des diagrammes de Voronoi.

Les tests unitaires en sont un autre exemple. Il est suggéré de proposer une liste d'exemples à tester. Par exemple, pour les grilles d'hexagones, je pourrais penser que je dois vérifier la condition add(Hex(1, 2), Hex(3, 4)) == Hex(4, 6) . Ensuite, je me souviens que vous devez vérifier les zéros: add(Hex(0, 1), Hex(7, 9)) == Hex(7, 10) . Ensuite, je me souviens que vous devez vérifier les valeurs négatives: add(Hex(-3, 4) + Hex(7, -8)) == Hex(4, -4) . Bon, super, j'ai quelques tests unitaires.

Mais si vous pensez un peu plus loin, je vérifie en fait add(Hex(A, B), Hex(C, D)) == Hex(A+C, B+D) . J'ai trouvé les trois exemples ci-dessus basés sur cette règle générale. Je vais dans la direction opposée à cette règle pour en venir aux tests unitaires. Si je peux encoder directement cette règle dans un système de test, alors le système lui-même pourra fonctionner dans l'ordre inverse pour créer des exemples de test. C'est ce qu'on appelle les tests basés sur les propriétés. (Voir aussi: tests métamorphiques )

Autre exemple: solveurs de contraintes. Dans de tels systèmes, l'utilisateur décrit ce qu'il souhaite voir sur la sortie et le système trouve un moyen de satisfaire ces restrictions. Citation du livre de génération de contenu procédural, chapitre 8 :

En utilisant les méthodes constructives du chapitre 3, ainsi que les méthodes fractales et de bruit du chapitre 4, nous pouvons créer différents types de données de sortie en ajustant les algorithmes jusqu'à ce que nous soyons satisfaits de leurs données de sortie. Mais si nous savons quelles propriétés le contenu généré devrait avoir, il sera plus pratique d'indiquer directement ce que nous voulons que l'algorithme général trouve le contenu qui répond à nos critères.

Ce livre décrit la programmation des ensembles de réponses (ASP), dans laquelle nous décrivons la structure de ce avec quoi nous travaillons (les carreaux sont le sol et les murs, les carreaux se bordent), la structure des solutions que nous recherchons (un donjon est un groupe tuiles connectées avec le début et la fin) et les propriétés des solutions (les passages latéraux ne doivent pas contenir plus de 5 pièces, il doit y avoir 1-2 boucles dans le labyrinthe, trois assistants doivent être vaincus avant d'atteindre le boss). Après cela, le système crée des solutions possibles et vous permet de décider quoi en faire.

Récemment, un solveur de contraintes a été développé, ce qui a suscité un grand intérêt en raison de son nom cool et de sa démo curieuse: Wave Function Collapse. [Il y a un article sur ce solveur sur Habr.] Si vous lui donnez des exemples d'images pour indiquer quelles restrictions sont imposées sur les tuiles voisines, il créera de nouveaux exemples qui correspondent aux modèles donnés. Son travail est décrit dans WaveFunctionCollapse is Constraint Solving in the Wild :

WFC implémente une méthode de recherche gourmande sans revenir en arrière. Cet article explore le WFC comme exemple de méthodes de décision basées sur des contraintes.

J'ai déjà accompli beaucoup de choses à l'aide de solveurs de contraintes. Comme pour l'algèbre, avant d'apprendre à les utiliser efficacement, j'ai besoin d'apprendre beaucoup.

Un autre exemple: le vaisseau spatial que j'ai créé . Le joueur peut faire glisser les moteurs n'importe où, et le système déterminera quels moteurs doivent être activés lorsque vous cliquez sur W, A, S, D, Q, E. Par exemple, dans ce vaisseau:


Si vous voulez voler vers l'avant, incluez deux moteurs arrière. Si vous souhaitez tourner à gauche, allumez les moteurs arrière droit et avant gauche. J'ai essayé de chercher une solution, forçant le système à itérer sur de nombreux paramètres :


Le système a fonctionné, mais pas parfait. Plus tard, je me suis rendu compte que c'est un autre exemple où la solution dans la direction opposée pourrait aider. Il s'est avéré que le mouvement des engins spatiaux peut être décrit par un système linéaire de restrictions . Si je comprenais cela, je pourrais utiliser une bibliothèque prête à l'emploi qui résout avec précision les contraintes, et non ma méthode d'essai et d'erreur, qui renvoie une approximation.

Et un autre exemple: le projet G9.js, dans lequel vous pouvez faire glisser la sortie d'une certaine fonction sur l'écran, et il détermine comment modifier les données d'entrée pour qu'elles correspondent aux données de sortie souhaitées. Les démos G9.js sont superbes! Assurez-vous de décommenter la ligne "décommenter la ligne suivante" dans la démo Rings.

Il est parfois utile de penser à une tâche dans l'ordre inverse. Il s'avère souvent que cela me donne de meilleures solutions qu'avec le raisonnement direct.