Project3 基于A*搜索算法迷宫游戏开发

本文主要是介绍Project3 基于A*搜索算法迷宫游戏开发，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Day1

实验要求：

1)迷宫游戏是非常经典的游戏，在该题中要求随机生成一个迷宫，并求解迷宫;
2)要求查找并理解迷宫生成的算法,并尝试用两种不同的算法来生成随机的迷宫。
3)要求游戏支持玩家走迷宫，和系统走迷宫路径两种模式。玩家走迷宫，通过键盘
方向键控制，并在行走路径上留下痕迹;系统走迷宫路径要求基于A*算法实现，输
出走迷宫的最优路径并显示。设计交互友好的游戏图形界面。

相关知识：

• 广度优先遍历(BFS)：
  关于路径搜索问题，我们在了解A*算法之前，应该先了解一下广度优先遍历算法，这也是一个万能的算法。它不仅仅用在路径搜索问题上，还应用在别的地方，比如说Windows画图工具里的颜料桶。按我的理解，广度优先算法就是体现在广度两个字，在路径搜索问题上体现在把整个地图跑完才能找到最短路径，没有方向性。
  广度优先搜索算法(BFS) 是最简便的图的搜索算法之一, 这一算法也是很多重要的图的算法的原型。
  BFS并不使用经验法则算法。所谓广度,就是一层一层的，向下遍历，层堵截，从算法的观点，所有因为展开节点而得到的子节点都会被加进一个先进先出的队列中。一 般的实验里， 其邻居节点尚未被检验过的节点会被放置在一个被称为 open的容器中(例如队列或是链表)，而被检验过的节点则被放置在被称为closed的容器中。

• A*算法：
  项目的关键是基于A算法生成迷宫路径，所以我们先要搞懂什么是A算法已经怎样来实现A算法。
  与广度优先遍历不一样的是，A算法在每一轮循环的时候，不会去探索所有的边界方块，而会去选择当前"代价最小"的方块进行探索，这就具有了方向性。这里的"代价"我们分为:预估代价和当前代价。
  **当前代价(F-cost)**从起点A移动到终点B的移动代价，沿着到达该方格而生成的路径。
  预估代价(G-cost):从起点A移动到终点B的估算成本。这个通常被称为试探法，有点让人混淆。为什么这么叫呢，因为这是个猜测。直到我们找到了路径我们才会知道真正的距离,因为途中有各种各样的东西(比如墙壁,水等)。最常用到的预估代价有欧拉距离跟曼哈顿距离，为了效率，我们通常使用曼哈顿距离。
  总代价：总代价=当前代价+预估代价
  关于A*算法的更详细讲解，这里有一篇国外的文章。大家可以去看一下，也可以看翻译过的。附上链接：
  A* Pathfinding for Beginners
  
  A*算法详解
  

Day2

相关知识：

• 地图随机生成：
  我们在解决基于A算法的迷宫问题时，需要一个地图类随机生成地图来帮助我们实现A算法，更加直观的感受到A*算法的原理。
  首先我们要创建一个map类，初始化相关参数例如宽度和长度等，并设置地图二维数据信息为0，值为0则表示能移动到该节点。

class Map():def __init__(self, width, height):self.width = widthself.height = heightself.map = [[0 for x in range(self.width)] for y in range(self.height)]

接下来我们要在map类中创建不能通过节点的函数，即创造迷宫中的障碍。这里我们用值为1来表示不能移动到该节点。

    def createBlock(self, block_num):for i in range(block_num):x, y = (randint(0, self.width - 1), randint(0, self.height - 1))self.map[y][x] = 1

