Forever Loop.

Trouble Busters

Thoughts on Pathfinding – 实现(上)

如果不考虑具体的实现代码,A* 算法其实是相当简单的。想象它有一个 OPEN 集和一个 CLOSED 集。其中 OPEN 集保存着等待那些筛选的节点。在最初,OPEN 集只包含一个元素,那就是最开始的起始节点。CLOSED 集包含那些已经被访问过的节点。在最初,CLOSED 集是没有任何内容的。如果用图的方式来理解,那么 OPEN 集就是边境而 CLOSED 集就是那些可访问区域的内部。由于每一个节点同时保存着指向其父节点的指针,所以我们可以知道它是如何被访问到的。

在实际流程中,有一个主要的循环不停地从 OPEN 集中取出最佳的节点 n(拥有最小 f 值的节点)并检查这个节点。如果 n 是最终的目标节点,那么我们的任务就完成了。否则,节点 n 将从 OPEN 集中移除并加入 CLOSED 集。接着检查节点 n 的邻居,节点 n’。如果 n’ 也被访问过,那么我们就不再考虑这个节点(注)。如果 n’ 在 OPEN 集中,那么它以后肯定是会被检查到的,所以我们现在也不需要考虑这个节点(注)。否则,我们把 n’ 加入 OPEN 集中,并把它的父节点设置成 n。通往节点 n’ 的花费 g(n’) 将被设置成 g(n) + movementcost(n, n’)。

你可以在这里查看一些交互式图例的演示。

注:我在这里忽视了一个小小的细节。操作时你其实需要检查节点的 g 值是否变小了,如果变小了,你应该重新 OPEN 它。

注:如果你使用的是始终最小的启发式,这种情况不会发生。在实际设计中,通常使用的是不最小的启发式

你可以在这里看到 Python 的 C++ 的实现方法。

(更多…)

『青空の下、キミのとなり』「青空の下、キミのとなり」/岚

六一快乐!o(* ̄▽ ̄*)ブ,这个学期过得好快,马上就要结束了呢。

今天给大家带来的是 2015 月九剧《欢迎来我家》的主题曲:青空の下、キミのとなり。一首刚开始 GET 不到 HIGH 点,但是越听越喜欢的歌曲。

THOUGHTS ON PATHFINDING 的新章节也将在本月更新,敬请期待。

没错,这就是一篇凑更新的 POST。

跳转之后可见歌词。

(更多…)