Note : Ce contenu a été créé avant que Fabernovel ne fasse partie du groupe EY, le 5 juillet 2022.

‍

Mais nous ne sommes pas les premiers à creuser cette idée. Candy Crush est un problème NP-difficile, c’est-à-dire faisant parti des exercices mathématiques les plus ardus à résoudre. De nombreux joueurs se sont donc posé la question d’une solution automatisée. Un groupe d’élèves de l’IUT de Clermont-Ferrand a, par exemple, réalisé une application de résolution à partir de la version ordinateur du jeu. Grâce à une photo de leur écran de PC, l’application Android affiche le meilleur coup à réaliser. D’autres ont créé une application mobile pour un jeu similaire (Puzzle and Dragons), mais il faut, avant de pouvoir l’utiliser, redessiner le niveau à la main. Nous souhaitions aller plus loin, en lisant directement la grille du téléphone, sans que l’utilisateur ait besoin de prendre une photo. Dans notre idée, tout se ferait naturellement, dans le jeu. La reconnaissance de la grille sur Android, ainsi que l’affichage de la solution par-dessus le jeu, ont donc été des objectifs majeurs de notre recherche. Il aurait aussi été possible de résoudre Candy Crush sans passer par un seul niveau, comme le montre Stavros Korokithakis dans son étude des appels réseau entre l’application et le serveur. Mais nous préférions nous rapprocher du joueur, en proposant une intéraction directe sur son écran.

Nous avons alors essayé de développer ce “Candy Crush Cheater” sur Android. Le principe ? Une application qui analyse la grille de jeu, calcule le meilleur coup à faire et l’affiche directement sur l’écran, par-dessus Candy Crush.

Étapes

Notre application tourne en tâche de fond, pendant que le joueur déplace ses bonbons sur Candy Crush. Son fonctionnement original se reflète à travers ces cinq étapes principales.

L’accessibilité, une façon de suivre l’utilisateur

Notre application tourne en continu à partir du moment où le joueur démarre le service. Cependant, il serait vain de commencer à chercher les bonbons sur la home du téléphone, ou sur son fil d’actualité Facebook… Nous devons seulement agir lorsqu’il se trouve sur Candy Crush, et donc savoir lorsque c’est le cas.

Nous utilisons les options d’accessibilité du téléphone pour savoir “où l’utilisateur se trouve”. A chaque instant, nous pouvons recevoir le nom de l’activité en premier plan (mais aussi son contenu), à condition que l’utilisateur nous y autorise. Initialement créée dans le but de faciliter l’accès à toutes les applications pour les personnes souffrant d’un handicap visuel (lecture automatique du contenu), l’accessibilité nous permet en outre de suivre à la trace notre utilisateur. Big Brother is watching you ! Les applications autorisées à utiliser l’accessibilité de votre téléphone sont donc potentiellement dangereuses, car elles peuvent surveiller tous vos mouvements et le contenu de vos applications. Il est préférable de ne pas accorder cette permission trop facilement, pour ne pas mettre en danger vos données sensibles. Mais pour notre part, nous nous contentons de regarder si l’utilisateur se trouve ou non dans l’application Candy Crush.

Nous utilisons pour cela un AccessibilityService, capable de détecter tous les changement d’écrans du téléphone :

public class HeadService extends AccessibilityService { @Override public void onAccessibilityEvent(AccessibilityEvent event) { if(event.getPackageName().toString().equals("com.king.candycrushsaga")){ startImageListener(); } } }

Photographie de l’état actuel du jeu

Avant de pouvoir analyser l’écran du jeu, il faut déjà l’obtenir. C’est grâce à l’objet MediaProjectionManager que nous avons pu réaliser des captures d’écran régulières.

MediaProjectionManager mProjectionManager = (MediaProjectionManager) getActivity().getSystemService(Context.MEDIA_PROJECTION_SERVICE); startActivityForResult(mProjectionManager.createScreenCaptureIntent(), REQUEST_CODE);

Notons néanmoins que cette classe n’existe qu’à partir de l’API 21, ce qui réduit grandement le nombre de téléphones sur lesquels notre application peut être installée. Mais cette solution possède l’avantage non négligeable de fonctionner sur des appareils non rootés, contrairement aux autres implémentations existantes.

Le service réalise donc une capture par seconde et l’enregistre dynamiquement dans la mémoire de l’appareil. A noter qu’une utilisation de la classe ImageReader.OnImageAvailableListener aurait aussi été possible ; les screenshots seraient alors plus fréquents (dès qu’un changement serait repéré à l’écran), mais leur qualité deviendrait moins bonne. Les tests réalisés avec cet outil ont mené à de moins bons résultats (une cadence de mise à jour plus élevée mais des captures d’écran parfois incomplètes). Un enregistrement par seconde suffit finalement pour trouver l’état de la grille et donner ensuite le meilleur coup à jouer.

