关于固定地点寻路逻辑算法

风月绯影

假设地图上有A B C 三个星区  A星区 到 C星区 必须先迁越到 B星区中转，
这样的寻路逻辑算法有人有什么好主意么
换种说话
我有几十上百个星区，从任意星区到其他星区需要经过N个星区，每个星区之间的连接是我已知的,我怎么算路过的星区和顺序

yxxiaobin

你可以到dome区下载我的一张演示图，叫做 太空防守。里边用到了寻路算法，经过多次优化，现在效率和条理性都不错了。
其核心思路如下：
1.用一个数组A（类型根据你的星区记录方式而定，反正是能用于记录星区就行了），按照下标从小到大的顺序形成一个访问序列，用一个整数变量 I 来记录这个序列当前已使用的最大下标（初始为0），用一个整数变量J来记录当前访问的元素下标（初始为0），用一个布尔数组B来记录每个星区是否被访问。比如，你从A区出发，那么先把A区记录到访问序列的第一个元素里，并把它标记为已访问，最后把变量I增加1。
2.把数组A的第J个元素赋值给一个临时变量X。
3.X记录的星区可能毗邻一个星区，也可能是多个，或者一个也没有，但是无论如何，你肯定有方法记录这种毗邻关系（如果没有的记录，那么就谈不到寻路了）。这时候，你需要遍历其毗邻位置，如果这一位置有一个有效星区，比较这个星区是不是目的地，如果是，返回这个星区，寻路结束。如果不是目的地，那么就把这个星区记录到数组A的第I个元素里，I增加1。直到A的所有毗邻星区都遍历完成。
4.设置J增加1。
5.如果J>I，那么寻路结束，返回空值，说明出发点和目的地之间无路可走。否则，转入步骤2。
如此一来，要不就是访问到了目的地，要不就是所有相连星区都访问一遍都不是目的地，从而循环结束。

如果你要知道完整的路径是怎样的，那么还需要一个整数型数组K，在遍历X的下级星区时，把下级星区在数组A中的下标对应的K中的元素记录为X在数组A中的下标。有点绕，举个例子：比如X星区在数组A中的下标是12，寻访到他的一个下级星区，记录到数组A中的元素20中，那么就把K[20]记录为12。这样，当寻到目的地后，从目的地开始按照K的记录反向追寻，逐一记录到数组C中，就能得到完整路径了（当然顺序是反的，你使用时应该从最大下标开始访问，下标依次减1）。如下所示：
数组下标 0     1     2     3     4     5     6     7     5     9
数组K值  0     0     1     1     2     3     3     3     4     5
比如寻访到数组A中的第9个元素时是目的地，这时看数组K中第9个元素是5，那么它的前一级星区就记录在数组A的第5个元素中，继续向前找，k的第5个元素是3，那么再前一级的星区就记录在元素3中，继续循环下去，直到访问到元素0为止。但是目前版本下，函数是无法直接返回一个数组的。这个问题可通过如下方案解决：
1.基于触发器的运行机制，只要不在从寻路开始到使用寻路结果这段时间内使用等待，可以使用一个公用的全局数组来记录路径，哪怕频繁调用这一函数，也不会冲突的。即便必须使用等待，你也可以在寻路结束后立即将变量赋值给另一个专用数组，然后再等待，这样就没问题了。如果必须在寻路过程中使用等待，那么这种方法就不能用了，可以用下边这个方法。
2.把下标串成一个字符串，用特定的符号隔开，比如用逗号、下划线等。如：13，7，2，0。然后返回这个字符串，调用时再用分割字符串函数重新分割成数组下标。

这种算法的优势在于：1.尽量少的访问路径点，从而增加效率；2.如果有多个星区符合目的地要求，我们只要从中选出一个就算完成，那么这种算法找到的路径是最短的。

-------------------------------------------------------------------------------------------------------------------------
刚看到你这帖子是研究，我还以为是疑问呢。

yxxiaobin

附上个图

ff1407

楼主，这个东西要研究就看你想做得有多复杂了。说白了就是“图的遍历”问题，基础上可以分为“深度优先”和“广度优先”两种。当然，遍历的时候会有很多方法，“动态规划”， “贪心算法”等等。当然你还能用“哈密顿图”等更庞大的逻辑。这东西大起来可以在大学开一门课程。
二楼虽然没说，但他是基于“深度优先”来做的

yxxiaobin

ff1407 发表于 2015-11-21 02:01
楼主，这个东西要研究就看你想做得有多复杂了。说白了就是“图的遍历”问题，基础上可以分为“深度优先”和 ...

