使用A *搜索算法解决策略游戏和迷宫中的路径寻找问题外文翻译资料

 2022-10-30 11:03:17

英语原文共 12 页,剩余内容已隐藏,支付完成后下载完整资料


使用A *搜索算法解决策略游戏和迷宫中的路径寻找问题

摘要:

路径搜索算法是用来解决寻找从出发点到目的点并避开障碍物的最短路径的问题。在计算机游戏中的现实人工智能(AI)设计中最大的挑战之一便是代理运动。路径寻找策略通常被用作AI运动系统的核心。在本次工作中,使用A *搜索算法在表示地图或迷宫的图像上找到从出发点到目的点的最短路径。在迷宫中寻找一条路径是一个基本的计算机科学问题,可以采取多种形式。A *算法广泛用于路径寻找和图的遍历。使用不同的地图和迷宫图像来测试系统性能(每个地图和迷宫100个图像)。系统总体性能是可接受的,并且能够找到图像上的两个点之间的最短路径。超过85%的图像可以找到所选择的两个点之间的最短路径。

关键词:

路径搜索、策略游戏、地图、迷宫求解、人工智能、搜索算法、A*

1.介绍

计算机游戏中的路径寻找已经成为多年的研究方向,这是游戏行业中有关游戏人工智能(AI)最流行却十分困难的问题。在商业计算机游戏中路径寻找的问题必须实时地、通常是在有限的存储器和CPU资源下解决[1]。计算工作应该通过使用搜索算法来找到路径。因此,在大型地图上的路径寻找产生了显着的性能瓶颈。

路径寻找可以看作是给出问题“如何从出发点到目的点”的答案。大多数情况下,从出发点(当前点)到目的点(下一个点)的路径可能包括多个不同的解决方案,但如果可能,解决方案需要涵盖以下目的:

1.从源A到目的地B的方法。

2.绕过障碍物的方法。

3.找到最短路径的方法。

4.快速找到路径的方法。

一些路径寻找算法只解决了一部分目的,也有一些路径寻找算法解决了所有这些问题。而在一些情况下,没有算法可以解决这些问题中的任何一个。找到从源到目的地的最短路径的示例在图1中示出。同时关于距离的最短路径并不总是时间上最快的[2]。不同的开销将影响到是从出发点A到目的点B的移动,而不是从出发点A到目的点C的移动。路径寻找算法涉及到寻找从出发点到目的点并避开障碍的最短路径的问题[3]。为了解决寻找最短路径的问题,人们创建了包括A *搜索算法,面包优先搜索算法和深度优先搜索算法等几种搜索算法。

图1.源到目的地的最短寻路。

随着游戏产业重要性的增加,路径寻找已经成为游戏产业中的一个普遍且令人沮丧的问题。例如角色扮演游戏和实时策略游戏等游戏通常具有要求从玩家的当前位置移动到系统预定的或玩家自行确定的目的地的任务[1]。代理运动是计算机游戏现实AI设计中最大的挑战之一。路径寻找策略通常用作AI运动系统的核心。在电子游戏中寻找路径最常见的挑战是巧妙地避开障碍并寻找在所有不同路径中最有益的路径。现代计算机游戏产业每年都在变得越来越大,越来越复杂,这其中也包括游戏地图的大小和游戏中存在的单位数量[2] [4]。

路径寻找的研究对于不同的工作领域都具有重要性,包括物流,游戏编程,操作管理,系统分析和设计,项目管理,网络和生产线。最短路径的研究发展了思维的因果关系的能力,让人工智能拥有类似于人类的学习和思维的能力。

迷宫令人困惑的正是其被求解器发现并选择最有效的路线在最短的时间到达目的地的出发点是不确定的。事实上,迷宫是因为迷津园而广为人知。迷津园只有一条弯曲的路线,没有分支,并且不被设计为难以理解。而在迷宫中,通道和墙是固定的。大多数迷宫求解算法与图形理论关系密切,其中没有回路的迷宫与图理论中的树相似。当迷宫有多个解时,求解器可以找到从出发点到目的点的最短路径[5] [6]。

1.1路径搜索算法

