ShiningDan的博客

数据可视化之布线算法

发表于 | 分类于 | | 阅读次数

本文中介绍的是现有的布线算法

寻路算法

A star 算法

A* 是一种single source single destination的算法，它的时间复杂度是O(|E|), E是地图上所有路径点所形成的路径网络的edge的数目。也就是说A*可以用来计算从一个点到另外一个点的最优路径。

A Star（又称A*），是结合了Dijkstra算法和贪心算法优点的算法，A Star的核心在于将游戏背景分为一个又一个格子，每个格子有自己的靠谱值，然后通过遍历起点的格子去找到周围靠谱的格子，接着继续遍历周围……最终找到终点。

Potential Field

它是将地图用一个矩阵来表示，矩阵储存着大小不同的电势

单位本身是一个负电势，游戏以一个数组储存所有单位的电势和位置 。这样，在计算一个单位需要怎么从A点到B点时，我们可以用一个新的矩阵将目的地B点设成正电势，并以不同方式（如圆形、四边形等）辐射开来，离B点越远电势越低，直到0。然后将地图矩阵，目的地矩阵，和所有单位数组的电势相加，得出一个新的、反映当前游戏世界的电势矩阵，然后单位再选择周围所有电势点中的最高电势点去走。

Flocking Behavior

Steering Behavior

在对于一大群单位的寻路，计算量是很大的，而且往往会有很多的重复，这些都是可以避免的。如果单位的移动是利用Steering Behavior 来实现的话，那么就可以为其中一个单位，称之为Leader，计算路径（例如用导航网格），然后其他单位按照以下Flocking原则来移动：

  1. 分离，避开相邻单位
  2. 一致，和整体的移动方向一致，这里应该是Leader的移动方向
  3. 聚合，向整体的平均位置靠拢这样的话，就可以降低寻路的计算量，并且得到更加真实的群体单位行进效果。

Steering Behavior，将一个单位考虑成一个受力点，通过增加不同的力，如吸引的，排斥的等等，实现如搜索、逃跑、躲避障碍和Flocking等行为。

对于不用Steering Behavior的一大群单位，
可以将他们设为一个组，计算这个组的路径（并且要考虑到这个组的半径以便通过转角位），
然后给每个单位offset一个适当的距离，

参考