|
最近在恶补各种知识，而且在寻找工作的过程中，也见识了好多面试题，开阔了自己的眼界。下面我来给大家分享下，我在解决问题过程中，用到的一个最小生成树算法。（写这个的原因有2个方面，1.首先，搜索关于最小生成树的部分，我没找到太多和Unity相关的知识，大部分是原理，所以，写个博客，强化一下自己的记忆。2.也方便大部分和我一样，找资料但是找不到太相关的文章，而抓瞎的人。当然，自己对最小生成树的算法理解，也相对浅显。欢迎各位大神指正。）
? ? ? ? ?闲言少序，咱们直接进入正题。最近接到的需求是，在2D地图上，生成随机数个点，并通过最小路径，将他们连接起来，而且路径不能重复，不能相交。这就让我想到了算法里面的最小生成树的概念。至于具体概念，我就不在这里赘述了。具体的概念和相关代码可以查看这个文章。数据结构--最小生成树详解_William-CSDN博客_最小生成树
我主要讲讲我的实现方式吧。先贴代码，再逐行解释。
public struct tree
? ? {
? ? ? ? public int goIndex1;
? ? ? ? public int goIndex2;
? ? ? ? public float distance;
? ? }
List<tree> gosDistance = new List<tree>();
? ? ? ? //计算各特殊点之间的距离，利用最小生成树，连接各个房间
? ? ? ? for (int i = 0; i < speciGos.Length; i++)
? ? ? ? {
? ? ? ? ? ? for (int j = i + 1; j < speciGos.Length; j++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? float distance = Vector2.Distance(speciGos[i].transform.position, speciGos[j].transform.position);
? ? ? ? ? ? ? ? tree tree1;
? ? ? ? ? ? ? ? tree1.goIndex1 = i;
? ? ? ? ? ? ? ? tree1.goIndex2 = j;
? ? ? ? ? ? ? ? tree1.distance = distance;
? ? ? ? ? ? ? ? gosDistance.Add(tree1);
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? List<int> connectP = new List<int>();
? ? ? ? int indexgos = 0;
? ? ? ? int n = sum;
? ? ? ? float[] mins = new float[gosDistance.Count - 1];
? ? ? ? for (int i = 0; i < gosDistance.Count; i++) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //先遍历所有距离，寻找最短距离连线
? ? ? ? {
? ? ? ? ? ? if (i == 0)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? mins[0] = 99999; ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?//初始化一个超级大的值
? ? ? ? ? ? }
? ? ? ? ? ? else if (mins[0] > gosDistance[i].distance)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? mins[0] = gosDistance[i].distance;
? ? ? ? ? ? ? ? indexgos = i;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? connectP.Add(gosDistance[indexgos].goIndex1);
? ? ? ? connectP.Add(gosDistance[indexgos].goIndex2); ? ? ? ? ? ? ? ? ? ? ? ? ? //将已找到的连接点放入数组中
? ? ? ? Debug.Log("当前连接最短的2个是物体" + gosDistance[indexgos].goIndex1 + "与物体" + gosDistance[indexgos].goIndex2);
首先我建立了一个List集合和一个tree的结构体，其中tree坐标记录的是2个物体的序号，以及他们之间的距离。然后，利用双重for循环，遍历物体之间的两两距离，放入gosDistance集合中。然后定义一个connectP的集合，用于存放已经找到的特殊点，另外sum就是所有需要遍历的特殊点总和。mins这个float数组是用来存储，每次2点间最短距离的具体数据的。然后我们初始化一个极大的距离值，将咱们所有比对的点之间的距离，进行比较，得出最短的具体。以及连接这两个点的物体序号，最后将最短的2个点的序号，存入connectP的集合，表示这两个点之间已经完成连接，并可以看作一个整体继续进行后续步骤了。（这是第一步，我们先连起来2个点，并保证他是所有特殊点两两连接中，最短的2个点。）
?n = n - 1;
? ? ? ? while (n > 1) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //第一次查到了2物体之间距离最短，然后根据这两物体与其他物体的连线距离，继续寻找距离最短的?? ?
? ? ? ? {
? ? ? ? ? ? for (int i = 0; i < gosDistance.Count; i++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if (i == 0)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? mins[n] = 99999;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? if (connectP.Contains(gosDistance[i].goIndex1) && !connectP.Contains(gosDistance[i].goIndex2)) ? ? ? ? ? ? ? ? ? ? ? ? ?//如果链表内包含第一个点，但不包含第二个点，则比较距离
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? if (mins[n] > gosDistance[i].distance)
? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? mins[n] = gosDistance[i].distance;
? ? ? ? ? ? ? ? ? ? ? ? indexgos = i;
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? else if (!connectP.Contains(gosDistance[i].goIndex1) && connectP.Contains(gosDistance[i].goIndex2))
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? if (mins[n] > gosDistance[i].distance)
? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? mins[n] = gosDistance[i].distance;
? ? ? ? ? ? ? ? ? ? ? ? indexgos = i;
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? ? ? if (!connectP.Contains(gosDistance[indexgos].goIndex1))
? ? ? ? ? ? {
? ? ? ? ? ? ? ? connectP.Add(gosDistance[indexgos].goIndex1);
? ? ? ? ? ? }
? ? ? ? ? ? else if (!connectP.Contains(gosDistance[indexgos].goIndex2))
? ? ? ? ? ? {
? ? ? ? ? ? ? ? connectP.Add(gosDistance[indexgos].goIndex2);
? ? ? ? ? ? }
? ? ? ? ? ? Debug.Log("当前距离:" + mins[n]);
? ? ? ? ? ? Debug.Log("当前连接点是" + gosDistance[indexgos].goIndex1 + "与" + gosDistance[indexgos].goIndex2);
下面我再解释后续继续查找的步骤代码，如何完成的。首先，n由于上面赋值了sum，是总物体数。我们已经进行了初次查找，所以总查找次数要减一。然后就是循环查找每2个点之间的距离，并把最短的那2个点放入connectP这个集合中，直至，查找了n-1次后，就可以找到连通所有点的最小生成树了。
最后给大家看一个Demo就是使用情况。
|