A*算法实现走迷宫
世间难得逍遥
|
|
446
|
0

1306 字
|
23 分钟

先看效果图

A*算法

A*算法是一种启发式搜索算法，它不需遍历所有节点，只是利用包含问题启发式信息的评价函数对节点进行排序，使搜索方向朝着最有可能找到目标并产生最优解的方向。它的独特之处是检查最短路径中每个可能的节点时引入了全局信息，对当前节点距终点的距离做出估计，并作为评价节点处于最短路径上的可能性度量。

A*算法中引入了评估函数，评估函数为：f（n）=g（n）+h（n） 其中：n是搜索中遇到的任意状态。g(n)是沿路径从起点到n点的移动耗费。h(n)是对n到目标状态代价的启发式估计。即评估函数f ( n) 是从初始节点到达节点n 处已经付出的代价与节点n 到达目标节点的接近程度估价值的总和。

这里我们定义n点到目标点的最小实际距离为h（n），A算法要满足的条件为：h（n）<=h（n）* 。迷宫走的时候只能往上下左右走，每走一步，代价为1，H值可以用不同的方法估算。我们这里使用的方法被称为曼哈顿方法，它计算从当前格到目的格之间水平和垂直的方格的数量总和，即： h（n）=|endPoint.x – n.x|+ |endpoint.y – n.y|这里endPoint表示迷宫的目标点，n表示当前点，很明显这里h（n）<=h（n）*。

类的定义

  1. mapPoint :代表图中的每一个格子，搜索路径的每一个格子，记录的信息有：
    • self.x = x self.y = y 当前节点的坐标位置
    • self.distanceStart = distanceStart 记录下由起点走到该节点的耗散值（由起点走到该节点的路径的距离，该节点的下一个节点会加1）
    • self.endX = endX self.endY = endY 目标节点
    • self.parentPoint = parentPoint # 前一个节点
  2. 方法：

评价函数：由于该评价函数比较容易计算，我直接放到该类中

def evaluate(self):
    return self.distanceStart + abs(self.x - self.endX) + abs(self.y - self.endY)

判断两个节点是否是同一个位置的

def isEq(self, point):
    if point.x == self.x and point.y == self.y:
        return True
    else:
        return False

A*算法代码实现

定义的数据结构

self.openList = []  # open表
self.closeList = []  # close表
self.route = []  # 路径列表

A*算法的主要过程

  1. 先将起点放进open表中
  2. 检查终点是否在open表中，否的话，从open表中取出评价值最低的节点作为当前节点，并向四周探索，将上、下、左、右 里面非障碍的子节点，并检查子节点是否已经存在于open表或close表，若是存在open表中，则比较两个子节点与open表中的节点的评价值，若是open表中的比较大，则将open表中的替换，否则不操作；若是close表中存在且close表的节点的评价值比较大，则放进该子节点open表，否则不做操作。 然后将当前节点移出open表，并放进close表。
  3. 循环第2点，知道检测到终点在open 表中，然后将终点记录在路径列表中route = [] 中，并通过循环不断得到前一个节点，一直记录下来，直达没有前一个节点为止。
