即时战略游戏中实用的寻路算法都有哪些，比较如何？【funs放肆游戏吧】_百度贴吧
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&签到排名：今日本吧第个签到，本吧因你更精彩，明天继续来努力！
本吧签到人数：0可签7级以上的吧50个
本月漏签0次！成为超级会员，赠送8张补签卡连续签到：天&&累计签到：天超级会员单次开通12个月以上，赠送连续签到卡3张
关注：7贴子：
即时战略游戏中实用的寻路算法都有哪些，比较如何？
rts中的寻路系统一般需要满足有以下几个条件，1. 效率高，因为rts普遍地图大，单位多，所以处理效率很重要2. 易编辑，以便于level design3. 效果真实，如能找出最优（或者是看上去合理）4. 可以应对动态的游戏世界，例如起建筑如
所说，一般用于寻路的算法是A Star，首先是A Star有利用到启发式函数（Heuristic Function）[1]，和另一个算法Dijkstra（A Star的无启发函数版）相比可能会更有效率，因为启发函数设计得当，可以大大减少计算的数量。因为启发函数的估计往往不是精确的，所以A Star [删：不像Dijkstra，] 不一定能找出人类人之上的最优解，但是对于游戏来说，看上去合理就行。然而用A Star作为寻路算法，仅仅是寻路系统的基本部分。作为系统，它需要有易编辑的特性。这就涉及到A Star中每个节点（Node）的表现方式。最基本的表现方式是方块（Tile），如下图 [2]其中，可以将山洞所占的的几个方块设为“Not Movable”，这样A Star就会不会考虑到这几个方块，系统所生成的路径就不会碰到山洞。用方块作为A Star节点优点是简单，不过也有比较多的问题，第一是，如果地图很大的话，方块就会很多，这样A Star的节点就会大大增加，处理的时间相应地会增大。第二是，单位的移动只能是上下左右，最多加上斜行，总共八个方向，不够真实第三是，单位的体积大小不一样的话，大单位的图像可能会覆盖到“Not Movable”部分。以上面的图片为例，一条路径会经过在山洞边边，一个占四个方块大小的巨人走过的话，就会走在山洞上面。为了解决上面的一些问题，我们可以使用路经点（Waypoint）来做A Star节点，如下图 [3]图中的红色的路径点代替了方块，成为A Star节点，这样的好处是我们可以自由地添加路径点，可以相对地减少A Star节点数目，同时也单位也可以按照设计师设计的方法去走。然而，从上图也可以看出它的问题不少，第一是，如果是大地图，路径点数量太少会显得生硬。第二是，需要考虑得面面俱到，不然一条直路忘了加路径点，单位就会“绕”（看上去）过去。为了更好地解决以上所述的问题，导航网格（Navmesh or Navigation Mesh）出现了，如下图所示 [4]现在，灰白色的多边形成为了A Star节点。它解决了上面所出现的所有问题，第一，从图中可以看出，节点的数目大大减少，因为多边形可以覆盖任意区域，不用限制成方块或点。除了提升计算速度之外，编辑导航网格的效率也大大增加。第二，通过计算直线两点和导航网格的相邻点（上图蓝色点）的位置关系，可以计算出两点是不是可以直接行走而没有阻碍物。例如上图从A点到B点通过计算可以得出可以直线行走，不用想方块和导航点那样绕来绕去。第三，在转角位不一定要经过相邻点，可以加上单位的体积半径，这样不同体积的单位都可以合理地通过转角。对于建筑的考虑在RTS中的寻路系统，还有一个很重要的话题，就是要可以应对动态的游戏世界。一个简单的例子就是起建筑。在一些需要频繁修改游戏世界的场景中，以方块为节点会更加容易作出修改 [14] ——只需要将建筑所占的方块的“Not Movable”修改成“Movable”。例如著名的塔防游戏《Field Runner》，应该是利用这种方法来实现的，而且作为塔防，《Field Runner》可以只在建塔之后寻路一次，缓存起来就行。所以在这一场景中方块又成为了一个方便快捷的选择。然而，导航网格也是可以动态修改的，不过开发难度会更大，而且运行中动态修改可能会造成延迟。有一些方法可以优化，例如动态地修改局部导航网格 [12]，或者是完全不修改，而将建筑看作局部的障碍物用另一套机制来应对 [13]。其实除了A Star算法之外，还有其他算法，或者技巧，可以用于RTS的寻路系统，这里简单地介绍一下，例如Potential Field，它是将地图用一个矩阵来表示，矩阵储存着大小不同的电势（整数）。例如，正电势表示吸引，负电势表示排斥。而游戏中的单位本身是一个负电势，游戏以一个数组储存所有单位的电势和位置 [7]。这样，在计算一个单位需要怎么从A点到B点时，我们可以用一个新的矩阵将目的地B点设成正电势，并以不同方式（如圆形、四边形等）辐射开来，离B点越远电势越低，直到0。然后将地图矩阵，目的地矩阵，和所有单位数组的电势相加，得出一个新的、反映当前游戏世界的电势矩阵，然后单位再选择周围所有电势点中的最高电势点去走。不过这里坑很多，因为它本质上是Greedy Algorithm，所以它未必能找出解。[5]然而在某些设定中，例如在没有过于复杂地形，并且需要单位自动不相互覆盖的情况下，Potential Field还是可以完成任务 [8]。因为相比A Star的寻路系统来说，这个方法会比较简单。还有Flocking Behavior，在对于一大群单位的寻路，计算量是很大的，而且往往会有很多的重复，这些都是可以避免的。如果单位的移动是利用Steering Behavior [9] 来实现的话，那么就可以为其中一个单位，称之为Leader，计算路径（例如用导航网格），然后其他单位按照以下Flocking原则来移动：1. 分离，避开相邻单位2. 一致，和整体的移动方向一致，这里应该是Leader的移动方向3. 聚合，向整体的平均位置靠拢这样的话，就可以降低寻路的计算量，并且得到更加真实的群体单位行进效果。另外一个技巧和Flocking Behavior类似 [10]，对于不用Steering Behavior的一大群单位，可以将他们设为一个组，计算这个组的路径（并且要考虑到这个组的半径以便通过转角位），然后给每个单位offset一个适当的距离，如果遇到小的通道，例如门，可以适当调整offset。《全面战争》里面一个队伍40人，大概用的就是这种方法 [11]。还有一个优化技巧是Chunk [15]。这个技巧和 @王亚晖 所提到的“先切分地图然后分块去做”应该是一致的。在规模宏大的地图中，为了进一步提高寻路速度，可以在编辑地图时将一些节点处理成一个Chunk，它有入口和出口，并且不同Chunk之间需要连接起来。从A点移动到B点，首先先在Chunk之间做寻路，得到一系列的Chunk，在Chunk 1的时候只需要在Chunk 1中寻路，去到Chunk 2的时候就只在Chunk 2中寻路。它本质上是将地图分为两种维度，一种是粗略的Chunk，一种是Chunk里面的节点（可以是方块，路径点，导航网格），并分开进行处理。有种空间分割（Space Partition）的味道在里面。这个方法我没有真正用过，还望大家补充。还有D Star，它主要运用在机器人领域 [6]，可以在未知环境中寻路，不过我没接触过。--------------Update 1----------------1. 增加了Potential Field的简单说明2. 增加了常用的启发函数例子3. 完善了A Star说明，指出它不一定能找出最优解--------------Update 2----------------1. 增加了Flocking Behavior在大群单位寻路的应用2. 增加了Flocking Behavior的替代技巧--------------Update 3----------------1. 增加了对于动态地修改游戏世界的考虑（如建筑）--------------Update 4----------------1. 增加了Chunk 优化技巧--------------Update 5----------------1. 在
的帮助下，发现A Star和最优解的一个错误，已更正。A Star的启发函数在单调的情况下是可以找出最优解的，但是这个最优解未必符合人类认知上的最优解，因为启发函数未必准确。注释和资料来源：[1] 启发式函数 Heuristic Function：估计路径所需的资源花费的函数，资源可以是“时间”，“体力”等等。对于精度要求不高的游戏来说，常用的启发函数是估算曼哈顿距离。[2] 图片来源： Implementing Auto-tiling Functionality in a Tile Map Editor[3] 图片来源：（这篇博客也有讲述寻路的概念，是一个不错的学习资源）[4] 图片来源：Game/AI: Fixing Pathfinding Once and For All （这篇博客更加全面地讲述各种寻路系统的节点代表方式，值得一看）[5] 推荐参考：Using Potential Fields in a Real-time Strategy Game Scenario (Tutorial)[6] 参考来源：[7] 单位可以移动，所以以数组来储存会比较方便，不用频繁更新矩阵。[8] 一个成功的例子：n-created[9] Steering Behavior，将一个单位考虑成一个受力点，通过增加不同的力，如吸引的，排斥的等等，实现如搜索、逃跑、躲避障碍和Flocking等行为。[10] [11] 资料来源：Flanking Total War’s AI: 11 Tricks to Conquer for Your Game[12] 动态地修改局部导航网格：Dynamic Navigation Mesh[13] RV Obstacles：[14] 资料来源：A* Pathfinding Project[15] 资料来源：RTS寻路系统概要 中orange030的补充
贴吧热议榜
使用签名档&&
保存至快速回贴求霸气好听的小组名字。我们是干部培训第八组。有个第四组叫fun4（放肆）。要类似于这种的_百度知道
求霸气好听的小组名字。我们是干部培训第八组。有个第四组叫fun4（放肆）。要类似于这种的
求霸气好听的小组名字。我们是干部培训第八组。有个第四组叫fun4（放肆），类似于这种的。。。
我有更好的答案
八 dao （横行霸道）
为您推荐：
其他类似问题
换一换
回答问题，赢新手礼包
个人、企业类
违法有害信息,请在下方选择后提交
色情、暴力
我们会通过消息、邮箱等方式尽快将举报结果通知您。Funs放肆电台
有声读物，音乐享受，电影分享，语言学习，心理美学，一切尽在放肆电台！（新浪微博：江江Jacky）
节目列表（39）
TA的专辑：
粤网文[8号 粤ICP备号-5
增值电信业务经营许可证 粤B2-
穗公网安备05号
荔枝全国公开举报电话：8
举报邮箱：
广州荔支网络技术有限公司 & All Rights Reserved.
本平台为信息网络存储空间网络服务平台亲爱的站长：点此；可以一次性增加N多外链哦!
温馨提示：尊敬的[广告放肆_www.adfuns.com]站点管理员，将本页链接加入您的网站友情链接，下次可以快速来到这里更新您的站点信息哦！每天更新您的[[广告放肆]每天为您精选来自全球的优质创意广告，不定时推出让您难以置信的经典图片合集，以及诸多的创意产品资讯。希望通过这个网站平台，给正在从事创意方面工作和热爱创意生活的朋友，带来趣味性、启发性的创意资讯。]站点信息，可以排到首页最前端的位置，让更多人看到您站点的信息哦。
我猜你会喜欢
百度超级链官网“超级链”基于区块链发展的解决方案，能解决现在能源消耗问题，还可以单链支持10万并发。百度目前正基于超级链完成自身企业的区块链转化。百度超级链 可免费领养区块链数字狗莱茨狗
度宇宙是继百度超级链、“图腾” 后，再推出的一个区块链项目。度宇宙将为用户打造一个由元素、引力、星球所构建的数字宇宙。用户可以通过多种系统行为获取度宇宙“元素”，并创造和扩建属于自己的星球，在用户星球质量逐渐增加的过程中，诸多新功能将逐步开启，度宇宙APP将于世界杯开幕式前后发布。日，百度推出的区块链原生应用“度宇宙”官网正式上线。
6月15日，区块链APP“度宇宙”正式上线，提供iOS版和安卓版下载。 产品玩法编辑
元素：度宇宙空间中漂浮着各种神奇的元素，需要通过引力将它们不断聚集。
星球：来到度宇宙的居民会有创世力量为其凝聚一颗独一无二星球，它是居民本身的外在实体。
引力：它是度宇宙居民脑力的外化形式，居民的引力越大，就能获得越多的元素。
探索：度宇宙中有各种神秘有趣的星球，在探索中可不断提升自身引力。
注：元素不断汇聚可成为星球，获取元素越多星球质量就越大，质量越大引力就越大，引力越大就能获得更多的元素。当星球的质量达到一定要求的时候，会开启神秘功能。
心动网址导航精选了国内国外著名的网站、好玩的、好看的、有趣的国内国外网站以及实用的、优秀的国内国外网站,包括国外视频、国外购物、国外交友、国外新闻等多种类型,同时提供精品行业分类目录提交，让用户全方位了解国内国外互联网动态！
站长啦工具箱提供二维码生成,dns解析查询,短网址生成,icp备案查询,ip定位,全民k歌解析,在线ping,端口扫描,子域名扫描,QQ在线状态,在线运行,时间戳转换,ua查询,whois查询,字符加解密等优质的小工具,站长喜欢的网站工具大全
天晴主机,提供虚拟主机,网站建设,景安云主机,腾讯云,阿里云,百度云,VPS云主机|动态拨号ADSL等全球知名云计算产品。IDC服务器租用,服务器托管等,高防服务器IDC代理加盟等,我们以高性价比、一流服务和强大的管理功能赢得数十万客户！Hlapi晏宇科技 嘉和云计算管理平台
官网之家-官方网站大全收录企业、品牌、机构、团体或个人的官方网站，通过这里网民可以直接登陆官方网站，让网民的网络生活远离钓鱼网站，每一个官方网址都附有相关的图片和文字介绍。认准官方网站jd27.com，谨防钓鱼欺骗!
Msvod魅思CMS V10,MSVOD v10,魅思视频系统V10演示网站msvod魅思视频系统,msvod v10 小视频系统合适用于各种教育、培训、教程、直销、搞笑、自拍、福利、写真、素材、广告、美容、健身、料理等N多视频行业的网站投入使用。 一个后台管理N个网站数据互通，每个网站可以单独绑定域名，单独设置SEO信息，单独设置LOGO，单独广告等
用户可以对视频上传作者进行各种礼物打赏，打赏所得金额作者可拿到对应的提成收入，所得收入可人民币提现
三级分销商可以拥有独立的分销商网站独立的管理后台，并且可以自定义绑定域名，可统计每天收益基本设置等
多线路播放
支持多服务器线路播放视频，不同的会员级别可指定观看不同的播放线路解决宽带负荷，从而提高会员的积极消费
视频上传提成
用户在线上传的视频，如该视频被其他用户比如10个金币消费了，发布视频者可得到如3个金币的奖励
视频试看限制
PC端可自定义设置视频试看时间超出时间提示购买VIP，手机采取每天试看次数超出次数提示购买VIP
结合云转码软件实现站长/用户上传视频支持任意格式转码，生成视频图片、名称、播放地址、完全自动
防盗链加密
结合云转码可现实防盗链，从而不用担心自己视频资源被盗链，除此之外播放地址我们还做了加密使资源更安全
用户每天签到可得到系统自动奖励的金币，24小时允许签到一次，从而提高用户对网站的黏贴度哦
用户登陆会员中心获取宣传地址分享到QQ、论坛、微信等，不同IP被点击一次奖励指定的消费金币
用户可凭卡密在会员中心进行充值获取金币，后台可生成卡密的金币数直接到发卡平台销售
播放器广告
整合Ckplay播放器，后台可控制加入播放前载入广告，暂停播放广告可开启/关闭广告
整合流行支付接口，比如微信支付，支付宝支付等以及第三方支付平台
封装安卓APP应用以及苹果APP应用，封装手机端数据同步自动更新
会员在线上传
用户可通过电脑、手机端在线上传视频以及发布图片小说等，实时分享到网站
上传视频奖励
用户上传视频一经站长后台审核通过，该用于将得到系统奖励的金币
MSVOD V10 功能远不止这些，以上只是介绍较为特色的功能简介，更详细的功能体验请亲自体验~！
入站排行榜
出站排行榜为什么心急如焚时间很紧的人反而更愿意选择游戏？【funs放肆游戏吧】_百度贴吧
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&签到排名：今日本吧第个签到，本吧因你更精彩，明天继续来努力！
本吧签到人数：0可签7级以上的吧50个
本月漏签0次！成为超级会员，赠送8张补签卡连续签到：天&&累计签到：天超级会员单次开通12个月以上，赠送连续签到卡3张
关注：7贴子：
为什么心急如焚时间很紧的人反而更愿意选择游戏？
有时候我们有一个错觉，压力能给我们带来动力。但其实不是这样。压力会从很多方面造成拖延。在压力下，大脑会更容易屈从于诱惑。无论是烟、零食还是游戏，都会分泌一种叫多巴胺的物质。这种多巴胺并不会带来真正的快乐，它激发的是人的渴望系统，它让你误以为做这些事会带来快乐。而人在压力状态下，对能分泌多巴胺的诱惑几乎没有任何抵抗力。如果你不喜欢多巴胺之类的说法，更通俗点的理解方式是这样的：压力会产生更多焦虑、抑郁等负性情绪，这是负能量。处理这些负能量本身就需要消耗大量的意志力和心理资源，就是要消耗正能量。于是我们陷入了这样的怪圈：压力越大，我们越需要时间和精力来放松，那就玩会游戏吧。玩过游戏后回头一看，原本就很紧迫的时间又消失了些，压力更大了，只好继续放松。压力和拖延就这样形成了恶性循环。另外，如果玩游戏中你有内疚和自责，那不仅会加重压力，还会产生这样的效果：好吧，我都已经玩游戏了，那再玩一会又何妨？你越是自责，越是容易自暴自弃，就变成你说的这效果了，明明觉得不好玩，却玩个不停。怎么办？给你两条建议：建议之一，是区分渴望和真正的快乐。有时候我们玩游戏或者做其它的事，是因为大脑激发了我们的渴望系统，让我们误以为会带来快乐。但其实不是。如果你能清醒地意识到，并不断提醒你自己这一点，游戏对你的诱惑就会减少些。建议之二，处理内疚和自责。这个我稍微说得长一点。我们本能地以为内疚和自责是我们对抗拖延症的朋友。我们相信，当我们屈从诱惑或者开始拖延时，需要有一个严厉的自我对我们提出批评和指责——就像孩子的我们的父母和老师所做的那样。我们从不怀疑充斥在成功学和励志小品中的口号：“想成功吗？那就对自己狠一点。”我们也觉得，自己之所以拖延，就是因为对自己不够严厉。于是我们更加自责。可惜这是一种错觉。通常的情况是，当我们在上一次拖延中对自己态度越严厉，下次越可能继续拖延。很多研究表明，内疚和自责会让我们陷入“放纵—自责—更严重的放纵”的恶性循环。内疚和自责会降低我们的自尊，让我们觉得自己懒惰、一事无成，因而更容易放纵自己。内疚和自责也会带来更多的压力，而压力也会让我们更容易屈从诱惑。那怎么办？如果不对拖延感到内疚，难道还要庆祝吗？也许是得庆祝。和我们的常识相悖的是，研究发现，当人们屈服于诱惑时，不让他们感觉到内疚，相反让他们感觉到快乐，居然能够增加人们抵御下次诱惑的能力。这是因为一旦摆脱了内疚和自责，我们反而能够思考为什么会失败，而不是简单地把原因归于自己，我们反而能够在和诱惑的战争中重整旗鼓，学着不轻易放纵自己了。一旦摆脱了内疚和自责，我们也不用消耗大量的心理资源去安抚内心的挫败感了——这样，我们反而有更多的心理资源来增强我们的自控。通常，我们认为意志力是规条戒律条，是理性的。但这些意志力的研究却发现，要增加自控能力，同样离不开自爱和自我怜悯，这些感性的东西。如果你是一个孩子，虽然已经尽了自己最大的努力，却因为贪玩的天性没有完成老师布置的作业，你希望爸爸妈妈怎么教育你呢？而如果你是这个孩子的父母，你又会怎么对待他呢？孩子需要的，不是严厉的批评，当然也不是放纵，是那种带着爱的规范，慈爱而坚定。坚定是不忘目标和方向，慈爱是能够原谅和接纳，毕竟孩子只是孩子。这个孩子就是你自己啊。说到这儿，我又要劝大家放弃治疗了。告诉自己，自己只是一个凡人，了解自己意志力的限度，接纳自己的不足，爱自己，是你重新积聚正能量的不二法门。因为说到底，能把我们从拖延症中拯救出来的，还得靠爱啊。另外推荐 《自控力》这本书，对类似你的例子，有详细描述。作者：动机在杭州
本周六19:00全网直播,20余款新品游戏重磅发布,更有海量福利等你拿!与Tencent WeGame 漫步星途,探索下一个未知世界,一起发现更多好游戏!
问题的关键在于，你面对的任务让你痛苦。我想说说这种痛苦本身。不管是用「焦虑情绪」也好，「压力」也好，「负能量」也好，这些说法都只是简单的标签，还不能增进我们对它的认识。如果说，只是因为时间紧迫而任务无进展，产生的焦虑感，似乎还是不够。的确这种痛苦会因为拖延行为的一再继续而愈发强烈，但拖延也只能说是维持并加强了这种感觉，还不能算是始作俑者。毕竟，在打开任务的那一刹那，这种感觉就已经存在了。我们痛苦，不满意生活当下的安排，哼唧扭动挣扎。至于打游戏？只是挣扎的一种渠道而已。长恨此身非我有，何时忘却营营？最近和拖延的来访者工作时，总是情不自禁地想到苏轼这句诗。总觉得这有点像是大家现在的生活写照。看上去忙忙碌碌，分秒必争，其实很多人，包括我自己，恐怕内心深处都有一些疲于奔命的大失落：我这么累是为什么？到什么时候是个尽头？是因为不拼就会被淘汰吧。是因为落后会被看不起吧。是因为不想让父母失望吧。是因为想让当初甩掉自己的女孩儿后悔吧。是因为北上广房价高得离谱吧。是因为身边的富二代又换了辆7系吧。是因为想做一番事业吧。是因为想让家人活得好点吧。是因为没法接受自己只有这么弱吧。我举一个来访者的例子，当然，关键信息做了处理。他要做一份简历，已经拖了很久很久。每当他想到这份简历，他就烦躁得浑身颤抖。因为他想要一份完美的简历，可以最大限度地增加他求职的胜算，可他一想到求职，就觉得那些他仰望的单位不会看上他，会接收他的地方他又看不上。想到这个他就更加痛苦了，他后悔自己过去浪费的时间，也恐惧自己将来会遭受的鄙视……他攒眉怒目，捶胸顿足，要和简历死磕到底，仿佛为了这件事不惜耗尽生命全部的能量。我觉得他太痛苦了，太痛苦了。可惜的是，正如很多有拖延行为的人一样，他一直相信，他的痛苦是「拖延」造成的。换句话说，他以为只要写完他的简历，所有的痛苦就可以烟消云散。暂时吧，直到他很快发现下一件让他痛苦的小事，并重新开始拖延。——比如看招聘信息。也不要责怪游戏、美剧或零食，或生活中其它的诱惑。它们没有魔力，是我们需要止痛片罢了。真正出了问题的，是生活本身。为什么生活对我们来说竟变得如此艰难？如果能解决这个问题，找到一种安定平和的心态，也就比较容易在适当的时间，做适当的事了。我说适当的事的意思，可能是指学习，也可能是指别的事。一切应该取决于你自己。你是谁？你在哪里？你喜欢什么？你这辈子打算怎样度过？澄清所有不相干的烦躁——就像「非要考上清华不可！」——单纯去看学习这件事情。你要真觉得有意思就试试，要确实志不在此，糊弄糊弄，对付过去也可以。考零分也不会判你刑的。不管怎样选择，踏踏实实的，安心就好。你自己觉得生活有意思就好。看起来特鸡汤？嗯，其实说到最后，我提供的解决方案就是一个词：幸福。一个人活得幸福点儿，有意思地生活，安心地工作，做事的时候就不必克服那么多痛苦。——别看我说得简单，这可一点都不简单。我觉得拖延之所以是现代的流行病，就是因为现代生活这个节奏太容易造成大家不幸福了。夸张点儿说，一个人要想真正超脱这一切，就必须做一场逆流而上的修行，花巨大的工夫去锤炼自己的心智，以对抗整个大环境施加下来的紧迫感，羞耻感，无能感，失控感……别问我怎么做到。我也还在刚起步的阶段，觉得要面临的挑战多得很。动机老师提到了爱和慈悲，这是很重要的法宝，虽然要学会使用也需要一些时间。最后，用一句话回答你的问题：心急如焚时间很紧的人还去玩游戏——或者用其它方式填充自己时间——是因为不幸福。不幸福造成了拖延，当然拖延进一步又加剧了不幸。对多少人来说，这都是无解的问题。作者：李松蔚
贴吧热议榜
使用签名档&&
保存至快速回贴