Intelligence artificielle – jeux vidéo – pathfinding – contourner les murs
Suite de la série consacrée à l’intelligence artificielle appliquée au jeu vidéo : le déplacement vers la cible.
Je vous conseille de lire les articles précédents dans l’ordre :
– Intelligence artificielle – jeux vidéo javascript – crash and turn
– Intelligence artificielle – jeux vidéo javascript – Gestion du déplacement
– Intelligence artificielle – jeux vidéo javascript – Gestion des obstacles
– Intelligence artificielle – jeux vidéo javascript – Se déplacer vers la cible
Introduction
Voici le dernier article de la série Intelligence artificielle – jeu vidéo 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 existe au moins un chemin pour atteindre la cible.
Allez, au boulot…
Au commencement…
D’abord le labyrinthe qui fait chier (n’ayons pas peur des mots).
let 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. Le fait que l’enemy traverse le mur vient d’une mauvaise information qui lui est donnée. 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.
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() {
let 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) {
let returnValue = false;
let 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.
let 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, cliquez 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 ne tourne pas rond.
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. Notre petit robot écoute ce qu’on lui dit, il prend la direction et passe à travers le mur.
Alors ajoutons 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 évite les successions d’instructions if, ce sera déjà du foutoir 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 :
let 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) {
let xDirection;
let yDirection;
let xDist;
let 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) {
let 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) {
let xDirection;
let yDirection;
let xDist;
let 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.
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 que crash and turn, 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.
