Comment faire un bon score à Plock ?

14 11 2009

Plock est un jeu Flash accessible via FaceBook. Le but est de supprimer le plus possible de blocs de couleur identique en une minute. Il n’y a pas vraiment de temp accordé à la stratégie, seuls des réflexes et un œil de lynx vous seront d’un grand secours. Et pour les daltoniens, c’est pas évident puisque tout est basé sur la couleur.

Pour vous faire une petite idée, voici à quoi ressemble l’aire de jeu :

L’aire de jeu de Plock

L’aire de jeu de Plock

À partir de ça, comment faire un bon score ?

C’est de la triche ! Mais je vais quand même vous expliquer😉

Oui, mon truc pour faire un bon score, c’est de la triche… Mais il fallait malgré tout le faire.

Plock est le genre de jeu qui se prête bien à l’écriture d’un robot. J’entends par robot un programme qui va simuler les actions d’un utilisateur. Il n’y a pas de hack à proprement parler puisque je ne rentre pas dans le code de Plock.

Le robot n’est rien d’autre qu’un programme écrit en langage C qui va prendre le contrôle de la souris.

Le principe consiste à :

  • analyser l’écran pour y détecter les blocs de couleurs de Plock,
  • à partir de cette analyse, rechercher deux blocks de couleur qui se touchent horizontalement ou verticalement,
  • déplacer la souris sur l’un de ces blocs,
  • simuler un clic souris (pression et relachement du bouton de gauche),
  • recommencer encore et encore à partir de l’analyse.

D’un score d’environ 890.000, je suis passé à un peu plus de 2.000.000.

Scores

Scores

Il est à mon avis possible d’obtenir plus avec une machine plus puissante car l’enchaînement de clics entraîne une surcharge au niveau des animations de l’aire de jeu ce qui a pour conséquence le loupage de clics qui sont répétés jusqu’à être pris.

Voici une vidéo enregistrée. Le score obtenu sur cette partie n’est que de 1.769.100. Mais c’est déjà pas mal😉

Avant de commencer

Bon, je dois vous l’avouer, je n’ai pas créé un programme d’intelligence artificielle.

Il a donc fallu aider le programme…

Tout d’abord, j’ai repéré à quelles coordonnées l’aire de jeu de Plock apparaissait sur mon écran lorsque la fenêtre de mon navigateur était agrandie.

Chez moi, ça donne les coordonnées (997,375) :

Aire de jeu de Plock dans la fenêtre du navigateur agrandie

Aire de jeu de Plock dans la fenêtre du navigateur agrandie

Ensuite, pour que le robot puisse repérer les blocs, je définis un point de référence. Les blocs ayant chacun une couleur précise, un seul pixel permet de déterminer le type de bloc. Par contre, le point de référence doit être bien choisi car les boutons ont des dégradés. C’est pour cela que j’ai choisi le point indiqué sur le zoom suivant :

Zoom sur le pixel de référence

Zoom sur le pixel de référence

Il faut aussi collecter d’autres informations :

  • la grille comporte 9 lignes de 8 colonnes,
  • les blocs sont de taille 42×42 pixels.

Voilà ! Toutes ces informations seront rentrées en dur dans le code du robot.

Le programme

Vous pouvez télécharger le programme complet.

Pour le compiler, ça se passe avec la commande suivante :

gcc robotplock.c -lX11

Si la commande se passe bien, un exécutable a.out est créé dans le même répertoire. Si vous n’arrivez pas à compiler, c’est qu’il vous manque les paquets de développement pour X11 (le programme ne fait appel à aucune autre bibliothèque que Xlib).

Entête du programme

Inclusion des différentes bibliothèques nécessaires au programme :

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <unistd.h>

#include <X11/Xlib.h>
#include <X11/Xutil.h>

Définition de TRUE et FALSE

Parce qu’on n’est pas des bœufs…

#define TRUE (1==1)
#define FALSE (1==0)

Définition des constantes

On définit dans cette partie les données en dur déjà présentées à la section précédente. On définit aussi les 6 couleurs possibles. Le code hexadécimal est récupéré avec la pipette de Gimp.

