Comment fonctionne l’IA de Bomber Dude ?


Tout d’abord, je tiens à préciser que je la trouve très faible, mais comme il y a pas mal de personnes qui m'on demandé comment marchait l'IA de Bomber Dude, je me suis dit que ça irait plus vite de faire un petit article dessus que de à chaque fois tout expliquer dans des tonnes de mails :p.

1) Les données accessibles à l’IA.

Je vais prendre comme exemple ce niveau :

L'essentiel de l’information disponible aux bots est sous forme de tableaux :

a) Tableau des collisions : (le rose et le rouge ne servent qu’a faire jolie. Dans ce tableau, une bombe est la même chose qu’un block permanent)

1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
1
1
0
1
1
1
0
1
0
1
0
1
1
0
0
1
0
0
0
0
0
0
1
1
0
1
1
1
0
1
0
1
0
1
1
0
0
0
0
0
0
0
0
0
1
1
0
1
0
1
0
1
0
1
0
1
1
0
0
0
0
0
0
0
0
0
1
1
0
1
0
1
0
1
0
1
0
1
1
0
0
0
0
0
0
0
0
0
1
1
0
1
0
1
0
1
0
1
0
1
1
0
0
0
1
1
0
0
0
0
1
1
0
1
0
1
0
1
0
1
0
1
1
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1


Ce tableau est généré au début de chaque partie et est updaté quand une bombe est posée ou explose.

 

 

b) Tableau des cases dangereuses : (les différents verts ne servent qu’a faire joli)

0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

Toutes les cases où il y a marqué ‘1’ sont dangereuses : quand les bombes exploseront, les explosions tueront tout ceux qui est dur une case avec marqué ‘1’.

À chaque fois que une bombe explose ou quelqu’un (un bot ou un joueur) pose une bombe, le tableau est updaté.

 

2) Le déplacement des bots.

Les bots se déplacent en se fixant des objectifs à très court terme. Un objectif est la case adjacente à atteindre.

Exemple : Si le bot a pour coordonnés :
x_bot = 32
y_bot = 32
les objectifs vont être:

pour aller en bas
pour aller en haut
pour aller à droite
pour aller à gauche
pour ne pas bouger
x_goal = 32
y_goal = 48
ou
x_goal = 32
y_goal = 16
ou
x_goal = 48
y_goal =32
ou
x_goal = 16
y_goal =32
ou
x_goal = 32
y_goal = 32


À chaque frame, le bot se déplace en direction de son objectif. Une fois qu’il a atteint son objectif, il se trouve un nouvel objectif :


if (x_bot > x_goal)
x_bot--;
if (x_bot < x_goal)
x_bot++;
if (y_bot > y_goal)
y_bot--;
if (y_bot < y_goal)
y_bot++;

if (x_bot == x_goal && y_bot == y_goal)
set_new_goal(&x_goal,&y_goal,x_bot,y_bot);


Remarque : Si on vient de poser une bombe sur la case où son objectif devait conduire le bot, il ne peux plus avancer car la case où il voulait aller était devenu une case dur. Dans les premières versions de Bomber Dude, le bot était coincé. Pour remédier à ce bug, à chaque fois que le bot est coincé, son objectif change et deviens de revenir sur la case précédente.

Bien entendu, ce qui est intéressant, c’est de savoir comment le bot se fixe des objectifs !

 

3) Mais en fonction de quoi le bot se fixe t-il des objectifs ? ^^

Il faut distinguer 2 situations :
*Le bot n’est pas dans une zone dangereuse, il est sur l’offensive.
*Le bot est dans une zone dangereuse, il est sur la défensive.

On aura donc :


void set_new_goal(short &xg,short &yg, short x, short y) {
   if (is_a_dangerous_zone(x,y)) {
      set_new_goal_offense(…);
   }
   else
	{
      set_new_goal_defense(…);
   }
}

En fonction de la situation de bot, il va se fixer des objectifs de manière différente :

 

 

a) Le bot sur l’offensive

Il n’est pas dans une zone dangereuse, donc il ne peut pas mourir là où il est. Il se fixe des objectifs de manière (attention c’est compliqué) aléatoire !

En fait il y a deux règles que le bot respecte :
- Il ne se fixera jamais un objectif dans une zone dangereuse (on regarde donc le Tableau des collisions)
- Il ne se fixera jamais un objectif dans un block dur (on regarde donc le Tableau des cases dangereuses)

Mais un bot sur l’offensive, ça ne fait pas que bouger : ça pose des bombes aussi ! A chaque fois qu’il doit se fixer un nouvel objectif, il a une chance sur 7 de tenter de poser une bombe.


Le code ressemble donc à cela :


void set_new_goal_offense(short &xg,short &yg, short x, short y) {
   short n=random(4);
   char dir_x[] = {-1,0,1,0};
   char dir_y[] = {0,-1,0,1};

   if ( not_dangerous(x,y,dix_x[n],dir_y[n]) && not_a_solid_block(x,y,dix_x[n],dir_y[n])) {
      N=random(7) ;
      *xg = x + dir_x[n]*16 ;
      *yg = y + dir_y[n]*16 ;
      if (random(7)==0)
      Try_to_put_bomb() ;
   }
}

 

(Remarque : On voit bien que cette fonction ne donne pas à chaque fois une nouvelle valeur à x_goal et y_goal. Cela n’est pas un problème car tant que un nouveau goal n’a pas été défini cette fonction est appelé à chaque frame. Cela signifie que le bot ne va pas bouger pendant quelques instant alors qu’il pourrais très bien bouger.)


J’insiste encore une fois sur le fait que le bot ne pose pas de bombes, il tente d’en poser.

 

 

b) Le bot sur la défensive

