Forever Loop.

Trouble Busters

Thoughts on Pathfinding – 启发式

启发式函数h(n)用于告知A*从图中任意一个顶点n到终点的最小预计花费。因此选择(构造)一个好的启发式函数是非常重要的。

启发式在A*中的体现:

启发式可以用来控制A*的表现。

  • 在极端情况下,如果h(n)为0,那么这时只有g(n)在负责A*,于是A*算法就变成了能够保证找到最短路径的Dijkstra算法。
  • 如果h(n)总是低于(或者等于)从n移动到终点的花费,A*依旧能够保证找到最短路径。h(n) 越小,A*拓展的节点越多,使得运行速度变慢。
  • 如果h(n)正好等于从n移动到终点的花费,那么A*将只快速得追踪生成的最短路径并且不再拓展节点。尽管这种情况并不可能常常发生,但是你可以在某些特别的环境下使用这种特性。只要你给了A*所需要的最佳的信息,A*的表现将非常优秀。
  • 在另一个极端情况下,如果h(n)相对于g(n)实在是太高了,那么这时只有h(n)在负责A*,于是A*算法就变成了贪婪最优优先搜索。

于是,我们对于h(n)如何控制A*的表现有了一个有趣的认识:在非常恰好的情况下,我们会非常快速得获得最短路径。但如果h(n)太低了,尽管我们依然能够获得最短路径,可是运行速度却变慢了。反之如果h(n)太高了,我们不一定能够获得最短路径,但是运行速度会变快。

A*的这个属性是非常有用的。举个例子,在某些情况下,你可能宁可需要一个只要“足够了”的路径而不是“完美”的路径。于是此时只要改变g(n)和h(n)之间的平衡,你就可以获得自己想要的结果。

注意:从技术上来讲,如果启发式功能没被使用,那么A*算法应该只被称为A。但是,我将仍然称之为A*因为它们的实现仍然是相同的,而且社区上几乎从来不会特意区分A还是A*。

(更多…)

『ラブライブ!』OST「硝子の花園」/絢瀬絵里(CV.南條愛乃)&東條希(CV.楠田亜衣奈)

“好冷!”——这是一开始就决定要说的。

今天给大家带来的是LoveLive!蓝光第六卷所附赠的特典歌曲《饺子花园》《硝子の花園》。其实一开始入教的时候我是Maki推,然后在渐渐地服用了各种药以后,特别是3rd之后就慢慢地开始喜欢爱乃了,然后一点点地进行下去,RadioGarden之后觉得kussn也好萌……现在已经有一点变成大家都喜欢的趋势了……

然后关于A*的进度,因为接近学期结束,いろいろ的事情都需要去处理(いろいろ的发音好萌゚∀゚)ノ),所以更新的频率会稍微减缓一些(新的一章已经完成70%咯!存在草稿里。)

 id=46959486

跳转之后可见歌词,也有B站的链接

(更多…)

『THE DIGITALIAN』「Zero-G」/岚

差不多每个月都应该写点东西了,嗯。目前没什么特别想说的,THOUGHT ON PATHFINDING正在缓慢翻译发布中,因为我翻的很烂而且更新频率比较慢,所以等不及的同学可以先去原文地址查看原版。

嗯,这次的歌曲是Arashi在十五周年之际发布的新专辑THE DIGITALIAN中的一首歌曲:Zero-G,很带感。Making最后的彩蛋也很棒。(〃∀〃)

跳转之后依旧可见歌词。

附上10月份的Rescue Time总结:

你怎么还是在玩⊂彡☆))д´)

(更多…)

Thoughts on Pathfinding – A*简介

原文出自:http://theory.stanford.edu/~amitp/GameProgramming/index.html

这是一篇非常适合初学者的算法文章,尽管网络上已经存在一些翻译版本,但是最近作者又对其进行了一些额外的补充,本着分享知识,顺便锻炼一下自己的翻译水平和算法水平的想法,我将结合已有的译文版本以及自己的理解同时配上中文版的插图,竭尽所能为大家带来良好的体验。

A*算法,又称A-Star算法,别名启发式搜索。是一种在静态路网图中求解最短路径的有效的方法之一,在接下来较长的一段时间里我将为大家带来A*算法以及基于A*算法的不同路径搜索策略。

以下,正文开始:

单个对象的移动看上去很简单,但其寻路的过程却是十分复杂的。那么我们为什么说寻路是复杂的呢?请各位考虑以下的这种情况:

如图,假设现在有一个需要进行移动的对象,其初始位置位于图形的底部,最终目标是到达图形的最上端。由于在对象的扫描范围内(以粉红色标识)并没有任何的障碍物,所以对象会一直向上移动。直到在接近图形顶部的时候,对象才发现障碍并改变前进方向,最终沿着红色路径绕过U型障碍物到达终点。但与此相反,拥有路径搜索的对象会在一开始就扫描一块较大的区域(以浅蓝色标识),并生成一条短的多的路径(以蓝色标识),引导对象从一开始就绕过障碍物达到目标。

当然,你也可以改进对象的移动策略,让其可以一开始就避免如上图一样的障碍,或者将障碍物标识成危险的(除非最终目标在其中):

路径搜索让对象从一开始就能计划好前进方向,而不是等到最后一刻才发现问题。但是在加入路径搜索和改进移动策略之间却有一个折衷之处。虽然预先的规划可以获得更好的结果,但是却会消耗较多的时间;尽管改进的移动策略通常会更快但是却有可能在移动过程中卡住。如果路网图经常需要进行变动(比如游戏地图),那么预先的规划的价值就比较 。我推荐复合的使用以上两种策略:路径搜索应用在那些整体规模较大,改动频率较少,路径较长的路网图上;而把改进的移动策略应用在那些整体规模相比较小,改动频率相比较快,路径相比较短的路网图上。

(更多…)