项目三：使用python实现迷宫并利用a*算法自动寻路--预习报告_a算法迷宫实验报告python

        第三个项目是迷宫的实现，这里我选择python语言，生成算法选择prime算法，自动寻路算法使用A*算法。

1.环境配置

        我使用的python环境为python3.9，在visual studio中进行编译运行，其中为了更好地进行实现，导入了python的pygame库以及time库，头文件中包含随机数头文件。

2.prime算法生成地图的原理

首先，定义墙和路，例如：

在这里，定义墙为0，路为1；

接下来，第一步，先找到一格路作为起点，从起点开始随机选择路周围的墙，若这格墙之后仍是墙，则继续随机选择路周围剩余的墙，若这格墙的下一格为路，则将这格墙改为路。图示：

代码实现：

  for i in range(0, len(lujing)):
      if lujing[i].row - 2 == lujing[x + 1].row and lujing[i].col == lujing[x + 1].col:
          lujin.append(Point(lujing[i].row - 1, lujing[i].col))
          break
      if lujing[i].row + 2 == lujing[x + 1].row and lujing[i].col == lujing[x + 1].col:
          lujin.append(Point(lujing[i].row + 1, lujing[i].col))
          break
      if lujing[i].row == lujing[x + 1].row and lujing[i].col - 2 == lujing[x + 1].col:
          lujin.append(Point(lujing[i].row, lujing[i].col - 1))
          break
      if lujing[i].row == lujing[x + 1].row and lujing[i].col + 2 == lujing[x + 1].col:
          lujin.append(Point(lujing[i].row, lujing[i].col + 1))
          break

 

第二步，记录已经遍历过的路，重复第一步的内容，但是判断时需要增加一个条件，也就是如果选择墙时，其下一格是曾经遍历过的路，那么这格墙就不能改为路，它一定是墙。图示：

代码实现：

   a = []
   for i in range(0, len(lu)):
       if point.col - 2 == lu[i].col and point.row == lu[i].row:
           a.append(lu[i])
       if point.col + 2 == lu[i].col and point.row == lu[i].row:
           a.append(lu[i])
       if point.col == lu[i].col and point.row - 2 == lu[i].row:
           a.append(lu[i])
       if point.col == lu[i].col and point.row + 2 == lu[i].row:
           a.append(lu[i])
   for j in range(0, len(lu)):
       if point.col == lu[j].col and point.row == lu[j].row:
           s = j
   genghuan = []
   for i in range(0, len(a)):
       for j in liebiao:
           if a[i].col == j.col:
               if a[i].row == j.row:

 

一直重复上述步骤，直到遍历所有起始生成的路径。

3.A*算法对寻路的实现

        A*算法的核心原理就是给路径增加一个路径增量，这就让每一步带来的收益均不同，可以从理想收益最大化的路径寻路，以缩短寻路所需的时间。

        路径增量的实现：路径增量为D+H，A*算法中，每走一步D都会增加1，而H则为从当前位置到寻路终点的估算值，这里采用曼哈顿距离，即横纵坐标距离之和。

        寻路时，优先选择路径增量最小的路径移动，若错误，则回溯，回溯即每次经过分岔路口时，就将该路口设为一个节点，若接下来走到了尽头，无路可走，就回溯到上一个节点，走另外一个分岔，如此一直递归，直到最终遍历到终点为止。

while True:
    # 判断最后走过的节点是否为终点
    if Close[-1] != [endx, endy]:
        Open = []
        # 减1得到数组下标值
        i, j = Close[-1][0] - 1, Close[-1][1] - 1
        # 对当前节点上下左右四个节点进行判断
        for ni, nj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
            if [ni + 1, nj + 1] not in Opens and 0 <= ni < rows and 0 <= nj < cols and a[ni, nj] == 0:
                Open.append([ni + 1, nj + 1])
        # 将已走过的节点值修改为路径值，并将路径值加1
        a[i, j] = road
        road = road + 1
        if Open:
            # 对所有扩展到的节点进行排序，reverse=True 结果从大到小，即尾部存储代价最小的节点
            Open = sorted(Open, key=lambda x: gs(x[0], x[1]) + h2(x[0], x[1]), reverse=True)
            Opens.extend(Open)
            # 将代价最小的节点存储到 Close 表
            Close.append(Open.pop())
            # 如果 pop 后 Open 表不为空，说明存在岔路，将岔路存储到 crossings 中
            if Open:
                crossings.extend(Open)
        # 判断是否存在未走过的分叉节点
        elif crossings:
            next_way = crossings.pop()
            # 实现路径回退，循环条件为回退节点与分叉节点不相邻
            while sum((np.array(Close[-1]) - np.array(next_way)) ** 2) != 1:
                # 当一条路径寻找失败后，是否将该路径岔路后的部分恢复为原地图
                # i, j = Close[-1]
                # a[i-1, j-1] = 0
                # 每次 while 循环路径值 road 减1，并弹出 Close 表中的节点
                road -= 1
                Close.pop()
            # 将 crossings 中最后一个节点添加到 Close 表
            Close.append(next_way)
        else:
 
            break
    else:
        a[endx - 1, endy - 1] = road
        break

4.游戏的最终实现

最后添加绘制函数，将地图绘制出来，添加键盘相应函数以完成迷宫的控制，代码较简单，略

实现界面：

地图绘制

移动及提示：