经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置：技术经验 » 程序设计 » C++ » 查看文章
地下城地图图块生成算法
来源：cnblogs　　作者：张宏港　　时间：2022/12/12 9:13:12　　对本文有异议

一. 概述

生成地下城，包含房间和迷宫通路。类似：

  1. 示例效果一
    image
  2. 示例效果二
    image

二. 思路

1.生成迷宫通路

image

  • 从房间的边缘坐标XY为奇数的格子生成迷宫，确保房间和迷宫通路之间有间隔墙壁（除了蓝色格子视为墙壁）。
  • 迷宫通路生长每次探测两个格子，确保迷宫通路间有间隔墙壁。

2.生成过程

image

三. 代码示例

位置结构体

  1. public struct Vec2
  2. {
  3.     public int x;
  4.     public int y;
  6.     public Vec2(int x, int y)
  7.     {
  8.         this.x = x;
  9.         this.y = y;
  10.     }
  12.     public static Vec2 Zero
  13.     {
  14.         get
  15.         {
  16.             return new Vec2(0, 0);
  17.         }
  18.     }
  20.     public override bool Equals(object obj)
  21.     {
  22.         if (!(obj is Vec2))
  23.             return false;
  25.         var o = (Vec2)obj;
  26.         return x == o.x && y == o.y;
  27.     }
  29.     public override int GetHashCode()
  30.     {
  31.         return x.GetHashCode() + y.GetHashCode();
  32.     }
  34.     public static Vec2 operator+ (Vec2 a, Vec2 b)
  35.     {
  36.         return new Vec2(a.x + b.x, a.y + b.y);
  37.     }
  39.     public static Vec2 operator* (Vec2 a, int n)
  40.     {
  41.         return new Vec2(a.x * n, a.y * n);
  42.     }
  44.     public static Vec2 operator* (int n, Vec2 a)
  45.     {
  46.         return new Vec2(a.x * n, a.y * n);
  47.     }
  49.     public static bool operator== (Vec2 a, Vec2 b)
  50.     {
  51.         return a.x == b.x && a.y == b.y;
  52.     }
  54.     public static bool operator !=(Vec2 a, Vec2 b)
  55.     {
  56.         return !(a.x == b.x && a.y == b.y);
  57.     }
  58. }

房间，区域的定义

  1. public struct Region
  2.     {
  3.         public int id;
  4.         public List<Vec2> positions;
  6.         public Region(int id)
  7.         {
  8.             this.id = id;
  9.             positions = new List<Vec2>();
  10.         }
  11.     }
  13.     struct Room
  14.     {
  15.         public Rect rect;
  17.         public List<Vec2> borders;
  18.         
  19.         public Room(int x, int y, int w, int h)
  20.         {
  21.             rect = new Rect(x, y, w, h);
  23.             borders = new List<Vec2>();
  25.             for (int i = x; i <= x + w; i++)
  26.                 for (int j = y; j <= y + h; j++)
  27.                     if (!(i > x && x < x + w && j > y && j < y + h))
  28.                         borders.Add(new Vec2(i, j));
  29.         }
  30.     }
  • Room中的格子，计算生成迷宫和尝试连接区域，只需要计算房间边缘的格子即borders。

生成算法上下文

  1. struct Context
  2.     {
  3.         public Vec2 size;
  4.         public int roomCnt;
  5.         public int windingPct;
  6.         public int roomSizeOff;
  9.         public int[,] map;
  10.         public List<Region> regions;
  11.         public List<Room> rooms;
  12.         public int regionIDIdx;
  13.     }
  • size 地图的大小，由输入地图大小裁剪成长宽为奇数的大小。
  • roomCnt 预期生成地图的数量。
  • windingPct 地图的蜿蜒程度最大为100 注意：即使为0，地图的蜿蜒程度一般也会比较大。
  • roomSizeOff 房间长或宽的数值正负偏移
  • map 记录地图土块的类型索引
  • regions 地区列表
  • room 房间列表
  • 地区ID索引计数

