在Unity中实现Townscaper风格的不规则网格生成从算法到实战第一次看到Townscaper的建筑布局时那种自然有机的排列方式让人眼前一亮——没有重复的网格每个四边形都像是被手工调整过却又保持着整体的和谐感。作为Unity开发者我们当然想在自己的项目中复现这种效果。本文将带你从零开始用C#实现这套独特的网格生成算法并解决实际开发中可能遇到的各种问题。1. 理解Townscaper网格的核心设计Townscaper的网格之所以看起来如此自然关键在于它打破了传统网格的机械感。游戏中的每个建筑基座都是由不规则但接近正方形的四边形组成这些四边形通过特定算法生成既保证了多样性又维持了整体协调性。核心算法流程基础三角剖分使用Delaunay三角剖分创建初始网格边随机剔除选择性合并相邻三角形形成四边形网格细分将剩余三角形和四边形进一步细分顶点松弛通过迭代调整使网格更加均匀美观实际开发中我们会发现完全按照理论算法实现可能会遇到性能问题特别是在移动设备上。因此需要根据项目需求对算法进行适当优化。2. 搭建Unity项目基础结构在开始编写算法前我们需要建立合理的数据结构来支撑整个系统。以下是核心类的设计[ExecuteInEditMode] public class OrganicGrid : MonoBehaviour { [Range(3, 20)] public int gridSize 10; [Range(1, 50)] public int relaxationIterations 15; public int seed 12345; private ListVertex vertices; private ListTriangle triangles; private ListQuad quads; private void OnValidate() { GenerateGrid(); } private void GenerateGrid() { // 初始化数据结构 vertices new ListVertex(); triangles new ListTriangle(); quads new ListQuad(); // 执行算法步骤 DelaunayTriangulation(); MergeTrianglesToQuads(); SubdivideMesh(); RelaxVertices(); } }数据结构设计要点Vertex类存储位置信息和邻接关系Triangle和Quad使用顶点索引而非直接引用便于序列化使用[ExecuteInEditMode]属性方便在编辑器中进行调试3. 实现Delaunay三角剖分Delaunay三角剖分是算法的第一步它为后续操作提供了良好的基础网格。在Unity中实现时我们需要注意以下几点private void DelaunayTriangulation() { // 1. 生成泊松盘采样点 ListVector2 points PoissonDiskSampling.GeneratePoints( gridSize, gridSize, 0.5f, 30, seed ); // 2. 创建超级三角形包含所有点 Triangle superTriangle CreateSuperTriangle(points); // 3. 逐步插入点并更新三角剖分 ListTriangle triangulation new ListTriangle { superTriangle }; foreach (Vector2 point in points) { ListTriangle badTriangles new ListTriangle(); // 找出外接圆包含当前点的三角形 foreach (Triangle tri in triangulation) { if (IsPointInCircumcircle(point, tri)) { badTriangles.Add(tri); } } // 构建多边形边界 ListEdge polygon new ListEdge(); foreach (Triangle tri in badTriangles) { foreach (Edge edge in tri.GetEdges()) { bool shared false; foreach (Triangle other in badTriangles) { if (tri ! other other.HasEdge(edge)) { shared true; break; } } if (!shared) polygon.Add(edge); } } // 移除坏三角形 foreach (Triangle tri in badTriangles) { triangulation.Remove(tri); } // 创建新三角形 foreach (Edge edge in polygon) { triangulation.Add(new Triangle( edge.a, edge.b, points.Count )); } vertices.Add(new Vertex(point)); points.Add(point); } // 移除与超级三角形顶点相关的三角形 triangulation.RemoveAll(t t.ContainsVertex(superTriangle.a) || t.ContainsVertex(superTriangle.b) || t.ContainsVertex(superTriangle.c) ); triangles triangulation; }性能优化技巧使用空间分区结构加速点查询对超级三角形顶点做特殊标记便于后续移除缓存计算结果避免重复计算4. 随机边剔除与四边形生成这一步是将三角形网格转换为四边形网格的关键。我们需要谨慎处理随机性确保结果既自然又有足够的可控性。private void MergeTrianglesToQuads() { System.Random random new System.Random(seed); ListTriangle activeTriangles new ListTriangle(triangles); while (activeTriangles.Count 0) { // 随机选择一个三角形 int index random.Next(0, activeTriangles.Count); Triangle triangle activeTriangles[index]; // 查找共享边的相邻三角形 Triangle neighbor FindAdjacentTriangle(triangle, activeTriangles); if (neighbor ! null) { // 合并两个三角形形成四边形 Quad quad CreateQuadFromTriangles(triangle, neighbor); quads.Add(quad); // 从活动列表中移除已处理的三角形 activeTriangles.Remove(triangle); activeTriangles.Remove(neighbor); } else { // 没有找到合适邻居跳过这个三角形 activeTriangles.RemoveAt(index); } } // 将未合并的三角形保留下来 foreach (Triangle tri in activeTriangles) { triangles.Add(tri); } }实际开发中的注意事项设置最大迭代次数防止无限循环添加有效性检查确保生成的四边形是凸的提供参数控制合并的激进程度5. 网格细分与最终优化为了获得更丰富的细节我们需要对现有的网格进行细分。这一步特别需要注意保持网格的拓扑正确性。private void SubdivideMesh() { DictionaryEdge, int edgeMidpoints new DictionaryEdge, int(); // 细分四边形 ListQuad newQuads new ListQuad(); foreach (Quad quad in quads) { // 计算每条边的中点 int[] midIndices new int[4]; Edge[] edges quad.GetEdges(); for (int i 0; i 4; i) { if (!edgeMidpoints.TryGetValue(edges[i], out midIndices[i])) { Vector2 midPos (vertices[edges[i].a].position vertices[edges[i].b].position) * 0.5f; midIndices[i] vertices.Count; vertices.Add(new Vertex(midPos)); edgeMidpoints.Add(edges[i], midIndices[i]); } } // 计算中心点 Vector2 center Vector2.zero; for (int i 0; i 4; i) { center vertices[quad[i]].position; } center / 4f; int centerIndex vertices.Count; vertices.Add(new Vertex(center)); // 创建4个新四边形 newQuads.Add(new Quad(quad.a, midIndices[0], centerIndex, midIndices[3])); newQuads.Add(new Quad(midIndices[0], quad.b, midIndices[1], centerIndex)); newQuads.Add(new Quad(centerIndex, midIndices[1], quad.c, midIndices[2])); newQuads.Add(new Quad(midIndices[3], centerIndex, midIndices[2], quad.d)); } quads newQuads; // 细分三角形转换为三个四边形 foreach (Triangle tri in triangles) { // 类似的处理逻辑... } }顶点松弛算法实现private void RelaxVertices() { // 构建邻接关系 Dictionaryint, Listint adjacency new Dictionaryint, Listint(); foreach (Quad quad in quads) { for (int i 0; i 4; i) { int a quad[i]; int b quad[(i 1) % 4]; if (!adjacency.ContainsKey(a)) adjacency[a] new Listint(); if (!adjacency.ContainsKey(b)) adjacency[b] new Listint(); if (!adjacency[a].Contains(b)) adjacency[a].Add(b); if (!adjacency[b].Contains(a)) adjacency[b].Add(a); } } // 迭代松弛 for (int iter 0; iter relaxationIterations; iter) { Vector2[] newPositions new Vector2[vertices.Count]; for (int i 0; i vertices.Count; i) { if (vertices[i].isLocked) { newPositions[i] vertices[i].position; continue; } Vector2 avg Vector2.zero; foreach (int neighbor in adjacency[i]) { avg vertices[neighbor].position; } avg / adjacency[i].Count; newPositions[i] Vector2.Lerp( vertices[i].position, avg, 0.5f ); } // 更新位置 for (int i 0; i vertices.Count; i) { vertices[i].position newPositions[i]; } } }6. 在Unity中的可视化与调试为了直观地看到算法效果我们需要实现编辑器可视化功能private void OnDrawGizmos() { if (vertices null || quads null) return; // 绘制顶点 Gizmos.color Color.white; foreach (Vertex vertex in vertices) { Gizmos.DrawSphere(vertex.position, 0.05f); } // 绘制四边形 Gizmos.color Color.green; foreach (Quad quad in quads) { for (int i 0; i 4; i) { Vector2 a vertices[quad[i]].position; Vector2 b vertices[quad[(i 1) % 4]].position; Gizmos.DrawLine(a, b); } } // 绘制三角形如果有 Gizmos.color Color.yellow; foreach (Triangle tri in triangles) { Vector2 a vertices[tri.a].position; Vector2 b vertices[tri.b].position; Vector2 c vertices[tri.c].position; Gizmos.DrawLine(a, b); Gizmos.DrawLine(b, c); Gizmos.DrawLine(c, a); } }调试技巧添加参数控制不同阶段的显示使用不同颜色区分不同类型的网格元素实现逐步执行功能观察算法每一步的变化7. 性能优化与进阶技巧在实际项目中使用这套系统时性能是需要重点考虑的因素。以下是几个关键优化点内存优化使用数组代替List存储大量数据对顶点数据进行压缩存储重用临时计算对象计算优化// 使用Job System并行计算顶点松弛 [BurstCompile] struct RelaxationJob : IJobParallelFor { public NativeArrayVector2 positions; [ReadOnly] public NativeMultiHashMapint, int adjacency; public void Execute(int index) { if (adjacency.CountValuesForKey(index) 0) return; Vector2 avg Vector2.zero; int count 0; foreach (int neighbor in adjacency.GetValuesForKey(index)) { avg positions[neighbor]; count; } if (count 0) { avg / count; positions[index] Vector2.Lerp(positions[index], avg, 0.5f); } } }美术控制参数添加参数控制网格密度变化实现区域权重控制不同部位的松弛程度提供手动调整关键顶点的功能在实现Townscaper风格网格的过程中最耗时的部分往往是调试网格生成的质量。建议在开发初期就建立完善的可视化系统并保存各种测试用例便于回归测试。当网格用于实际建筑生成时还需要考虑如何将2D网格扩展到3D空间这需要额外的算法支持。