最后我们要将地图简单显示出来，值2则表示一条从开始节点到目的节点的路径。并且创建一个可以随机获取移动节点的函数。

	def showMap(self):print("+" * (3 * self.width + 2))for row in self.map:s = '+'for entry in row:s += ' ' + str(entry) + ' 's += '+'print(s)print("+" * (3 * self.width + 2))

	def generatePos(self, rangeX, rangeY):x, y = (randint(rangeX[0], rangeX[1]), randint(rangeY[0], rangeY[1]))while self.map[y][x] == 1:x, y = (randint(rangeX[0], rangeX[1]), randint(rangeY[0], rangeY[1]))return (x , y)

• A*算法介绍：
  1.为了将每一个搜索到并将添加到open列表的节点，都会创建一个下面的节点类，保存有entry的位置信息(x，y)，并计算出预估代价和实际代价和该节点的父节点(pre_entry)

2.从open列表中找出总代价即F值最小的节点
如果open列表为空，则返回none

3.添加临节点。

	# add available adjacent positionsdef addAdjacentPositions(map, location, dest, openlist, closedlist):poslist = getPositions(map, location)for pos in poslist:# if position is already in closedlist, do nothingif isInList(closedlist, pos) is None:findEntry = isInList(openlist, pos)h_cost = calHeuristic(pos, dest)g_cost = location.g_cost + getMoveCost(location, pos)if findEntry is None :# if position is not in openlist, add it to openlistopenlist[pos] = SearchEntry(pos[0], pos[1], g_cost, g_cost+h_cost, location)elif findEntry.g_cost > g_cost:# if position is in openlist and cost is larger than current one,# then update cost and previous positionfindEntry.g_cost = g_costfindEntry.f_cost = g_cost + h_costfindEntry.pre_entry = location

4.获取所有能够移动的节点，这里提供了两种移动方式。
1）允许上，下，左，右4邻域的移动
2）允许上，下,左,右左上，右上,左下,右下8邻域的移动

	def getNewPosition(map, locatioin, offset):x,y = (location.x + offset[0], location.y + offset[1])if x < 0 or x >= map.width or y < 0 or y >= map.height or map.map[y][x] == 1:return Nonereturn (x, y)def getPositions(map, location):# use four ways or eight ways to moveoffsets = [(-1,0), (0, -1), (1, 0), (0, 1)]#offsets = [(-1,0), (0, -1), (1, 0), (0, 1), (-1,-1), (1, -1), (-1, 1), (1, 1)]poslist = []for offset in offsets:pos = getNewPosition(map, location, offset)if pos is not None:			poslist.append(pos)return poslist

5.代码初始化
可以调整地图的长度，宽度和不可移动节点的数目。
可以调整开始节点和目标节点的取值范围。

