本文共 3587 字，大约阅读时间需要 11 分钟。

A*算法在迷宫中的应用

问题描述

在一个迷宫游戏中，小怪物需要自动绕过障碍物并寻找主角。迷宫通常由小方格组成，红色格子是终点，绿色格子是起点，蓝色格子是墙壁。AI角色从起点开始，每一步只能向上、下、左、右移动一格，且不能穿越墙壁。目标是让AI角色用最少的步数到达终点。

解题思路

为了实现这一目标，我们引入了两个集合和一个公式：

每个格子都有三个属性：

• G：从起点走到当前格子的步数成本。
• H：在不考虑障碍的情况下，从当前格子走到终点的距离。
• F：综合评估，等于G和H之和，即从起点到当前格子再到终点的总步数。

算法步骤如下：

代码实现

def a_star_search(start, end):
    open_list = []
    close_list = []
    open_list.append(start)
    
    while len(open_list) > 0:
        current_grid = find_min_grid(open_list)
        open_list.remove(current_grid)
        close_list.append(current_grid)
        
        neighbors = get_neighbors(current_grid, open_list, close_list)
        for grid in neighbors:
            if grid not in open_list:
                grid.init_grid(current_grid, end)
                open_list.append(grid)
        
        if any((grid.x == end.x and grid.y == end.y) for grid in open_list):
            result_grid = next((grid for grid in open_list if grid.x == end.x and grid.y == end.y), None)
            break
        
    return result_grid
def find_min_grid(open_list):
    if not open_list:
        return None
    min_grid = open_list[0]
    for grid in open_list:
        if grid.f < min_grid.f:
            min_grid = grid
    return min_grid
def get_neighbors(grid, open_list, close_list):
    neighbors = []
    if is_valid(grid.x, grid.y - 1, open_list, close_list):
        neighbors.append(Grid(grid.x, grid.y - 1))
    if is_valid(grid.x, grid.y + 1, open_list, close_list):
        neighbors.append(Grid(grid.x, grid.y + 1))
    if is_valid(grid.x - 1, grid.y, open_list, close_list):
        neighbors.append(Grid(grid.x - 1, grid.y))
    if is_valid(grid.x + 1, grid.y, open_list, close_list):
        neighbors.append(Grid(grid.x + 1, grid.y))
    return neighbors
def is_valid(x, y, open_list, close_list):
    if x < 0 or x >= len(MAZE) or y < 0 or y >= len(MAZE[0]):
        return False
    if MAZE[x][y] == 1:
        return False
    if any(grid.x == x and grid.y == y for grid in open_list):
        return False
    if any(grid.x == x and grid.y == y for grid in close_list):
        return False
    return True
class Grid:
    def __init__(self, x, y):
        self.x = x
        self.y = y
        self.f = 0
        self.g = 0
        self.h = 0
        self.parent = None
    
    def init_grid(self, parent, end):
        self.parent = parent
        if parent is not None:
            self.g = parent.g + 1
        else:
            self.g = 1
        self.h = abs(self.x - end.x) + abs(self.y - end.y)
        self.f = self.g + self.h

代码解释

迷宫设置与路径回溯

MAZE = [
    [0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 1, 0, 0, 0],
    [0, 0, 0, 1, 0, 0, 0],
    [0, 0, 0, 1, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0]
]
start_grid = Grid(2, 1)
end_grid = Grid(2, 5)
result_grid = a_star_search(start_grid, end_grid)
path = []
while result_grid is not None:
    path.append(Grid(result_grid.x, result_grid.y))
    result_grid = result_grid.parent
for i in range(len(MAZE)):
    for j in range(len(MAZE[0])):
        if (i, j) in path:
            print("*", end="")
        else:
            print(str(MAZE[i][j]), end="")
    print()

结果展示

运行上述代码后，您可以看到迷宫地图和路径。路径用星号表示，迷宫中的0表示空地，1表示墙壁。

转载地址：http://wdvg.baihongyu.com/