La fèche rouge
Aujourd’hui je vais entamer un truc super cool, le pathfinding, c’est-à-dire la recherche de chemin, court si possible (ben ouais sinon c’est pas intéressant).
Ce qui est marrant, c’est que tout le projet est un peu parti de là. Il y a deux ans de cela, je travaillais avec Loic, un développeur passionné de jeux vidéo. Je me souviens, à l’époque on avait évoqué Advance Wars et on avait entamé une discussion sur ce qu’on avait appelé l’algorithme de la flèche rouge, qui permettait d’afficher le déplacement d’une unité dans le jeu, marqué par une super grosse flèche rouge. Sa particularité était qu’en fonction de tel ou tel obstacle, le système calculait toujours le chemin le plus économique en terme de « point de mouvement ». On avait réfléchi ensemble sur comment on l’aurait codé si on avait dû repartir de zéro. À un moment on avait même pensé développer le jeu ensemble, mais ça ne s’est jamais fait.
Et comme je m’appelle Yann et que je suis un bonhomme, j’ai décidé de développer le jeu en solo ! Enfin… avec mon pote Chewbacca. Plus sérieusement, voici un exemple pris directement en jeu.
Idée
L’idée que j’ai eue, c’est de créer un grille de déplacement et de partir d’une position de départ qui serait celle de l’unité à déplacer et d’ajouter des numéros sur chaque case de la grille qui correspondrait au nombre de point de mouvement (pm) nécessaire à cette unité pour arriver dessus. Et en pointant une case d’arrivée, afficher le chemin en recherchant systématiquement les cases adjacentes les plus petites.
Profil du terrain
Comme tu l’as vu en partie 1, ma map est un tableau où chaque case est représentée par un numéro qui correspond à un décors. Maintenant, je vais créer une nouvelle grille qui correspondra au profil de la carte, c’est-à-dire qui montre le type de terrain. J’ai choisi d’utiliser des lettres et des chiffres, a est une case normale, -1 est une forêt, x est une montagne et 1 correspond à la position de mon unité.
$map_for_tank = array(
0 => array("x","x","x","x","x","x","x","x","x","x","x","x","x","x","x",),
1 => array("x","x","a","-1","a","a","a","a","a","a","-1","a","a","a","x",),
2 => array("x","a","a","-1","a","-1","x","a","a","a","a","a","a","a","x",),
3 => array("x","a","a","a","a","x","x","x","a","a","x","a","a","a","x",),
4 => array("x","a","a","a","a","x","x","x","a","a","x","a","a","a","x",),
5 => array("x","a","a","a","a","x","x","-1","a","a","a","a","a","a","x",),
6 => array("x","a","a","a","a","a","a","-1","-1","a","x","x","a","x","x",),
7 => array("x","x","a","a","a","a","a","a","a","a","x","x","a","a","x",),
8 => array("x","x","x","x","x","a","x","-1","a","a","a","a","a","a","x",),
9 => array("x","x","x","x","x","x","x","x","x","x","x","x","x","x","x",),
);
Je crée une classe algo_red_arrow qui va se charger de calculer la grille et je définis quelques variables, dont la position d’origine, pour avoir un point de référence. J’appelle la fonction d’initialisation et au passage je crée la méthode display_tab pour afficher la map et rendre ça un peu plus digeste.
class algo_red_arrow{
public function __construct(){
}
public function init_map(&$arr,$y,$x, $largeur, $hauteur){
$this->display_tab($arr,$y,$x);
}
}
$map = $map = $map_for_tank;
//position de départ
$position_x = 3;
$position_y = 6;
$map[$position_y][$position_x] = 1;
$grid = new algo_red_arrow();
//calcule de la largeur et hauteur
$largeur = count($map[0]);
$hauteur = count($map);
$grid->init_map($map,$position_y,$position_x,$largeur, $hauteur);
public function display_tab($arr,$y,$x,$end_y = 0, $end_x = 0){
echo "<table border='1' cellpadding='0' cellspacing='0' style='float:left; margin:10px;'>";
foreach($arr as $k => $v){
echo "<tr>";
foreach($v as $k2 => $v2){
if($y == $k && $x == $k2){
echo "<td style='width:30px; height:30px; text-align:center; background-color:red;'>";
}elseif($end_y == $k && $end_x == $k2){
echo "<td style='width:30px; height:30px; text-align:center; background-color:yellow;'>";
}elseif($v2 == "x"){
echo "<td style='width:30px; height:30px; text-align:center; background-color:black; color:white'>";
}else{
echo "<td style='width:30px; height:30px; text-align:center;'>";
}
echo $v2;
echo "</td>";
}
echo "</tr>";
}
echo "</table>";
}
Alors voici ce que ça donne, les cases blanches représentent des terrains franchissables et les noires des terrains qui ne le sont pas. L’unité que je veux déplacer est représentée par la case rouge, et la case jaune est la case d’arrivée, mais comme je ne l’ai pas encore définie, par défaut elle se met en 0,0.
Déplacement de base
La première étape consiste à remplir toutes les cases disponibles (qui ne sont pas égales à x) et à avoir une grille avec des valeurs de plus en plus élevées dans les cases les plus éloignées de l’origine (case rouge), mais pour faire ça je vais avoir besoin au préalable de créer quelques méthodes.
La méthode plus_proche_chemin va être une méthode qui recherche la case avec la valeur la plus petite autours de la case courante. Au niveau du code, je définis un minima super grand, puis je cherche la case adjacente la plus petite (haut, droit, bas, gauche) en prenant soin de tester si la case existe et si elle est plus grande que 0. À la fin de la fonction je retourne soit false soit le minima.
public function plus_proche_chemin(&$arr,$y,$x, $force_return = false){
//fixe une valeur minimale très haute
$min = 99999999;
//haut
if(isset($arr[$y-1][$x])){
if($arr[$y-1][$x] > 0){
$min = $arr[$y-1][$x];
}
}
//droite
if(isset($arr[$y][$x+1])){
if($arr[$y][$x+1] > 0){
if($arr[$y][$x+1] < $min){
$min = $arr[$y][$x+1];
}
}
}
//bas
if(isset($arr[$y+1][$x])){
if($arr[$y+1][$x] > 0){
if($arr[$y+1][$x] < $min){
$min = $arr[$y+1][$x];
}
}
}
//gauche
if(isset($arr[$y][$x-1])){
if($arr[$y][$x-1] > 0){
if($arr[$y][$x-1] < $min){
$min = $arr[$y][$x-1];
}
}
}
if($min < 99999999){
return $min;
}else{
return false;
}
}
La seconde méthode calculate_one_deplacement va me permettre de boucler sur chaque case de la grille et de lancer la méthode plus_proche_chemin (juste au dessus). Si pour une case un minima à été trouvé, alors cette même case vaut ce minima incrémenté de 1.
public function calculate_one_deplacement($arr, &$standart_array, $largeur, $hauteur){
//fini
$fini = true;
//création du tableau
for($tmp_hauteur = 0; $tmp_hauteur < $hauteur; $tmp_hauteur++){
for($tmp_largeur = 0; $tmp_largeur < $largeur; $tmp_largeur++){
//construction grille
if($standart_array[$tmp_hauteur][$tmp_largeur] == "a" || $standart_array[$tmp_hauteur][$tmp_largeur] < 0){
$valeur = $this->plus_proche_chemin($standart_array, $tmp_hauteur, $tmp_largeur,true);
if(!empty($valeur)){
$standart_array[$tmp_hauteur][$tmp_largeur] = intval( $valeur ) + 1;
//défini la grille comme non finie
$fini = false;
}
}elseif($standart_array[$tmp_hauteur][$tmp_largeur] == "x"){
$standart_array[$tmp_hauteur][$tmp_largeur] = "";
}
}
}
return $fini;
}
Enfin la méthode generate_defaut_grid va appeler la méthode calculate_one_deplacement et répéter celle-ci jusqu’à ce que plus aucune case ne soit trouvée.
public function generate_defaut_grid($arr, $largeur, $hauteur){
//tableau par défaut
$standart_array = $arr;
//on défini la grille comme non finie
$grille_fini = false;
//tant que la grille n'est pas finie on traite la grille
while($grille_fini == false){
$grille_fini = $this->calculate_one_deplacement($arr,$standart_array, $largeur, $hauteur);
}
//si la grille est finie on la retourne
return $standart_array;
}
Je lance le calcul depuis l’init_map et j’affiche le résultat.
public function init_map(&$arr,$y,$x, $largeur, $hauteur){
$grille_deplacement_standart = $this->generate_defaut_grid($arr, $largeur,$hauteur);
$this->display_tab($grille_deplacement_standart,$y,$x);
}
Le droit chemin
Dans le jeu, chaque unité peut se déplacer soit en haut, à droite, en bas ou à gauche, il n’y pas de déplacement en diagonal, et l’algorithme préfère toujours des chemins avec le moins de changement de direction possible. Je dois donc intégrer des pénalités pour chaque changement de direction à ma grille de déplacement.
L’idée c’est de faire une croix à partir de la position de départ, qui représente les déplacements en ligne dans chaque direction. Ensuite c’est de vérifier pour chaque case s’il existe une case « voisine », de récupérer cette valeur, de l’affecter à la case courante et de l’incrémenter de 1.
La croix ! Rien de compliqué, je fais 4 boucles depuis la position de départ, vers le haut, la droite, le bas et la gauche et pour chaque boucle je définis la variable $valeur_de_la_case à 1 (c’est la valeur de la case de base). Au fur et à mesure que je parcours une direction, si je tombe sur la lettre a, alors j’affecte cette case avec la valeur de la variable. En fait, je considère qu’il n’y a pas encore de changement de direction, si jamais c’est une pénalité de terrain alors j’incrémente la valeur avec la valeur absolue de la pénalité et si je tombe sur un x alors je stoppe la bouche (cul de sac).
public function calcul_croix($arr, $y, $x, $largeur, $hauteur){
//valeur de base
$valeur_de_la_case = 1;
//axe haut
for($i = $y-1; $i >= 0; $i--){
if($arr[$i][$x] == "x"){
break;
}elseif($arr[$i][$x] == "a"){
$arr[$i][$x] = $valeur_de_la_case;
}elseif($arr[$i][$x] != "a" && $arr[$i][$x] < 0 ){
//obstacle
//récupération de la valeur
$valeur_de_la_case += $arr[$i][$x] * (-1);
$arr[$i][$x] = $valeur_de_la_case;
}
}
//axe bas
$valeur_de_la_case = 1;
for($i = $y+1; $i < $hauteur; $i++){
if($arr[$i][$x] == "x"){
break;
}if($arr[$i][$x] == "a"){
$arr[$i][$x] = $valeur_de_la_case;
}elseif($arr[$i][$x] != "a" && $arr[$i][$x] < 0 ){
//obstacle
//récupération de la valeur
$valeur_de_la_case += $arr[$i][$x] * (-1);
$arr[$i][$x] = $valeur_de_la_case;
}
}
//axe gauche
$valeur_de_la_case = 1;
for($i = $x-1; $i >= 0; $i--){
if($arr[$y][$i] == "x"){
break;
}if($arr[$y][$i] == "a"){
$arr[$y][$i] = $valeur_de_la_case;
}elseif($arr[$y][$i] != "a" && $arr[$y][$i] < 0 ){
//obstacle
//récupération de la valeur
$valeur_de_la_case += $arr[$y][$i] * (-1);
$arr[$y][$i] = $valeur_de_la_case;
}
}
//axe droite
$valeur_de_la_case = 1;
for($i = $x+1; $i < $largeur; $i++){
if($arr[$y][$i] == "x"){
break;
}if($arr[$y][$i] == "a"){
$arr[$y][$i] = $valeur_de_la_case;
}elseif($arr[$y][$i] != "a" && $arr[$y][$i] < 0 ){
//obstacle
//récupération de la valeur
$valeur_de_la_case += $arr[$y][$i] * (-1);
$arr[$y][$i] = $valeur_de_la_case;
}
}
//retourne la map avec la croix
return $arr;
}
J’appelle le calcul de la croix et dans l’init j’affiche le résultat.
public function init_map(&$arr,$y,$x, $largeur, $hauteur){
$grille_deplacement_standart = $this->generate_defaut_grid($arr, $largeur,$hauteur);
$arr = $this->calcul_croix($arr, $y, $x, $largeur, $hauteur);
$this->display_tab($arr,$y,$x);
}
Et maintenant la résolution des changements de direction avec la méthode valeur_hors_croix. Je récupère les différents « voisins » que je stocke dans le tableau $valeur_adjacente et je donne comme valeur à la case, le plus petit voisin incrémenté de 1, sans oublier de l’additionner avec la variable facteur qui contient la pénalité de terrain.
public function valeur_hors_croix(&$arr, $largeur, $hauteur){
//copie du tableau
$arr_find_empty_value = $arr;
//est-ce que la grille est finie (on suppose que oui)
$grille_fini = true;
//parcours de la grille
for($tmp_hauteur = 0; $tmp_hauteur < $hauteur; $tmp_hauteur++){
for($tmp_largeur = 0; $tmp_largeur < $largeur; $tmp_largeur++){
//si la pièce est un vide alors on cherche dans tous les sens la plus proche pièce
//si la pièce est un obstacle on calcule aussi sa valeur
if( $arr[$tmp_hauteur][$tmp_largeur] == "a" || $arr[$tmp_hauteur][$tmp_largeur] < 0){
//si il y a un obstacle on calcule la valeur de la nouvelle pièce
$facteur = 1;
if($arr[$tmp_hauteur][$tmp_largeur] < 0 ){
$facteur += $arr[$tmp_hauteur][$tmp_largeur]*(-1);
}
//tableau qui contiendra les différentes valeurs adjacentes
$valeur_adjacente = array();
//haut
for($i = $tmp_hauteur-1; $i >= 0; $i--){
if($arr[$i][$tmp_largeur] == "x" || $arr[$i][$tmp_largeur] < 0){
break;
}elseif($arr[$i][$tmp_largeur] > 0){
$valeur_adjacente[] = $arr[$i][$tmp_largeur]+$facteur;
break;
}
}
//bas
for($i = $tmp_hauteur+1; $i < $hauteur; $i++){
if($arr[$i][$tmp_largeur] == "x" || $arr[$i][$tmp_largeur] < 0){
break;
}elseif($arr[$i][$tmp_largeur] > 0){
$valeur_adjacente[] = $arr[$i][$tmp_largeur]+$facteur;
break;
}
}
//gauche
for($i = $tmp_largeur-1; $i >= 0; $i--){
if($arr[$tmp_hauteur][$i] == "x" || $arr[$tmp_hauteur][$i] < 0){
break;
}elseif($arr[$tmp_hauteur][$i] > 0){
$valeur_adjacente[] = $arr[$tmp_hauteur][$i]+$facteur;
break;
}
}
//droite
for($i = $tmp_largeur+1; $i < $largeur; $i++){
if($arr[$tmp_hauteur][$i] == "x" || $arr[$tmp_hauteur][$i] < 0){
break;
}elseif($arr[$tmp_hauteur][$i] > 0){
$valeur_adjacente[] = $arr[$tmp_hauteur][$i]+$facteur;
break;
}
}
//recherche du plus petit nombre
if(!empty($valeur_adjacente)){
//s'il y a une case qui change on défini la grille comme non finie
$grille_fini = false;
$arr_find_empty_value[$tmp_hauteur][$tmp_largeur] = min($valeur_adjacente);
}
}
//break;
}
//break;
}
//le tableau avec les valeurs trouvées devient le nouveau tableau
$arr = $arr_find_empty_value;
//on retourne l'état de la grille
return $grille_fini;
}
Si ça peut t’aider voici ce que je sous-entends par voisin.
Sans oublier la boucle et l’appel de la méthode, que je place dans l’init.
public function init_map(&$arr,$y,$x, $largeur, $hauteur){
$grille_deplacement_standart = $this->generate_defaut_grid($arr, $largeur,$hauteur);
$arr = $this->calcul_croix($arr, $y, $x, $largeur, $hauteur);
$this->display_tab($arr,$y,$x);
//pour chaque case vérifier les lignes les plus proches
$grille_fini = false;
while($grille_fini == false){
//calcule des valeurs hors de l'axe
$grille_fini = $this->valeur_hors_croix($arr, $largeur, $hauteur);
$this->display_tab($arr,$y,$x);
}
}
Voici un aperçu de ce qui se passe pendant le traitement de l’algorithme valeur_hors_croix.
Fusion
Pour obtenir la grille finale, je merge les deux grilles que je viens de calculer et je redéfinis la case d’origine à 1.
Démo
Cet algorithme m’a demandé un bon mois de réflexion et presque 2 semaines de travail, mais je suis très content du résultat. Je l’ai intégré à ma carte, et ça marche très bien ! Dans un prochain article je t’expliquerai comment placer cette fameuse flèche rouge !
24/04/2016
Yann Vangampelaere - nouslesdevs -
