unity使用深度优先搜索算法自动生成随机迷宫
关键词：unity C# 随机生成迷宫 深度优先搜索算法 迷宫算法
最近有空，研究了一下深度优先搜索算法，并做成一个生成迷宫的例子。
参考的是：
https://en.wikipedia.org/wiki/Maze_generation_algorithm
以下是效果图。
话不多说，代码直接贴在下面。
1 using System.Collections; 2 using System.Collections.Generic; 3 using UnityEngine; 4 using UnityEngine.UI; 5 6 public class WorldBehaviour : MonoBehaviour 7 { 8 public struct MapPointState 9 { 10 public int x; 11 public int y; 12 13 public bool isVisit; 14 public int state; 15 16 public List direction; 17 18 public MapPointState(int x, int y, bool isVisit, int state) 19 { 20 this.x = x; 21 this.y = y; 22 this.isVisit = isVisit; 23 this.state = state; 24 direction = new List (); 25 } 26 } 27 28 public RectTransform mainCanvas; 29 public Image image; 30 31 public int worldWidth; 32 public int worldHeight; 33 34 private Image[,] pathImages; 35 36 private MapPointState[,] mapPointStates; 37 38 private Queue mapQueue; 39 40 private Stack pathStack; 41 42 private int currentVisits; 43 44 private bool isReadyStop; 45 private Coroutine coroutine; 46 // Use this for initialization 47 void Start() 48 { 49 pathImages = new Image[worldHeight, worldWidth]; 50 mapQueue = new Queue (); 51 52 coroutine = StartCoroutine(WaitAndShow()); 53 54 CreateAllPath(); 55 InitDepthFirstSearch(); 56 StartDepthFirstSearch(); 57 } 58 /// 59 /// 初始化 60 /// 61 private void InitDepthFirstSearch() 62 { 63 mapPointStates = new MapPointState[worldHeight, worldWidth]; 64 pathStack = new Stack (); 65 66 int[] a = { 0, 1, 2, 3 };//0Up 1Down 2Left 3Right 67 68 for (int i = 0; i < worldWidth; i++) 69 { 70 for (int j = 0; j < worldHeight; j++) 71 { 72 mapPointStates[i, j] = new MapPointState(i, j, false, 0); 73 mapPointStates[i, j].direction.AddRange(a); 74 } 75 } 76 } 77 /// 78 /// 开始 79 /// 80 private void StartDepthFirstSearch() 81 { 82 DepthFirstSearch(Random.Range(0, worldHeight), Random.Range(0, worldWidth), -1); 83 84 print(currentVisits); 85 isReadyStop = true; 86 } 87 /// 88 /// 搜索 89 /// 90 /// 当前所在x 91 /// 当前所在y 92 /// 来时的方向 93 private void DepthFirstSearch(int x, int y, int direction)//抽象坐标轴x↑y→ 94 { 95 //若超过边界 96 if (x < 0 || x >= worldHeight || y < 0 || y >= worldWidth) 97 { 98 if (pathStack.Count > 0) 99 DepthFirstSearch(pathStack.Peek().x, pathStack.Peek().y, -1);100 return;101 }102 //若剩余方向为0103 if (mapPointStates[x, y].direction.Count == 0)104 {105 if (pathStack.Contains(mapPointStates[x, y]))106 {107 pathStack.Pop();108 mapPointStates[x, y].isVisit = true;109 mapQueue.Enqueue(mapPointStates[x, y]);110 }111 if (pathStack.Count > 0)112 DepthFirstSearch(pathStack.Peek().x, pathStack.Peek().y, -1);113 return;114 }115 //移除来时方向116 if (mapPointStates[x, y].direction.Contains(direction))117 {118 mapPointStates[x, y].direction.Remove(direction);119 }120 121 currentVisits++;122 123 //随机下一个方向124 int nextDirection = mapPointStates[x, y].direction[Random.Range(0, mapPointStates[x, y].direction.Count)];125 mapPointStates[x, y].direction.Remove(nextDirection);126 127 int newX = -1, newY = -1;128 129 ProcessNextPosition(x, y, nextDirection, ref newX, ref newY);130 131 //搜索下一个方向132 if (newX != -1 && newY != -1)133 {134 AddNewPointInMap(x, y);135 136 switch (nextDirection)137 {138 case 0:139 nextDirection = 1;140 break;141 case 1:142 nextDirection = 0;143 break;144 case 2:145 nextDirection = 3;146 break;147 case 3:148 nextDirection = 2;149 break;150 }151 152 DepthFirstSearch(newX, newY, nextDirection);153 154 return;155 }156 //回溯157 if (mapPointStates[x, y].direction.Count > 0)158 {159 DepthFirstSearch(x, y, -1);160 }161 else if (pathStack.Count > 0)162 {163 DepthFirstSearch(pathStack.Peek().x, pathStack.Peek().y, -1);164 }165 }166 /// 167 /// 计算下一个坐标168 /// 169 /// 当前x170 /// 当前y171 /// 下一个方向172 /// 新x173 /// 新y174 private void ProcessNextPosition(int x, int y, int nextDirection, ref int newX, ref int newY)175 {176 switch (nextDirection)177 {178 case 0:179 if (x + 1 < worldHeight && mapPointStates[x + 1, y].state != 1)180 {181 if ((y - 1 >= 0 && mapPointStates[x + 1, y - 1].state == 1) || (y + 1 < worldWidth && mapPointStates[x + 1, y + 1].state == 1))182 {183 break;184 }185 186 if (x + 2 < worldHeight && mapPointStates[x + 2, y].state == 1)187 {188 AddNewPointInMap(x, y);189 break;190 }191 192 newX = x + 1;193 newY = y;194 }195 break;196 case 1:197 if (x - 1 >= 0 && mapPointStates[x - 1, y].state != 1)198 {199 if ((y - 1 >= 0 && mapPointStates[x - 1, y - 1].state == 1) || (y + 1 < worldWidth && mapPointStates[x - 1, y + 1].state == 1))200 {201 break;202 }203 204 if (x - 2 >= 0 && mapPointStates[x - 2, y].state == 1)205 {206 AddNewPointInMap(x, y);207 break;208 }209 210 newX = x - 1;211 newY = y;212 }213 break;214 case 2:215 if (y - 1 >= 0 && mapPointStates[x, y - 1].state != 1)216 {217 if ((x + 1 < worldHeight && mapPointStates[x + 1, y - 1].state == 1) || (x - 1 >= 0 && mapPointStates[x - 1, y - 1].state == 1))218 {219 break;220 }221 222 if (y - 2 >= 0 && mapPointStates[x, y - 2].state == 1)223 {224 AddNewPointInMap(x, y);225 break;226 }227 228 newX = x;229 newY = y - 1;230 }231 break;232 case 3:233 if (y + 1 < worldWidth && mapPointStates[x, y + 1].state != 1)234 {235 if ((x + 1 < worldHeight && mapPointStates[x + 1, y + 1].state == 1) || (x - 1 >= 0 && mapPointStates[x - 1, y + 1].state == 1))236 {237 break;238 }239 240 if (y + 2 < worldWidth && mapPointStates[x, y + 2].state == 1)241 {242 AddNewPointInMap(x, y);243 break;244 }245 246 newX = x;247 newY = y + 1;248 }249 break;250 }251 }252 253 /// 254 /// 增加新点进地图255 /// 256 /// 257 /// 258 private void AddNewPointInMap(int x, int y)259 {260 mapPointStates[x, y].state = 1;261 262 if (!mapQueue.Contains(mapPointStates[x, y]))263 {264 mapQueue.Enqueue(mapPointStates[x, y]);265 }266 267 if (!pathStack.Contains(mapPointStates[x, y]))268 {269 pathStack.Push(mapPointStates[x, y]);270 }271 }272 /// 273 /// 创建所有路径274 /// 275 private void CreateAllPath()276 {277 for (int i = 0; i < worldHeight; i++)278 {279 for (int j = 0; j < worldWidth; j++)280 {281 pathImages[i, j] = Instantiate(image, new Vector3(i * 32, j * 32, 0), Quaternion.identity, mainCanvas);282 }283 }284 }285 /// 286 /// 设置路径颜色287 /// 288 /// 289 private void SetPathColor(MapPointState mapPointState)290 {291 if (mapPointState.isVisit)292 pathImages[mapPointState.x, mapPointState.y].color = new Color(0, 1, 0, 1);293 else294 pathImages[mapPointState.x, mapPointState.y].color = new Color(1, 1, 1, 1);295 }296 /// 297 /// 等待显示298 /// 299 /// 另附上工程文件：
https://files.cnblogs.com/files/JinT-Hwang/NewUnityProject1.7z
欢迎交流指教:)