百度了一下，我这个属于广度优先，因为我的目的是找到距离出发点最近的符合要求的目的点，深度优先是不合适的。

风月绯影

yxxiaobin 发表于 2015-11-26 18:51
百度了一下，我这个属于广度优先，因为我的目的是找到距离出发点最近的符合要求的目的点，深度优先是不合 ...

没太看懂你这个
我现在用的是双端遍历的算法
因为我的路点是固定的，从起点终点搜索遍历可通过的路径来筛选出来最终路线，我还在简化算法
我是基于A*算法来做的

ff1407

yxxiaobin 发表于 2015-11-26 18:51
百度了一下，我这个属于广度优先，因为我的目的是找到距离出发点最近的符合要求的目的点，深度优先是不合 ...

广度优先就是先搜索旁边的，然后一层层推开去。深度则是先推到最远出然后一次次的回溯。这只是计算顺序（先查哪一个）的问题。

ff1407

风月绯影 发表于 2015-11-27 14:09
没太看懂你这个
我现在用的是双端遍历的算法
因为我的路点是固定的，从起点终点搜索遍历可通过的路径来 ...

楼主，A星属于搜索时的决策算法，采用A星算法的话有可能会得不到最优解。不过这就看你地方玩法里要不要必须用最优解啦，不用的话大可随意。

yxxiaobin

风月绯影 发表于 2015-11-27 14:09
没太看懂你这个
我现在用的是双端遍历的算法
因为我的路点是固定的，从起点终点搜索遍历可通过的路径来 ...

在ff1407所说的广度算法中，我描述的写法是比较简单的一种，适合不带有太多附加条件的问题。这种算法的优势在于能非常高效的找到最短路径。
如果你有什么更好的算法，不妨贴出来，大家讨论一下。

yxxiaobin

ff1407 发表于 2015-11-27 21:50
广度优先就是先搜索旁边的，然后一层层推开去。深度则是先推到最远出然后一次次的回溯。这只是计算顺序（ ...

恩，是这样的。
对于“找到距离点A路径最短的点B”这种题目，广度优先是适用的。因为点B可以有很多个，从点A到达同一个点B的路径也可以有很多条，要找最短的一条路径，用深度优先就不得不访问所有点，然后比较所有点B到点A的路径长度。而广度优先的话，第一个访问到的点B必然路径最短，省去了很多步骤。

windywel

楼主可以在地图初始化的时候为每一个星区生成一个路由表，使用Dijkstra's Algorithm。
这样当单位在A区域的时候他需要去E区域，只用查询A区的表，看下一个该去的是哪一个区域就可以了。有点像网络IP路由。这样，只要知道要去哪个区域，寻路就很高效。
可以参考：http://www.eecs.berkeley.edu/~jo ... _discussion_2up.pdf
不过是英文的。

yxxiaobin

windywel 发表于 2015-11-30 10:08
楼主可以在地图初始化的时候为每一个星区生成一个路由表，使用Dijkstra's Algorithm。
这样当单位在A区域 ...

能详细描述下做法吗？英文的我看不懂。
目前我的做法是用一个数组记录节点间的连接关系，然后用广度优先算法进行遍历，直到找到一个符合要求的节点。你所说的路由表有什么不同点，或者说优势在于什么？

windywel

yxxiaobin 发表于 2015-12-2 10:09
能详细描述下做法吗？英文的我看不懂。
目前我的做法是用一个数组记录节点间的连接关系，然后用广度优先 ...

如果你地图中需要寻路的单位比较少的话，你这样就可以了。

但是，如果有大量单位需要寻路，你这样实时的算会非常耗时，也就是玩家电脑差的话要卡。
使用个路由表的优缺点：
缺点：
   1，在建立的时候会消耗大量时间。
   2，占更多的内存。

优点：
   1，建立好后，寻路就是简单数组查询，即使是大量单位乱移动也不会因为寻路卡。例如，每个单位只要标记其需要去的区N,当他到达一个区X时，X查询路由表，会告诉他要去N,你下一个需要去的是Y区域。

路由表：
每个区域Ai需要记录为了到区域Aj(j!=i)应该去的下一个区域Ak(k!=i)是什么。Ak和Ai连通

例如，当单位U,需要去A4时，他目前在A1.
A1的表是
想去的区域  |   下一个应该去的区域
    A5                        A2
    A4                        A3
    A3                        A3
    A2                        A2
    查表，要去A4，应该去A3,移动到A3

