Unity系列研究

Unity-基于路径点寻路算法的研究(三)寻找寻路路径

在上一篇文章Unity-基于路径点寻路算法的研究(二)中介绍了寻路中障碍的判断,这里我将接着向大家介绍如何找到一条有向路径。

先来看一张图

在上图中蓝色点所围成的棕色区域为移动区域,黄色的点V为起始点,绿色的点为寻路路径点。

假设我要从 V点到达Q点,该怎么找到一条路径呢。看图我们可以能很容易的知道,V到Q的一条路径为V->T->S->P->Q,当然了这只是凭我们人脑感官上得到的结果,我们该如何让计算机去求得这条路径呢。其实一提到路径我们就容易想到数据结构中图的最短路径的求解,这里我们就可以采用类似的思路来求解路径。

我们知道图是可以被分解为树的,这里的话我们就可以通过构造一个树形结构来求解寻路路径,接下来我来介绍一些求解思路。

因为V点是起始点,那么我们就以V点为根节点开始搜寻其他节点

第一步,查找V点所能直接到达的节点,这里找到了T点,那么T点就做为V点的子节点。

第二步,查找V点子节点做所能直接到达的节点(这里不包含其父节点),T点能直接到达点有S、U点,那么S点和U点就作为T点的子节点。

第三步,查找T点所有子节点所能直接到达的节点(T有两个子节点,这里先查找哪一个都是可以的),先查找S点,S点所能直接到达的点有U点和P点,那么U点和P点作为T点的子节点。接着查找U点所能直接到达的节点,这里U点不能直接到达任何一个节点,所以结束U点查找。

第四步,查找S点所有子节点所能直接到达的节点,先查找U点,U点不能直接到达任何一个节点,结束U点的查找。然后查找P点所能直接到达的节点,P点能直接到达的点有Q点和R点,那么Q点和R点作为P点的子节点。

第五步,查找P点所有子节点所能直接到达的节点,先查找Q点,Q点能直接到达R点,R点作为Q点的子节点;然后查找R点所能直接到达的节点,R点不能到达任何节点,结束R点查找。

到此所有节点查找完成,最终得到的是个如下图一样的树形结构

20160815160305

有同学该问了这哪里是一个树,看起来就像一个有向图。那这里再将其拆分一些就得到了下图

20160815161442

通过这么一个树形结构就很容易得到我们想要的任何路径,我们想从V点到Q点,就直接可以通过Q点反向查找自己的父节点就行了。从V点到Q点有两条路径V->T->S->P->Q和V->T->S->P->R->Q,这里我们就选择V->T->S->P->Q这条路径点最少的就行了。注意,这里两个路径点之间是没有权重的概念的,这里可以理解为所有两个路径点之间的权重都是相等的。

上面介绍了解决思路,我会在下一篇文章中介绍如何进一步优化以及代码编写。

(0)

本文由 树莓屋 作者:Berry贝锐 发表,转载请注明来源!

关键词:,

热评文章

发表评论