路径寻找是研究如何从出发点到目的点。最短路径问题是计算机科学文献中研究最多的问题之一。给定加权图,问题是在顶点之间的形成的图中查找最小总权重路径。有几种算法开发的变异问题,其中包括定向边与无向边。图形是由多个顶点和连接它们的边组成,而一个标记图具有与每个顶点相关联的一个或多个描述,以将该顶点与图形中的其他顶点区分开。图的搜索分为盲目搜索和启发式搜索[7]。

盲目搜索有时被称为统一搜索,因为它不具有关于其作用域的信息。盲目搜索唯一能够做的是区分非目标状态和目标状态。盲目搜索没有关于接下来应该扩展哪个状态(顶点)的偏好;而启发式搜索则是对发现和开发的算法和规则的研究。启发式搜索是一种经验法则,可以解决给定的问题,但不保证一定可以获得解决方案。启发式是关于某一领域的知识,可以帮助指导相同领域中的搜索和推理[7] [8]。

1.1.1深度优先搜索算法

深度优先搜索算法使用“先进先出”栈,在算法中是递归的。如果必要,这种算法在任何的时候都可以更深入到搜索空间。这种算法的实现很简单,但是其主要问题是需要大的计算能力来小幅增加图形大小[6] [8]。

1.1.2深度有限搜索算法

深度有限搜索算法是一种统一搜索,其工作原理与深度优先搜索算法类似,但通过对搜索深度施加最大限制以避免其在完整性上的缺点。该算法将在深度限制内找到一个解决方案,这保证了所有图形的完整性。

1.1.3广度优先搜索算法

广度优先搜索算法使用“先进先出”队列。该算法一次访问一个顶点。广度优先搜索算法按照它们到源顶点的距离的顺序访问顶点,其中距离为被测量遍历边的数量[6] [8]。

1.1.4最佳搜索算法

最佳优先搜索算法使用两个列表(开放列表和封闭列表)来限制状态,类似于广度优先搜索算法。在每个步骤中,最佳优先搜索根据启发式函数对队列进行排序。该算法简单地选择具有最好启发式值的未访问的顶点来作为下一个访问的顶点。

1.1.5爬山搜索算法

爬山搜索算法扩展了搜索中的当前状态并评估其子顶点。它是一个迭代算法,从问题的任意解决情况开始,然后以递增地方式通过改变其中的单个元素来找到更好的解决方案。如果某次更改产生了更好的解决方案,则对新解决方案进行增量更改,重复操作,直到无法产生更好的解决方案。此算法无法从失败策略中恢复。

1.1.6 Flood-Fill搜索算法

在Flood-Fill搜索算法中,通过整个已知地图的信息来维护其数据结构。这个算法非常简单,但是它需要大量的程序调用,这可能导致递归栈溢出,没有机制来确定访问的像素是否实际上被测试。假设(x,y)是中心像素,则当其四个相邻的水平或垂直相邻像素中的一个或多个被填充时,需要填充(x,y)。在这个方案中对角线像素被认为是不连接的[9]。

2.计算机游戏中人工智能的挑战

在本节中,简要描述了开发用于计算机游戏的AI时出现的主要问题。该列表不包括所有问题,但是给出了实际的电脑游戏向AI社区提出的问题的类型。计算机游戏中的挑战性问题的列表如表1所示。通过这个问题列表可以得出的结论是,不仅游戏可以从更好的AI技术中受益,AI也可以受益于计算机游戏提供的挑战[10]。

表1.电脑游戏人工智能挑战性问题。

问题

描述

1

复杂的决策空间

大多数最先进的计算机游戏涉及复杂的战略(实时战略游戏)或可信行为(互动戏剧),这两种行为共享获得巨大决策空间的特性。

2

创作支持

手工制作的行为最终是一种复杂的编程语言中的软件代码,存在人为错误的风险。

3

意外情况

当然不可能准备所有可能的情况以及可能在游戏过程中遇到的玩家的战略,

4

知识工程

即使假设策略或行为是手工制作的,在游戏中编写这些类型的行为集需要巨大的人力工程的努力。

5

回放能力和变异性

玩家可能会无聊地看到相同的策略和行为一次又一次。

6

夸大的目标

这是可能的,人类工程行为或战略没有完全实现游戏目标。

3.拟议方法