生长方向枚举

  2. public enum EDir
  3. {
  4.     Up = 0,
  5.     Down = 1,
  6.     Left = 2,
  7.     Right = 3,
  8. }
  10. static Dictionary<EDir, Vec2> dirDict = new Dictionary<EDir, Vec2> 
  11.     {
  12.         {EDir.Up, new Vec2(0, 1) },
  13.         {EDir.Down, new Vec2(0, -1) },
  14.         {EDir.Left, new Vec2(-1, 0) },
  15.         {EDir.Right, new Vec2(1, 0) },
  16.     };

初始化上下文&裁剪地图

  1. Context context;
  3.     public void Init(int w, int h, int roomCnt, int windingPct, int roomSizeOff)
  4.     {
  5.         int x = w - w % 2 - 2 - 1;
  6.         int y = h - h % 2 - 2 - 1;
  7.         context = new Context()
  8.         {
  9.             size = new Vec2(x, y),
  10.             roomCnt = roomCnt,
  11.             windingPct = windingPct,
  12.             roomSizeOff = roomSizeOff,
  14.             map = new int[x, y],
  15.             regions = new List<Region>(),
  16.             rooms = new List<Room>(),
  17.             regionIDIdx = -1,
  18.         };
  19.     }
  • 地图的长宽都被裁剪成奇数，并内缩一个单位。

生成地图房间

  1. void GenRooms()
  2.     {
  3.         for (int i = 0; i < context.roomCnt;)
  4.         {
  5.             var size = R.Range(1, 3 + context.roomSizeOff) * 2 + 1;
  6.             var off = R.Range(0, 1 + size / 2) * 2;
  7.             var w = size;
  8.             var h = size;
  10.             if (R.Range(0, 2) > 0)
  11.                 w += off;
  12.             else
  13.                 h += off;
  15.             var x = R.Range(0, (context.size.x - w) / 2) * 2 ;
  16.             var y = R.Range(0, (context.size.y - h) / 2) * 2 ;
  18.             var rect = new Rect(x, y, w, h);
  20.             bool isOverlap = false;
  21.             foreach (var room in context.rooms)
  22.                 if (rect.Overlaps(room.rect))
  23.                 {
  24.                     isOverlap = true;
  25.                     break;
  26.                 }
  28.             if (isOverlap)
  29.                 continue;
  31.             ++i;
  32.             GrowRegion();
  33.             for (int m = x; m < x + w; m++)
  34.                 for (int n = y; n < y + h; n++)
  35.                     Carve(m, n);
  37.             context.rooms.Add(new Room(x, y, w, h));
  38.         }
  39.     }
  • 根据roomCnt参数生成房间
  • 随机生成房间的大小和位置
  • 若是新生成的房间和其他的房间重合则重新生成
  • 生成房间的位置都是奇数，所以每个房间之上隔一个单位

生成迷宫通路

  1. void GenMaze()
  2.     {
  3.         foreach (var room in context.rooms)
  4.             foreach (var pos in room.borders)
  5.                 if (pos.x % 2 == 0 && pos.y % 2 == 0)
  6.                     GrowMaze(pos);
  7.     }
  9.     void GrowMaze(Vec2 pos)
  10.     {
  11.         Vec2 forward = Vec2.Zero;
  12.         var stack = new Stack<Vec2>();
  13.         stack.Push(pos);
  14.         GrowRegion();
  15.         bool isStart = true;
  16.         while (stack.Count > 0)
  17.         {
  18.             var p = stack.Pop();
  19.             List<Vec2> dirs = new List<Vec2>();
  20.             foreach (var pair in dirDict)
  21.             {
  22.                 var dir = pair.Value;
  23.                 if (CanMazeGrow(p, dir))
  24.                     dirs.Add(dir);
  25.             }
  27.             if (dirs.Count > 0)
  28.             {
  29.                 if (!(dirs.Contains(forward) && R.Range(0, 100) < context.windingPct))
  30.                     forward = dirs[R.Range(0, dirs.Count)];
  32.                 if (isStart)
  33.                     isStart = false;
  34.                 else
  35.                     Carve(p + forward);
  37.                 Carve(p + 2 * forward);
  38.                 stack.Push(p + 2 * forward);
  39.             }
  40.             else
  41.                 forward = Vec2.Zero;
  42.         }
  43.         TryShrinkRegion();
  44.     }
  46. 	bool CanMazeGrow(Vec2 pos, Vec2 dir)
  47.     {
  48.         return CanCarve(pos + dir) && CanCarve(pos + 2 * dir);
  49.     }
  51.     bool CanCarve(Vec2 pos)
  52.     {
  53.         return CanCarve(pos.x, pos.y);
  54.     }
  56.     bool CanCarve(int x, int y)
  57.     {
  58.         return InMap(x, y) && context.map[x, y] == 0;
  59.     }
  61.     bool InMap(Vec2 pos)
  62.     {
  63.         return InMap(pos.x, pos.y);
  64.     }
  66.     bool InMap(int x, int y)
  67.     {
  68.         var size = context.size;
  69.         return x >= 0 && x < size.x && y >= 0 && y < size.y;
  70.     }
  72.     void Carve(Vec2 pos, int ty = 1)
  73.     {
  74.         Carve(pos.x, pos.y, ty);
  75.     }
  77.     void Carve(int x, int y, int ty = 1)
  78.     {
  79.         context.map[x, y] = ty;
  80.         context.regions[context.regionIDIdx].positions.Add(new Vec2(x, y));
  81.     }
  • 从每个房间的边缘XY为奇数尝试生长迷宫通路
  • 递归的生长迷宫向四周探测两个单位，符合条件则向那个方向生长两个单位，直到不能生长
  • 若至少生长了一次，则形成一个迷宫通路区域
  • 第一次生长时，为了避免后面影响连接的计算，第一次的第一个单位填充被忽略