#define STARTX 997 ← coordonnée X du premier bloc à l’écran
#define STARTY 375 ← coordonnée Y du premier bloc à l’écran
#define WIDTH 42   ← largeur d’un bloc en pixels
#define HEIGHT 42  ← hauteur d’un bloc en pixels
#define COLUMNS 8  ← nombre de blocs par ligne de l’aire de jeu
#define ROWS 9     ← nombre de lignes de blocs de l’aire de jeu

#define ORANGE 0xffd341
#define VERT 0xa8bf36
#define BLANC 0xf2f2f2
#define ROSE 0xe01271
#define VIOLET 0xa842b0
#define BLEU 0x5ba4dd

Définition de variables globales

Ces 2 variables sont utilisées par les fonctions appelant la bibliothèque Xlib. Elles évitent d’ouvrir et de fermer un accès à l’affichage de façon incessante :

Display *display;  ← l’affichage courant
Window rootwindow; ← la fenêtre racine (l’écran entier)

Fonction mouseMove

Cette fonction permet de déplacer le curseur de la souris n’importe où sur l’écran. Les coordonnées fournies sont relatives à l’écran entier. Elle utilise les deux variables globales display et rootwindow.

void mouseMove(int x,int y) {
  XWarpPointer(
    display,
    None,
    rootwindow,
    0,0,
    0,0,
    x,y
  );

  XFlush(display);
}

Fonction mouseClick

La fonction mouseClick est un tantinet plus complexe que la fonction mouseMove. Tout d’abord, elle doit récupérer la fenêtre (au sens X11) se trouvant sous le curseur avec la fonction XQueryPointer. La subtilité, c’est que XQueryPointer retourne la fenêtre père et non la fenêtre du dernier enfant (les fenêtres sont imbriquées). Il y a donc une boucle pour appeler plusieurs XQueryPointer afin de l’obtenir.

Une fois la fenêtre récupérée, on peut lui envoyer l’événement correspondant à la pression du bouton gauche de la souris, attendre 60 millisecondes (avec usleep), et envoyer l’événement correspondant au relachement du bouton gauche de la souris. Cela permet de simuler un clic.

void mouseClick(int button) {
  XEvent event;

  memset(&event,0x00,sizeof(event));

  event.type               =ButtonPress;
  event.xbutton.button     =button;
  event.xbutton.same_screen=True;

  XQueryPointer(
    display,
    rootwindow,
    &event.xbutton.root,
    &event.xbutton.window,
    &event.xbutton.x_root,
    &event.xbutton.y_root,
    &event.xbutton.x,
    &event.xbutton.y,
    &event.xbutton.state
  );

  event.xbutton.subwindow=event.xbutton.window;

  while(event.xbutton.subwindow) {
    event.xbutton.window=event.xbutton.subwindow;

    XQueryPointer(
      display,
      event.xbutton.window,
      &event.xbutton.root,
      &event.xbutton.subwindow,
      &event.xbutton.x_root,
      &event.xbutton.y_root,
      &event.xbutton.x,
      &event.xbutton.y,
      &event.xbutton.state
    );
  }

  if(XSendEvent(display,PointerWindow,True,0xfff,&event)==0) {
    fprintf(stderr, "Erreur à la génération de l’événement !!!\n");
  }

  XFlush(display);

  usleep(60000);

  event.type         =ButtonRelease;
  event.xbutton.state=0x100;

  if(XSendEvent(display,PointerWindow,True,0xfff,&event)==0) {
    fprintf(stderr, "Erreur à la génération de l’événement !!!\n");
  }
  XFlush(display);
}

Fonction getPixel

La fonction getPixel permet de récupérer la couleur (sur 32 bits) d’un point quelconque de l’écran. Ce n’est pas une fonction optimale mais le nombre de points à récupérer n’est pas important.

unsigned long getPixel(int x,int y) {
  XImage *image;

  image=XGetImage(
    display,
    rootwindow,
    x,y,
    1,1,
    AllPlanes,
    ZPixmap
  );

  return XGetPixel(image,0,0);
}

Fonction fillGrid

La fonction fillGrid analyse l’écran et remplit un tableau de lettres correspondant à chaque couleur. Et une couleur “x” pour signaler que la couleur n’a pas pu être déterminée. Étant donné que Plock fait usage de pleins de petites animations, il est naturel que cela se produise. Par contre, si aucune couleur n’a pu être détectée, la fonction renvoie FALSE pour l’indiquer.