路径寻找需要大量的资源,特别是在运动密集型游戏中。为此,需要一种有效且廉价的方法。在这项工作中,使用来自战略游戏的图像表示地图和迷宫解决图像。A *算法广泛用于路径寻找和图遍历。该算法将用于找到图像上两点之间的最短路径。所提出的方法如图2所示。

图2.拟议的方法

3.1 图像采集

这里使用来自策略游戏的图片。地图将转换为三种主要颜色(红色,绿色和蓝色)。有三个元素可以在地图上移动(第一个元素只能在代表水的蓝色区域移动,第二个元素只能在代表地面的绿色区域移动,第三个元素可以移动到地图上的任意位置代表两栖)。迷宫解决也用于这项工作,白色区域表示可步行空间,而黑色区域表示不可行走空间。随着计算机的发展,迷宫解算算法变得自动化,但是解决迷宫的执行时间仍然随着迷宫尺寸和复杂性而不利地缩放。输入图像如图3所示。

图3.原始输入图像。

3.2 A *搜索算法

A *是一个通用搜索算法,可用于找到某些问题的解决方案,寻找路径是其中之一。该算法汇集了等价搜索和启发式搜索的特征。对于路径寻找,A *算法一次又一次地检查其提供的未被探索的位置。当被检查的位置是目标时,完成A *算法。在任何其他情况下,它有助于记录所有的位置的邻居以进行额外的探索[7]。 A *可能是游戏AI中最流行的路径寻找算法。该算法的时间复杂度取决于使用的启发式搜索[8]。

3.2.1 A *如何工作

游戏地图需要在A *算法可以工作之前准备好或完成预处理。游戏环境将作为图形使用[3],这会将地图分成不同的点或位置,通常称为顶点。这些顶点用于记录搜索的进度。除了保持地图位置,每个顶点还有三个其他属性,分别是fitness,goal和heuristic通常称为f,g和h [8]。g,h和f的用处是量化到达当前顶点的路径。属性g,h和f的描述见表2。不同的值将被分配给顶点之间的路径。通常,这些值将表示顶点之间的距离。顶点之间的成本不必是距离。如果你想找到需要最短时间来遍历的路径,那么成本可以是时间。A *使用两个列表(打开列表和关闭列表)。打开列表包含地图中尚未探索的所有顶点。封闭列表包含已被探索的所有顶点。除了标准的打开/关闭列表,标记数组可以用来确定某顶点是在打开列表还是关闭列表[7] [11]。

表2.属性描述。

属性

描述

1

g

表示从源顶点到目标顶点的获取成本(源和目标之间路径中所有值的总和)

2

h

表示从源顶点到目的地顶点的估计成本

3

f

表示g和h的总和,是通过源顶点的路径的成本的最佳估计(f = g h)

3.2.2。 A *算法

1.P是源顶点。

2.将g,h和f值分配给P.

3.将源顶点添加到打开列表中。

4.重复以下步骤:

A.查找打开列表上具有最低f的顶点。将此顶点称为当前顶点。

B.将其切换到关闭列表。

C.对于来自当前顶点的每个可达顶点

a)如果它在关闭列表上,忽略。

b)如果它不在打开的列表上,将其添加到打开列表。使当前顶点成为此顶点的父顶点。记录此顶点的g,h和f值。

c)如果它已经在打开的列表上,检查看这是否是一个更好的路径。如果是,将其父级更改为当前顶点,并重新计算g和f值。

D.结束时

a)将目标顶点添加到关闭列表。

b)找不到目标顶点,打开列表为空。

5.从目的地顶点向源顶点向后跟踪,得到路径。

4.实验结果

使用装有12.0GB RAM的Intel(R)Core TM i7-5500U CPU 2.40GHz的笔记本电脑进行分析。使用编程语言Visual Basic构建应用程序。图形用户界面(GUI)构建为使系统更容易使用并加快用户的工作。

主界面显示图像(地图或迷宫)和可用于实现所选图像上的路径寻找操作的主要

剩余内容已隐藏,支付完成后下载完整资料


资料编号:[138316],资料为PDF文档或Word文档,PDF文档可免费转换为Word

原文和译文剩余内容已隐藏,您需要先支付 30元 才能查看原文和译文全部内容!立即支付

以上是毕业论文外文翻译,课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。