连接区域

  1. void Connect()
  2.     {
  3.         for (int i = 0; i < context.rooms.Count; i++)
  4.         {
  5.             context.regions[i].positions.Clear();
  6.             foreach (var pos in context.rooms[i].borders)
  7.                 context.regions[i].positions.Add(pos);
  8.         }
  10.         Dictionary<int, Region> dict = new Dictionary<int, Region>();
  11.         for (int i = 0; i < context.regions.Count; i++)
  12.             dict[i] = context.regions[i];
  14.         var idxs = new List<int>();
  15.         while (dict.Count > 1)
  16.         {
  17.             idxs.Clear();
  18.             foreach (var pair in dict)
  19.                 idxs.Add(pair.Key);
  21.             var dest = idxs[idxs.Count - 1];
  22.             idxs.RemoveAt(idxs.Count - 1);
  24.             bool isMerge = false;
  25.             foreach (var idx in idxs)
  26.             {
  27.                 var connectPos = Vec2.Zero;
  28.                 if (TryConnectRegion(dict[dest], dict[idx], out connectPos))
  29.                 {
  30.                     GrowRegion();
  31.                     dict[context.regionIDIdx] = context.regions[context.regionIDIdx];
  32.                     foreach (var pos in dict[dest].positions)
  33.                         dict[context.regionIDIdx].positions.Add(pos);
  35.                     foreach (var pos in dict[idx].positions)
  36.                         dict[context.regionIDIdx].positions.Add(pos);
  38.                     Carve(connectPos);
  39.                     dict.Remove(dest);
  40.                     dict.Remove(idx);
  41.                     isMerge = true;
  42.                     break;
  43.                 }
  44.             }
  46.             if (!isMerge)
  47.             {
  48.                 Debug.Log("Region Merge Failed!");
  49.                 return;
  50.             }
  51.         }
  52.     }
  53. 	
  54. 	bool TryConnectRegion(Region a, Region b, out Vec2 connectPos)
  55.     {
  56.         for (int i = 0; i < a.positions.Count; i++)
  57.         {
  58.             var ap = a.positions[i];
  59.             if (ap.x % 2 == 0 && ap.y % 2 == 0)
  60.                 for (int j = 0; j < b.positions.Count; j++)
  61.                 {
  62.                     var bp = b.positions[j];
  63.                     if (bp.x % 2 == 0 && bp.y % 2 == 0)
  64.                         if (ap.y == bp.y)
  65.                         {
  66.                             if (ap.x - bp.x == 2)
  67.                             {
  68.                                 connectPos = ap + new Vec2(-1, 0);
  69.                                 return true;
  70.                             }
  72.                             if (ap.x - bp.x == -2)
  73.                             {
  74.                                 connectPos = ap + new Vec2(1, 0);
  75.                                 return true;
  76.                             }
  77.                         }
  78.                         else if (ap.x == bp.x)
  79.                         {
  80.                             if (ap.y - bp.y == 2)
  81.                             {
  82.                                 connectPos = ap + new Vec2(0, -1);
  83.                                 return true;
  84.                             }
  86.                             if (ap.y - bp.y == -2)
  87.                             {
  88.                                 connectPos = ap + new Vec2(0, 1);
  89.                                 return true;
  90.                             }
  91.                         }
  92.                 }
  93.         }
  95.         connectPos = Vec2.Zero;
  96.         return false;
  97.     }
  • 递归的对区域进行两两合并
  • 两个区域若是各自存在一个格子，若是这两个格子的距离为2个单位则这两个单位可通过Lerp(格子a,格子b，0.5)这个格子连接，这两个区域合并成为一个区域。
  • 若是有需要可以判断两个区域中是否有房间，可以把这个格子作为"门"之类的东西。

