Diversi algoritmi di ricerca sono adattati a compiti diversi. Oggi parleremo della ricerca A*, uno degli algoritmi di pathfinding più efficaci. Questo è molto adatto per i giochi per computer e per la creazione di grafici di ricerca come i percorsi tra le città e così via. Potresti aver notato, ad esempio, nei videogiochi strategici o tattici, come dopo aver premuto un pulsante, il tuo giocatore o gruppo inizia immediatamente, senza indugio, ad attraversare il campo fino al punto specificato. Non c'è alcun ritardo proprio perché i giochi utilizzano algoritmi efficaci che calcolano esattamente come il giocatore ha bisogno per arrivare da qualche parte. Oppure un nemico che trova inequivocabilmente il giocatore e inizia a camminare nella giusta direzione da lontano. Di solito, per tali azioni viene utilizzato l'algoritmo A*.
Cos'è l'algoritmo A*
L'algoritmo di ricerca del percorso A* è un esempio di algoritmo di ricerca best-first. Lo scopo dell'algoritmo A* è trovare un percorso da un punto a un altro. È uno dei classici per la ricerca di algoritmi sui grafici. Scopriamo come funziona utilizzando un esempio. Immagina un gioco 2D con una vista dall'alto verso il basso. Dividiamo la nostra area di gioco in quadrati, ad esempio 8*8 celle come una scacchiera. Le nostre cellule possono essere di due tipi, percorribili o impraticabili (ostacolo). In ogni periodo di tempo un giocatore o un nemico che si avvicina al giocatore si sposta di una cella. Nei giochi, le celle percorribili possono essere di natura diversa, ad esempio una strada pianeggiante, erba o sabbia, che determina la difficoltà di muoversi lungo di esse, ma per semplicità assumeremo che tutte le celle percorribili vengano superate allo stesso modo. Nell'immagine sotto, le celle blu rappresentano gli ostacoli.
Assegniamo una cella (o nodo) come cella iniziale (il carattere è al suo interno) e l'altra cella come cella di destinazione o obiettivo (quella con la bandiera) e descriviamo come funziona l'algoritmo A* in questo caso. Il personaggio è nella cella (1,1) e il bersaglio è nella cella (7,7). Ogni cella ha vicini orizzontali, verticali e diagonali. Dipende dal gioco, se calcoliamo i nodi diagonali oppure no. Ad esempio in molti giochi con vista dall'alto come Bomberman o Pacman i personaggi possono muoversi solo orizzontalmente o verticalmente. In questo caso ogni nodo, eccetto quelli che toccano i bordi, ha solo 4 vicini. Se parliamo di un gioco in cui i personaggi possono muoversi in diagonale, ogni nodo può avere fino a 8 vicini. Nella prima fase dell'algoritmo, la cella in cui si trova il carattere ha due vicini. Più precisamente tre, ma uno di questi è un ostacolo. 
È chiaro che la via diagonale è più lunga. se impostiamo il lato della nostra cella in modo che sia condizionatamente uguale a uno, la lunghezza della diagonale di questa cella è uguale alla radice quadrata di due. Questo è ciò che dice il teorema di Pitagora. Per passare dalla cella A alla cella B, devi prima selezionare una delle celle vicine, quindi quella successiva e così via. Inoltre, lungo il percorso, capisci se è possibile passare dalla cella iniziale a quella di destinazione. L'algoritmo A* ad ogni passaggio seleziona una delle celle vicine in base al valore della funzione F. Questa funzione misura quanto è buona una cella candidata per essere inclusa nel nostro percorso più breve. Questa è la funzione di costo ed è la somma della funzione di movimento G e della funzione euristica.
-
Costo G: è una distanza da un nodo iniziale.
-
Il costo H (euristico) è una distanza dal nodo finale (obiettivo). Questa funzione può essere diversa, uno sviluppatore decide cosa è meglio. Forse la scelta di H è la più importante in A*, e questo è il punto che rende più o meno efficace qualsiasi particolare implementazione dell'algoritmo. In teoria puoi usare qualsiasi funzione tu voglia.
Nel nostro caso, conosciamo la posizione della cella di destinazione e possiamo, ad esempio, calcolare la distanza geometrica euclidea tra la cella di destinazione e quella corrente. Più breve è la distanza, più siamo vicini all'obiettivo.
-
Costo F = G + H. Quindi l'algoritmo calcola i costi F di tutti i nodi vicini e sceglie uno dei costi F più bassi da considerare per primo. Quando ne scegliamo uno lo contrassegniamo come chiuso e calcoliamo i valori per questo nodo vicino.
Funzione euristicaCome possiamo calcolare H?
Questa è una funzione euristica. Il nome stesso significa che è determinato dall'esperienza e può essere diverso. Qui lo prenderemo uguale alla cosiddetta distanza euclidea tra i punti (x1, y1) e (x2, y2): Nell'immagine
, per il primo passaggio, ci sono due opzioni, e sono uguali nel costo, ma nel passaggio successivo, il personaggio si ritrova in un vicolo cieco in una delle opzioni. Pertanto, stiamo andando dall'altra parte. Nella prossima iterazione, abbiamo già 4 opzioni. 
Due di queste non sono adatte, perché portano all'indietro, e le altre opzioni sono ugualmente buone, ma l'algoritmo ha deciso che era meglio andare in diagonale verso la cella (3,2). Inoltre, ad ogni passaggio, il calcolo della funzione F viene ripetuto finché il carattere non raggiunge la cella di destinazione. Se, ovviamente, un tale passaggio esiste. 
Il percorso verde sull'immagine GIF indica il percorso ottimale del personaggio verso la bandiera.
A* Algoritmo passo dopo passo
Per implementare l'algoritmo in Java, è necessario eseguire i seguenti passaggi 1. Per prima cosa è necessario creare due elenchi, per i nodi aperti e per i nodi chiusi. 2. Inizializzare entrambi gli elenchi. In un elenco chiuso, il nodo iniziale punta all'elenco aperto. 3. mentre ci sono elementi nella lista aperta: 3a. Trova il nodo min con il più piccolo F 3b. Rimuovi min dall'elenco aperto 3c. Determinare i vicini min (fino a 8, se si prendono in considerazione le diagonali) 3d. Controlla ciascun vicino: a) se il vicino è la cella obiettivo, interrompi la ricerca b) In caso contrario, calcola G, H per esso. G = min.G + distanza tra vicino e min F = G + H c) se il nodo con la stessa posizione del vicino è nella lista aperta e la sua F è inferiore a quella del vicino, salta quel vicino d) se il nodo con la stessa posizione del vicino è nella lista chiusa e la sua f è inferiore a quella del vicino, salta quel vicino. Altrimenti aggiungi il nodo all'elenco aperto Fine del ciclo interno 3e. Aggiunta di min all'elenco chiuso Fine del ciclo esterno Quindi, ad ogni iterazione faremo quanto segue:- Seleziona la cella dal nostro elenco aperto con il punteggio totale stimato più basso.
- Rimuovi questa cella dall'elenco aperto.
- Aggiungi tutte le celle che possiamo raggiungere da esso all'elenco aperto.
- Quando lo facciamo, elaboriamo anche il nuovo punteggio da quel nodo a ciascuno nuovo per vedere se è un miglioramento rispetto a ciò che abbiamo finora e, in tal caso, aggiorniamo ciò che sappiamo di quella cella.
A* Pseudocodice
Ecco un breve pseudocodice del pathfinding 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.nDallo pseudocodice all'implementazione A* in Java
R* Il pathfinding nella realizzazione Java dovrebbe avere alcuni metodi per servire l'algoritmo:- Cella, una struttura per contenere i parametri necessari
- Elenchi aperti e chiusi
- Metodo per calcolare la funzione euristica
- Metodo per tracciare il percorso dall'origine alla destinazione
- Metodi per verificare se la cella specificata è bloccata, se è già raggiunta, se è valida e così via
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);
}
}
Il percorso: -> (0,0) -> (1,0) -> (2,1) -> (3,1) -> (4,1) -> (5,2) -> (5, 3) -> (6,4) -> (6,5) -> (6,6)
Si può vedere che questo è uno dei tanti percorsi più brevi che possono essere costruiti tra questi due punti. Si noti che il sesto passaggio nel nostro esempio nell'immagine e nell'output del programma è diverso, sebbene i percorsi si siano rivelati ugualmente efficaci. Il programma seleziona una delle tante opzioni più efficaci.
GO TO FULL VERSION