реализовать алгоритм A * в Python

Question

Я хочу реализовать A * algorithm in Python. Агент первоначально находится в координатах (6,2) и пытается достичь координат (4,11). Вселенная этого агента представляет собой сетку 12x12 positions, в которой подмножество позиций недоступно. Действия агента очень просты: он может двигаться на один шаг на север, юг, восток и запад от своего текущего положения. Движения по диагонали не допускаются. Агент не знает его положения. недоступен да и да только при непосредственной близости к этому заблокированному положению. Каждый Paso дается агентом на пути от начальных отсчетов положения, как расстояние (расстояние до сих пор)

1 У меня есть много трудностей, чтобы построить поисковую вселенную, которая в этом случае будет в 12x12 позиции сетки.

-не знаю, чтобы определить шаги координаты агента, принимая во внимание блоков не достижимые

спасибо за вашу помощь

Answer 1

Вы можете создать свои сетки в виде списка списка Booleans, таких как:

grid = [[True for i in range(12)] for i in range(12)] 

и установить позиции, которые не доступны для False как

not_accessible = [(5, 10), (10, 7), (1, 0), (2, 4), (5, 2), 
        (5, 8), (5, 2), (8, 7), (6, 11), (2, 9), 
        (11, 0), (2, 10), (3, 4), (3, 5), (1, 5), 
        (8, 1), (3, 1), (11, 11), (9, 3), (3, 7)] 

for x, y in not_accessible: 
    grid[x][y] = False 

и определить некоторую функцию, чтобы переместить

def new_field(direction, x0, y0, grid): 
    if direction == 'L': 
     x1, y1 = x0 - 1, y0 
    elif direction == 'R': 
     x1, y1 = x0 + 1, y0 
    elif direction == 'U': 
     x1, y1 = x0, y0 + 1 
    elif direction == 'D': 
     x1, y1 = x0, y0 - 1 

    if x1 not in range(12) or y1 not in range(12): 
     raise Exception('New field outside of grid') 
    if not grid[x1][y1]: 
     raise Exception('New field not accessible') 

    return x1, y1 

Например

print new_field('U', 0, 0, grid) 
# => (0, 1) 

print new_field('D', 0, 0, grid) 
# => Exception: New field outside of grid 

print new_field('R', 0, 0, grid) 
# => Exception: New field not accessible 

Это должно дать вам хороший старт для реализации фактического алгоритма.