主要參考： 三套簡單的迷宮地圖生成方案（兔四）,按照自己的了解實作
實作版本： 4.26.2
本文原創位址
主要步驟
初始化大地圖，隻有0和1的狀态。其中，0和1分别代表道路和牆體，注意四周皆牆
靠近邊緣随機選取狀态為1的道路點，作為起點 a
在起點 a 的上下左右四個方向，跨兩個尋找同樣為1的道路點 c
如果找到，則将它們之間的牆體 b 打通，然後将 c 作為新的起點，然後繼續進行第2步
如果四個方向都沒有找到，則不斷回退到上一點，直到找到有一點其他方向滿足條件，然後繼續查詢
當查無可查的時候，迷宮也就填充完畢了
效果
這種算法生成的迷宮會有比較明顯的主路
UE4 實作主要代碼
頭檔案
點選檢視代碼<code>//@本文原創位址 javascript:void(0) public: UPROPERTY(VisibleAnywhere) USceneComponent* rootComp; UPROPERTY() TArray<UStaticMeshComponent*> roadrMeshs; UPROPERTY(EditAnywhere) UStaticMesh* PlaneMesh; UPROPERTY(EditAnywhere) UStaticMesh* BlockMesh; UPROPERTY(EditAnywhere) uint32 width; UPROPERTY(EditAnywhere) uint32 height; UPROPERTY(EditAnywhere) float playRate=0.2f; // 示範速度 UPROPERTY(EditAnywhere) int32 creationMode=0; // 生成迷宮的方式，三選一 UPROPERTY() FTimerHandle timerHandle; std::vector<std::vector<int32>> roadArr; //迷宮矩陣 TQueue<TTuple<int32, int32>> taskQueue; //繪制隊列 public: //改變mesh 生成道路 void ChangeMesh(); // 按照間隔規則，DFS算法生成迷宮 // 此時 roadArr 中，0代表牆，1代表道路點，2代表已經确認過的道路點 void Simple_CreateMaze(); void Simple_DFSFindPath(int32 x, int32 y); bool Simple_checkPointValid(int32 x, int32 y);</code>
CPP
<code>//@本文原創位址 javascript:void(0) // 建立迷宮 void AMazeCreator::Simple_CreateMaze() { roadArr = std::vector<std::vector<int32>>(width, std::vector<int32>(height, 0)); //初始化 for (int32 i = 0; i < (int32)width; i++) { for (int32 j = 0; j < (int32)height; j++) { UStaticMeshComponent* smComp = NewObject<UStaticMeshComponent>(this); smComp->SetupAttachment(rootComp); smComp->RegisterComponent(); smComp->SetRelativeScale3D(FVector(1.0f)); smComp->SetRelativeLocation(FVector((j - (int32)height / 2) * 100, (i - (int32)width / 2) * 100, 0)); //判斷是否可以作為道路點 bool bCanBeRoad = (i % 2) && (j % 2) && i * j != 0 && i != height - 1 && j != width - 1; roadArr[i][j] = (int32)bCanBeRoad; smComp->SetStaticMesh(bCanBeRoad ? PlaneMesh : BlockMesh); roadrMeshs.Add(smComp); } } Simple_DFSFindPath(1, 1); // 搜尋 GetWorld()->GetTimerManager().SetTimer(timerHandle,this, &AMazeCreator::ChangeMesh, playRate, true,1); } // 此時 roadArr 中，0代表牆，1代表道路點，2代表已經确認過的道路點 void AMazeCreator::Simple_DFSFindPath(int32 x, int32 y) { roadArr[x][y] = 2; taskQueue.Enqueue(TTuple<int32, int32>(x, y)); TArray<int32> offsetX = { -1, 0, 1, 0 }; TArray<int32> offsetY = { 0, -1, 0, 1 }; int32 randomInt = UKismetMathLibrary::RandomInteger(4); //随機某個方向開始 for (int32 j = randomInt; j < randomInt + 4; ++j) { int32 i = j % 4; if (Simple_checkPointValid(x + offsetX[i] * 2, y + offsetY[i] * 2)) { roadArr[x + offsetX[i]][y + offsetY[i]] = 2; taskQueue.Enqueue(TTuple<int32, int32>(x + offsetX[i], y + offsetY[i])); Simple_DFSFindPath(x + offsetX[i] * 2, y + offsetY[i] * 2); } } } bool AMazeCreator::Simple_checkPointValid(int32 x, int32 y) { return (0 < x && x < (int32)width - 1) && (0 < y && y < (int32)height - 1) && roadArr[x][y] == 1; } void AMazeCreator::ChangeMesh() { TTuple<int32, int32> point; if (taskQueue.Dequeue(point) && roadrMeshs.Num() > 0) { roadrMeshs[point.Get<0>() * height + point.Get<1>()]->SetStaticMesh(PlaneMesh); roadrMeshs[point.Get<0>() * height + point.Get<1>()]->AddRelativeLocation(FVector(0, 0, -50)); } } void AMazeCreator::BeginPlay() { Super::BeginPlay(); switch (creationMode) { case 0:Simple_CreateMaze(); break; case 1:Prim_CreateMaze(); break; case 2:Kruskal_CreateMaze(); break; } }</code>
然後将 a 點周圍所有的牆體點标記為待檢測點，加入到待檢測集合
從待檢測集合随機取一個點 b ，判斷順着它方向的下一個點 c，是否是道路
如果是，則将這個待檢測點牆體打通，将其移出待檢測集合；将下一個點 c作為新的起點，重新執行第3步
如果不是就把這個待檢測點移出待檢測集合，重新作為牆體點
不斷重複，直到待檢測集合全部檢查過，重新為空。
效果及小結
該算法不會出現明顯的主路，迷宮相對比較自然，但迷宮的分岔路會比較多
<code>//@本文原創位址 javascript:void(0) // 按照間隔規則，随機Prim算法生成迷宮 // 此時 roadArr 中，0代表牆，1代表道路點，2代表待确認的道路點，3代表已經确認過的道路點 TArray<TTuple<int32, int32,int32, int32>> CheckCache; //待确定點和其再往外一點的坐标 void Prim_CreateMaze(); void Prim_FindPath(int32 x, int32 y); bool Prim_checkPointValid(int32 x, int32 y, int32 checkState); std::vector<std::vector<int32>> roadArr; //迷宮矩陣 TQueue<TTuple<int32, int32>> taskQueue; //繪制隊列</code>
<code>//@本文原創位址 javascript:void(0) // 建立迷宮 void AMazeCreator::Prim_CreateMaze() { roadArr = std::vector<std::vector<int32>>(width, std::vector<int32>(height, 0)); //初始化 for (int32 i = 0; i < (int32)width; i++) { for (int32 j = 0; j < (int32)height; j++) { UStaticMeshComponent* smComp = NewObject<UStaticMeshComponent>(this); smComp->SetupAttachment(rootComp); smComp->RegisterComponent(); smComp->SetRelativeScale3D(FVector(1.0f)); smComp->SetRelativeLocation(FVector((j - (int32)height / 2) * 100, (i - (int32)width / 2) * 100, 0)); //判斷是否可以作為道路點 bool bCanBeRoad = (i % 2) && (j % 2) && i * j != 0 && i != width - 1 && j != height - 1; roadArr[i][j] = (int32)bCanBeRoad; smComp->SetStaticMesh(bCanBeRoad ? PlaneMesh : BlockMesh); roadrMeshs.Add(smComp); } } Prim_FindPath(1, 1); // 搜尋 GetWorld()->GetTimerManager().SetTimer(timerHandle,this, &AMazeCreator::ChangeMesh, playRate, true,1); } // 此時 roadArr 中，0代表牆，1代表道路點，2代表待确認的道路點，3代表已經确認過的道路點 void AMazeCreator::Prim_FindPath(int32 x, int32 y) { roadArr[x][y] = 3; taskQueue.Enqueue(TTuple<int32, int32>(x, y)); TArray<int32> offsetX = { -1, 0, 1, 0 }; TArray<int32> offsetY = { 0, -1, 0, 1 }; for (int32 i = 0; i < 4; ++i) { if (Prim_checkPointValid(x + offsetX[i], y + offsetY[i], 0)){ //判斷周邊一格是否是牆 roadArr[x + offsetX[i]][y + offsetY[i]] = 2; //設為待确定點 CheckCache.Add(TTuple<int32, int32, int32, int32>(x + offsetX[i], y + offsetY[i], x + offsetX[i] * 2, y + offsetY[i] * 2)); //将其放入待确定點集合 } } while (CheckCache.Num() > 0) { int32 idx = UKismetMathLibrary::RandomInteger(CheckCache.Num()); //随機選取待确定點 int32 x1 = CheckCache[idx].Get<0>(); int32 y1 = CheckCache[idx].Get<1>(); int32 x2 = CheckCache[idx].Get<2>(); int32 y2 = CheckCache[idx].Get<3>(); if (Prim_checkPointValid(x2, y2, 1)){ //判斷待确定點向外一點是否是道路點 roadArr[x1][y1] = 3; //待确定點轉為确定點 taskQueue.Enqueue(TTuple<int32, int32>(x1, y1)); //将該點壓入改變mesh隊列 CheckCache.Swap(idx, CheckCache.Num() - 1); //與最後一個元素交換，并移出 CheckCache.Pop(); Prim_FindPath(x2, y2); //遞歸，往外一點作為下次監測點 } else { roadArr[x1][y1] = 0; //待确定點重新轉為牆 CheckCache.Swap(idx, CheckCache.Num() - 1); //與最後一個元素交換，并移出 CheckCache.Pop(); } } } bool AMazeCreator::Prim_checkPointValid(int32 x, int32 y, int32 checkState) { return (0 < x && x < (int32)width - 1) && (0 < y && y < (int32)height - 1) && roadArr[x][y] == checkState; }</code>
建立所有牆的清單（除了四邊），并且建立所有單元的集合，每個集合中隻包含一個單元。
随機從牆的清單中選取一個，取該牆兩邊分隔的兩個單元
兩個單元屬于不同的集合，則将去除目前的牆，把分隔的兩個單元連同目前牆三個點作為一個單元集合；并将目前選中的牆移出清單
如果屬于同一個集合，則直接将目前選中的牆移出清單
不斷重複第 2 步，直到所有牆都檢測過
該算法同樣不會出現明顯的主路，岔路也比較多
UE4 實作主要代碼
<code>//@本文原創位址 javascript:void(0) //随機Kruskal算法 (并查集) TMap<TTuple<int32, int32>, TTuple<int32, int32>> rootArr; //根節點 TMap<TTuple<int32, int32>, int32> rank; //深度 TArray<TTuple<int32, int32>> blockArr; //牆的清單 TTuple<int32, int32>& Kruskal_Find(const TTuple<int32, int32>& coord);//查找根 void Kruskal_Union(const TTuple<int32, int32>& coord1, const TTuple<int32, int32>& coord2); void Kruskal_CreateMaze(); void Kruskal_FindPath(); std::vector<std::vector<int32>> roadArr; //迷宮矩陣 TQueue<TTuple<int32, int32>> taskQueue; //繪制隊列</code>
<code>//@本文原創位址 javascript:void(0) // 建立迷宮 void AMazeCreator::Kruskal_CreateMaze() { roadArr = std::vector<std::vector<int32>>(width, std::vector<int32>(height, 0)); //初始化 for (int32 i = 0; i < (int32)width; i++) { for (int32 j = 0; j < (int32)height; j++) { UStaticMeshComponent* smComp = NewObject<UStaticMeshComponent>(this); smComp->SetupAttachment(rootComp); smComp->RegisterComponent(); smComp->SetRelativeScale3D(FVector(1.0f)); //判斷是否可以作為道路點 bool bCanBeRoad = (i % 2) && (j % 2) && i * j != 0 && i != width - 1 && j != height - 1; roadArr[i][j] = (int32)bCanBeRoad; smComp->SetStaticMesh(bCanBeRoad ? PlaneMesh : BlockMesh); smComp->SetRelativeLocation(FVector((j - (int32)height / 2) * 100, (i - (int32)width / 2) * 100, (int32)bCanBeRoad*-50)); roadrMeshs.Add(smComp); //并查集初始化，不含邊界 if (i * j != 0 && i != width - 1 && j != height - 1) { TTuple<int, int> coord = TTuple<int, int>(i, j); rootArr.Emplace(coord, coord); //初始化集合，每個集合的根都是自己 rank.Add(coord, 1); if (!bCanBeRoad) { //記錄牆體 blockArr.Add(coord); } } } } Kruskal_FindPath(); // 搜尋 GetWorld()->GetTimerManager().SetTimer(timerHandle,this, &AMazeCreator::ChangeMesh, playRate, true,1); } void AMazeCreator::Kruskal_FindPath() { while (blockArr.Num()>0) { int32 idx = UKismetMathLibrary::RandomInteger(blockArr.Num()); //随機選取牆 auto coords= blockArr[idx]; int32 x = coords.Get<0>(); int32 y = coords.Get<1>(); //取牆體兩邊的點 TTuple<int32, int32> p1 = x % 2 ? TTuple<int32, int32>(x, y - 1) : TTuple<int32, int32>(x - 1, y); TTuple<int32, int32> p2 = x % 2 ? TTuple<int32, int32>(x, y + 1) : TTuple<int32, int32>(x + 1, y); if (roadArr[p1.Get<0>()][p1.Get<1>()] == 1 //被牆隔離的兩條道路是否相交 && roadArr[p2.Get<0>()][p2.Get<1>()] == 1 && Kruskal_Find(p1) != Kruskal_Find(p2)) { Kruskal_Union(p1, p2); //合并兩條無交集的道路 rootArr[coords] = p1; //該牆的根節點也應該變化 roadArr[x][y] = 1; taskQueue.Enqueue(coords); } blockArr.Swap(idx, blockArr.Num() - 1); blockArr.Pop(); } } TTuple<int32, int32>& AMazeCreator::Kruskal_Find(const TTuple<int32, int32>& coord) { if (rootArr[coord] != coord) //路徑壓縮 rootArr[coord] = Kruskal_Find(rootArr[coord]); return rootArr[coord]; } void AMazeCreator::Kruskal_Union(const TTuple<int32, int32>& coord1, const TTuple<int32, int32>& coord2) { auto& root1 = Kruskal_Find(coord1); auto& root2 = Kruskal_Find(coord2); if (rank[root1] <= rank[root2]) rootArr[root1] = root2; else rootArr[root2] = root1; if (rank[root1] == rank[root2] && root1 != root2) rank[root2]++; }</code>