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。

相关文章

VSCode开发中有哪些好用的插件和快捷键

VSCode开发中有哪些好用的插件和快捷键

《VSCode开发中有哪些好用的插件和快捷键》作为全球最受欢迎的编程工具,VSCode的快捷键体系是提升开发效率的核心密码,：本文主要介绍VSCode开发中有哪些好用的插件和快捷键的相关资料,文中... 目录前言1、vscode插件1.1 Live-server1.2 Auto Rename Tag1.3
阅读更多...
Agent开发核心技术解析以及现代Agent架构设计

Agent开发核心技术解析以及现代Agent架构设计

《Agent开发核心技术解析以及现代Agent架构设计》在人工智能领域,Agent并非一个全新的概念,但在大模型时代,它被赋予了全新的生命力,简单来说,Agent是一个能够自主感知环境、理解任务、制定... 目录一、回归本源：到底什么是Agent？二、核心链路拆解：Agent的"大脑"与"四肢"1. 规划模
阅读更多...
Python+wxPython开发一个文件属性比对工具

Python+wxPython开发一个文件属性比对工具

《Python+wxPython开发一个文件属性比对工具》在日常的文件管理工作中,我们经常会遇到同一个文件存在多个版本,或者需要验证备份文件与源文件是否一致,下面我们就来看看如何使用wxPython模... 目录引言项目背景与需求应用场景核心需求运行结果技术选型程序设计界面布局核心功能模块关键代码解析文件大
阅读更多...
C++多线程开发环境配置方法

C++多线程开发环境配置方法

《C++多线程开发环境配置方法》文章详细介绍了如何在Windows上安装MinGW-w64和VSCode,并配置环境变量和编译任务,使用VSCode创建一个C++多线程测试项目,并通过配置tasks.... 目录下载安装 MinGW-w64下载安装VS code创建测试项目配置编译任务创建 tasks.js
阅读更多...
一文详解Python如何开发游戏

一文详解Python如何开发游戏

《一文详解Python如何开发游戏》Python是一种非常流行的编程语言,也可以用来开发游戏模组,：本文主要介绍Python如何开发游戏的相关资料,文中通过代码介绍的非常详细,需要的朋友可以参考下... 目录一、python简介二、Python 开发 2D 游戏的优劣势优势缺点三、Python 开发 3D
阅读更多...
基于Python开发Windows自动更新控制工具

基于Python开发Windows自动更新控制工具

《基于Python开发Windows自动更新控制工具》在当今数字化时代,操作系统更新已成为计算机维护的重要组成部分,本文介绍一款基于Python和PyQt5的Windows自动更新控制工具,有需要的可... 目录设计原理与技术实现系统架构概述数学建模工具界面完整代码实现技术深度分析多层级控制理论服务层控制注
阅读更多...
Java中的分布式系统开发基于 Zookeeper 与 Dubbo 的应用案例解析

Java中的分布式系统开发基于 Zookeeper 与 Dubbo 的应用案例解析

《Java中的分布式系统开发基于Zookeeper与Dubbo的应用案例解析》本文将通过实际案例,带你走进基于Zookeeper与Dubbo的分布式系统开发,本文通过实例代码给大家介绍的非常详... 目录Java 中的分布式系统开发基于 Zookeeper 与 Dubbo 的应用案例一、分布式系统中的挑战二
阅读更多...
基于Go语言开发一个 IP 归属地查询接口工具

基于Go语言开发一个 IP 归属地查询接口工具

《基于Go语言开发一个IP归属地查询接口工具》在日常开发中,IP地址归属地查询是一个常见需求,本文将带大家使用Go语言快速开发一个IP归属地查询接口服务,有需要的小伙伴可以了解下... 目录功能目标技术栈项目结构核心代码（main.go）使用方法扩展功能总结在日常开发中，IP 地址归属地查询是一个常见需求：
阅读更多...
基于 Cursor 开发 Spring Boot 项目详细攻略

基于 Cursor 开发 Spring Boot 项目详细攻略

《基于Cursor开发SpringBoot项目详细攻略》Cursor是集成GPT4、Claude3.5等LLM的VSCode类AI编程工具,支持SpringBoot项目开发全流程,涵盖环境配... 目录cursor是什么？基于 Cursor 开发 Spring Boot 项目完整指南1. 环境准备2. 创建
阅读更多...
SpringBoot 多环境开发实战(从配置、管理与控制)

SpringBoot 多环境开发实战(从配置、管理与控制)

《SpringBoot多环境开发实战(从配置、管理与控制)》本文详解SpringBoot多环境配置,涵盖单文件YAML、多文件模式、MavenProfile分组及激活策略,通过优先级控制灵活切换环境... 目录一、多环境开发基础（单文件 YAML 版）（一）配置原理与优势（二）实操示例二、多环境开发多文件版
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2