Intelligence artificielle – jeux vidéo – pathfinding
Pour illustrer l’intelligence artificielle et le pathfinding dans le jeu vidéo, la question est connaissez vous le jeu Berzerk? Pour ceux qui ne connaissent pas. Il s’agit d’un jeu dans lequel le joueur se déplace de pièces en pièces. Bien sur, chaque pièce regorge de robots qui cherchent à l’éliminer en le poursuivant. Et pour passer d’un pièce à l’autre, il lui faut abattre tous ses ennemis.
Je fais référence à Berzerk parce que ce jeu illustre parfaitement l’usage d’un algorithme simple, le Crash and Turn Algorithm. Facile à mettre en œuvre, cet algorithme simule une poursuite. Par conséquent, c’est un premier pas dans l’intelligence artificielle dans le jeu vidéo.
Je vous montre comment développer et utiliser cet algorithme Crash and Turn en javascript.
Dans cette première partie, vous créerez un lecteur et un afficheur de labyrinthe. Ceci pour rendre la modification rapide pour les différents tests à faire.
Que fait cet algorithme de pathfinding?
L’objectif de l’algorithme Crash and Turn est de déplacer seul d’un lieu A vers un lieu B.
L’algorithme Crash and Turn consiste à se déplacer droit devant jusqu’à la rencontre d’un obstacle. Lorsqu’on rencontre l’obstacle, alors on change de direction à droite ou à gauche. Puis on se déplace droit devant jusqu’au nouvel obstacle.
Le lecteur afficheur de labyrinthe
Je vous propose donc de créer une fonction qui lit une structure de données représentative d’un labyrinthe et l’affiche dans un canvas html5.
Dans un premier temps, une fonction qui crée un canvas html5 et l’intègre dans un élément html. Ainsi cette fonction prend 6 paramètres. Un identifiant, sa largeur, sa hauteur, sa position sur la pile des éléments affichés à l’écran, l’élément html auquel il est rattaché et sa couleur.
let createCanvasContext = function(name, width, height, zindex, htmlElement, color) {
let canvas = window.document.createElement("canvas");
canvas.id = name;
canvas.style.position = "absolute";
if ( color != undefined )
canvas.style.background = color;
canvas.style.zIndex = zindex;
canvas.width = width;
canvas.height = height;
if ( htmlElement != undefined )
htmlElement.appendChild(canvas.getContext('2d').canvas);
return canvas.getContext('2d');
}C’est une autre fonction qui permet d’afficher les murs du labyrinthe, un simple carré de 10 pixels sur 10. Cette fonction prend en paramètre le canvasContext dans lequel le mur est affiché, sa couleur et sa position.
let showSquare = function(canvasContext,color,x,y) {
canvasContext.beginPath();
canvasContext.rect(x*10,y*10,10,10);
canvasContext.fillStyle = color;
canvasContext.fill();
canvasContext.stroke();
}Ensuite trois fonctions pour afficher mur, joueur et ennemi.
let showWall = function(canvasContext,x,y) {
showSquare(canvasContext,"yellow",x,y);
}
let showPlayer = function(canvasContext,x,y) {
showSquare(canvasContext,"yellow",x,y);
}
let showEnemy = function(canvasContext,x,y) {
showSquare(canvasContext,"red",x,y);
}Pour l’exemple tout sera représenté par un simple carré. Les murs en gris, l’ennemi en rouge et le joueur en jaune.
Pour terminer, la fonction lit la structure de données et l’affiche dans le canvas html5. Elle modifie la structure de données en y enlevant le joueur et l’ennemi.
let initGameGrid = function() {
for(let i in walls) {
let line = walls[i];
let element = line.split("");
for(let j in element) {
if ( element[ j ] == "#" ) {
showWall(gameCanvasContext,j,i);
} else if ( element[ j ] == "E" ) {
showPlayer(gameCanvasContext,j,i);
element[ j ] = " ";
} else if ( element[ j ] == "P" ) {
showPlayer(gameCanvasContext,j,i);
element[ j ] = " ";
}
}
}
}Et la structure de données json avant lecture pour affichage. Le signe # représente un mur, la lettre E représente l’ennemi qui se déplace automatiquement. La lettre P représente le joueur vers lequel l’ennemi E se déplace.
let walls = {
0: " ",
1: " # ",
2: " # ",
3: " ",
4: " ",
5: " ",
6: " # ",
7: " # # ",
8: " # # ",
9: " E # P ",
10: " # ",
11: " # # ",
12: " # # ",
13: " # # ",
14: " ",
15: " ",
16: " ",
17: " # ",
18: " # ",
19: " "
}Et la structure de données json après lecture pour affichage.
0: " ",
1: " # ",
2: " # ",
3: " ",
4: " ",
5: " ",
6: " # ",
7: " # # ",
8: " # # ",
9: " # ",
10: " # ",
11: " # # ",
12: " # # ",
13: " # # ",
14: " ",
15: " ",
16: " ",
17: " # ",
18: " # ",
19: " "Remarquez qu’il devient facile de modifier le labyrinthe.
Le code complet
<html>
<body>
<div id="gameDiv" style="margin-left:auto;margin-right:auto;width:1168px;height:740px;">
</div>
</body>
<script>
(function() {
let createCanvasContext = function(name, width, height, zindex, htmlElement, color) {
let canvas = window.document.createElement("canvas");
canvas.id = name;
canvas.style.position = "absolute";
if ( color != undefined )
canvas.style.background = color;
canvas.style.zIndex = zindex;
canvas.width = width;
canvas.height = height;
if ( htmlElement != undefined )
htmlElement.appendChild(canvas.getContext('2d').canvas);
return canvas.getContext('2d');
}
let showSquare = function(canvasContext,color,x,y) {
canvasContext.beginPath();
canvasContext.rect(x*10,y*10,10,10);
canvasContext.fillStyle = color;
canvasContext.fill();
canvasContext.stroke();
}
let showWall = function(canvasContext,x,y) {
showSquare(canvasContext,"grey",x,y);
}
let showPlayer = function(canvasContext,x,y) {
showSquare(canvasContext,"yellow",x,y);
}
let showEnemy = function(canvasContext,x,y) {
showSquare(canvasContext,"red",x,y);
}
let initGameGrid = function() {
for(let i in walls) {
let line = walls[i];
let element = line.split("");
for(let j in element) {
if ( element[ j ] == "#" ) {
showWall(gameCanvasContext,j,i);
} else if ( element[ j ] == "E" ) {
showEnemy(gameCanvasContext,j,i);
element[ j ] = " ";
} else if ( element[ j ] == "P" ) {
showPlayer(gameCanvasContext,j,i);
element[ j ] = " ";
}
}
}
}
let walls = {
0: " ",
1: " # ",
2: " # ",
3: " ",
4: " ",
5: " ",
6: " # ",
7: " # # ",
8: " # # ",
9: " E # P ",
10: " # ",
11: " # # ",
12: " # # ",
13: " # # ",
14: " ",
15: " ",
16: " ",
17: " # ",
18: " # ",
19: " "
}
let gameDiv = document.getElementById("gameDiv");
let gameCanvasContext = createCanvasContext("game",200,200,1,gameDiv,"#000000");
initGameGrid();
})();
</script>
</html>Ce qui donne.
