Scribd Logo
Upload

Welcome to Scribd!

  • 1 views

    A star

    Uploaded by

    adarshvbspu

    Copyright:

    © All Rights Reserved
    Download as TXT, PDF, TXT or read online from Scribd

    A star

    Uploaded by

    adarshvbspu
    1 views1 page

    Copyright

    © © All Rights Reserved

    Available Formats

    TXT, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

    © All Rights Reserved
    Download as TXT, PDF, TXT or read online from Scribd
    Download as txt, pdf, or txt
    1 views1 page

    A star

    Uploaded by

    adarshvbspu

    Copyright:

    © All Rights Reserved
    Download as TXT, PDF, TXT or read online from Scribd
    Download as txt, pdf, or txt
    You are on page 1of 1

    from heapq import heappop, heappush

    def heuristic(a, b):


    # Manhattan distance heuristic
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

    def a_star(grid, start, goal):


    rows, cols = len(grid), len(grid[0])
    open_set = []
    heappush(open_set, (0, start))
    came_from = {}
    g_score = {start: 0}
    f_score = {start: heuristic(start, goal)}

    while open_set:
    _, current = heappop(open_set)

    if current == goal:
    # Reconstruct the path
    path = []
    while current in came_from:
    path.append(current)
    current = came_from[current]
    path.append(start)
    return path[::-1]

    for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
    neighbor = (current[0] + dr, current[1] + dc)
    if 0 <= neighbor[0] < rows and 0 <= neighbor[1] < cols and
    grid[neighbor[0]][neighbor[1]] == 0:
    tentative_g_score = g_score[current] + 1

    if tentative_g_score < g_score.get(neighbor, float('inf')):


    came_from[neighbor] = current
    g_score[neighbor] = tentative_g_score
    f_score[neighbor] = tentative_g_score + heuristic(neighbor,
    goal)
    heappush(open_set, (f_score[neighbor], neighbor))

    return None # Return None if no path is found

    # Example grid (0 = walkable, 1 = obstacle)


    grid = [
    [0, 1, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 1, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 0, 0]
    ]

    start = (0, 0) # Starting position


    goal = (4, 4) # Goal position

    path = a_star(grid, start, goal)

    if path:
    print("Path found:", path)
    else:
    print("No path found")

    You might also like