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

2024-03-09 06:38
文章标签 开发 游戏 搜索算法 迷宫 project3

本文主要是介绍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 坐标相减取绝对值，再加和。

  • 欧拉距离
    欧氏距离是人们在解析几何里最常用的一种计算方法，但是计算起来比较复杂，要平方，加和，再开方
    公式如下：
    x1,x2,y1,y2分别为两个点的坐标

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


http://www.chinasem.cn/article/789817。

相关文章

这15个Vue指令，让你的项目开发爽到爆

这15个Vue指令，让你的项目开发爽到爆

1. V-Hotkey 仓库地址: github.com/Dafrok/v-ho… Demo: 戳这里 https://dafrok.github.io/v-hotkey 安装: npm install --save v-hotkey 这个指令可以给组件绑定一个或多个快捷键。你想要通过按下 Escape 键后隐藏某个组件，按住 Control 和回车键再显示它吗？小菜一碟： <template
阅读更多...
Hadoop企业开发案例调优场景

Hadoop企业开发案例调优场景

需求 （1）需求：从1G数据中，统计每个单词出现次数。服务器3台，每台配置4G内存，4核CPU，4线程。 （2）需求分析： 1G / 128m = 8个MapTask；1个ReduceTask；1个mrAppMaster 平均每个节点运行10个 / 3台 ≈ 3个任务（4    3    3） HDFS参数调优 （1）修改：hadoop-env.sh export HDFS_NAMENOD
阅读更多...
嵌入式QT开发：构建高效智能的嵌入式系统

嵌入式QT开发：构建高效智能的嵌入式系统

摘要： 本文深入探讨了嵌入式 QT 相关的各个方面。从 QT 框架的基础架构和核心概念出发，详细阐述了其在嵌入式环境中的优势与特点。文中分析了嵌入式 QT 的开发环境搭建过程，包括交叉编译工具链的配置等关键步骤。进一步探讨了嵌入式 QT 的界面设计与开发，涵盖了从基本控件的使用到复杂界面布局的构建。同时也深入研究了信号与槽机制在嵌入式系统中的应用，以及嵌入式 QT 与硬件设备的交互，包括输入输出设
阅读更多...
OpenHarmony鸿蒙开发（ Beta5.0）无感配网详解

OpenHarmony鸿蒙开发（ Beta5.0）无感配网详解

1、简介 无感配网是指在设备联网过程中无需输入热点相关账号信息，即可快速实现设备配网，是一种兼顾高效性、可靠性和安全性的配网方式。 2、配网原理 2.1 通信原理 手机和智能设备之间的信息传递，利用特有的NAN协议实现。利用手机和智能设备之间的WiFi 感知订阅、发布能力，实现了数字管家应用和设备之间的发现。在完成设备间的认证和响应后，即可发送相关配网数据。同时还支持与常规Sof
阅读更多...
活用c4d官方开发文档查询代码

活用c4d官方开发文档查询代码

当你问AI助手比如豆包，如何用python禁止掉xpresso标签时候，它会提示到 这时候要用到两个东西。https://developers.maxon.net/论坛搜索和开发文档 比如这里我就在官方找到正确的id描述 然后我就把参数标签换过来
阅读更多...
Linux_kernel驱动开发11

Linux_kernel驱动开发11

一、改回nfs方式挂载根文件系统         在产品将要上线之前，需要制作不同类型格式的根文件系统         在产品研发阶段，我们还是需要使用nfs的方式挂载根文件系统         优点：可以直接在上位机中修改文件系统内容，延长EMMC的寿命         【1】重启上位机nfs服务         sudo service nfs-kernel-server resta
阅读更多...
【区块链 + 人才服务】区块链集成开发平台 | FISCO BCOS应用案例

【区块链 + 人才服务】区块链集成开发平台 | FISCO BCOS应用案例

随着区块链技术的快速发展，越来越多的企业开始将其应用于实际业务中。然而，区块链技术的专业性使得其集成开发成为一项挑战。针对此，广东中创智慧科技有限公司基于国产开源联盟链 FISCO BCOS 推出了区块链集成开发平台。该平台基于区块链技术，提供一套全面的区块链开发工具和开发环境，支持开发者快速开发和部署区块链应用。此外，该平台还可以提供一套全面的区块链开发教程和文档，帮助开发者快速上手区块链开发。
阅读更多...
Vue3项目开发——新闻发布管理系统（六）

Vue3项目开发——新闻发布管理系统（六）

文章目录 八、首页设计开发1、页面设计2、登录访问拦截实现3、用户基本信息显示①封装用户基本信息获取接口②用户基本信息存储③用户基本信息调用④用户基本信息动态渲染 4、退出功能实现①注册点击事件②添加退出功能③数据清理 5、代码下载 八、首页设计开发 登录成功后，系统就进入了首页。接下来，也就进行首页的开发了。 1、页面设计 系统页面主要分为三部分，左侧为系统的菜单栏，右侧
阅读更多...
v0.dev快速开发

v0.dev快速开发

探索v0.dev：次世代开发者之利器 今之技艺日新月异，开发者之工具亦随之进步不辍。v0.dev者，新兴之开发者利器也，迅速引起众多开发者之瞩目。本文将引汝探究v0.dev之基本功能与优势，助汝速速上手，提升开发之效率。 何谓v0.dev？ v0.dev者，现代化之开发者工具也，旨在简化并加速软件开发之过程。其集多种功能于一体，助开发者高效编写、测试及部署代码。无论汝为前端开发者、后端开发者
阅读更多...
国产游戏崛起：技术革新与文化自信的双重推动

国产游戏崛起：技术革新与文化自信的双重推动

近年来，国产游戏行业发展迅猛，技术水平和作品质量均得到了显著提升。特别是以《黑神话：悟空》为代表的一系列优秀作品，成功打破了过去中国游戏市场以手游和网游为主的局限，向全球玩家展示了中国在单机游戏领域的实力与潜力。随着中国开发者在画面渲染、物理引擎、AI 技术和服务器架构等方面取得了显著进展，国产游戏正逐步赢得国际市场的认可。然而，面对全球游戏行业的激烈竞争，国产游戏技术依然面临诸多挑战，未来的
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2