裁剪迷宫通路

  1. void CutMaze()
  2.     {
  3.         var region = context.regions[context.regionIDIdx];
  4.         List<Vec2> dirs = new List<Vec2>();
  5.         foreach (var pos in region.positions)
  6.             CutMazeArrangement(pos);
  7.     }
  9.     void CutMazeArrangement(Vec2 pos)
  10.     {
  11.         if (context.map[pos.x, pos.y] == 0)
  12.             return;
  14.         List<Vec2> dirs = new List<Vec2>();
  15.         foreach (var pair in dirDict)
  16.         {
  17.             var dir = pair.Value;
  18.             var test = pos + dir;
  19.             if (!InMap(test))
  20.                 continue;
  21.             if (context.map[test.x, test.y] == 1)
  22.                 dirs.Add(test);
  23.         }
  25.         if (dirs.Count == 1)
  26.         {
  27.             context.map[pos.x, pos.y] = 0;
  28.             CutMazeArrangement(dirs[0]);
  29.         }
  30.     }
  • 递归的检查所有迷宫通路的格子，若是此格子的连通方向只有一个，则消除此格子。

完整代码

  1. using System.Collections;
  2. using System.Collections.Generic;
  3. using UnityEngine;
  4. using R = UnityEngine.Random;
  6. public struct Vec2
  7. {
  8.     public int x;
  9.     public int y;
  11.     public Vec2(int x, int y)
  12.     {
  13.         this.x = x;
  14.         this.y = y;
  15.     }
  17.     public static Vec2 Zero
  18.     {
  19.         get
  20.         {
  21.             return new Vec2(0, 0);
  22.         }
  23.     }
  25.     public override bool Equals(object obj)
  26.     {
  27.         if (!(obj is Vec2))
  28.             return false;
  30.         var o = (Vec2)obj;
  31.         return x == o.x && y == o.y;
  32.     }
  34.     public override int GetHashCode()
  35.     {
  36.         return x.GetHashCode() + y.GetHashCode();
  37.     }
  39.     public static Vec2 operator+ (Vec2 a, Vec2 b)
  40.     {
  41.         return new Vec2(a.x + b.x, a.y + b.y);
  42.     }
  44.     public static Vec2 operator* (Vec2 a, int n)
  45.     {
  46.         return new Vec2(a.x * n, a.y * n);
  47.     }
  49.     public static Vec2 operator* (int n, Vec2 a)
  50.     {
  51.         return new Vec2(a.x * n, a.y * n);
  52.     }
  54.     public static bool operator== (Vec2 a, Vec2 b)
  55.     {
  56.         return a.x == b.x && a.y == b.y;
  57.     }
  59.     public static bool operator !=(Vec2 a, Vec2 b)
  60.     {
  61.         return !(a.x == b.x && a.y == b.y);
  62.     }
  64.     
  65. }
  68. public enum EDir
  69. {
  70.     Up = 0,
  71.     Down = 1,
  72.     Left = 2,
  73.     Right = 3,
  74. }
  76. public class DungeonBuild
  77. {
  78.     public struct Region
  79.     {
  80.         public int id;
  81.         public List<Vec2> positions;
  83.         public Region(int id)
  84.         {
  85.             this.id = id;
  86.             positions = new List<Vec2>();
  87.         }
  88.     }
  90.     struct Room
  91.     {
  92.         public Rect rect;
  94.         public List<Vec2> borders;
  95.         
  96.         public Room(int x, int y, int w, int h)
  97.         {
  98.             rect = new Rect(x, y, w, h);
  100.             borders = new List<Vec2>();
  102.             for (int i = x; i <= x + w; i++)
  103.                 for (int j = y; j <= y + h; j++)
  104.                     if (!(i > x && x < x + w && j > y && j < y + h))
  105.                         borders.Add(new Vec2(i, j));
  106.         }
  107.     }
  110.     struct Context
  111.     {
  112.         public Vec2 size;
  113.         public int roomCnt;
  114.         public int windingPct;
  115.         public int roomSizeOff;
  118.         public int[,] map;
  119.         public List<Region> regions;
  120.         public List<Room> rooms;
  121.         public int regionIDIdx;
  122.     }
  124.     static Dictionary<EDir, Vec2> dirDict = new Dictionary<EDir, Vec2> 
  125.     {
  126.         {EDir.Up, new Vec2(0, 1) },
  127.         {EDir.Down, new Vec2(0, -1) },
  128.         {EDir.Left, new Vec2(-1, 0) },
  129.         {EDir.Right, new Vec2(1, 0) },
  130.     };
  131.     
  133.     Context context;
  135.     public void Init(int w, int h, int roomCnt, int windingPct, int roomSizeOff)
  136.     {
  137.         int x = w - w % 2 - 2 - 1;
  138.         int y = h - h % 2 - 2 - 1;
  139.         context = new Context()
  140.         {
  141.             size = new Vec2(x, y),
  142.             roomCnt = roomCnt,
  143.             windingPct = windingPct,
  144.             roomSizeOff = roomSizeOff,
  146.             map = new int[x, y],
  147.             regions = new List<Region>(),
  148.             rooms = new List<Room>(),
  149.             regionIDIdx = -1,
  150.         };
  151.     }
  153.     public void Build()
  154.     {
  155.         GenRooms();
  157.         GenMaze();
  159.         Connect();
  161.         CutMaze();
  162.     }
  164.     public int[,] GetResult()
  165.     {
  166.         return context.map;
  167.     }
  169.     public Vector2 GetSize()
  170.     {
  171.         return new Vector2(context.size.x, context.size.y);
  172.     }
  174.     void GrowRegion()
  175.     {
  176.         context.regionIDIdx++;
  177.         context.regions.Add(new Region(context.regionIDIdx));
  178.     }
  180.     void TryShrinkRegion()
  181.     {
  182.         if (context.regions[context.regionIDIdx].positions.Count == 0)
  183.         {
  184.             context.regions.RemoveAt(context.regionIDIdx);
  185.             context.regionIDIdx--;
  186.         }
  187.     }
  189.     void GenRooms()
  190.     {
  191.         for (int i = 0; i < context.roomCnt;)
  192.         {
  193.             var size = R.Range(1, 3 + context.roomSizeOff) * 2 + 1;
  194.             var off = R.Range(0, 1 + size / 2) * 2;
  195.             var w = size;
  196.             var h = size;
  198.             if (R.Range(0, 2) > 0)
  199.                 w += off;
  200.             else
  201.                 h += off;
  203.             var x = R.Range(0, (context.size.x - w) / 2) * 2 ;
  204.             var y = R.Range(0, (context.size.y - h) / 2) * 2 ;
  206.             var rect = new Rect(x, y, w, h);
  208.             bool isOverlap = false;
  209.             foreach (var room in context.rooms)
  210.                 if (rect.Overlaps(room.rect))
  211.                 {
  212.                     isOverlap = true;
  213.                     break;
  214.                 }
  216.             if (isOverlap)
  217.                 continue;
  219.             ++i;
  220.             GrowRegion();
  221.             for (int m = x; m < x + w; m++)
  222.                 for (int n = y; n < y + h; n++)
  223.                     Carve(m, n);
  225.             context.rooms.Add(new Room(x, y, w, h));
  226.         }
  227.     }
  229.     void GenMaze()
  230.     {
  231.         foreach (var room in context.rooms)
  232.             foreach (var pos in room.borders)
  233.                 if (pos.x % 2 == 0 && pos.y % 2 == 0)
  234.                     GrowMaze(pos);
  235.     }
  237.     void GrowMaze(Vec2 pos)
  238.     {
  239.         Vec2 forward = Vec2.Zero;
  240.         var stack = new Stack<Vec2>();
  241.         stack.Push(pos);
  242.         GrowRegion();
  243.         bool isStart = true;
  244.         while (stack.Count > 0)
  245.         {
  246.             var p = stack.Pop();
  247.             List<Vec2> dirs = new List<Vec2>();
  248.             foreach (var pair in dirDict)
  249.             {
  250.                 var dir = pair.Value;
  251.                 if (CanMazeGrow(p, dir))
  252.                     dirs.Add(dir);
  253.             }
  255.             if (dirs.Count > 0)
  256.             {
  257.                 if (!(dirs.Contains(forward) && R.Range(0, 100) < context.windingPct))
  258.                     forward = dirs[R.Range(0, dirs.Count)];
  260.                 if (isStart)
  261.                     isStart = false;
  262.                 else
  263.                     Carve(p + forward);
  265.                 Carve(p + 2 * forward);
  266.                 stack.Push(p + 2 * forward);
  267.             }
  268.             else
  269.                 forward = Vec2.Zero;
  270.         }
  271.         TryShrinkRegion();
  272.     }
  274.     void Connect()
  275.     {
  276.         for (int i = 0; i < context.rooms.Count; i++)
  277.         {
  278.             context.regions[i].positions.Clear();
  279.             foreach (var pos in context.rooms[i].borders)
  280.                 context.regions[i].positions.Add(pos);
  281.         }
  283.         Dictionary<int, Region> dict = new Dictionary<int, Region>();
  284.         for (int i = 0; i < context.regions.Count; i++)
  285.             dict[i] = context.regions[i];
  287.         var idxs = new List<int>();
  288.         while (dict.Count > 1)
  289.         {
  290.             idxs.Clear();
  291.             foreach (var pair in dict)
  292.                 idxs.Add(pair.Key);
  294.             var dest = idxs[idxs.Count - 1];
  295.             idxs.RemoveAt(idxs.Count - 1);
  297.             bool isMerge = false;
  298.             foreach (var idx in idxs)
  299.             {
  300.                 var connectPos = Vec2.Zero;
  301.                 if (TryConnectRegion(dict[dest], dict[idx], out connectPos))
  302.                 {
  303.                     GrowRegion();
  304.                     dict[context.regionIDIdx] = context.regions[context.regionIDIdx];
  305.                     foreach (var pos in dict[dest].positions)
  306.                         dict[context.regionIDIdx].positions.Add(pos);
  308.                     foreach (var pos in dict[idx].positions)
  309.                         dict[context.regionIDIdx].positions.Add(pos);
  311.                     Carve(connectPos);
  312.                     dict.Remove(dest);
  313.                     dict.Remove(idx);
  314.                     isMerge = true;
  315.                     break;
  316.                 }
  317.             }
  319.             if (!isMerge)
  320.             {
  321.                 Debug.Log("Region Merge Failed!");
  322.                 return;
  323.             }
  324.         }
  325.     }
  327.     bool TryConnectRegion(Region a, Region b, out Vec2 connectPos)
  328.     {
  329.         for (int i = 0; i < a.positions.Count; i++)
  330.         {
  331.             var ap = a.positions[i];
  332.             if (ap.x % 2 == 0 && ap.y % 2 == 0)
  333.                 for (int j = 0; j < b.positions.Count; j++)
  334.                 {
  335.                     var bp = b.positions[j];
  336.                     if (bp.x % 2 == 0 && bp.y % 2 == 0)
  337.                         if (ap.y == bp.y)
  338.                         {
  339.                             if (ap.x - bp.x == 2)
  340.                             {
  341.                                 connectPos = ap + new Vec2(-1, 0);
  342.                                 return true;
  343.                             }
  345.                             if (ap.x - bp.x == -2)
  346.                             {
  347.                                 connectPos = ap + new Vec2(1, 0);
  348.                                 return true;
  349.                             }
  350.                         }
  351.                         else if (ap.x == bp.x)
  352.                         {
  353.                             if (ap.y - bp.y == 2)
  354.                             {
  355.                                 connectPos = ap + new Vec2(0, -1);
  356.                                 return true;
  357.                             }
  359.                             if (ap.y - bp.y == -2)
  360.                             {
  361.                                 connectPos = ap + new Vec2(0, 1);
  362.                                 return true;
  363.                             }
  364.                         }
  365.                 }
  366.         }
  368.         connectPos = Vec2.Zero;
  369.         return false;
  370.     }
  372.     void CutMaze()
  373.     {
  374.         var region = context.regions[context.regionIDIdx];
  375.         List<Vec2> dirs = new List<Vec2>();
  376.         foreach (var pos in region.positions)
  377.             CutMazeArrangement(pos);
  378.     }
  380.     void CutMazeArrangement(Vec2 pos)
  381.     {
  382.         if (context.map[pos.x, pos.y] == 0)
  383.             return;
  385.         List<Vec2> dirs = new List<Vec2>();
  386.         foreach (var pair in dirDict)
  387.         {
  388.             var dir = pair.Value;
  389.             var test = pos + dir;
  390.             if (!InMap(test))
  391.                 continue;
  392.             if (context.map[test.x, test.y] == 1)
  393.                 dirs.Add(test);
  394.         }
  396.         if (dirs.Count == 1)
  397.         {
  398.             context.map[pos.x, pos.y] = 0;
  399.             CutMazeArrangement(dirs[0]);
  400.         }
  401.     }
  403.     bool CanMazeGrow(Vec2 pos, Vec2 dir)
  404.     {
  405.         return CanCarve(pos + dir) && CanCarve(pos + 2 * dir);
  406.     }
  408.     bool CanCarve(Vec2 pos)
  409.     {
  410.         return CanCarve(pos.x, pos.y);
  411.     }
  413.     bool CanCarve(int x, int y)
  414.     {
  415.         return InMap(x, y) && context.map[x, y] == 0;
  416.     }
  418.     bool InMap(Vec2 pos)
  419.     {
  420.         return InMap(pos.x, pos.y);
  421.     }
  423.     bool InMap(int x, int y)
  424.     {
  425.         var size = context.size;
  426.         return x >= 0 && x < size.x && y >= 0 && y < size.y;
  427.     }
  429.     void Carve(Vec2 pos, int ty = 1)
  430.     {
  431.         Carve(pos.x, pos.y, ty);
  432.     }
  434.     void Carve(int x, int y, int ty = 1)
  435.     {
  436.         context.map[x, y] = ty;
  437.         context.regions[context.regionIDIdx].positions.Add(new Vec2(x, y));
  438.     }
  439. }

