Contoh Pseudocode dan Implementasi A* dalam Python:

 

python

_____________________________________________________________________________________________
import heapq

# Fungsi untuk menghitung jarak Manhattan
def manhattan_distance(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

# Fungsi untuk mencari rute menggunakan A* Algorithm
def a_star(start, goal, grid):
    open_list = []
    closed_list = set()
    g_costs = {start: 0}
    f_costs = {start: manhattan_distance(start, goal)}
    parents = {start: None}
    
    heapq.heappush(open_list, (f_costs[start], start))
    
    while open_list:
        current_f_cost, current = heapq.heappop(open_list)
        
        if current == goal:
            path = []
            while current:
                path.append(current)
                current = parents[current]
            return path[::-1]
        
        closed_list.add(current)
        
        # Menentukan tetangga (4 arah)
        neighbors = [(current[0] + 1, current[1]), (current[0] - 1, current[1]),
                    (current[0], current[1] + 1), (current[0], current[1] - 1)]
        
        for neighbor in neighbors:
            if 0 <= neighbor[0] < len(grid) and 0 <= neighbor[1] < len(grid[0]) and grid[neighbor[0]][neighbor[1]] == 0:
                if neighbor in closed_list:
                    continue
                
                tentative_g_cost = g_costs[current] + 1
                if neighbor not in g_costs or tentative_g_cost < g_costs[neighbor]:
                    parents[neighbor] = current
                    g_costs[neighbor] = tentative_g_cost
                    f_costs[neighbor] = tentative_g_cost + manhattan_distance(neighbor, goal)
                    heapq.heappush(open_list, (f_costs[neighbor], neighbor))
    
    return None

# Contoh grid (0 = jalan, 1 = rintangan)
grid = [
    [0, 1, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 1, 0],
    [0, 1, 0, 0, 0],
    [0, 0, 0, 1, 0]
]

start = (0, 0)  # Titik awal
goal = (4, 4)   # Titik tujuan

path = a_star(start, goal, grid)
print("Path ditemukan:", path)

Penjelasan A Algorithm:*

• Manhattan Distance: Digunakan untuk menghitung jarak antara dua titik di grid. Ini adalah perkiraan jarak langsung antara titik awal dan titik tujuan.
• Open List: Daftar yang berisi titik yang belum dieksplorasi, diurutkan berdasarkan nilai f (f = g + h).
• Closed List: Daftar yang berisi titik yang telah dieksplorasi.
• Pencarian Jalur: Algoritma A* memeriksa tetangga dari titik saat ini, menghitung biaya dan memilih jalur terpendek.