
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.

-
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



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.n
Dallo 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);
}
}
Qui nell'esempio abbiamo la stessa griglia dell'immagine sopra. Basta "disegnarlo" con un array 2D. Il programma restituisce il seguente percorso:
GO TO FULL VERSION