在Python中实现A*算法

Question

我想实现一个A * algorithm in Python。代理最初位于坐标(6,2)，并试图到达坐标(4,11)。这个代理的宇宙是一个12x12 positions的网格，其中位置的子集是不可访问的。特工的行动是非常基本的：它可以向北、向南、向东和向西移动一步。不允许对角线移动。特工不知道自己的位置。 不可接近是，且仅当紧靠此锁定位置时是。 代理在从初始位置开始的路径上给出的每个paso都算作行驶距离（distance 到目前为止）

1我有很多困难来建立搜索宇宙，在这个例子中是12x12网格位置。在

2不知道如何定义代理移动的坐标，考虑到无法到达的块

谢谢你的帮助

Answer 1

您可以将网格设计为布尔值列表，例如：

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

并设置False不可访问的位置

^{pr2}$

定义一些要移动的函数

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

这将为您实现实际算法提供一个良好的开端。在