A3的表
想去的区域  |   下一个应该去的区域
   A4                          A4
   A1                          A1
    查表， 要去A4, 应该去A4,移动到A4

windywel

yxxiaobin 发表于 2015-12-2 10:09
能详细描述下做法吗？英文的我看不懂。
目前我的做法是用一个数组记录节点间的连接关系，然后用广度优先 ...

建立路由表的算法也可以用你的深度搜索。简单粗暴的算法是开局做一个N到N的寻路，然后在每个节点记录。

yxxiaobin

windywel 发表于 2015-12-3 05:40
如果你地图中需要寻路的单位比较少的话，你这样就可以了。

但是，如果有大量单位需要寻路，你这样实时 ...

你说的意思我明白了，这个做法最大的好处是不用做图的遍历。但是弊端也很明显，需要建立大量的数据来记录每个节点到其他节点路径的首站。
这个对于固定不变的路径是有一定优势的，配合数据表很容易实现，在有大量路径查询同时进行时表现尤其优秀。但是如果节点与节点之间的关系频繁变动，则效率会变得极其低下，因为要频繁的重写路径表，这个算法我虽没有具体去实现，但是粗略的思考一下，比查询某个节点要费时的多。
综合上边的分析，结论是：如果1.节点间的连接关系固定，2.瞬时会有大量的路径查询，那么可以使用数据表来建立每个节点的路径表。如果节点间关系不固定，而且查询不是很多（比如每秒100次以内）的情况下，还是优先使用广度优先的遍历算法来查询更有效率。至于节点数量，这个对两种方法都有负面影响，如果节点连接关系固定，则对第一种方案影响较小，如果连接关系多变，那么第一种的效率会急剧下滑。
两个应用举例：
比如在我的图中，玩家可掌握的节点数量最多为720，其中可发起查询的节点数量约占1/3至1/2，每个节点平均每秒发起0.5次查询。所以瞬时查询数量其实不高。这样遍历算法是极具效率的。而且后期战斗激烈，节点不免损坏。如果使用路由表，一旦节点损坏，尤其是中间起连接作用的节点损坏，就要重写好多路径表，而玩家必然要去修复，修复后又要重写一次，这样是很不值的。
但是如果是固定传送阵寻路，路由表则明显具有优势。比如在地图上有若干个区域，每个区域通过特定的传送阵和特定区域相连，这些传送阵一旦激活，就不会再更改指向。为了实现跨区域智能寻路，就要配合触发器来进行传送阵寻路，这种情况下就很适合路由表。

windywel

yxxiaobin 发表于 2015-12-3 15:57
你说的意思我明白了，这个做法最大的好处是不用做图的遍历。但是弊端也很明显，需要建立大量的数据来记录 ...

恩，我说的这个是只适用于楼主的固定寻路...动态的话还是要A*,D*之类的效率才高。

yxxiaobin

突然想到一个问题：我所给的算法并没有考虑相互连接的节点间的距离差异，也就是说，在我的算法里，认为只要两个节点相连，他们的距离都是一致的。这个在虚拟网路（我自己的地图中就使用了虚拟网路）中比较实用。但是如果涉及到现实网路（比如让一个单位沿网路移动），那么两个节点间的距离显然未必是固定的。这时候就要考虑距离问题了。假如从出发点到目的地有两条路可走，都是要经过3个节点，但是这两条路也未必是一样长的。而且，如果路上有其他影响移动速度的因素（比如虫族在菌毯上移动就会快一些），即使在距离上一样长，但是从效率上来说仍然会有差异，甚至可能会是距离远的一条路更快捷。更进一步，比如设定虫族在菌毯上移动更快，而神族在能量场中移动更快，而且不同等级的能量场加速效果也不同，这样一来寻路算法就会变得更加复杂。大家有时间的话可以考虑下这种问题，编程高手们不妨做个演示出来。
--------------------------------------------------------------------
针对最后的问题，一个初步的思路如下：
将寻路分为两部分，一部分是相邻两个节点间寻路，其实就是将这段路径细分成若干单元格，这样就形成了一个更小的网络，每个单元格有若干个比例值，以此对应能量场或菌毯之类的加速影响。比如某单元格有菌毯，能使虫族单位加速10%，那么这个单元格的虫族比例值就可以设置为0.9，如果是虫族单位要求寻路，计算这一单元格的路径长度时就用实际长度乘以虫族比例，然后按单元格进行寻路，找出最短路径，将路径长度作为节点间距离。第二部分是大的网络寻路，根据节点的连接以及节点间的距离找出需要途径的节点。
第二部分没有什么问题，尽管需要考虑节点间的路径长度，但是也算是比较基本的寻路问题了。难就难在第一部分——节点间的寻路，如果是以前的游戏，按照八方向寻路的话，倒是可以直接分割路径为边长为1的田字格，但是星际2显然是任意方向寻路的，这个算法没有一定基本功恐怕就很难写好了。我能想到的就是不采用预先分割的方法形成单元格，而是每寻到一个路径点，就以这个路径点为起点向四周若干方向辐射出一个节点，但是只局限在前方一定角度内（比如180度），以免走回头路（如下图所示）。不过这样一来效率恐怕不会很高。
示意动态节点的寻路方案：

