![A* Algoritmo de pesquisa em Java - 1](https://cdn.codegym.cc/images/article/1eaf6b25-bbf7-49d5-b8d0-e0d16f78cbbe/800.jpeg)
O que é algoritmo A*
O algoritmo Pathfinding A* é um exemplo de algoritmo de busca do melhor primeiro. O objetivo do algoritmo A* é encontrar um caminho de um ponto a outro. É um dos clássicos para pesquisar algoritmos de grafos. Vamos descobrir como funciona usando um exemplo. Imagine um jogo 2D com visão de cima para baixo. Vamos dividir nossa área de jogo em ganância quadrada, por exemplo 8*8 células como um tabuleiro de xadrez. Nossas células podem ser de dois tipos: transitáveis ou intransponíveis (obstáculo). Cada período de tempo que um jogador ou inimigo que se aproxima do jogador move uma célula. Nos jogos, as células transitáveis podem ser de natureza diferente, por exemplo, uma estrada plana, grama ou areia, o que determina a dificuldade de movimentação ao longo delas, mas para simplificar, assumiremos que todas as células transitáveis são passadas da mesma maneira. Na imagem abaixo, as células azuis são obstáculos.![A* Algoritmo de Pesquisa em Java - 2](https://cdn.codegym.cc/images/article/58ac1410-d008-4dd9-939b-067ae2d842ac/512.jpeg)
![A* Algoritmo de Pesquisa em Java - 3](https://cdn.codegym.cc/images/article/c4f6169e-5b2a-473b-b7e8-dd3baa308f24/512.jpeg)
-
Custo G - é a distância de um nó inicial.
-
O custo H (heurística) é a distância do nó final (objetivo). Esta função pode ser diferente, um desenvolvedor decide o que é melhor. Talvez a escolha de H seja a mais importante em A*, e este é o ponto que torna qualquer implementação particular do algoritmo mais ou menos eficaz. Teoricamente você pode usar qualquer função que desejar.
No nosso caso, conhecemos a posição da célula alvo e podemos, por exemplo, calcular a distância euclidiana geométrica entre a célula alvo e a célula atual. Quanto menor a distância, mais perto estamos do objetivo.
-
Custo F = G + H. Portanto, o algoritmo calcula os custos F de todos os nós vizinhos e escolhe um dos custos F mais baixos para observar primeiro. Quando escolhemos um, marcamos-o como fechado e calculamos os valores para os vizinhos deste nó.
Função heurísticaComo podemos calcular H?
Esta é uma função heurística. O próprio nome significa que é determinado pela experiência e pode ser diferente. Aqui vamos considerá-la igual à chamada distância euclidiana entre os pontos (x1, y1) e (x2, y2):![A* Algoritmo de Pesquisa em Java - 4](https://cdn.codegym.cc/images/article/ab9f62f8-4423-48a8-a01f-5321aab97273/256.jpeg)
![A* Algoritmo de Pesquisa em Java - 5](https://cdn.codegym.cc/images/article/7f515298-36db-4476-ae1f-ab162336355b/512.jpeg)
![A* Algoritmo de Pesquisa em Java - 6](https://cdn.codegym.cc/images/article/4a042a32-5062-49b9-a197-2f8aa933af09/512.jpeg)
![A* Algoritmo de Pesquisa em Java - 7](https://cdn.codegym.cc/images/article/6d117ebf-e0c0-43b6-9150-4805c456ab01/original.gif)
A* Algoritmo passo a passo
Para implementar o algoritmo em Java, você precisa seguir os seguintes passos 1. Primeiro você precisa criar duas listas, para nós abertos e nós fechados. 2. Inicialize ambas as listas. Numa lista fechada, o nó inicial aponta para a lista aberta. 3. enquanto houver elementos na lista aberta: 3a. Encontre o nó min com o menor F 3b. Remova min da lista aberta 3c. Determine vizinhos mínimos (até 8, se as diagonais forem levadas em consideração) 3d. Verificando cada vizinho: a) se o vizinho for a célula alvo, pare de pesquisar b) Caso contrário, calcule G, H para ele. G = min.G + distância entre vizinho e min F = G + H c) se o nó com a mesma posição do vizinho estiver na lista aberta e seu F for menor que o do vizinho, pule esse vizinho d) se o nó com a mesma posição do vizinho está na lista fechada e seu f é menor que o do vizinho, pule esse vizinho. Caso contrário, adicione o nó à lista aberta. Fim do loop interno 3e. Adicionando min à lista fechada Fim do loop externo Então, a cada iteração faremos o seguinte:- Selecione a célula da nossa lista aberta com a pontuação total estimada mais baixa.
- Remova esta célula da lista aberta.
- Adicione todas as células que pudermos alcançar à lista aberta.
- Quando fazemos isso, também processamos a nova pontuação desse nó para cada novo para ver se é uma melhoria em relação ao que temos até agora e, se for, atualizamos o que sabemos sobre aquela célula.
A* Pseudocódigo
Aqui está um breve pseudocódigo do 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
Do pseudocódigo à implementação A* em Java
A* Pathfinding na realização Java deve ter alguns métodos para servir ao algoritmo:- Célula, uma estrutura para armazenar os parâmetros necessários
- Listas abertas e fechadas
- Método para calcular a função heurística
- Método para rastrear o caminho da origem ao destino
- Métodos para verificar se determinada célula está bloqueada, se já foi alcançada, se é válida e assim por diante
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);
}
}
Aqui, no exemplo, temos a mesma grade da imagem acima. Basta "desenhá-lo" com um array 2D. O programa gera o seguinte caminho:
GO TO FULL VERSION