Le bot est dans une zone dangereuse et il risque de mourir. Il ne va donc pas chercher à mettre des bombes ! Il va faire qu’une seule chose : chercher à aller dans une zone non dangereuse.

Le problème est donc un problème de path finding : on connaître la direction (en haut, en bas, à droite, à gauche?) pour que le bot prenne le chemin vers la case la plus proche possible où il n’y a pas de danger.

Comment faire?
J’ai tout d’abord essayer de faire un algorithme récursif, mais j’ai échoué ! En fait j’ai trouvé une méthode mais elle était très lente… (la difficulté ne provient pas de réussir à trouver un algorithme mais de trouver un algorithme rapide).

En réfléchissant un peu j’ai trouvé une assez bonne solution que je vais tenter d'expliquer avec un exemple:


X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
0
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X

On a un tableau contenant toutes cases durs (les 'X'). La position du joueur est représenté par un 'J'.

 

 

 

1/ La première étape consiste a marquer les 4 cases aux alentours du joueur avec la valeur '1' dans une copie du 1er tableau et de marquer les directions par rapport au joueur dans une 2e tableau.
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
1
X
X
X
X
X
1
0
1
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X

Tableau contenant les blocks solides
X
X
X
X
X
U
X
L
R
X
D
X
X
X
X
X
X
X
X
X
X
X
X

Tableau contenant les directions par rapport à la case de départ.
 

2/ La 2e étape est une boucle: à chaque itération, on va chercher les cases d'indices 'n' (en lisant le tableau) et marquer les cases aux alentours d'un indice 'n+1' si elles n'ont pas déja une valeur. On obtient donc succéssivement:

X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
2
X
X
X
X
1
X
X
X
X
X
2
1
0
1
2
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X

 

X
X
X
X
U
X
U
X
L
L
R
R
X
D
X
X
X
X
X
X
X
X
X
X
X
X

 

1ère itération
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
3
X
X
X
X
3
2
3
X
X
X
3
X
1
X
X
X
X
X
3
2
1
0
1
2
3
X
X
X
3
X
X
X
3
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X

 

X
X
X
U
X
U
U
U
X
L
U
X
L
L
L
R
R
R
X
L
D
R
X
X
X
X
X
X
X
X
X
X
X
X

 

2e itération
X
X
X
X
X
X
X
X
X
X
X
4
X
X
X
X
3
X
X
X
X
4
3
2
3
4
X
X
X
3
X
1
X
X
X
X
X
4
3
2
1
0
1
2
3
X
X
X
3
X
X
X
3
X
X
X
4
4
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X

 

X
X
U
X
U
X
U
U
U
U
U
X
L
U
X
L
L
L
L
R
R
R
X
L
D
R
X
L
R
X
X
X
X
X
X
X
X
X
X
X

 

3e itération

etc...

Implémentation:

      for (x=0;x<10;x++) {
         for (y=0;y<10;y++) {
            if (distance[y][x] == d) {

               if (!solid[y][x+1] && distance[y][x+1]==-1) {
                  direction[y][x+1] = direction[y][x];
                  distance[y][x+1]=d+1;
               }


               if (!solid[y][x-1] && distance[y][x-1]==-1) {
                  direction[y][x-1] = direction[y][x];
                  distance[y][x-1]=d+1;
               }

               if (!solid[y+1][x] && distance[y+1][x]==-1) {
                  direction[y+1][x] = direction[y][x];
                  distance[y+1][x]=d+1;
               }

               if (!solid[y-1][x] && distance[y-1][x]==-1) {
                  direction[y-1][x] = direction[y][x];
                  distance[y-1][x]=d+1;
               }


            }
         }
      }
 
A chaque itération on vérifie si une des cases marquées n'est pas dans une zone dangereuse. Si oui, on arrête la recherche, et on dit au bot d'aller dans la direction enregistrées dans le 2e tableau pour cette même case.
L'avantage de cette technique est qu'elle est:

 

 

 

 

 

Une fois le chemin trouver, le bot sait dans quelle direction il doit aller (aller une case en haut, en bas, à gauche, à droite). Il peut donc changer son objectif.


Void set_new_goal_defense(short &xg,short &yg, short x, short y) {
   char dir_x[] = {-1,0,1,0};
   char dir_y[] = {0,-1,0,1};
   short direction = Find_dir_to_go(x,y);
   *xg = x + dir_x[n]*16 ;
   *yg = y + dir_y[n]*16 ;
}


(Remarque : le bot n’enregistre pas le chemin complet qu’il doit prendre. À chaque fois qu’il valide son objectif (c'est-à-dire à chaque fois qu’il bouge d’une case), le bot recalcule le chemin le plus court. Le bot n’enregistre pas le chemin le plus court parce que la topologie de la carte peut changer : Si on pose une bombe sur le chemin qu’il doit prendre, le bot sera coincé. De même, si un block explose, un chemin plus court peut soudainement exister)


4) La pose des bombes

Les bots vont poser un bombe seulement si après avoir poser la bombe, ils peuvent aller dans une zone non dangereuse: C’est pour éviter qu’ils se coincent.


5) Autres détails

-Dans les premières version du jeu, dès que l’on posait une bombe, les cases aux alentours devenaient dangereuses. Ce système comportait de nombreux défauts. Les bots étaient peureux (!) : ils ne s’approchaient
J’ai corrigé le système en rendant les cases dangereuses que quand les bombes allaient bientôt exploser. Mais cette technique force a tenir compte des explosions « en réseaux » : Une bombe qui vient d’être posée peut aussitôt exploser si une bombe posée avant explose à coté d’elle.

-Des gens se sont plaint que les bots restaient dans leurs coins. Pour changer ça j'ai