Analyse de l’image obtenue

Nous nous attaquons ensuite à la partie la plus coriace de notre application de résolution : la reconnaissance de la grille de bonbons.

La méthode la plus efficace pour reconnaître un motif sur une image utilise sans aucun doute la convolution. Pour l’appliquer, nous prenons notre modèle (ici un bonbon coloré) et nous le déplaçons sur l’image, pixel par pixel, jusqu’à trouver l’endroit qui lui “correspond” le mieux (la correspondance se définit comme un score établi à partir d’une formule mathématique dépendant de la méthode de convolution choisie). Ce procédé est implémenté dans la bibliothèque OpenCV, sous le nom de matchTemplate. Après un premier essai avec cette méthode, qui donnait pourtant d’excellents résultats, nous nous sommes rendu compte que les performances des téléphones ne suffiraient pas à cette analyse et qu’il serait nécessaire de trouver une nouvelle solution.

Nous avons donc opté pour un algorithme plus simple ; notre service parcourt les pixels de l’image, jusqu’à trouver une couleur très proche du bonbon que nous recherchons. Une recherche simple par teinte, en oubliant les formes de nos modèles, nous a permis d’améliorer grandement les performances de l’application et de la rendre réellement utilisable (sans attendre quinze secondes avant de recevoir le déplacement à effectuer).

A la recherche du meilleur coup à jouer

Maintenant que la grille est prête, nous pouvons la parcourir afin de trouver le meilleur coup à réaliser. Nous cherchons alors tous les mouvements possibles. La règle de Candy Crush est simple : un déplacement n’est possible que s’il permet l’alignement de trois bonbons de même couleur.

Notre algorithme de recherche parcourt la grille et regarde, pour chaque bonbon, 16 de ses voisins et examine leur couleur. Il détermine ainsi si un déplacement est possible vers le haut, vers le bas, vers la gauche ou vers la droite. Le schéma ci-dessous résume notre recherche :

En cherchant les déplacements, nous attribuons aussi des scores fictifs, afin de les classer les uns par rapport aux autres. Ils sont pour le moment assez intuitifs : 1 point pour un simple coup, 3 ou 4 points pour un alignement de 4 bonbons, 5 points pour la création d’un bonbon bombe, etc. Le but principal est de spécifier à l‘algorithme une façon de classer ces déplacements, selon le nombre de points qu’ils nous offriront dans le jeu. Dans tous les cas, l’application se charge ensuite de trouver le meilleur et de l’afficher à l’utilisateur. En cas d’égalité, nous choisissons le coup le plus bas, afin qu’il déplace le maximum de bonbons (il aura ainsi plus de chances de nous rapporter des points).

Affichage des résultats

Et nous arrivons à l’étape finale de notre application ! Étape qui nous permet de répondre à la question : “Pourquoi une application Android ? Une version bientôt disponible sur iOS ?” La réponse est non, car il faut afficher les résultats par-dessus Candy Crush. Montrer au joueur le déplacement à effectuer ne peut se faire sans cette fonctionnalité, disponible uniquement sur Android. On la retrouve par exemple avec les “bulles de conversation” Facebook, qui apparaissent à l’écran, par-dessus n’importe quel autre contenu. C’est un peu ce que nous faisons sur l’écran de Candy Crush.

Une vue spécifique, équipée d’un WindowManager, est détenue par le service principal. Nous pouvons lui ajouter n’importe quel élément : un bouton, du texte, une image. Nous avons choisi cette dernière option et dessinons alors un contour assombri autour des bonbons à déplacer.