ff1407

yxxiaobin 发表于 2015-12-3 22:30
突然想到一个问题：我所给的算法并没有考虑相互连接的节点间的距离差异，也就是说，在我的算法里，认为只要 ...

今天刚好路过，看了下你的想法，没太细看。
不过我说说自己的想法吧。你考虑的问题可以归结为搜索时的动态权值问题，这里权是单位使用这段路的消耗，可以是时间，路程或粮草等各种东西。我们先假设这个消耗是时间吧。
你的算法里不是会记录路径点的个数吗，其实这就是假设所有单条路径的消耗都是1的情况，要记录消耗，你只需要改成每次加是该路径的消耗0.9或者1.1之类，而不是1。要扩展它，只需要在扩建一个临时路由表，每个点上记录两个值，分别是到达该点时的最短消耗和该最短消耗所采用的上一个点。在找到一个新的点时，把当前的消耗和前一个点记录在它上。第二次搜到时（也就是该点已经有记录数据），我们把当前消耗和该点上的比较，如果小于它，那替换记录，大于就不用管啦。当搜索完成时，你的终点会被搜索过多次，同时多次替换记录的结构就是消耗最小的结果。
这个方法还能有助于避免重复，当你发现要搜索的点已经有记录并且消耗记录比你当前的还小，那就不用搜索那个点了，因为已经有一条更好的路径建立在里该点上。

yxxiaobin

ff1407 发表于 2015-12-5 10:36
今天刚好路过，看了下你的想法，没太细看。
不过我说说自己的想法吧。你考虑的问题可以归结为搜索时的动 ...

这两天也稍微读了几篇入门级的寻路算法的文章，比如A星，比如最小堆等，其中也有一些提到了你所说的权值（我叫他比例值，一个意思）。这些问题倒不难理解。目前我感觉困难的地方在于：星际2的寻路模式比较像现实中人走路的模式——从一个点到另一个点，只要没有阻碍，就直线走过去，而不会考虑这个角度是多少。可是如果按照最简单的单元格划分法，无论怎么分，都无法做到这样直接走过去的路径，路径总是按照固定的若干个方向走，所以一般是一条弯曲的曲线。有没有什么方法在不明显提高代价的情况下获取这样平直的路径呢？

pri

yxxiaobin 发表于 2015-12-3 15:57
你说的意思我明白了，这个做法最大的好处是不用做图的遍历。但是弊端也很明显，需要建立大量的数据来记录 ...

其实可以动态的建立路径表来减少计算量，先定义2个二维数组 as 整数，先设为A、B，一个用记录上标的变量 as 整数。首先判断A（出发节点，目标节点）是否为0，如果是则用你的广度优先找到通行路径后，把A（出发节点，目标节点）设置为当前上标，然后用重复动作 设置B（当前上标，重复次数）为寻路点（重复次数）， 重复动作设置当前上标+1，判断B（当前上标，1）是否为0，如果为0则退出重复，否则重复动作判断B（A（出发节点，目标节点），重复次数）与B（A（出发节点，目标节点），重复次数+1）是不是相连的，直到B（A（出发节点，目标节点），重复次数）为目的地。如果路上有一个节点不是相邻的就把B（A（出发节点，目标节点），1）=0，把当前上标设为A（出发节点，目标节点），把A（出发节点，目标节点）设为0，然后重复开始的动作。（不想复制粘贴了）
这样建立路径表唯一不好的地方就是在建立一条更近的路之后不会选更近的路，除非原来的路被拆除，所以只适用于虚拟连接中。
还有一个需要注意的地方就是在出发节点被拆除后要把它的路径表设为可用（不必删除，因为新的路径会覆盖原有的）。
其实用一个3维数组也行的，一般认为出发点远少于节点总数的话使用3维数组需要更多的内存。