Intelligence artificielle – jeux vidéo – fini le passe muraille

 

Suite de l’article Intelligence artificiellejeux vidéo javascript – obstacle, il faut maintenant atteindre la cible.
Je vous conseille de lire les articles précédents dans l’ordre :
Intelligence artificiellejeux vidéo javascript – crash and turn
Intelligence artificiellejeux vidéo javascript – mouvement
Intelligence artificiellejeux vidéo javascript – obstacle
Intelligence artificiellejeux vidéo javascript – atteindre la cible

 

Introduction

Voici le dernier article de la série sur l’algorithme crash and turn. Peut être me direz vous enfin!!!

Bref, en l’état le petit enemy trouve sa cible sans problème dans un labyrinthe. Cependant, ce même labyrinthe doit respecter certaines caractéristiques : les murs peuvent être horizontaux ou verticaux mais un mur horizontal ne peut être accolé à un mur vertical et vice-versa.

Si ces caractéristiques ne sont pas respectées, notre petit enemy traverse les murs.

Peut-être cela suffit-il ? Mais bon, il conviendrait de s’affranchir de ces limites pour pouvoir faire des labyrinthes sans contraintes.

Il y a tout de même une contrainte incontournable quelque soit le labyrinthe, il doit exister au moins un chemin pour atteindre la cible.

Allez, au boulot les feignasses…

 

Au commencement…

D’abord le labyrinthe qui fait chier (n’ayons pas peur des mots).

var walls = {
  0:  "                    ",
  1:  "              #     ",
  2:  "              #     ",
  3:  "                    ",
  4:  "                    ",
  5:  "                    ",
  6:  "              #     ",
  7:  "         #    #     ",
  8:  "         #    #     ",
  9:  "  E           #  P  ",
  10: "              #     ",
  11: "         #  ###     ",
  12: "         #    #     ",
  13: "         #    #     ",
  14: "                    ",
  15: "                    ",
  16: "                    ",
  17: "              #     ",
  18: "              #     ",
  19: "                    "
 }

Pour voir le passe muraille en action, cliquez sur Passe Muraille en action.

 

Fini les pouvoirs

Terminé passe muraille, l’intelligence artificielle va réfléchir un peu plus.

En regardant d’un peu plus près ce qui se passe, on constate que le problème vient du choix de la direction : ce qui fait que l’enemy traverse le mur vient d’une mauvaise information qui lui est donné : on lui dit qu’il peut aller là ou il y a un mur, donc il y va. Tout ça est virtuel, donc il peut le faire.

Donc c’est la méthode searchDirectionTarget qui est déconnante. Il faut donc modifier cette fonction.

Il suffit lorsqu’une direction est donnée, de vérifier qu’effectivement il n’y a pas un mur devant en utilisant la méthode wallDSPInFrontOf et en lui ajoutant un paramètre direction.

  wallDSPInFrontOf : function() {
    var returnValue = false;
    switch ( this.currentDirection ) {
	 case "E":
	  if (this.x+1 >=20 || walls[this.y][this.x+1] == "#")
		returnValue = true;
	  break;
 
	 case "W":
	  if (this.x-1 <0 || walls[this.y][this.x-1] == "#")
		returnValue = true;
      break;
 
	 case "N":
	  if (this.y-1 <0 || walls[this.y-1][this.x] == "#")
		returnValue = true;
      break;
 
	 case "S":
	  if (this.y+1 >=20 || walls[this.y+1][this.x] == "#")
		returnValue = true;
      break;
	}
	return returnValue;
  }

devient

  wallDSPInFrontOf : function(frontOfDirection) {
    var returnValue = false;
    var lDirection = frontOfDirection == undefined ? this.currentDirection : frontOfDirection;
    switch ( lDirection ) {
	 case "E":
	  if (this.x+1 >=20 || walls[this.y][this.x+1] == "#")
		returnValue = true;
	  break;
 
	 case "W":
	  if (this.x-1 <0 || walls[this.y][this.x-1] == "#")
		returnValue = true;
      break;
 
	 case "N":
	  if (this.y-1 <0 || walls[this.y-1][this.x] == "#")
		returnValue = true;
      break;
 
	 case "S":
	  if (this.y+1 >=20 || walls[this.y+1][this.x] == "#")
		returnValue = true;
      break;
	}
	return returnValue;
  },

Jusqu’ici, tout va bien, rien de complexe.

Vient ensuite la modification de la méthode searchDirectionTarget en y intégrant le test supplémentaire : lorsque je donne une direction, y a t-il un mur ?

Prenons le bout de code suivant extrait de la méthode searchDirectionTarget :

   ....
   if ( this.currentDirection != "E" && this.currentDirection != "W" ) {
    if ( enemy.x > player.x ) {
     xDist = enemy.x - player.x;
     xDirection  = "W";
    } else {
     xDist = player.x - enemy.x;
     xDirection  = "E";
    }
   }
   ....

