`

A*分层寻路

阅读更多

在家上网赚钱更容易

作者:Patrick Lester 2003年1月9日更新
译者:Panic 2005年7月21日
译者序:很久没有翻译文章了,这次找了这个短一些的。这个文章是偶以前翻译的《A*寻路初探》的补充,介绍了A*更进一步的,更实用的方法。

原文链接:http://www.policyalmanac.org/games/twoTiered.htm
以下是翻译正文:

 

在我的主题A* Pathfinding for Beginners中(译者注:译文 A*寻路初探)中,我概述了A*算法,说明了如何创建一个通用的寻路功能。然而仅创建一个寻路功能,用途是很有限的。
考虑如下的RPG场景,一个剑士想找到绕过旁边墙壁的路:

对于这类地图,你可以用不同的方式,密度来放置节点。在这个例子中,我们使用高密度网格,如下:

在这个图中,白色节点是可通过的。没有节点的地方是不可通过的。这个例子还有一些不同的地方。在这个例子中,你可以“穿越”不可通过区域的拐角。同时,“方格”也不再是方格。因为这是一个投影视角的例子,我们在Y(垂直方向)拥有X(水平方向)两倍的节点。这使得正确的投影路径成为可能。

如你所见,用这么密集的节点网络,我们不仅能寻路绕过旁边的墙壁,还能在墙壁和旁边的桶之间找到路径。我们密集的网格也使得绕过底部不可通过的火把成为可能。这总的说来是精确寻路。

好,在短距离上,那的确很酷,但是如果我们要穿越整个地图进行寻路,该怎么办?使用像这么密的网格,轻易就会让你在一条路径上使用A*的搜索节点的数量达到10,000+。这几乎会让任何PC失去响应。

那么我们来看另一种选择。创建一个低密度的网格,就像下面这样,如何?

在这个例子里,节点在等边菱形的中心。菱形之间通过性的数据沿边界存储在同一个数组中,在图片上用小红点表示。要从一个图素移动到它周围8个图素上,相邻的图素必须是可通过的,并且路径没有被挡住。

这个节点网格的密度是先前的72分之一。原来我们需要面对10,000+的节点,而现在,取而代之的是1/72原来的数量,或者说,少于200个。我们的电脑可以轻易处理这个。穿越地图寻路的问题迎刃而解。

合而为一

那么,我们用哪种方法呢?两者!

在给定的搜索中,你得先在地图范围内,用宏观寻路的方法。然后切换到微观寻路,寻找从当前位置到路径上两个宏观节点以外的路径。每次你进入一个宏观菱形“方格”,你应该用微观寻路算法寻路到两个宏观节点之前。这导致浪费了每次微观寻路的后半截路径,但是你有必要这样做以便路径看起来足够好-并且这也不是很严重的浪费,因为你的微观寻路算法只计算了相关的一小段路径。一旦你到达了距离目标2-3宏观节点的地方,你应该完全切换到微观寻路算法,完成到最终位置的寻路。

用这种方法,你将得到更接近现实的快速穿越地图的寻路以及能穿越角落,木桶等等就像最开始那个微观寻路例子的效果。有够酷,哈!

如果你 真的 有野心,你可以开发3种寻路器,如果你的地图实在太大,一个工作在真正的宏观层次,一个在中间层,一个在微观层。专家已经为像帝国时代(Age of Empires)这样的游戏设计了这些。这仅仅取决于你的需要。

好,就这些了。像以前一样,你可以通过这个联系我:

现在,祝你好运。

在家上网赚钱更容易

分享到:
评论

相关推荐

    A*寻路算法《一》

    此外,对于大规模图,可以采用分层寻路或者区域分解的方法来降低计算复杂度。 6. **AStar_demo_1.mp4**:这个视频文件可能包含了一个A*寻路算法的演示示例,通过动画直观地展示了算法的运行过程,帮助理解每个步骤...

    基于A*算法的游戏地图寻路实现及性能比较 (2011年)

    在A*算法描述的基础上,给出了基于分层寻路思想的A*算法优化方法及划分游戏地图的6种方式.针对26×20=520个节点的游戏地图,利用栅格法按8方向连接对游戏地图进行了划分,分别采用Dijkstra算法、双向宽度优先搜索算法、...

    人工智能寻路算法在电子游戏中的研究和应用.doc

    在电子游戏设计与开发中,人工智能寻路算法扮演着至关重要的角色。...A*算法及其优化策略,如二叉堆和分层寻路,都是确保游戏AI性能的关键技术,它们共同推动着电子游戏领域的发展,让游戏世界变得更加生动、智能。

    A* Pathfinding Project v4.2.18

    添加了有关从 Unity 的寻路迁移到此包的教程:从 Unity 导航迁移。 添加了有关如何处理大世界中寻路的教程:大世界。 分层网格图上的最近节点查询现在明显更快。 网格图上线播的性能提高了大约 2 倍。 提高了...

    matlab实现AStar和 HybridAStar算法.zip

    Hybrid A*引入了一些策略,如节点剪枝、动态调整启发式函数、分层搜索等,目的是在保持A*算法效率的同时,进一步减少搜索空间,提高性能。例如,它可能在某些情况下采用更简单的启发式函数或者利用局部搜索来优化...

    一种基于A*算法的分层路径规划在3D游戏中的应用研究

    提出了一种分层的解决方案,首先通过建立导航网格划分状态空间;接着使用引入地形估价因子的 算法进行网格寻路,并通过拐角点法生成路径,同时对 算法的OPEN表进行了二叉堆的优化;最后介绍了基于射线透射的局部 ...

    3D游戏中常用算法 如碰撞检测 A* 四叉树 BSP分割树 地形LOD等等

    2. **A*寻路算法**:A* 是一种广泛应用的路径搜索算法,用于在图形化网格或图中找到两点间的最短路径。它基于启发式函数,结合了Dijkstra算法的全局最优性和BFS(广度优先搜索)的高效性。 3. **四叉树**:四叉树是...

    Astar_AStar_A算法_航路_航迹规划_航路规划.zip

    - 游戏AI:游戏中的角色移动、敌人寻路等,常采用A* 来计算最佳移动路径。 - 物流配送:在物流路线规划中,A* 可以帮助计算出最高效的配送路径。 6. **A* 算法的局限性** - 对启发式函数的要求较高,如果估计...

    区域化环境中机器人导航的高效细到粗寻路策略

    通过设计区域化空间知识模型(RSK-Model)和基于区域的寻路算法,即精细到粗略A *(FTC-A *)搜索算法,为区域化环境中的机器人导航提出了一种有效的寻路策略。 。 首先,提出了一种模拟人脑环境表示形式的RSK模型来...

    游戏编程中的核心技术和算法

    - **树与图**:构建复杂的游戏世界和寻路算法。 #### 设计模式 - **单例模式**:确保一个类只有一个实例,并提供全局访问点。 - **工厂模式**:创建对象的过程抽象化。 - **观察者模式**:定义对象之间的依赖关系,...

    C++经典编程题、、、、

    1. **分层计数:**根据小正方形的不同大小,分层进行计数。 2. **面积计算:**根据每个大小的小正方形数量计算总面积。 3. **结果输出:**输出小正方形总数及总面积。 #### 题目11:素数判定与排列组合 **知识点...

    GIS最短路径算法初探

    本文将深入探讨GIS领域的最短路径算法,重点分析静态最短路径算法与动态最短路径算法,并对比Dijkstra算法、A*算法、D*算法等典型寻路算法的特点及适用条件。 ### 静态最短路径算法 #### Dijkstra算法 Dijkstra...

    僵尸射击游戏源码

    2. **角色与敌人AI**:僵尸作为敌人,其行为模式和动作可能由简单的状态机或者更复杂的AI算法控制,如寻路算法(A*寻路)和反应系统。 3. **射击系统**:玩家射击的实现涉及子弹发射、轨迹计算、碰撞检测以及伤害计算...

    Routing_engine:越野导航系统

    越野导航系统在线可见度图算法无需图形预计算的A *寻路动态边缘权重庞大的远足和乡村道路数据库大面积超快速寻路O(h)能见度多边形计算(h-障碍物数量) 图构建的分层方法OSM映射数据最小化存储和预先计算的数据...

    毕业设计项目:校园导航系统 QT界面+TSP(模拟退火)+A star寻路+最少换乘+单车调度(最小费用最大流)等.zip

    所以在分层思想中,我们所调用的函数也是这样的,上层可以调用下层和同一层的函数,下层函数不可以调用上层函数,否则程序的层次性会被打破,导致结构错综复杂,难以维护和管理。 那么怎样才能做到向上管理呢,有...

    c_Language_Games_Example.rar_games

    8. **算法与数据结构**:游戏开发中可能涉及多种算法,如搜索算法(A*寻路)、图形渲染算法(BSP树分层)以及优化算法(快速排序)。同时,理解如队列、栈和图等数据结构也是必要的。 9. **内存管理**:C语言要求...

    游戏模版

    4. **数据结构与算法**:游戏中会用到各种数据结构(如队列、栈、图、树等)和算法(如A*寻路、四叉树碰撞检测等),以优化性能和实现复杂逻辑。 5. **图形编程**:包括3D建模、纹理映射、光照模型、着色器等,用于...

    区域环境中机器人导航的一种有效的从粗到粗寻路策略

    为了实现这一目标,研究者们提出了区域化空间知识模型(RSK模型)和基于区域的寻路算法,即细到粗的A*(FTC-A*)搜索算法。RSK模型模仿人类大脑中环境的表征,将被划分成区域的环境表示成一种分层嵌套的结构。在这种...

    自动驾驶算法的一些demo.zip

    这些任务依赖于复杂的算法,如A*寻路算法、模型预测控制(MPC)以及基于规则和学习的决策系统。 5. **控制算法**:将决策结果转化为实际的车辆运动,需要控制器设计。PID控制器、模型预测控制等经典控制理论常用于...

    cocos2d-x 地图行走

    总结,cocos2d-x提供了强大的地图系统和行走逻辑支持,结合Tiled Map、A*寻路算法、碰撞检测以及脚本接口,开发者可以轻松构建出富有交互性的2D游戏世界。通过深入理解和实践,你将能创造出更多引人入胜的游戏体验。

Global site tag (gtag.js) - Google Analytics