没有合适的资源?快使用搜索试试~ 我知道了~
首页A*算法入门:人工智能寻路基础
A*算法入门:人工智能寻路基础
需积分: 9 4 下载量 73 浏览量
更新于2024-07-24
收藏 328KB DOC 举报
本文主要介绍了游戏算法中的经典A*寻路算法,这是一个在人工智能领域广泛应用的优化搜索方法,尤其在游戏路径规划、地图探索等方面具有显著优势。作者提到,尽管对A*算法早有耳闻,但之前并未深入研究,这次决定从基础做起,通过阅读一篇广为人知的文章来学习和理解这个算法。 A*算法的核心原理是结合了启发式函数和最佳优先搜索策略。它通过估测从当前节点到目标节点的“最短”路径,即实际代价加上预估代价,来指导搜索过程。实际代价通常是指从起点到当前节点的实际步数,而预估代价是基于某种启发式函数估计的从当前节点到目标节点的最低代价。通过这种方式,算法能够在众多可能路径中找到一条相对最优的解。 文章指出,A*算法并非一开始就全面阐述,而是逐步深入,适合初学者循序渐进地学习。它首先引导读者理解搜索区域的网格化处理,将复杂问题简化为二维数组,便于管理和计算。搜索过程中,节点(方块)被标记为可达或不可达,路径是通过这些节点的集合表示。算法寻找从起点到终点的最短路径,允许路径在非方格形状的区域中灵活延伸。 作者强调,虽然文章没有提供详细的编程实现,但它为后续的学习提供了清晰的理论框架,鼓励读者根据自己的需求选择不同的编程语言进行实践,比如文中提供了C++和Blitz Basic的示例代码。此外,文档还包括了可执行文件,方便直接观察算法的运行效果。 这篇关于A*寻路算法的文章通过直观的示例和易于理解的语言,让读者逐渐掌握了这一关键的AI技术,是游戏开发者和人工智能初学者入门的理想教程。
资源详情
资源推荐
%%!#,把起始格添加到开启列表。
%%!,重复如下的工作:
%%%%%a) 寻找开启列表中 F 值最低的格子。我们称它为当前格。
b) 把它切换到关闭列表。
c) 对相邻的 8 格中的每一个?
* 如果它不可通过或者已经在关闭列表中,略过它。反之如下。
* 如果它不在开启列表中,把它添加进去。把当前格作为这一格的父节点。记录这一格的 F,G,和
H 值。
* 如果它已经在开启列表中,用 G 值为参考检查新的路径是否更好。更低的 G 值意味着更好的路
径。如果是这样,就把这一格的父节点改成当前格,并且重新计算这一格的 G 和 F 值。如果你保持你的
开启列表按 F 值排序,改变之后你可能需要重新对开启列表排序。
d) 停止,当你
* 把目标格添加进了开启列表,这时候路径被找到,或者
* 没有找到目标格,开启列表已经空了。这时候,路径不存在。
%%!保存路径。从目标格开始,沿着每一格的父节点移动直到回到起始格。这就是你的路径。
题外话
离题一下,见谅,值得一提的是,当你在网上或者相关论坛看到关于 的不同的探讨,你有时会看
到一些被当作 算法的代码而实际上他们不是。要使用 ,你 必须包含上面讨论的所有元素--特定
的开启和关闭列表,用 &+' 和 ) 作路径评价。有很多其他的寻路算法,但他们并不是 A*,A*被认为是
他们当中最好的。 1!23 在这篇文章后面的参考文档中论述了一部分,包括他们的一些优点和缺
点。有时候特定的场合其他算法会更好,但你必须很明确你在作什么。好了,够多 的了。回到文章。
实现的注解
现在你已经明白了基本原理,写你的程序的时候还得考虑一些额外的东西。下面这些材料中的一些引用
了我用 和 ! 写的程序,但对其他语言写的代码同样有效。
#, 维护开启列表:这是 A*寻路算法最重要的组成部分。每次你访问开启列表,你都需要寻找 & 值最低
的方格。有几种不同的方法实现这一点。你可以把路径元素随意 保存,当需要寻找 & 值最低的元素的时
候,遍历开启列表。这很简单,但是太慢了,尤其是对长路径来说。这可以通过维护一格排好序的列表
来改善,每次寻找 & 值 最低的方格只需要选取列表的首元素。当我自己实现的时候,这种方法是我的首
选。
在小地图。这种方法工作的很好,但它并不是最快的解决方 案。更苛求速度的 程序员使用叫做
“41!5的方法,这也是我在代码中使用的方法。凭我的经验,这种方法在大多数场合会快 ~
倍,并且在长路经上速度呈几何级数提升# 倍以上速度。 如果你想了解更多关于 41! 的内
容,查阅我的文章,6!1!)!!!78。
, 其他单位:如果你恰好看了我的例子代码,你会发现它完全忽略了其他单位。我的寻路者事实上可
以相互穿越。取决于具体的游戏,这也许可以,也许不行。如果你 打算考虑其他单位,希望他们能互相
绕过,我建议在寻路算法中忽略其他单位,写一些新的代码作碰撞检测。当碰撞发生,你可以生成一条
新路径或者使用一些标准 的移动规则比如总是向右,等等直到路上没有了障碍,然后再生成新路径。
为什么在最初的路径计算中不考虑其他单位呢?那是因为其他单位会移动,当你到达 他们原来的位置的
时候,他们可能已经离开了。这有可能会导致奇怪的结果,一个单位突然转向,躲避一个已经不在那里
剩余22页未读,继续阅读
噬灬魂
- 粉丝: 0
- 资源: 1
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 计算机人脸表情动画技术发展综述
- 关系数据库的关键字搜索技术综述:模型、架构与未来趋势
- 迭代自适应逆滤波在语音情感识别中的应用
- 概念知识树在旅游领域智能分析中的应用
- 构建is-a层次与OWL本体集成:理论与算法
- 基于语义元的相似度计算方法研究:改进与有效性验证
- 网格梯度多密度聚类算法:去噪与高效聚类
- 网格服务工作流动态调度算法PGSWA研究
- 突发事件连锁反应网络模型与应急预警分析
- BA网络上的病毒营销与网站推广仿真研究
- 离散HSMM故障预测模型:有效提升系统状态预测
- 煤矿安全评价:信息融合与可拓理论的应用
- 多维度Petri网工作流模型MD_WFN:统一建模与应用研究
- 面向过程追踪的知识安全描述方法
- 基于收益的软件过程资源调度优化策略
- 多核环境下基于数据流Java的Web服务器优化实现提升性能
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功