En fonction d’une position par rapport au joueur (player), enemy décide d’une direction sans vérifier que celle-ci est un mur. Donc on rajoute cette vérification :

   ....
   if ( this.currentDirection != "E" && this.currentDirection != "W" ) {
    if ( enemy.x > player.x ) {
     xDist = enemy.x - player.x;
     xDirection  = "W";
     if ( this.wallDSPInFrontOf(xDirection) )
      xDirection = "E";
    } else {
     xDist = player.x - enemy.x;
     xDirection  = "E";
     if ( this.wallDSPInFrontOf(xDirection) )
      xDirection = "W";
    }
   }
   ....

On fait pareil pour l’axe Nord / Sud :

   ....
   if ( this.currentDirection != "N" && this.currentDirection != "S" ) {
    if ( enemy.y > player.y ) {
     yDist = enemy.y - player.y;
     yDirection  = "N";
     if ( this.wallDSPInFrontOf(yDirection) )
      yDirection = "S";
    } else {
     yDist = player.y - enemy.y;
     yDirection  = "S";
     if ( this.wallDSPInFrontOf(yDirection) )
      yDirection = "N";
    }   
   }
   ....

Pour le live, il suffit de cliquer sur TEST LIVE.



Eh là miracle, passe muraille n’est plus.

Hé bien non, il peut toujours traverser les murs lorsque qu’il y a un cul de sac ou une voie sans issue. Il suffit de tester avec le labyrinthe suivant :

var walls = {
  0:  "                    ",
  1:  "              #     ",
  2:  "              #     ",
  3:  "                    ",
  4:  "                    ",
  5:  "                    ",
  6:  "              #     ",
  7:  "         #    #     ",
  8:  "         #    #     ",
  9:  "  E           #  P  ",
  10: "            # #     ",
  11: "         #  ###     ",
  12: "         #    #     ",
  13: "         #    #     ",
  14: "                    ",
  15: "                    ",
  16: "                    ",
  17: "              #     ",
  18: "              #     ",
  19: "                    "
 }

Pour le live, il suffit de cliquer sur TEST LIVE.



Décidément, il commence à nous les briser cet enemy. Mais, croyez-moi, le développeur est toujours plus grand.

Voici pourquoi ça déconne.

En l’état, la méthode searchDirectionToTarget (appelée lorsqu’il y a un obstacle) cherche une direction cardinale (N, S, E, W) en fonction de sa direction courante :
– si la direction courante est N ou S, elle renvoie la direction E ou W selon la présence d’un mur en E ou W;
-> dans un cul de sac au Nord ou au Sud, il y a un mur à l’Est (E) et un mur à l’Ouest (W)
– si la direction courante est E ou W, elle renvoie la direction N ou S selon la présence d’un mur en N ou S.
-> dans un cul de sac au Est ou au Ouest, il y a un mur au Nord (N) et un mur au Sud (S)

Le cas du cul de sac renvoie donc une direction qui est un mur et donc notre petit robot écoute ce qu’on lui dit, prend la direction et passe à travers le mur.

Alors il suffit d’ajouter encore le test wallInFrontOf, me direz-vous!!!!

D’abord, c’est une solution au prix d’une succession d’instructions if et donc du code pas très élégant.

Je sais que ce qui a été produit n’est pas parfait en terme d’organisation de code. Malgré cela, si on peut éviter les successions d’inbstructions if, ce sera déjà du bordel en moins et un code moins endetté.

Ensuite c’est une solution qui se mord la queue…Et il y a plus simple pour pour résoudre le problème.

Il suffit de faire repartir l’enemy dans le sens opposé.

Ce qui oblige à sauvegarder ce sens : jusqu’ici l’enemy n’a que sa direction courante comme information.

Commencez par rajouter cette propriété previousDirection à l’objet enemy :

 var enemy = {
  x : 0,
  y : 0,
  
  previousDirection : undefined,
  currentDirection : undefined,
  xStep : 0,
  yStep : 0,

  ...
 }

Ensuite affectez lui la valeur de la direction courante (currentDirection) à chaque recherche de direction donc dans la méthode searchDirectionToTarget :

 searchDirectionToTarget : function(enemy, player) {
  var xDirection;
  var yDirection;   
  var xDist;
  var yDist;

  this.previousDirection = this.currentDirection;

  ...
}

Créez ensuite une nouvelle méthode à l’objet enemy qui donne la direction opposée à une direction donnée en paramètre :

 setOppositeDirection : function(direction) {
  var returnValue = "?";
  switch(direction) {
   case "E":
    returnValue = "W";
    break;
   case "W":
    returnValue = "E";
    break;
   case "N":
    returnValue = "S";
    break;
   case "S":
    returnValue = "N";
    break;
  }
  return returnValue;
 },

