A*寻路算法(Python)_a算法迷宫实验报告python

一、题目描述
在一个迷宫游戏里，有一些小怪物要去攻击主角，现在希望给这些小怪物加上聪明的AI，让他们可以自动绕过迷宫中的障碍物，寻找到主角所在。
二、解题思路
迷宫游戏里的场景通常都是由小方格组成。假设我们有一个7*5大小的迷宫，图中红色格子是终点，绿色格子是起点，蓝色格子是一堵墙。

AI角色从起点开始，每一步只能向上、下、左、右移动1格，且不能穿越墙壁，那么如何让AI角色用最少的步数达到终点？

首先要引入两个集合和1个公式：
open_list：可到达的格子
close_list：已到达的格子
一个公式如下：
F=G+H
每一个格子都具有F、G、H这三个属性：
G：从起点走到当前格子的成本，也就是已经花费了多少步。
H：在不考虑障碍的情况下，从当前格子走到目标格子的距离，也就是离目标还有多远。
F：G和H的综合评估，也就是从起点到达当前格子，再从当前格子到达目标格子的总步数。

第一步：把起点放入open_list，也就是可到达格子的集合。
第二步：找出open_list中F值最小的方格作为当前方格。
第三步：找出当前方格上下左右所有可到达的格子，看他们是否在open_list或者close_list中，如果不在，则将他们加入open_list中。计算出相应G、H、F值，并把当前格子作为他们的父节点。
之后进行第二轮，我们需要一次又一次重复刚刚的第二不和第三步，直到直到终点为止。

三、代码实现

def a_star_search(start, end):
    # 待访问的格子
    open_list = []
    # 已访问的格子
    close_list = []
    # 把起点加入open_list
    open_list.append(start)
    # 主循环，每一轮检查一个当前方格节点
    while len(open_list) > 0:
        # 在open_list中查找 F值最小的节点作为当前方格节点
        current_grid = find_min_gird(open_list)
        # 当前方格节点从openList中移除
        open_list.remove(current_grid)
        # 当前方格节点进入 closeList
        close_list.append(current_grid)
        # 找到所有邻近节点
        neighbors = find_neighbors(current_grid, open_list, close_list)
        for grid in neighbors:
            if grid not in open_list:
            # 邻近节点不在openList中，标记父亲、G、H、F，并放入openList
                grid.init_grid(current_grid, end)
                open_list.append(grid)
        # 如果终点在openList中，直接返回终点格子
        for grid in open_list:
            if (grid.x == end.x) and (grid.y == end.y
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24