WIDTH = 10
HEIGHT = 10
BLOCK_NUM = 15
map = Map(WIDTH, HEIGHT)
map.createBlock(BLOCK_NUM)
map.showMap()source = map.generatePos((0,WIDTH//3),(0,HEIGHT//3))
dest = map.generatePos((WIDTH//2,WIDTH-1),(HEIGHT//2,HEIGHT-1))
print("source:", source)
print("dest:", dest)
AStarSearch(map, source, dest)
map.showMap()

代码实现：

from random import randintclass SearchEntry():def __init__(self, x, y, g_cost, f_cost=0, pre_entry=None):self.x = xself.y = y# cost move form start entry to this entryself.g_cost = g_costself.f_cost = f_costself.pre_entry = pre_entrydef getPos(self):return (self.x, self.y)class Map():def __init__(self, width, height):self.width = widthself.height = heightself.map = [[0 for x in range(self.width)] for y in range(self.height)]def createBlock(self, block_num):for i in range(block_num):x, y = (randint(0, self.width - 1), randint(0, self.height - 1))self.map[y][x] = 1def generatePos(self, rangeX, rangeY):x, y = (randint(rangeX[0], rangeX[1]), randint(rangeY[0], rangeY[1]))while self.map[y][x] == 1:x, y = (randint(rangeX[0], rangeX[1]), randint(rangeY[0], rangeY[1]))return (x, y)def showMap(self):print("+" * (3 * self.width + 2))for row in self.map:s = '+'for entry in row:s += ' ' + str(entry) + ' 's += '+'print(s)print("+" * (3 * self.width + 2))def AStarSearch(map, source, dest):def getNewPosition(map, locatioin, offset):x, y = (location.x + offset[0], location.y + offset[1])if x < 0 or x >= map.width or y < 0 or y >= map.height or map.map[y][x] == 1:return Nonereturn (x, y)def getPositions(map, location):# use four ways or eight ways to moveoffsets = [(-1, 0), (0, -1), (1, 0), (0, 1)]# offsets = [(-1,0), (0, -1), (1, 0), (0, 1), (-1,-1), (1, -1), (-1, 1), (1, 1)]poslist = []for offset in offsets:pos = getNewPosition(map, location, offset)if pos is not None:poslist.append(pos)return poslist# imporve the heuristic distance more precisely in futuredef calHeuristic(pos, dest):return abs(dest.x - pos[0]) + abs(dest.y - pos[1])def getMoveCost(location, pos):if location.x != pos[0] and location.y != pos[1]:return 1.4else:return 1# check if the position is in listdef isInList(list, pos):if pos in list:return list[pos]return None# add available adjacent positionsdef addAdjacentPositions(map, location, dest, openlist, closedlist):poslist = getPositions(map, location)for pos in poslist:# if position is already in closedlist, do nothingif isInList(closedlist, pos) is None:findEntry = isInList(openlist, pos)h_cost = calHeuristic(pos, dest)g_cost = location.g_cost + getMoveCost(location, pos)if findEntry is None:# if position is not in openlist, add it to openlistopenlist[pos] = SearchEntry(pos[0], pos[1], g_cost, g_cost + h_cost, location)elif findEntry.g_cost > g_cost:# if position is in openlist and cost is larger than current one,# then update cost and previous positionfindEntry.g_cost = g_costfindEntry.f_cost = g_cost + h_costfindEntry.pre_entry = location# find a least cost position in openlist, return None if openlist is emptydef getFastPosition(openlist):fast = Nonefor entry in openlist.values():if fast is None:fast = entryelif fast.f_cost > entry.f_cost:fast = entryreturn fastopenlist = {}closedlist = {}location = SearchEntry(source[0], source[1], 0.0)dest = SearchEntry(dest[0], dest[1], 0.0)openlist[source] = locationwhile True:location = getFastPosition(openlist)if location is None:# not found valid pathprint("can't find valid path")break;if location.x == dest.x and location.y == dest.y:breakclosedlist[location.getPos()] = locationopenlist.pop(location.getPos())addAdjacentPositions(map, location, dest, openlist, closedlist)# mark the found path at the mapwhile location is not None:map.map[location.y][location.x] = 2location = location.pre_entryWIDTH = 10
HEIGHT = 10
BLOCK_NUM = 15
map = Map(WIDTH, HEIGHT)
map.createBlock(BLOCK_NUM)
map.showMap()source = map.generatePos((0, WIDTH // 3), (0, HEIGHT // 3))
dest = map.generatePos((WIDTH // 2, WIDTH - 1), (HEIGHT // 2, HEIGHT - 1))
print("source:", source)
print("dest:", dest)
AStarSearch(map, source, dest)
map.showMap()

最后：

由衷地感谢社区上各位大佬，看了他们的博客以及相关指导，我学到了很多东西·。
博客制作不易
respect

补充

• 曼哈顿距离
  曼哈顿距离也叫出租车距离，用来标明两个点在标准坐标系上的绝对轴距总和。
  公式如下：
  

只需要把两个点坐标的 x 坐标相减取绝对值，y 坐标相减取绝对值，再加和。

• 欧拉距离
  欧氏距离是人们在解析几何里最常用的一种计算方法，但是计算起来比较复杂，要平方，加和，再开方
  公式如下：
  

这篇关于Project3 基于A*搜索算法迷宫游戏开发的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---