อัลกอริธึมการค้นหาที่แตกต่างกันได้รับการปรับแต่งให้เหมาะกับงานที่แตกต่างกัน วันนี้เราจะมาพูดถึงการค้นหาแบบ A* ซึ่งเป็นหนึ่งในอัลกอริธึมการค้นหาเส้นทางที่มีประสิทธิภาพมากที่สุด ตัวนี้เหมาะมากกับเกมคอมพิวเตอร์และการสร้างกราฟการค้นหา เช่น เส้นทางระหว่างเมือง เป็นต้น คุณอาจสังเกตเห็น เช่น ในวิดีโอเกมเชิงกลยุทธ์หรือยุทธวิธี หลังจากกดปุ่ม ผู้เล่นหรือกลุ่มของคุณจะเริ่มทันทีโดยไม่ชักช้าเพื่อข้ามสนามไปยังจุดที่คุณระบุ ไม่มีการล่าช้าอย่างแน่นอนเนื่องจากเกมใช้อัลกอริธึมที่มีประสิทธิภาพซึ่งคำนวณได้อย่างแม่นยำว่าผู้เล่นจะต้องไปที่ไหนสักแห่งอย่างไร หรือศัตรูที่ค้นพบผู้เล่นอย่างไม่ผิดพลาดและเริ่มเดินในทิศทางที่ถูกต้องจากระยะไกล โดยปกติแล้ว อัลกอริธึม A* จะใช้สำหรับการดำเนินการดังกล่าว
อัลกอริธึม A* คืออะไร
อัลกอริธึมการค้นหาเส้นทาง A* เป็นตัวอย่างของอัลกอริธึมการค้นหาที่มาก่อนดีที่สุด วัตถุประสงค์ของอัลกอริทึม A* คือการค้นหาเส้นทางจากจุดหนึ่งไปยังอีกจุดหนึ่ง เป็นหนึ่งในคลาสสิกสำหรับการค้นหาอัลกอริธึมกราฟ ลองมาดูกันว่ามันทำงานอย่างไรโดยใช้ตัวอย่าง ลองนึกภาพเกม 2 มิติที่มีมุมมองจากบนลงล่าง มาแบ่งพื้นที่เกมของเราออกเป็นตารางความโลภ เช่น 8*8 เซลล์เหมือนกระดานหมากรุก เซลล์ของเราสามารถเป็นหนึ่งในสองประเภท คือผ่านได้หรือผ่านไม่ได้ (อุปสรรค) แต่ละช่วงเวลาที่ผู้เล่นหรือศัตรูที่เข้ามาใกล้ผู้เล่นจะย้ายหนึ่งเซลล์ ในเกม เซลล์ที่ผ่านได้อาจมีลักษณะที่แตกต่างกัน เช่น ถนนเรียบ หญ้า หรือทราย ซึ่งกำหนดความยากในการเคลื่อนที่ไปตามเซลล์เหล่านั้น แต่เพื่อความง่าย เราจะถือว่าเซลล์ที่ผ่านได้ทั้งหมดนั้นผ่านไปในลักษณะเดียวกัน ในภาพด้านล่าง เซลล์สีน้ำเงินคือสิ่งกีดขวาง
เรามากำหนดเซลล์หนึ่ง (หรือโหนด) เป็นเซลล์เริ่มต้น (มีอักขระอยู่ในนั้น) และอีกเซลล์หนึ่งเป็นเซลล์เป้าหมายหรือเป้าหมาย (เซลล์ที่มีแฟล็ก) และอธิบายวิธีการทำงานของอัลกอริทึม A* สำหรับกรณีนี้ อักขระอยู่ในเซลล์ (1,1) และเป้าหมายอยู่ในเซลล์ (7,7) แต่ละเซลล์มีเพื่อนบ้านแนวนอน แนวตั้ง และแนวทแยง ขึ้นอยู่กับเกมว่าเราคำนวณโหนดแนวทแยงหรือไม่ ตัวอย่างเช่น ในเกมที่มีมุมมองจากบนลงล่างหลายเกม เช่น Bomberman หรือ Pacman ตัวละครสามารถเคลื่อนที่ได้ในแนวนอนหรือแนวตั้งเท่านั้น ในกรณีนี้ ทุกโหนด ยกเว้นการสัมผัสขอบ จะมีเพื่อนบ้านเพียง 4 ตัว หากเรากำลังพูดถึงเกมที่ตัวละครสามารถเคลื่อนที่ในแนวทแยงได้ ทุกโหนดสามารถมีเพื่อนบ้านได้สูงสุด 8 คน ในขั้นตอนแรกของอัลกอริทึม เซลล์ที่มีอักขระอยู่จะมีเพื่อนบ้านสองคน แม่นยำยิ่งขึ้นสาม แต่หนึ่งในนั้นคืออุปสรรค 
เห็นได้ชัดว่าทางทแยงยาวกว่า ถ้าเราตั้งค่าด้านของเซลล์ให้เท่ากับ 1 โดยมีเงื่อนไข ความยาวของเส้นทแยงมุมของเซลล์นี้จะเท่ากับรากที่สองของ 2 นี่คือสิ่งที่ทฤษฎีบทพีทาโกรัสกล่าวไว้ หากต้องการเดินทางจากเซลล์ A ไปยังเซลล์ B คุณต้องเลือกเซลล์ใกล้เคียงเซลล์ใดเซลล์หนึ่งก่อน จากนั้นจึงเลือกเซลล์ถัดไป ไปเรื่อยๆ นอกจากนี้ให้ทำความเข้าใจด้วยว่าเป็นไปได้หรือไม่ที่จะเดินทางจากเซลล์เริ่มต้นไปยังเป้าหมาย อัลกอริธึม A* ในแต่ละขั้นตอนจะเลือกเซลล์ข้างเคียงหนึ่งเซลล์ตามค่าของฟังก์ชัน F ฟังก์ชันนี้จะวัดว่าเซลล์ที่เป็นตัวเลือกจะถูกรวมไว้ในเส้นทางที่สั้นที่สุดของเราได้ดีเพียงใด นี่คือฟังก์ชันต้นทุน และเป็นผลรวมของฟังก์ชันการย้าย G และฟังก์ชันการศึกษาสำนึก
-
ราคา G — คือระยะห่างจากโหนดเริ่มต้น
-
ต้นทุน H (Heuristic) คือระยะห่างจากโหนดสุดท้าย (เป้าหมาย) ฟังก์ชั่นนี้อาจแตกต่างออกไป นักพัฒนาจะตัดสินใจว่าอะไรดีกว่ากัน บางทีการเลือก H อาจเป็นสิ่งสำคัญที่สุดใน A* และนี่คือจุดที่ทำให้การนำอัลกอริทึมไปใช้อย่างมีประสิทธิภาพมากขึ้นหรือน้อยลง ตามทฤษฎี คุณสามารถใช้ฟังก์ชันใดก็ได้ที่คุณต้องการ
ในกรณีของเรา เราทราบตำแหน่งของเซลล์เป้าหมาย และสามารถคำนวณระยะทางแบบยุคลิดทางเรขาคณิตระหว่างเป้าหมายและเซลล์ปัจจุบันได้ ยิ่งระยะทางสั้นเท่าไรก็ยิ่งใกล้ถึงเป้าหมายมากขึ้นเท่านั้น
-
ราคา F = G + H ดังนั้นอัลกอริธึมจะคำนวณต้นทุน F ของโหนดข้างเคียงทั้งหมด และเลือกต้นทุน F ที่ต่ำที่สุดรายการใดรายการหนึ่งก่อน เมื่อเราเลือกอันใดอันหนึ่ง เราจะทำเครื่องหมายว่าปิดแล้วและคำนวณค่าสำหรับเพื่อนบ้านของโหนดนี้
ฟังก์ชันฮิวริสติกเราจะคำนวณ H ได้อย่างไร?
นี่คือฟังก์ชันฮิวริสติก ชื่อนั้นหมายความว่ามันถูกกำหนดโดยประสบการณ์ และอาจแตกต่างออกไปได้ ตรงนี้เราจะถือว่ามันเท่ากับระยะทางที่เรียกว่ายูคลิดระหว่างจุด (x1, y1) และ (x2, y2):
ในภาพ สำหรับขั้นตอนแรก มีสองตัวเลือก และมีราคาเท่ากัน แต่ในขั้นตอนถัดไป ตัวละครจะเข้าสู่ทางตันในตัวเลือกใดตัวเลือกหนึ่ง ดังนั้นเราจึงไปทางอื่น ในการวนซ้ำครั้งต่อไป เรามี 4 ตัวเลือกแล้ว 
สองตัวนั้นไม่เหมาะสมเพราะมันนำไปสู่การถอยหลังและตัวเลือกอื่น ๆ ก็ดีพอ ๆ กัน แต่อัลกอริธึมตัดสินใจว่าควรไปในแนวทแยงไปที่เซลล์ดีที่สุด (3,2) นอกจากนี้ ในแต่ละขั้นตอน การคำนวณฟังก์ชัน F จะถูกทำซ้ำจนกระทั่งอักขระไปถึงเซลล์เป้าหมาย ถ้ามีข้อความดังกล่าวอยู่แน่นอน 
ทางสีเขียวบนรูปภาพ GIF บ่งบอกถึงเส้นทางที่เหมาะสมที่สุดของตัวละครไปยังธง
A* อัลกอริทึมทีละขั้นตอน
ในการใช้อัลกอริทึมใน Java คุณต้องทำตามขั้นตอนต่อไปนี้ 1. ขั้นแรกคุณต้องสร้างสองรายการสำหรับโหนดเปิดและโหนดปิด 2. เริ่มต้นทั้งสองรายการ ในรายการปิด โหนดเริ่มต้นชี้ไปที่รายการเปิด 3. ในขณะที่มีองค์ประกอบอยู่ในรายการเปิด: 3a ค้นหาโหนด min ด้วย F 3b ที่เล็กที่สุด ลบ min ออกจากรายการเปิด 3c กำหนดเพื่อนบ้านขั้นต่ำ (สูงสุด 8 หากคำนึงถึงเส้นทแยงมุม) 3d ตรวจสอบเพื่อนบ้านแต่ละคน: a) ถ้าเพื่อนบ้านเป็นเซลล์เป้าหมาย ให้หยุดค้นหา b) ถ้าไม่ ให้คำนวณ G, H G = min.G + ระยะห่างระหว่างเพื่อนบ้านและ min F = G + H c) ถ้าโหนดที่มีตำแหน่งเดียวกันกับเพื่อนบ้านอยู่ในรายการเปิดและ F ของโหนดนั้นน้อยกว่าโหนดเพื่อนบ้าน ให้ข้ามเพื่อนบ้านนั้น d) ถ้า โหนดที่มีตำแหน่งเดียวกันกับเพื่อนบ้านอยู่ในรายการปิด และ f ของมันน้อยกว่าโหนดเพื่อนบ้าน ให้ข้ามเพื่อนบ้านนั้นไป มิฉะนั้น ให้เพิ่มโหนดในรายการที่เปิดอยู่ จุดสิ้นสุดของวงใน 3e การเพิ่ม min ไปยังรายการปิด จุดสิ้นสุดของวงรอบนอก ดังนั้นในการวนซ้ำแต่ละครั้ง เราจะดำเนินการต่อไป:- เลือกเซลล์จากรายการเปิดของเราซึ่งมีคะแนนรวมโดยประมาณต่ำสุด
- ลบเซลล์นี้ออกจากรายการที่เปิดอยู่
- เพิ่มเซลล์ทั้งหมดที่เราสามารถเข้าถึงได้ไปยังรายการที่เปิดอยู่
- เมื่อเราทำเช่นนี้ เรายังประมวลผลคะแนนใหม่จากโหนดนั้นไปยังแต่ละโหนดใหม่เพื่อดูว่าเป็นการปรับปรุงสิ่งที่เรามีจนถึงตอนนี้หรือไม่ และหากเป็นเช่นนั้น เราจะอัปเดตสิ่งที่เรารู้เกี่ยวกับเซลล์นั้น
A* ซูโดโค้ด
นี่คือรหัสเทียมสั้น ๆ ของการค้นหาเส้นทาง 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จาก pseudocode ไปจนถึง A* Implementation ใน Java
A* Pathfinding ในการสำนึก Java ควรมีวิธีการบางอย่างเพื่อรองรับอัลกอริทึม:- เซลล์ โครงสร้างสำหรับเก็บพารามิเตอร์ที่จำเป็น
- รายการเปิดและปิด
- วิธีการคำนวณฟังก์ชันฮิวริสติก
- วิธีการติดตามเส้นทางจากต้นทางไปยังปลายทาง
- วิธีการตรวจสอบว่าเซลล์ที่กำหนดถูกบล็อกหรือไม่ หากถึงเซลล์นั้นแล้ว เซลล์นั้นถูกต้องหรือไม่ เป็นต้น
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);
}
}
เส้นทาง: -> (0,0) -> (1,0) -> (2,1) -> (3,1) -> (4,1) -> (5,2) -> (5, 3) -> (6,4) -> (6,5) -> (6,6)
จะเห็นได้ว่านี่เป็นหนึ่งในเส้นทางที่สั้นที่สุดหลายเส้นทางที่สามารถสร้างระหว่างสองจุดนี้ได้ โปรดทราบว่าขั้นตอนที่หกในตัวอย่างของเราในภาพและในผลลัพธ์ของโปรแกรมนั้นแตกต่างกัน แม้ว่าเส้นทางจะมีประสิทธิภาพเท่ากันก็ตาม โปรแกรมจะเลือกตัวเลือกที่มีประสิทธิภาพมากที่สุดตัวใดตัวหนึ่ง
GO TO FULL VERSION