Algoritme pencarian yang berbeda disesuaikan untuk tugas yang berbeda. Hari ini kita akan berbicara tentang pencarian A*, salah satu algoritma pencarian jalur yang paling efektif. Yang ini sangat cocok untuk permainan komputer dan membangun grafik pencarian seperti jalan antar kota dan sebagainya. Anda mungkin telah memperhatikan, misalnya, dalam video game strategis atau taktis, bagaimana setelah menekan sebuah tombol, pemain atau grup Anda segera mulai tanpa penundaan melintasi lapangan ke titik yang Anda tentukan. Tidak ada penundaan justru karena permainan ini menggunakan algoritme efektif yang menghitung dengan tepat bagaimana pemain harus mencapai suatu tempat. Atau musuh yang secara akurat menemukan pemain tersebut dan mulai berjalan ke arah yang benar dari jauh. Biasanya, algoritma A* digunakan untuk tindakan seperti itu.
Apa itu algoritma A*
Algoritma pathfinding A* merupakan salah satu contoh algoritma pencarian terbaik pertama. Tujuan dari algoritma A* adalah untuk menemukan jalur dari satu titik ke titik lainnya. Ini adalah salah satu algoritma pencarian grafik klasik. Mari kita cari tahu cara kerjanya menggunakan sebuah contoh. Bayangkan sebuah game 2D dengan tampilan top-down. Mari kita bagi area permainan kita menjadi persegi keserakahan, misalnya 8*8 sel seperti papan catur. Sel kita bisa menjadi salah satu dari dua jenis, bisa dilewati atau tidak bisa dilewati (penghalang). Setiap periode waktu seorang pemain atau musuh yang mendekati pemain tersebut menggerakkan satu sel. Dalam permainan, sel yang bisa dilewati bisa memiliki sifat yang berbeda, misalnya jalan datar, rumput atau pasir, yang menentukan kesulitan untuk bergerak di sepanjang sel tersebut, tetapi untuk kesederhanaan kita akan berasumsi bahwa semua sel yang bisa dilewati dilewati dengan cara yang sama. Pada gambar di bawah, sel biru adalah penghalang.
Mari kita tetapkan satu sel (atau node) sebagai sel awal (karakter ada di dalamnya), dan sel lainnya sebagai sel target atau tujuan (yang memiliki bendera), dan jelaskan cara kerja algoritma A* untuk kasus ini. Karakternya ada di sel (1,1) dan targetnya ada di sel (7,7). Setiap sel memiliki tetangga horizontal, vertikal, dan diagonal. Itu tergantung pada permainannya, apakah kita menghitung node diagonal atau tidak. Misalnya di banyak permainan dengan tampilan top-down seperti Bomberman atau Pacman, karakter hanya dapat bergerak secara horizontal atau vertikal. Dalam hal ini setiap node, kecuali menyentuh tepinya, hanya memiliki 4 tetangga. Jika kita berbicara tentang permainan di mana karakter dapat bergerak secara diagonal, setiap node dapat memiliki hingga 8 tetangga. Pada langkah pertama algoritma, sel tempat karakter berada memiliki dua tetangga. Lebih tepatnya tiga, tapi salah satunya menjadi kendala. 
Yang jelas jalur diagonalnya lebih panjang. jika kita menetapkan sisi sel kita secara kondisional sama dengan satu, maka panjang diagonal sel ini sama dengan akar kuadrat dari dua. Inilah yang dikatakan teorema Pythagoras. Untuk berpindah dari sel A ke sel B, pertama-tama Anda harus memilih salah satu sel tetangga, lalu sel berikutnya, dan seterusnya. Juga, sepanjang jalan, pahami apakah mungkin untuk berpindah dari sel awal ke sel target. Algoritma A* pada setiap langkah memilih salah satu sel tetangga sesuai dengan nilai fungsi F. Fungsi ini mengukur seberapa baik suatu sel kandidat untuk dimasukkan dalam jalur terpendek kita. Ini adalah fungsi biaya, dan merupakan jumlah dari fungsi perpindahan G dan fungsi heuristik.
-
G cost — adalah jarak dari titik awal.
-
Biaya H (Heuristik) adalah jarak dari titik akhir (tujuan). Fungsi ini bisa berbeda, pengembang memutuskan mana yang lebih baik. Mungkin pilihan H adalah yang paling penting dalam A*, dan inilah poin yang membuat penerapan algoritma tertentu menjadi lebih atau kurang efektif. Secara teoritis Anda dapat menggunakan fungsi apa pun yang Anda inginkan.
Dalam kasus kita, kita mengetahui posisi sel target dan dapat, misalnya, menghitung jarak geometrik Euclidean antara sel target dan sel saat ini. Semakin pendek jaraknya, semakin dekat kita dengan tujuan.
-
F biaya = G + H. Jadi algoritme menghitung semua biaya F node tetangga dan memilih salah satu biaya F terendah untuk dilihat terlebih dahulu. Ketika kita memilih salah satu, kita menandainya sebagai tertutup dan menghitung nilai untuk tetangga simpul ini.
Fungsi heuristik Bagaimana cara menghitung H?
Ini adalah fungsi heuristik. Namanya sendiri artinya ditentukan oleh pengalaman, dan bisa berbeda-beda. Di sini kita akan menganggapnya sama dengan apa yang disebut jarak Euclidean antara titik (x1, y1) dan (x2, y2):
Pada gambar, untuk langkah pertama, ada dua pilihan, dan biayanya sama, namun pada langkah selanjutnya, karakter menemui jalan buntu di salah satu opsi. Oleh karena itu, kami mengambil jalan sebaliknya. Pada iterasi berikutnya, kita sudah memiliki 4 opsi. 
Dua di antaranya tidak cocok, karena mengarah ke belakang, dan opsi lainnya sama bagusnya, namun algoritme memutuskan bahwa yang terbaik adalah bergerak secara diagonal ke sel (3,2). Selanjutnya pada setiap langkah perhitungan fungsi F diulangi hingga karakter mencapai sel target. Jika, tentu saja, ada bagian seperti itu. 
Jalur hijau pada gambar GIF menunjukkan jalur optimal karakter menuju bendera.
Algoritma A* langkah demi langkah
Untuk mengimplementasikan algoritma di Java, Anda perlu melakukan langkah-langkah berikut 1. Pertama, Anda perlu membuat dua daftar, untuk node terbuka dan node tertutup. 2. Inisialisasi kedua daftar. Dalam daftar tertutup, titik awal menunjuk ke daftar terbuka. 3. selagi ada elemen dalam daftar terbuka: 3a. Temukan node min dengan F 3b terkecil. Hapus min dari daftar terbuka 3c. Tentukan tetangga min (hingga 8, jika diagonal diperhitungkan) 3d. Memeriksa setiap tetangga: a) jika tetangga adalah sel target, berhenti mencari b) Jika tidak, hitung G, H untuk sel tersebut. G = min.G + jarak antar tetangga dan min F = G + H c) jika node yang posisinya sama dengan tetangganya berada dalam daftar terbuka dan F-nya lebih kecil dari tetangganya, lewati tetangga tersebut d) jika node yang posisinya sama dengan tetangganya ada di daftar tertutup, dan f-nya lebih kecil dari tetangganya, lewati tetangga itu. Jika tidak, tambahkan node ke daftar terbuka Akhir dari loop dalam 3e. Menambahkan min ke daftar tertutup Akhir dari loop luar Jadi, pada setiap iterasi kita akan melakukan hal berikutnya:- Pilih sel dari daftar terbuka kami dengan perkiraan skor total terendah.
- Hapus sel ini dari daftar terbuka.
- Tambahkan semua sel yang dapat kita jangkau ke daftar terbuka.
- Saat kami melakukan ini, kami juga memproses skor baru dari node tersebut ke setiap node baru untuk melihat apakah ini merupakan peningkatan dari apa yang kami miliki sejauh ini, dan jika ya, kami memperbarui apa yang kami ketahui tentang sel tersebut.
A* Kodesemu
Berikut adalah pseudocode singkat dari pencarian jalur 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.nDari pseudocode hingga Implementasi A* di Java
A* Pathfinding dalam realisasi Java harus memiliki beberapa metode untuk melayani algoritma:- Sel, suatu struktur untuk menampung parameter yang diperlukan
- Daftar terbuka dan tertutup
- Metode untuk menghitung fungsi heuristik
- Metode untuk menelusuri jalur dari sumber ke tujuan
- Metode untuk memeriksa apakah sel tertentu diblokir, apakah sudah tercapai, apakah valid, dan seterusnya
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);
}
}
Jalannya: -> (0,0) -> (1,0) -> (2,1) -> (3,1) -> (4,1) -> (5,2) -> (5, 3) -> (6,4) -> (6,5) -> (6,6)
Terlihat bahwa ini adalah salah satu dari beberapa jalur terpendek yang dapat dibangun antara kedua titik tersebut. Perhatikan bahwa langkah keenam dalam contoh kita pada gambar dan keluaran program berbeda, meskipun jalurnya ternyata sama efektifnya. Program ini memilih salah satu dari banyak pilihan yang paling efektif.
GO TO FULL VERSION