public class HeadLayer extends View { private WindowManager.LayoutParams params = new WindowManager.LayoutParams( WindowManager.LayoutParams.WRAP_CONTENT, WindowManager.LayoutParams.WRAP_CONTENT, WindowManager.LayoutParams.TYPE_PHONE, WindowManager.LayoutParams.FLAG_NOT_FOCUSABLE | WindowManager.LayoutParams.FLAG_WATCH_OUTSIDE_TOUCH, PixelFormat.TRANSLUCENT); private void addToWindowManager() { windowManager = (WindowManager) context.getSystemService(Context.WINDOW_SERVICE); windowManager.addView(frameLayout, params); LayoutInflater layoutInflater = (LayoutInflater) context.getSystemService(Context.LAYOUT_INFLATER_SERVICE); layoutInflater.inflate(R.layout.head, frameLayout); image = (ImageView) frameLayout.findViewById(R.id.solution); }

Puis nous modifions ce contour en fonction des résultats suivants.

Quelques limites

Si ce travail nous offre une application Android fonctionnelle, elle reste néanmoins limitée sur certains points. Nous avons rencontré quelques obstacles tenaces, mais pourtant extrêmement intéressants pour la suite.

Des niveaux excessivement différents

L’application Candy Crush Saga rassemble plus de 2000 niveaux. Et une bonne dose d’objectifs différents ! Le gameplay sur lequel nous nous sommes concentrés concerne les premiers niveaux. Il faut marquer le plus grand nombre de points en un nombre de déplacements limités. L’application vise donc simplement le meilleur coup possible sur la grille. Mais pour d’autres niveaux, cette technique n’est absolument pas efficace. Les objectifs évoluent ; il faut alors faire tomber des fruits en bas de l’écran (et donc réaliser des déplacements sous ces fruits pour les faire descendre), ou éliminer des morceaux de gelée présents derrière les bonbons (et donc focaliser les déplacements sur ces endroits spécifiques). Et ces deux objectifs ne sont que des exemples. Une adaptation du Candy Crush Cheater est bien sûr possible. Nous avons pensé, par exemple, à demander à l’utilisateur l’objectif de son niveau avant de tenter de le résoudre. Mais cela implique de développer tous les moteurs correspondants. C’est dans cette optique que nous avons ajouté la possibilité pour le joueur d’afficher tous les coups possibles. Il peut ainsi choisir en fonction des objectifs de son niveau.

Mais cet obstacle ne serait pas le seul. Avec les divers objectifs, les motifs varient aussi. Les 6 bonbons principaux reconnus par notre application ne suffisent alors plus. Il faudrait déceler tous les types de fruits possibles (cerises, marrons), mais aussi les morceaux de glace (étape a priori très difficile car ils se confondraient dans la transparence de l’arrière plan), les chocolats, réglisses, etc.

Cependant, cette difficulté ne s’appliquerait pas à d’autres types de jeux mobiles : sudoku, Bejeweled Classic, Puzzle and Dragons, et tout autre jeu de logique. Nous pourrions donc imaginer nous tourner vers ce type de jeu, plus abordable car les objectifs n’évoluent pas avec le temps. La structure de notre application n’en serait alors pas modifiée : il suffirait de changer le moteur et de réorienter la reconnaissance des motifs. Une adaptation facilitée grâce aux étapes déjà implémentées.

Une mémoire vive en difficulté

Il a fallu faire face à un second problème : la mémoire vive disponible dans le téléphone. En effet, Candy Crush s’est révélé être une application extrêmement gourmande sur ce point, occupant parfois une grande partie de la RAM. Si notre cheater a été optimisé au maximum, les calculs ne sont pas sans conséquence sur le hardware, forcément limité, du téléphone.

Candy Crush est donc parfois ralenti par les recherches effectuées en arrière plan. Il est préférable de l’utiliser sur des téléphones puissants (même si des tests nous montrent qu’1Go de RAM suffit). Il est aussi souhaitable de fermer les autres applications actives (par exemple les “music player”) avant de démarrer notre service, pour mettre l’appareil dans les meilleures conditions possibles.

Si les performances du téléphone sont mises à rude épreuve, notre application reste parfaitement utilisable dans la plupart des cas. Nous pouvons aussi imaginer des améliorations en l’appliquant à d’autres jeux, moins gourmands en mémoire vive.

Conclusion

Candy Crush Cheater est donc une application qui se sert de nombreuses spécificités méconnues du téléphone et cette exploration a été une excellente façon de les découvrir. Si certaines fonctionnalités peuvent encore être améliorées, l’application est tout de même très efficace sur les principaux niveaux du jeu.

Cependant, nous souhaitons mettre en garde les utilisateurs contre ce genre d’applications. Candy Crush Cheater possède tout de même les droits pour capturer tous les mouvements de votre écran, lire le contenu textuel de votre mobile et écrire par-dessus vos applications. On peut alors imaginer de nombreux scénarios mettant en péril la vie privée ou la sécurité des joueurs. Un mot de passe ou un numéro de carte bleue présent en clair sur l’appareil devient tout à fait lisible et utilisable par l’application. De même, un contenu modifié peut être placé sur votre écran, sans que ce dernier soit détectable à vos yeux. Gardons alors en tête qu’il ne vaut mieux pas accepter toutes ces autorisations, à moins d’avoir une confiance sans faille en l’éditeur de l’application.

Enfin, nous fournissons le code source de l’application, afin que chacun puisse se faire sa propre opinion du “Candy Crush Cheater”, ou l’utiliser pour coder sa résolution automatique d’un autre jeu ! ;)