Il ne reste plus qu’à utiliser tout cela.

Souvenez-vous qu’en l’état, la méthode searchDirectionToTarget (appelée lorsqu’il y a un obstacle) cherche une direction cardinale (N, S, E, W) en fonction de sa direction courante :
– si la direction courante est N ou S, elle renvoie la direction E ou W selon la présence d’un mur en E ou W;
– si la direction courante est E ou W, elle renvoie la direction N ou S selon la présence d’un mur en N ou S.

Cette fonction ne gère pas la problématique du cul de sac.

Donc avant de renvoyer une direction, la méthode searchDirectionToTarget vérifie que les potentielles directions ne sont pas des murs.

Si c’est le cas, elle renvoie la direction opposée à la précédente direction (celle qui a servi à amener l’enemy là où il est).
Dans le cas contraire, elle recherche la meilleure direction en fonction de la position du player (ce qui est déjà fait dans le code existant).

Lorsque les potentielles directions sont des murs, la fonction donne la valeur « ? » à la direction courante pour indiquer que les directions potentielles ne sont pas possibles.

 searchDirectionToTarget : function(enemy, player) {
  ...
   
  if ( this.currentDirection != "E" && this.currentDirection != "W" ) {
   if ( this.wallDSPInFrontOf("E") && this.wallDSPInFrontOf("W") ) {
    this.currentDirection = "?";
   } else {
   ...
   }
  }

  if ( this.currentDirection != "N" && this.currentDirection != "S" ) {
   if ( this.wallDSPInFrontOf("N") && this.wallDSPInFrontOf("S") ) {
    this.currentDirection = "?";
   } else {
   ....
  }
 }

 ...
},

Si la valeur « ? » est donnée à la direction courante alors on donne comme valeur à la direction courante la valeur de la direction précédente (previousDirection).

 searchDirectionToTarget : function(enemy, player) {
  ....
 
 if ( this.currentDirection == "?" ) 
  this.currentDirection = this.setOppositeDirection(this.previousDirection);
 else {
  ...
 }
},

Le code de la méthode searchDirectionToTarget :

 searchDirectionToTarget : function(enemy, player) {
  var xDirection;
  var yDirection;   
  var xDist;
  var yDist;
  this.previousDirection = this.currentDirection;
   
  if ( this.currentDirection != "E" && this.currentDirection != "W" ) {
   if ( this.wallDSPInFrontOf("E") && this.wallDSPInFrontOf("W") ) {
    this.currentDirection = "?";
  } else {
   if ( enemy.x > player.x ) {
    xDist = enemy.x - player.x;
    xDirection  = "W";
    if ( this.wallDSPInFrontOf(xDirection) )
     xDirection = "E";
    } else {
     xDist = player.x - enemy.x;
     xDirection  = "E";
     if ( this.wallDSPInFrontOf(xDirection) )
      xDirection = "W";
    }
   }
  }
 
  if ( this.currentDirection != "N" && this.currentDirection != "S" ) {
   if ( this.wallDSPInFrontOf("N") && this.wallDSPInFrontOf("S") ) {
    this.currentDirection = "?";
   } else {
    if ( enemy.y > player.y ) {
     yDist = enemy.y - player.y;
     yDirection  = "N";
     if ( this.wallDSPInFrontOf(yDirection) )
      yDirection = "S";
    } else {
     yDist = player.y - enemy.y;
     yDirection  = "S";
     if ( this.wallDSPInFrontOf(yDirection) )
      yDirection = "N";
    }  
  }
 }
 
 if ( this.currentDirection == "?" ) 
  this.currentDirection = this.setOppositeDirection(this.previousDirection);
 else {
  if ( xDist > yDist ) {
   this.currentDirection = xDirection != undefined ? xDirection : yDirection;
  } else {
   this.currentDirection = yDirection != undefined ? yDirection : xDirection;
  }
 }
},

Pour le test en live, cliquez TEST LIVE.

 

Conclusion

La série sur l’algorithme crash and turn est terminée. Même s’il trouve toujours l’enemy, il ne le fait pas de manière optimale. En effet, il existe d’autres algorithmes préconisés dans la recherche de chemins, entre autres l’algorithme de Dijkstra. J’en parlerai dans un prochain article toujours dans le cadre du jeu vidéo javascript html5.

Des remarques, des améliorations, des idées, des coquilles : dites le. Faites savoir si cet article vous a été utile par un commentaire ou les réseaux sociaux.

 

Posté dans html5Taggé intelligence artificielle, intelligence artificielle jeu vidéo, jeu vidéo javascript  |  Laisser un commentaire

Répondre