Différents algorithmes de recherche sont adaptés à différentes tâches. Aujourd'hui, nous allons parler de la recherche A*, l'un des algorithmes de recherche de chemin les plus efficaces. Celui-ci est très bien adapté aux jeux informatiques et à la création de graphiques de recherche tels que les trajets entre les villes, etc. Vous avez peut-être remarqué, par exemple, dans les jeux vidéo stratégiques ou tactiques, qu'après avoir appuyé sur un bouton, votre joueur ou votre groupe se met immédiatement et sans délai à parcourir le terrain jusqu'au point que vous avez spécifié. Il n'y a pas de retard précisément parce que les jeux utilisent des algorithmes efficaces qui calculent exactement comment le joueur doit se rendre quelque part. Ou un ennemi qui trouve sans équivoque le joueur et commence à marcher dans la bonne direction de loin. Habituellement, l’algorithme A* est utilisé pour de telles actions.
Qu'est-ce que l'algorithme A*
L'algorithme de recherche de chemin A* est un exemple d'algorithme de recherche du meilleur premier. Le but de l’algorithme A* est de trouver un chemin d’un point à un autre. C'est l'un des classiques de la recherche d'algorithmes de graphes. Voyons comment cela fonctionne à l'aide d'un exemple. Imaginez un jeu 2D avec une vue descendante. Divisons notre zone de jeu en carrés de cupidité, par exemple 8*8 cases comme un échiquier. Nos cellules peuvent être de deux types, praticables ou infranchissables (obstacle). À chaque période de temps, un joueur ou un ennemi qui s'approche du joueur se déplace d'une case. Dans les jeux, les cellules praticables peuvent être de nature différente, par exemple une route plate, de l'herbe ou du sable, qui détermine la difficulté de se déplacer le long d'elles, mais par souci de simplicité, nous supposerons que toutes les cellules praticables sont franchies de la même manière. Dans l’image ci-dessous, les cellules bleues représentent des obstacles.
Attribuons une cellule (ou nœud) comme cellule de départ (le personnage s'y trouve) et l'autre cellule comme cellule cible ou cible (celle avec le drapeau), et décrivons comment l'algorithme A* fonctionne dans ce cas. Le personnage est dans la cellule (1,1) et la cible est dans la cellule (7,7). Chaque cellule a des voisins horizontaux, verticaux et diagonaux. Cela dépend du jeu, si l'on calcule ou non les nœuds diagonaux. Par exemple, dans de nombreux jeux en vue descendante tels que Bomberman ou Pacman, les personnages ne peuvent se déplacer que horizontalement ou verticalement. Dans ce cas, chaque nœud, à l’exception des bords, n’a que 4 voisins. Si nous parlons d'un jeu où les personnages peuvent se déplacer en diagonale, chaque nœud peut avoir jusqu'à 8 voisins. A la première étape de l'algorithme, la cellule où se trouve le personnage a deux voisines. Plus précisément, trois, mais l'un d'eux constitue un obstacle. 
Il est clair que le chemin diagonal est plus long. si nous définissons le côté de notre cellule comme étant conditionnellement égal à un, alors la longueur de la diagonale de cette cellule est égale à la racine carrée de deux. C'est ce que dit le théorème de Pythagore. Pour passer de la cellule A à la cellule B, vous devez d’abord sélectionner l’une des cellules voisines, puis la suivante, et ainsi de suite. En cours de route, comprenez également s'il est possible de passer de la cellule initiale à la cellule cible. L'algorithme A* sélectionne à chaque étape l'une des cellules voisines en fonction de la valeur de la fonction F. Cette fonction mesure dans quelle mesure une cellule candidate doit être incluse dans notre chemin le plus court. Il s’agit de la fonction de coût, et c’est la somme de la fonction de déplacement G et de la fonction heuristique.
-
Coût G — est une distance par rapport à un nœud de départ.
-
Le coût H (heuristique) est une distance du nœud final (objectif). Cette fonction peut être différente, un développeur décide ce qui est le mieux. Le choix de H est peut-être le plus important dans A*, et c’est ce point qui rend plus ou moins efficace toute implémentation particulière de l’algorithme. Théoriquement, vous pouvez utiliser n’importe quelle fonction de votre choix.
Dans notre cas, nous connaissons la position de la cellule cible et pouvons, par exemple, calculer la distance euclidienne géométrique entre la cellule cible et la cellule actuelle. Plus la distance est courte, plus nous sommes proches du but.
-
Coût F = G + H. Ainsi, l'algorithme calcule les coûts F de tous les nœuds voisins et choisit l'un des coûts F les plus bas à examiner en premier. Lorsque nous en choisissons un, nous le marquons comme fermé et calculons les valeurs de ce nœud voisin.
Fonction heuristiqueComment calculer H ?
Il s'agit d'une fonction heuristique. Le nom lui-même signifie qu'il est déterminé par l'expérience et peut être différent. Ici, nous la prendrons égale à la distance dite euclidienne entre les points (x1, y1) et (x2, y2) :
Dans l'image, pour la première étape, il y a deux options, et elles ont le même coût, mais à l'étape suivante, le personnage se retrouve dans une impasse dans l'une des options. Nous allons donc dans l’autre sens. Dans la prochaine itération, nous avons déjà 4 options. 
Deux d'entre elles ne conviennent pas, car elles mènent en arrière, et les autres options sont tout aussi bonnes, mais l'algorithme a décidé qu'il était préférable d'aller en diagonale jusqu'à la cellule (3,2). De plus, à chaque étape, le calcul de la fonction F est répété jusqu'à ce que le caractère atteigne la cellule cible. Si, bien entendu, un tel passage existe. 
Le chemin vert sur l'image GIF indique le chemin optimal du personnage vers le drapeau.
A* Algorithme étape par étape
Pour implémenter l'algorithme en Java, vous devez suivre les étapes suivantes 1. Vous devez d'abord créer deux listes, pour les nœuds ouverts et les nœuds fermés. 2. Initialisez les deux listes. Dans une liste fermée, le nœud de départ pointe vers la liste ouverte. 3. tant qu'il y a des éléments dans la liste ouverte : 3a. Trouvez le nœud min avec le plus petit F 3b. Supprimer min de la liste ouverte 3c. Déterminer les voisins min (jusqu'à 8, si l'on prend en compte les diagonales) 3d. Vérification de chaque voisin : a) si le voisin est la cellule cible, arrêtez de chercher b) Sinon, calculez G, H pour cela. G = min.G + distance entre voisin et min F = G + H c) si le nœud avec la même position que le voisin est dans la liste ouverte et que son F est inférieur à celui du voisin, sauter ce voisin d) si le nœud avec la même position que le voisin est dans la liste fermée, et son f est inférieur à celui du voisin, ignorez ce voisin. Sinon, ajoutez le nœud à la liste ouverte Fin de la boucle interne 3e. Ajout de min à la liste fermée Fin de la boucle externe Ainsi, à chaque itération nous allons faire la suivante :- Sélectionnez la cellule dans notre liste ouverte avec le score total estimé le plus bas.
- Supprimez cette cellule de la liste ouverte.
- Ajoutez toutes les cellules accessibles depuis celui-ci à la liste ouverte.
- Lorsque nous faisons cela, nous traitons également le nouveau score de ce nœud vers chaque nouveau pour voir s'il s'agit d'une amélioration par rapport à ce que nous avons jusqu'à présent, et si c'est le cas, nous mettons à jour ce que nous savons sur cette cellule.
A*Pseudocode
Voici un bref pseudocode de la recherche de chemin A* :Input: a grid with locked and empty cells, with start and goal cell.
Output: least cost path from start to goal cell.
Initialisation
openList = {startCell} //list of traversed cells
closedList = {} //list of already traversed cells
g.startCell = 0 //cost from source cell to a cell
h.startCell = h(startCell, goal) //heuristic
f.startCell = g.startCell + h.StartCell
while openList is not empty
do
//let the currentCell equal the cell with the least f value
currentCell = Cell on top of openList, with least f
if currentCell == end return
remove currentCell from openList
add currentCell to closedList
foreach n in child.currentCell
if n in closedList
continue
cost = g.currentCell + distance(currentCell,n)
if (n in openList and cost < g.n)
remove n from closedList
g.n = cost
h.n = h(n, goal)
f.n = g.n + h.nDu pseudocode à l’implémentation A* en Java
Une réalisation* Pathfinding en Java devrait avoir certaines méthodes pour servir l'algorithme :- Cellule, une structure pour contenir les paramètres nécessaires
- Listes ouvertes et fermées
- Méthode pour calculer la fonction heuristique
- Méthode pour tracer le chemin de la source à la destination
- Méthodes pour vérifier si la cellule donnée est bloquée, si elle est déjà atteinte, si elle est valide, etc.
package Asterist;
import java.util.PriorityQueue;
import java.util.Stack;
public class AAsterisk {
//Java Program to implement A* Search Algorithm
//Here we're creating a shortcut for (int, int) pair
public static class Pair {
int first;
int second;
public Pair(int first, int second){
this.first = first;
this.second = second;
}
@Override
public boolean equals(Object obj) {
return obj instanceof Pair && this.first == ((Pair)obj).first && this.second == ((Pair)obj).second;
}
}
// Creating a shortcut for tuple<int, int, int> type
public static class Details {
double value;
int i;
int j;
public Details(double value, int i, int j) {
this.value = value;
this.i = i;
this.j = j;
}
}
// a Cell (node) structure
public static class Cell {
public Pair parent;
// f = g + h, where h is heuristic
public double f, g, h;
Cell()
{
parent = new Pair(-1, -1);
f = -1;
g = -1;
h = -1;
}
public Cell(Pair parent, double f, double g, double h) {
this.parent = parent;
this.f = f;
this.g = g;
this.h = h;
}
}
// method to check if our cell (row, col) is valid
boolean isValid(int[][] grid, int rows, int cols,
Pair point)
{
if (rows > 0 && cols > 0)
return (point.first >= 0) && (point.first < rows)
&& (point.second >= 0)
&& (point.second < cols);
return false;
}
//is the cell blocked?
boolean isUnBlocked(int[][] grid, int rows, int cols,
Pair point)
{
return isValid(grid, rows, cols, point)
&& grid[point.first][point.second] == 1;
}
//Method to check if destination cell has been already reached
boolean isDestination(Pair position, Pair dest)
{
return position == dest || position.equals(dest);
}
// Method to calculate heuristic function
double calculateHValue(Pair src, Pair dest)
{
return Math.sqrt(Math.pow((src.first - dest.first), 2.0) + Math.pow((src.second - dest.second), 2.0));
}
// Method for tracking the path from source to destination
void tracePath(
Cell[][] cellDetails,
int cols,
int rows,
Pair dest)
{ //A* Search algorithm path
System.out.println("The Path: ");
Stack<Pair> path = new Stack<>();
int row = dest.first;
int col = dest.second;
Pair nextNode = cellDetails[row][col].parent;
do {
path.push(new Pair(row, col));
nextNode = cellDetails[row][col].parent;
row = nextNode.first;
col = nextNode.second;
} while (cellDetails[row][col].parent != nextNode); // until src
while (!path.empty()) {
Pair p = path.peek();
path.pop();
System.out.println("-> (" + p.first + "," + p.second + ") ");
}
}
// A main method, A* Search algorithm to find the shortest path
void aStarSearch(int[][] grid,
int rows,
int cols,
Pair src,
Pair dest)
{
if (!isValid(grid, rows, cols, src)) {
System.out.println("Source is invalid...");
return;
}
if (!isValid(grid, rows, cols, dest)) {
System.out.println("Destination is invalid...");
return;
}
if (!isUnBlocked(grid, rows, cols, src)
|| !isUnBlocked(grid, rows, cols, dest)) {
System.out.println("Source or destination is blocked...");
return;
}
if (isDestination(src, dest)) {
System.out.println("We're already (t)here...");
return;
}
boolean[][] closedList = new boolean[rows][cols];//our closed list
Cell[][] cellDetails = new Cell[rows][cols];
int i, j;
// Initialising of the starting cell
i = src.first;
j = src.second;
cellDetails[i][j] = new Cell();
cellDetails[i][j].f = 0.0;
cellDetails[i][j].g = 0.0;
cellDetails[i][j].h = 0.0;
cellDetails[i][j].parent = new Pair( i, j );
// Creating an open list
PriorityQueue<Details> openList = new PriorityQueue<>((o1, o2) -> (int) Math.round(o1.value - o2.value));
// Put the starting cell on the open list, set f.startCell = 0
openList.add(new Details(0.0, i, j));
while (!openList.isEmpty()) {
Details p = openList.peek();
// Add to the closed list
i = p.i; // second element of tuple
j = p.j; // third element of tuple
// Remove from the open list
openList.poll();
closedList[i][j] = true;
// Generating all the 8 neighbors of the cell
for (int addX = -1; addX <= 1; addX++) {
for (int addY = -1; addY <= 1; addY++) {
Pair neighbour = new Pair(i + addX, j + addY);
if (isValid(grid, rows, cols, neighbour)) {
if(cellDetails[neighbour.first] == null){ cellDetails[neighbour.first] = new Cell[cols]; }
if (cellDetails[neighbour.first][neighbour.second] == null) {
cellDetails[neighbour.first][neighbour.second] = new Cell();
}
if (isDestination(neighbour, dest)) {
cellDetails[neighbour.first][neighbour.second].parent = new Pair ( i, j );
System.out.println("The destination cell is found");
tracePath(cellDetails, rows, cols, dest);
return;
}
else if (!closedList[neighbour.first][neighbour.second]
&& isUnBlocked(grid, rows, cols, neighbour)) {
double gNew, hNew, fNew;
gNew = cellDetails[i][j].g + 1.0;
hNew = calculateHValue(neighbour, dest);
fNew = gNew + hNew;
if (cellDetails[neighbour.first][neighbour.second].f == -1
|| cellDetails[neighbour.first][neighbour.second].f > fNew) {
openList.add(new Details(fNew, neighbour.first, neighbour.second));
// Update the details of this
// cell
cellDetails[neighbour.first][neighbour.second].g = gNew;
//heuristic function cellDetails[neighbour.first][neighbour.second].h = hNew;
cellDetails[neighbour.first][neighbour.second].f = fNew;
cellDetails[neighbour.first][neighbour.second].parent = new Pair( i, j );
}
}
}
}
}
}
System.out.println("Failed to find the Destination Cell");
}
// test
public static void main(String[] args) {
//0: The cell is blocked
// 1: The cell is not blocked
int[][] grid = {
{ 1, 1, 0, 0, 1, 0, 0, 0 },
{ 1, 0, 0, 1, 1, 0, 1, 0 },
{ 1, 1, 0, 1, 0, 0, 1, 0 },
{ 1, 1, 0, 1, 1, 1, 1, 1 },
{ 1, 1, 0, 0, 0, 1, 1, 1 },
{ 0, 1, 1, 1, 0, 1, 1, 0 },
{ 1, 1, 0, 1, 1, 1, 1, 0 },
{ 0, 1, 1, 1, 1, 1, 1, 1 }
};
// Start is the left-most upper-most corner
Pair src = new Pair(0,0);
//(8, 0);
// Destination is the right-most bottom-most corner
Pair dest = new Pair(6, 6);
AAsterisk app = new AAsterisk();
app.aStarSearch(grid, grid.length , grid[0].length, src, dest);
}
}
Le chemin : -> (0,0) -> (1,0) -> (2,1) -> (3,1) -> (4,1) -> (5,2) -> (5, 3) -> (6,4) -> (6,5) -> (6,6)
On peut voir qu’il s’agit de l’un des nombreux chemins les plus courts pouvant être construits entre ces deux points. Notez que la sixième étape de notre exemple dans l'image et dans la sortie du programme est différente, bien que les chemins se soient avérés tout aussi efficaces. Le programme sélectionne l'une des nombreuses options les plus efficaces.
GO TO FULL VERSION