1.前言如果在阅读此篇文章的时候不了解地牢算法的建议去看一下这里不介绍地牢算法了只是谈论一下地牢算法不好的地方如何去扩展和优化地牢算法下面是地牢算法的链接https://www.cnblogs.com/sufferingStriver/p/8834862.html2.地牢算法缺点看过地牢算法以后现在提出几个需求比如必须要生成有n个房间的一个地图但是地牢算法会在计算的时候将不满足条件的房间去掉还有比如有一个要求有一些房间必须只有一个入口地牢算法在这个时候是没有办法搞定这种需求因为最小生成树是没有办法解决这种特殊的点所以需要想办法拓展一下。3.优化和拓展算法这里需要优化分散房间位置的算法最先想到的方法就是一个随机区域之内随机放n个房间如果和之前设置的房间位置碰撞了就重新随机这样的话怎么去判断随机区域大小如果随机区域直接最大之前不管多少房间这样一定不会重叠的但是这样指定不行房间密度会太散了一个房间到另外一个房间可能太远了这样指定不行所以怎么样可以判断最佳的随机区域大小第一个想法就是所有房间宽加起来就是随机区域的最大宽所有高加起来是就是随机区域的最大高如图所示但是这样的随机区域就是最佳吗这个最坏情况也是一定可以放下所有房间的可以看出来这个区域也太大了这样需要想办法优化这个随机区域大小于是经过一番思考可以这样优化随机区域的大小就是找到n房间中最大宽度值和最大高度值上面的图最大高度是3房间最大宽度是2房间如下图所示房间1放在(MaxWidth,MaxHeight),房间2,3放在(2*MaxWidth,2*MaxHeight),房间4,5,6放在(3*MaxWidth,3*MaxHeight),房间7,8,9,10放在(4*MaxWidth,4*MaxHeight),房间11,12,13,14,15放在(5*MaxWidth,5*MaxHeight)这样就算出现最坏情况也没有问题的慢慢增加随机区域为什么一定可以容下所有房间大家可以自己思考一下代码如下bool SetRandomRoom(int i, int MaxWidth, int MaxHeight,uint Count) { int x Random.Range(0, MaxWidth); int y Random.Range(0, MaxHeight); Rooms[i].SetLocation(x, y); if(Count 0x0fff)//栈溢出保护 return false; for (int j 0; j i - 1; j) { if (isOverLap(Rooms[i], Rooms[j]))//如果重叠 { SetRandomRoom(i, MaxWidth, MaxHeight, Count1); break; } } return true; } void SetMapPoint() { int i,j,k 0,k11,MaxHeight0,MaxWidth0,MaxWidthCell0,MaxHeightCell0; for (i 0; i Rooms.Count; i)//打散房间 { for (j i 1; j Rooms.Count; j) { if (Random.Range(0, 2) 1) SwapRoomInfo(i, j); } if (MaxWidthCell Room[i].Rect.Width) MaxWidthCell Room[i].Rect.Width; if (MaxHeightCell Room[i].Rect.Height) MaxHeightCell Room[i].Rect.Height; } for (i 0; i Room.Count; i) { if (k i)//控制房间密度 { k k k1; k1 k1 1; MaxWidth MaxWidth MaxWidthCell; MaxHeightCell MaxHeight MaxHeightCell; } if (SetRandomRoom(i, MaxWidth, MaxHeight, 0) false) { //TODO 防止意外(回滚所有随机) k 0;k1 1; MaxWidth MaxHeight 0; i 0; } } }这样就可以把房间位置散开而且比较密集。之后最小生成树连接这些点然后如何去添加只有单个入口的房间呢需要在这个最小生成树里用贪心算法去添加这些点随机这些特殊点(确保这些和之前的房间和路线碰撞)然后连接这些特殊点但是这里有一个问题因为随机函数的问题可能多次随机都有无法找到连接的路线这样的话尝试了一定次数之后这样我们需要遍历随机范围将将剩余的特殊点都连接进去。4.终结如果有更好的方法或者疑问大家可以留言讨论一下如果需要demo工程的小伙伴请大家留言一下~笔者会抽空用unity写一个demo出来提供下载。