def Astart(self):
        # 将起点放到open表中
        self.openList.append(self.startPoint)
        while (not self.isOK):
            # 先检查终点是否在open表中 ，没有继续，有则结束
            if self.inOpenList(self.endPoint) != -1:  # 在open表中
                self.isOK = True  #
                self.end = self.openList[self.inOpenList(self.endPoint)]
                self.route.append(self.end)
                self.te = self.end
                while (self.te.parentPoint != 0):
                    self.te = self.te.parentPoint
                    self.route.append(self.te)
            else:
                self.sortOpenList()  # 将估值最小的节点放在index = 0
                current_min = self.openList[0]  # 估值最小节点
                self.openList.pop(0)
                self.closeList.append(current_min)
                # 开拓current_min节点，并放到open 表
                if current_min.x - 1 >= 0:  # 没有越界
                    if (self.mapStatus[current_min.y][current_min.x - 1]) != 0:  # 非障碍,可开拓
                        self.temp1 = mapPoint(current_min.x - 1, current_min.y, current_min.distanceStart + 1,
                                              self.endPoint.x, self.endPoint.y, current_min)
                        if self.inOpenList(self.temp1) != -1:  # open表存在相同的节点
                            if self.temp1.evaluate() < self.openList[self.inOpenList(self.temp1)].evaluate():
                                self.openList[self.inOpenList(self.temp1)] = self.temp1
                        elif self.inCloseList(self.temp1) != -1:  # 否则查看close表是否存在相同的节点（存在）
                            if self.temp1.evaluate() < self.closeList[self.inCloseList(self.temp1)].evaluate():
                                self.closeList[self.inCloseList(self.temp1)] = self.temp1
                        else:  # open 、 close表都不存在 temp1
                            self.openList.append(self.temp1)
 
                if current_min.x + 1 < 15:
                    if (self.mapStatus[current_min.y][current_min.x + 1]) != 0:  # 非障碍,可开拓
                        self.temp2 = mapPoint(current_min.x + 1, current_min.y, current_min.distanceStart + 1,
                                              self.endPoint.x, self.endPoint.y, current_min)
                        if self.inOpenList(self.temp2) != -1:  # open表存在相同的节点
                            if self.temp2.evaluate() < self.openList[self.inOpenList(self.temp2)].evaluate():
                                self.openList[self.inOpenList(self.temp2)] = self.temp2
                        elif self.inCloseList(self.temp2) != -1:  # 否则查看close表是否存在相同的节点（存在）
                            if self.temp2.evaluate() < self.closeList[self.inCloseList(self.temp2)].evaluate():
                                self.closeList[self.inCloseList(self.temp2)] = self.temp2
                        else:
                            self.openList.append(self.temp2)
 
                if current_min.y - 1 >= 0:
                    if (self.mapStatus[current_min.y - 1][current_min.x]) != 0:  # 非障碍,可开拓
                        self.temp3 = mapPoint(current_min.x, current_min.y - 1, current_min.distanceStart + 1,
                                              self.endPoint.x, self.endPoint.y, current_min)
                        if self.inOpenList(self.temp3) != -1:  # open表存在相同的节点
                            if self.temp3.evaluate() < self.openList[self.inOpenList(self.temp3)].evaluate():
                                self.openList[self.inOpenList(self.temp3)] = self.temp3
                        elif self.inCloseList(self.temp3) != -1:  # 否则查看close表是否存在相同的节点（存在）
                            if self.temp3.evaluate() < self.closeList[self.inCloseList(self.temp3)].evaluate():
                                self.closeList[self.inCloseList(self.temp3)] = self.temp3
                        else:
                            self.openList.append(self.temp3)
 
                if current_min.y + 1 < 15:
                    if (self.mapStatus[current_min.y + 1][current_min.x]) != 0:  # 非障碍,可开拓
                        self.temp4 = mapPoint(current_min.x, current_min.y + 1, current_min.distanceStart + 1,
                                              self.endPoint.x, self.endPoint.y, current_min)
 
                        if self.inOpenList(self.temp4) != -1:  # open表存在相同的节点
                            if self.temp4.evaluate() < self.openList[self.inOpenList(self.temp4)].evaluate():
                                self.openList[self.inOpenList(self.temp4)] = self.temp4
                        elif self.inCloseList(self.temp4) != -1:  # 否则查看close表是否存在相同的节点（存在）
                            if self.temp4.evaluate() < self.closeList[self.inCloseList(self.temp4)].evaluate():
                                self.closeList[self.inCloseList(self.temp4)] = self.temp4
                        else:
                            self.openList.append(self.temp4)
 
    def drawMapBlock(self, event):
        x, y = event.x, event.y
        if (30 <= x <= 480) and (30 <= y <= 480):
            i = int((x // 30) - 1)
            j = int((y // 30) - 1)
            # 记录下起止点，并不能选择多个起点或者多个终点
            if self.blockcolorIndex == 1 and not self.selectedStart:
                self.startPoint = mapPoint(i, j, 0, 0, 0, 0)
                self.selectedStart = True
                self.canvas.create_rectangle((i + 1) * 30, (j + 1) * 30, (i + 2) * 30, (j + 2) * 30,
                                             fill=self.blockcolor[self.blockcolorIndex])
                self.blockcolorIndex = 0
            elif self.blockcolorIndex == 2 and not self.selectedEnd:
                self.endPoint = mapPoint(i, j, 0, 0, 0, 0)
                self.selectedEnd = True
                self.canvas.create_rectangle((i + 1) * 30, (j + 1) * 30, (i + 2) * 30, (j + 2) * 30,
                                             fill=self.blockcolor[self.blockcolorIndex])
                self.blockcolorIndex = 0
            else:
                self.canvas.create_rectangle((i + 1) * 30, (j + 1) * 30, (i + 2) * 30, (j + 2) * 30,
                                             fill=self.blockcolor[self.blockcolorIndex])
                self.mapStatus[j][i] = self.blockcolorIndex
 
    # 检查终点是否在open表中
    def endInOpenList(self):
        for i in self.openList:
            if self.endPoint[0] == i.x and self.endPoint[1] == i.y:
                return True
        return False
 
    # 将节点加进open表前，检查该节点是否在open表中
    def inOpenList(self, p1):
        for i in range(0, len(self.openList)):
            if p1.isEq(self.openList[i]):
                return i
        return -1
 
    # 将节点加进open表前，检查该节点是否在close表中
    # 若在返回索引，不在返回-1
    def inCloseList(self, p1):
        for i in range(0, len(self.closeList)):
            if p1.isEq(self.closeList[i]):
                return i
        return -1
 
    # 将 估值最小的 排在 index = 0
    def sortOpenList(self):
        if len(self.openList) > 0:
            if len(self.openList) > 1:
                for i in range(1, len(self.openList)):
                    if self.openList[i].evaluate() < self.openList[0].evaluate():
                        self.t = self.openList[0]
                        self.openList[0] = self.openList[i]
                        self.openList[i] = self.t

最终代码

# -*- coding: utf-8 -*-
 
from tkinter import Button
from tkinter import Tk
from tkinter import Canvas
 
import numpy as np
 
 
class Maze(object):
 
    def __init__(self):
 
        self.blockcolorIndex = 0
        self.blockcolor = ['black', 'yellow', 'red', 'green']  # 障碍颜色为黑色、起点黄色 终点红色、路径绿色
        self.mapStatus = np.ones((15, 15), dtype=int)  # 地图状态数组（全0数组） 1无障碍 0障碍
        self.startPoint = 'start'  # 起点
        self.endPoint = 'end'  # 终点
 
        self.selectedStart = False  # 是否选了起点 默认否
        self.selectedEnd = False  # 是否选了终点 默认否
 
        self.openList = []  # open表
        self.closeList = []  # close表
        self.isOK = False  # 是否已经结束
 
        self.route = []  # 路径列表
        # UI
        self.root = Tk()
        self.root.title('走迷宫(A*算法)')
        self.root.geometry("800x800+300+0")
        self.btn_obstacle = Button(self.root, text="选择障碍", command=self.selectobstacle)
        self.btn_obstacle.pack()
        self.btn_start = Button(self.root, text="选择起点", command=self.selectstart)
        self.btn_start.pack()
        self.btn_end = Button(self.root, text="选择终点", command=self.selectend)
        self.btn_end.pack()
        self.btn_action = Button(self.root, text="开始寻路", command=self.selectaction)
        self.btn_action.pack()
        self.btn_restart = Button(self.root, text="重新开始", command=self.selectrestart)
        self.btn_restart.pack()
        self.canvas = Canvas(self.root, width=500, height=500, bg="white")
        self.canvas.pack()
        for i in range(1, 17):
            self.canvas.create_line(30, 30 * i, 480, 30 * i)  # 横线
            self.canvas.create_line(30 * i, 30, 30 * i, 480)  # 竖线
        self.canvas.bind("<Button-1>", self.drawMapBlock)
        self.root.mainloop()
 
    def selectrestart(self):
        self.mapStatus = np.ones((15, 15), dtype=int)  # 地图状态数组（全0数组） 1无障碍 0障碍
        self.startPoint = 'start'
        self.endPoint = 'end'
        self.selectedStart = False  # 是否选了起点 默认否
        self.selectedEnd = False  # 是否选了终点 默认否
        self.openList = []  # open表
        self.closeList = []  # close表
        self.isOK = False  # 是否已经结束
        self.route = []
        self.canvas.destroy()
        self.canvas = Canvas(self.root, width=500, height=500, bg="white")
        self.canvas.pack()
 
        for i in range(1, 17):
            self.canvas.create_line(30, 30 * i, 480, 30 * i)  # 横线
            self.canvas.create_line(30 * i, 30, 30 * i, 480)  # 竖线
        self.canvas.bind("<Button-1>", self.drawMapBlock)
 
    def selectobstacle(self):
        self.blockcolorIndex = 0  # 'black'
 
    def selectstart(self):
        if not self.selectedStart:
            self.blockcolorIndex = 1  # yellow
        else:
            self.blockcolorIndex = 0  # black
 
    def selectend(self):
        if not self.selectedEnd:
            self.blockcolorIndex = 2  # red
        else:
            self.blockcolorIndex = 0  # black
 
    def selectaction(self):
        self.blockcolorIndex = 3  # 'green'
        self.Astart()
        self.route.pop(-1)
        self.route.pop(0)
        for i in self.route:
            self.canvas.create_rectangle((i.x + 1) * 30, (i.y + 1) * 30, (i.x + 2) * 30, (i.y + 2) * 30, fill='green')
 
    def Astart(self):
        # 将起点放到open表中
        self.openList.append(self.startPoint)
        while (not self.isOK):
            # 先检查终点是否在open表中 ，没有继续，有则结束
            if self.inOpenList(self.endPoint) != -1:  # 在open表中
                self.isOK = True  #
                self.end = self.openList[self.inOpenList(self.endPoint)]
                self.route.append(self.end)
                self.te = self.end
                while (self.te.parentPoint != 0):
                    self.te = self.te.parentPoint
                    self.route.append(self.te)
            else:
                self.sortOpenList()  # 将估值最小的节点放在index = 0
                current_min = self.openList[0]  # 估值最小节点
                self.openList.pop(0)
                self.closeList.append(current_min)
                # 开拓current_min节点，并放到open 表
                if current_min.x - 1 >= 0:  # 没有越界
                    if (self.mapStatus[current_min.y][current_min.x - 1]) != 0:  # 非障碍,可开拓
                        self.temp1 = mapPoint(current_min.x - 1, current_min.y, current_min.distanceStart + 1,
                                              self.endPoint.x, self.endPoint.y, current_min)
                        if self.inOpenList(self.temp1) != -1:  # open表存在相同的节点
                            if self.temp1.evaluate() < self.openList[self.inOpenList(self.temp1)].evaluate():
                                self.openList[self.inOpenList(self.temp1)] = self.temp1
                        elif self.inCloseList(self.temp1) != -1:  # 否则查看close表是否存在相同的节点（存在）
                            if self.temp1.evaluate() < self.closeList[self.inCloseList(self.temp1)].evaluate():
                                self.closeList[self.inCloseList(self.temp1)] = self.temp1
                        else:  # open 、 close表都不存在 temp1
                            self.openList.append(self.temp1)
 
                if current_min.x + 1 < 15:
                    if (self.mapStatus[current_min.y][current_min.x + 1]) != 0:  # 非障碍,可开拓
                        self.temp2 = mapPoint(current_min.x + 1, current_min.y, current_min.distanceStart + 1,
                                              self.endPoint.x, self.endPoint.y, current_min)
                        if self.inOpenList(self.temp2) != -1:  # open表存在相同的节点
                            if self.temp2.evaluate() < self.openList[self.inOpenList(self.temp2)].evaluate():
                                self.openList[self.inOpenList(self.temp2)] = self.temp2
                        elif self.inCloseList(self.temp2) != -1:  # 否则查看close表是否存在相同的节点（存在）
                            if self.temp2.evaluate() < self.closeList[self.inCloseList(self.temp2)].evaluate():
                                self.closeList[self.inCloseList(self.temp2)] = self.temp2
                        else:
                            self.openList.append(self.temp2)
 
                if current_min.y - 1 >= 0:
                    if (self.mapStatus[current_min.y - 1][current_min.x]) != 0:  # 非障碍,可开拓
                        self.temp3 = mapPoint(current_min.x, current_min.y - 1, current_min.distanceStart + 1,
                                              self.endPoint.x, self.endPoint.y, current_min)
                        if self.inOpenList(self.temp3) != -1:  # open表存在相同的节点
                            if self.temp3.evaluate() < self.openList[self.inOpenList(self.temp3)].evaluate():
                                self.openList[self.inOpenList(self.temp3)] = self.temp3
                        elif self.inCloseList(self.temp3) != -1:  # 否则查看close表是否存在相同的节点（存在）
                            if self.temp3.evaluate() < self.closeList[self.inCloseList(self.temp3)].evaluate():
                                self.closeList[self.inCloseList(self.temp3)] = self.temp3
                        else:
                            self.openList.append(self.temp3)
 
                if current_min.y + 1 < 15:
                    if (self.mapStatus[current_min.y + 1][current_min.x]) != 0:  # 非障碍,可开拓
                        self.temp4 = mapPoint(current_min.x, current_min.y + 1, current_min.distanceStart + 1,
                                              self.endPoint.x, self.endPoint.y, current_min)
 
                        if self.inOpenList(self.temp4) != -1:  # open表存在相同的节点
                            if self.temp4.evaluate() < self.openList[self.inOpenList(self.temp4)].evaluate():
                                self.openList[self.inOpenList(self.temp4)] = self.temp4
                        elif self.inCloseList(self.temp4) != -1:  # 否则查看close表是否存在相同的节点（存在）
                            if self.temp4.evaluate() < self.closeList[self.inCloseList(self.temp4)].evaluate():
                                self.closeList[self.inCloseList(self.temp4)] = self.temp4
                        else:
                            self.openList.append(self.temp4)
 
    def drawMapBlock(self, event):
        x, y = event.x, event.y
        if (30 <= x <= 480) and (30 <= y <= 480):
            i = int((x // 30) - 1)
            j = int((y // 30) - 1)
            # 记录下起止点，并不能选择多个起点或者多个终点
            if self.blockcolorIndex == 1 and not self.selectedStart:
                self.startPoint = mapPoint(i, j, 0, 0, 0, 0)
                self.selectedStart = True
                self.canvas.create_rectangle((i + 1) * 30, (j + 1) * 30, (i + 2) * 30, (j + 2) * 30,
                                             fill=self.blockcolor[self.blockcolorIndex])
                self.blockcolorIndex = 0
            elif self.blockcolorIndex == 2 and not self.selectedEnd:
                self.endPoint = mapPoint(i, j, 0, 0, 0, 0)
                self.selectedEnd = True
                self.canvas.create_rectangle((i + 1) * 30, (j + 1) * 30, (i + 2) * 30, (j + 2) * 30,
                                             fill=self.blockcolor[self.blockcolorIndex])
                self.blockcolorIndex = 0
            else:
                self.canvas.create_rectangle((i + 1) * 30, (j + 1) * 30, (i + 2) * 30, (j + 2) * 30,
                                             fill=self.blockcolor[self.blockcolorIndex])
                self.mapStatus[j][i] = self.blockcolorIndex
 
    # 检查终点是否在open表中
    def endInOpenList(self):
        for i in self.openList:
            if self.endPoint[0] == i.x and self.endPoint[1] == i.y:
                return True
        return False
 
    # 将节点加进open表前，检查该节点是否在open表中
    def inOpenList(self, p1):
        for i in range(0, len(self.openList)):
            if p1.isEq(self.openList[i]):
                return i
        return -1
 
    # 将节点加进open表前，检查该节点是否在close表中
    # 若在返回索引，不在返回-1
    def inCloseList(self, p1):
        for i in range(0, len(self.closeList)):
            if p1.isEq(self.closeList[i]):
                return i
        return -1
 
    # 将 估值最小的 排在 index = 0
    def sortOpenList(self):
        if len(self.openList) > 0:
            if len(self.openList) > 1:
                for i in range(1, len(self.openList)):
                    if self.openList[i].evaluate() < self.openList[0].evaluate():
                        self.t = self.openList[0]
                        self.openList[0] = self.openList[i]
                        self.openList[i] = self.t
 
 
class mapPoint(object):
    def __init__(self, x, y, distanceStart, endX, endY, parentPoint):
        self.x = x
        self.y = y
        self.distanceStart = distanceStart
        self.endX = endX
        self.endY = endY
        self.parentPoint = parentPoint  # 前一个节点
 
    def evaluate(self):
        return self.distanceStart + abs(self.x - self.endX) + abs(self.y - self.endY)
 
    def isEq(self, point):
        if point.x == self.x and point.y == self.y:
            return True
        else:
            return False
 
 
def main():
    Maze()
 
 
if __name__ == '__main__':
    main()

文章标题：A*算法实现走迷宫
文章作者：世间难得逍遥
文章链接：https://www.abyss.website/classify/algorithm/maze/

许可协议： CC BY 4.0 转载请保留原文链接及作者。


A*算法Python
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																					

							
							
						

										
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

                    

                    
			        推荐文章
		            

		            

							
Louvain社区发现算法原理，细节以及实现

							
							

							
PageRank算法详解

							
							

							
MATLAB实现BP算法对iris数据集进行分类

							
							

							
SafeChat——基于python的安全即时通讯系统

							
							

							
遗传算法解决旅行商问题（TSP）