迷宫问题的A*算法（python实现）

附件中A_star.py为算法实现，有两个txt文件作为测试样例，mediumMaze是一个封闭的迷宫，openmaze是一个开放的迷宫

import numpy as np
import time

f = open（“openMaze.txt““r“）
#f = open（“mediumMaze.txt““r“）
list = []
line = f.readline（）
while line:
    line=line.strip（‘\n‘）
    #print（line）
    list.append（line）
    line = f.readline（）
    
f.close（）
hang = len（list）
lie = len（list[1]）

maze = np.zeros（（hanglie）dtype = np.int）
for i in range（hang）:
    for j in range（lie）:
        if list[i][j] == ‘%‘:
            maze[i][j] = 1
        elif list[i][j] == ‘ ‘:
            maze[i][j] = 0
        elif list[i][j] == ‘.‘:#终点用2表示
            maze[i][j] = 2
        elif list[i][j] == ‘P‘:#起点用3表示
            maze[i][j] = 3

###############初始化标记数组
mark = np.zeros（（hanglie）dtype = np.int）
for i in range（len（maze））:
    for j in range（len（maze[i]））:
        if maze[i][j] == 2:
            endx = i
            endy = j
        if maze[i][j] == 3:
            startx = i
            starty = j

#################初始化迷宫的四种方向走法
next_step = [[01]       #向右走
              [10]      #向下走
              [0-1]     #向左走
               [-10]]

#定义启发函数
def function（xy）:
    return abs（endx - x）+abs（endy - y）
 
parent = np.zeros（（hanglie）dtype = int）
cost_so_far = np.zeros（（hanglie）dtype = int）
open = []
closed = []
F = []
total_explore = 0 ####记录总的探索的节点数

cost_so_far[startx][starty] = 0
open.append（[startxstarty]）
F.append（0）
flag = 0   #flag等于1表示到达终点，否则表示没有到达

###############算法开始
starttime = time.time（）    #记录开始时间
while（len（open） != 0）:
        index = F.index（min（F））
        current = open[index]
        del open[index]
        del F[index]
        closed.append（current）
        current_x = current[0]
        current_y = current[1]
        for i in range（len（next_step））:
            next_x = current_x + next_step[i][0]
            next_y = current_y + next_step[i][1]
            
            next = [next_xnext_y]
            f = 9*function（next_xnext_y） + cost_so_far[current_x][current_x] + 1
            if（next_x < 0 or next_y < 0 or next_x > len（maze） or next_y > len（maze[0]））:
                continue
            if（next in closed）:
                continue
            if（next in open）:
                same_index = open.index（next）
                same_f = F[same_index]
                if（f < same_f）:
                    F[same_index] = f
                    parent[next_x][next_y] = i
                    cost_so_far[next_x][next_y] = cost_so_far[current_x][current_y] + 1
                    continue
                else:
                    continue
            if（maze[next_x][next_y] == 0）:
                parent[next_x][next_y] = i
                open.append（[next_xnext_y]）
                F.append（f）
                total_explore += 1        ######每当有一个节点加入open集当中，总的探索的节点数加1
                cost_so_far[next_x][next_y] = cost_so_far[current_x][current_y] + 1

            if（next_x == endx and next_y == endy）:
                flag = 1
                break

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     文件        4812  2019-06-02 20:27  A_star.py
     文件        1447  2019-05-16 17:09  mediumMaze.txt
     文件         778  2019-05-16 17:09  openMaze.txt