在Unity里复刻Townscaper的有机网格：从Delaunay三角剖分到四边形松弛的完整C#实现

在Unity中构建Townscaper风格有机网格的实战指南当第一次看到Townscaper那充满手绘感的建筑网格时许多开发者都会被其独特的有机美学所吸引。这种看似随意却又和谐统一的四边形网格背后隐藏着一套精妙的算法组合。本文将带你从零开始在Unity中完整实现这套生成系统不仅还原Delaunay三角剖分到四边形松弛的每个技术细节更会分享实际开发中的调试技巧和可视化优化方法。1. 算法核心原理与设计思路Townscaper网格的魔力源于对规整中的随机性的精准把控。与传统的规整网格不同这种有机网格需要满足三个关键特性局部接近正方形、全局无重复模式和自然过渡的密度变化。实现这一效果需要四个阶段的算法协作Delaunay三角剖分作为计算几何的黄金标准它能确保生成的三角形尽可能接近等边为后续步骤奠定基础。在Townscaper的实现中原始算法采用正六边形区域内的点集进行三角化这种设计既保证了无限地图拼接的可能性又避免了传统泊松盘采样可能产生的密度不均问题。随机边剔除与四边形形成通过有控制地随机移除三角形之间的共享边将相邻三角形合并为四边形。这一步骤需要特别注意随机性必须可控通过mSeed参数需要保留部分三角形以保证多样性合并后的四边形应尽量接近矩形统一细分处理将剩余的三角形和初步形成的四边形细分为更小的四边形单元。这里采用了一种巧妙的细分策略三角形→3个小四边形四边形→4个小四边形所有细分保持顶点连接的一致性迭代松弛优化通过Lloyd算法变体让顶点逐步向其邻域中心移动使网格呈现更自然的分布。在Townscaper的实现中这个过程特别考虑了边界顶点的固定处理迭代次数的控制mSearchIterationCount形状优化的终止条件// 算法阶段控制参数示例 [Range(2, 12)] public int mSideSize 8; [Range(1, 20)] public int mSearchIterationCount 12; [Range(0, 65535)] public int mSeed 15911; public bool bTriangulation true; public bool bRemovingEdges false; public bool bSubdivideFaces false; public bool bRelax false;2. Unity工程准备与数据结构设计在Unity中实现这套系统首先需要建立合理的数据结构。以下是核心类的设计要点2.1 基础数据结构class Point { public Vector2 mPosition; public bool mSide; // 边界标记 }; class Triangle { public int mA, mB, mC; // 顶点索引 public bool mValid true; // 有效性标记 }; class Quad { public int mA, mB, mC, mD; // 顶点索引 }; class Neighbours { public Listint mNeighbour new Listint(); public void Add(int i) { mNeighbour.Add(i); } public int count mNeighbour.Count; };2.2 网格生成控制器主控制器Hexagrid需要管理整个生成流程并提供调试可视化功能[ExecuteInEditMode] public class Hexagrid : MonoBehaviour { private ListPoint mPoints; private ListTriangle mTriangles; private ListQuad mQuads; private Neighbours[] mNeighbours; private int mBaseQuadCount 0; void Triangulation() { /*...*/ } void RemovingEdges() { /*...*/ } void SubdivideFaces() { /*...*/ } void Relax() { /*...*/ } void OnValidate() { // 参数变化时重新生成 Regenerate(); } void Update() { // 实时更新松弛效果 if (bRelax) Relax(); } }提示使用[ExecuteInEditMode]可以让网格在编辑器模式下实时更新极大方便调试3. 分步实现与关键代码解析3.1 六边形区域三角化实现三角化阶段的核心是在正六边形区域内生成均匀点集并构建Delaunay三角网void Triangulation() { mPoints.Clear(); mTriangles.Clear(); // 六边形顶点生成 float sideLength 0.5f * Mathf.Tan(60 * Mathf.Deg2Rad); for (int x 0; x mSideSize * 2 - 1; x) { int height (x mSideSize) ? (mSideSize x) : (mSideSize * 3 - 2 - x); float deltaHeight mSideSize - height * 0.5f; for (int y 0; y height; y) { bool isSide x 0 || x (mSideSize * 2 - 2) || y 0 || y height - 1; mPoints.Add(new Point { mPosition new Vector2( (x - mSideSize 1) * sideLength, y deltaHeight ), mSide isSide }); } } // 对称三角化处理 int offset 0; for (int x 0; x (mSideSize * 2 - 2); x) { int height (x mSideSize) ? (mSideSize x) : (mSideSize * 3 - 2 - x); if (x mSideSize - 1) { // 左侧三角形 for (int y 0; y height; y) { mTriangles.Add(new Triangle(offset y, offset y height, offset y height 1)); if (y height - 1) break; mTriangles.Add(new Triangle(offset y height 1, offset y 1, offset y)); } } else { // 右侧三角形 for (int y 0; y height - 1; y) { mTriangles.Add(new Triangle(offset y, offset y height, offset y 1)); if (y height - 2) break; mTriangles.Add(new Triangle(offset y 1, offset y height, offset y height 1)); } } offset height; } }3.2 随机边剔除与四边形形成这个阶段需要谨慎处理随机性确保结果既自然又可复现void RemovingEdges() { System.Random rand new System.Random(mSeed); int searchCount 0; while (searchCount mSearchIterationCount) { int triIndex rand.Next() % mTriangles.Count; if (!mTriangles[triIndex].mValid) { searchCount; continue; } int[] adjacents GetAdjacentTriangles(triIndex); if (adjacents.Length 0) { int i2 adjacents[0]; var t1 mTriangles[triIndex]; var t2 mTriangles[i2]; // 提取四个独特顶点形成四边形 int[] indices { t1.mA, t1.mB, t1.mC, t2.mA, t2.mB, t2.mC }; var unique indices.Distinct().OrderBy(x x).ToArray(); if (unique.Length 4) { mQuads.Add(new Quad(unique[0], unique[2], unique[3], unique[1])); mTriangles[triIndex].mValid false; mTriangles[i2].mValid false; } } searchCount; } mBaseQuadCount mQuads.Count; }3.3 统一细分策略实现细分阶段需要同时处理三角形和四边形确保拓扑结构正确void SubdivideFaces() { var middles new Dictionaryuint, int(); // 细分四边形 for (int i 0; i mBaseQuadCount; i) { var quad mQuads[i]; int[] indices { quad.mA, quad.mB, quad.mC, quad.mD }; Subdivide(indices, middles); } // 细分剩余三角形 foreach (var tri in mTriangles) { if (tri.mValid) { int[] indices { tri.mA, tri.mB, tri.mC }; Subdivide(indices, middles); } } } void Subdivide(int[] indices, Dictionaryuint, int middles) { int centerIndex AddCenterPoint(indices, middles); // 根据面类型(3或4边)创建细分面 for (int i 0; i indices.Length; i) { int next (i 1) % indices.Length; uint edgeKey GetEdgeKey(indices[i], indices[next]); if (!middles.TryGetValue(edgeKey, out int edgeIndex)) { edgeIndex AddEdgePoint(indices[i], indices[next]); middles[edgeKey] edgeIndex; } // 创建新四边形 mQuads.Add(new Quad(indices[i], edgeIndex, centerIndex, middles[GetEdgeKey(indices[(i - 1 indices.Length) % indices.Length], indices[i])])); } }4. 网格优化与可视化调试4.1 松弛算法实现细节松弛阶段通过迭代优化顶点位置使网格更加均匀void Relax() { // 构建邻接关系 mNeighbours new Neighbours[mPoints.Count]; for (int i 0; i mPoints.Count; i) mNeighbours[i] new Neighbours(); // 收集邻接信息 for (int i mBaseQuadCount; i mQuads.Count; i) { var quad mQuads[i]; int[] indices { quad.mA, quad.mB, quad.mC, quad.mD }; for (int j 0; j 4; j) { int a indices[j], b indices[(j 1) % 4]; AddNeighbour(a, b); AddNeighbour(b, a); } } // 移动顶点到邻域中心 for (int i 0; i mPoints.Count; i) { if (mPoints[i].mSide) continue; var nb mNeighbours[i]; Vector2 center Vector2.zero; for (int j 0; j nb.count; j) center mPoints[nb.mNeighbour[j]].mPosition; mPoints[i].mPosition center / nb.count; } } void AddNeighbour(int a, int b) { var nb mNeighbours[a]; if (!nb.mNeighbour.Contains(b)) { nb.Add(b); } }4.2 调试可视化技巧在开发过程中实时可视化至关重要void OnDrawGizmos() { if (mPoints null) return; // 绘制点 Gizmos.color Color.white; foreach (var point in mPoints) { Gizmos.DrawSphere(new Vector3(point.mPosition.x, 0, point.mPosition.y), 0.05f); } // 绘制三角形 if (bTriangulation) { Gizmos.color Color.blue; foreach (var tri in mTriangles) { if (!tri.mValid) continue; DrawTriangle(tri.mA, tri.mB, tri.mC); } } // 绘制四边形 Gizmos.color Color.green; foreach (var quad in mQuads) { DrawQuad(quad.mA, quad.mB, quad.mC, quad.mD); } }注意在Editor模式下使用Gizmos绘制时建议通过参数控制不同阶段的显示避免视觉混乱5. 参数调优与性能考量5.1 关键参数影响分析参数影响范围推荐值效果变化mSideSize网格密度4-8值越大细节越多但计算量指数增长mSeed随机模式任意整数改变网格整体布局但保持密度mSearchIterationCount四边形数量8-15值越大四边形比例越高松弛迭代次数网格规整度10-20过多迭代会导致过度均匀化5.2 性能优化建议数据结构优化使用原生数组替代List处理大量几何数据对频繁访问的数据(如邻接关系)进行缓存算法优化将松弛计算移到Compute Shader对静态网格启用对象池复用内存管理避免在Update中频繁分配内存对中间计算结果进行重用// 优化的邻接关系计算示例 struct NeighbourData { public int count; public fixed int indices[6]; }; unsafe void BuildNeighbours() { var neighbourData new NativeArrayNeighbourData(mPoints.Count, Allocator.Temp); // 并行计算邻接关系 // ...使用Burst编译和JobSystem加速 // 转换到托管内存 for (int i 0; i mPoints.Count; i) { mNeighbours[i].mNeighbour.Clear(); for (int j 0; j neighbourData[i].count; j) { mNeighbours[i].Add(neighbourData[i].indices[j]); } } }在实际项目中当网格顶点超过5000个时建议将生成过程放在后台线程避免主线程卡顿。对于移动平台可以考虑预生成多种网格变体运行时根据设备性能选择合适精度的版本。