原文链接：https://www.cnblogs.com/hggzhang/p/16971561.html

 友情链接：直通硅谷 　点职佳 　北美留学生论坛

C++热门文章

  • C/C++编程笔记：编写不会在C ++中编译的C程序，我教你呀！
  • 洛谷 P2085 最小函数值
  • 使用C++界面框架ImGUI开发一个简单程序
  • C++ Json解析CJsonObject的详细使用
  • C++编译错误杂记
  • 二分法（二）：采用二分法解决“最小化最大值问题”
  • C++实现json字符串与map的转换
  • C++借助curses库实现俄罗斯方块
  • 长乐培训Day5
  • 【OpenFOAM】——OpenFOAM入门算例学习

    • C++推荐文章

  • #8. 「模板」树链剖分
  • 预设型 DP
  • Standard Template Libary or C++ Standard Library
  • 一种优秀的虚拟机内存架构 - AQ
  • 如何让 MGR 不从 Primary 节点克隆数据？
  • TLScanary：Pwn中的利器
  • c++临时对象导致的生命周期问题
  • C++(Qt)-GIS开发-简易瓦片地图下载器
  • 逆向通达信 x 逆向微信 x 逆向Qt
  • C++面向对象

    • 本站QQ群：前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

    W3xue 的所有内容仅供测试，对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
    关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接（目前9元/月）请联系QQ：27243702 沸活量
    皖ICP备17017327号-2　皖公网安备34020702000426号