int fillGrid(char grid[ROWS][COLUMNS]) {
  int i,j,cx=0;

  for(j=0;j<ROWS;j++) {
    for(i=0;i<COLUMNS;i++) {
      switch(getPixel(STARTX+i*WIDTH,STARTY+j*HEIGHT)) {
        case ORANGE: grid[j][i]='o'; break;
        case VERT  : grid[j][i]='g'; break;
        case BLANC : grid[j][i]='w'; break;
        case ROSE  : grid[j][i]='r'; break;
        case VIOLET: grid[j][i]='v'; break;
        case BLEU  : grid[j][i]='b'; break;
        default    : grid[j][i]='x'; cx++;
      }
    }
  }

  if(cx==(ROWS*COLUMNS)) {
    return FALSE;
  } else {
    return TRUE;
  }
}

Fonction printGrid

Cette fonction affiche juste le contenu de la grille. Elle est utilisée pour le débogage.

void printGrid(char grid[ROWS][COLUMNS]) {
  int i,j;
  for(j=0;j<ROWS;j++) {
    for(i=0;i<COLUMNS;i++) {
      printf("%c",grid[j][i]);
    }
    printf("\n");
  }
}

Fonction searchTwins

La fonction searchTwins recherche 2 blocs adjacents de couleur identique. Pour obtenir naturellement des ensembles de blocs conséquents, on privilégie les couleurs dans un ordre quelconque. Ensuite on recherche d’abord 2 couleurs horizontalement et enfin verticalement.

Comme vous le voyez, l’algorithme de recherche est très basique…

int searchTwins(char grid[ROWS][COLUMNS],int *x,int *y) {
  int i,j,c;
  char couleurs[]="ogwrvb";

  for(c=0;c<6;c++) {
    /* Horizontal search */
    for(j=0;j<ROWS;j++) {
      for(i=0;i<COLUMNS-1;i++) {
        if(grid[j][i]!=couleurs[c]) continue;
        if(grid[j][i]==grid[j][i+1]) {
          *x=i; *y=j;
          return TRUE;
        }
      }
    }

    /* Vertical search */
    for(j=0;j<ROWS-1;j++) {
      for(i=0;i<COLUMNS;i++) {
        if(grid[j][i]!=couleurs[c]) continue;
        if(grid[j][i]==grid[j+1][i]) {
          *x=i; *y=j;
          return TRUE;
        }
      }
    }
  }

  return FALSE;
}

Fonction main

La fonction main consiste en une boucle récupérant la disposition des blocs et l’analysant. Quand 2 blocs adjacents sont trouvés, le curseur souris est déplacé sur le premier bloc et un clic est généré. On fait une petite pause de 20 millisecondes entre le déplacement de la souris et le clic et de 40 millisecondes entre chaque clic.

int main(int argc,char **argv) {
  char grid[ROWS][COLUMNS];
  int i,j;
  int x,y;

  display=XOpenDisplay(NULL);
  rootwindow=RootWindow(display,DefaultScreen(display));

  i=-1;
  j=-1;

  while(fillGrid(grid)) {
    if(searchTwins(grid,&i,&j)) {
      printf("[%d,%d]\n",i,j);
      x=STARTX+i*WIDTH+WIDTH/2;
      y=STARTY+j*HEIGHT;
      mouseMove(x,y);
      usleep(20000);
      mouseClick(1);
    }
    usleep(40000);
  }

Actions

Information

3 responses

14 11 2009
Niko

Imposteur, va…
Comment veux-tu rivaliser ?

25 01 2010
Piel92

Bravo!
Ton BOT est très bien trouvé, mais tu pourrais intégrer une IA pour qu’il clique sur les blocs les plus aventageux.
Bonne continuation.

p-s: pourrais-tu me donner l’équivalent de cette source en C pour windows grâce a msdn?
Merci d’avance.

26 01 2010
zigazou

Merci !

Pour l’instant je suis surtout limité par la lenteur du plugin Flash sous Linux plus que par le choix des blocs…

Et concernant une version C pour Windows/MSDN, je ne suis malheureusement pas en mesure de te la fournir : d’une part je n’ai pas Windows, d’autre part, ça va faire quelques années que je n’ai pas mis les mains dans le développement C sous cet environnement…

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s




%d blogueurs aiment cette page :