钢铁雄心3秘籍
本项目基于unity2017开发（然而并没有使用什么新的东西），目标是实现像钢铁雄心那样的可点击地图。文章大概分为3-5部分，我会尽量在一个月内完成。本项目将作为我的毕设，仅供学习参考，请不要在2018年7月份前进行转载或使用，如有冲突，本人将追究到底！
一．项目由来与开发背景
项目由来就很简单了，前一段时间玩钢四，不知道脑子哪根筋不对，突然想自己实现一下这样的地图模块，正好要上报毕设项目，于是就这么愉快的决定了。项目都是在公司摸鱼时写的，最大的难点——多边形三角化已基本完成了，所以来写几篇文章，整理整理思路。如果想详细了解本项目，请移步GitHub，求fork，求star，反正各种求。
之前实现过简单的tilt brush面片绘制，算是有点基础？不过写这个项目时才发现自己漏了很多知识，边学边做，开发难度并不算低。幸好在此期间收到了来自很多“朋友”的帮助，万分感谢。
二．方案利弊分析
可点击地图，最直观的方案应该就是在地图下面添加一些隐藏的按钮，你以为你点的是地图，其实是按钮！但这个方案有严重的缺陷，按钮形状就那么几种，圆的，方的，最多再加个三角，不能再多。然而应该没有哪块地图属于这些形状吧？
其次就是根据当前点击的坐标判断点击的位置，触发一些事件来模拟按钮的点击。这个方案是可以实现的，然而玩过钢铁雄心系列的玩家都知道，加载场景就得几十秒，地图是真的“大”，如果采用坐标判断，性能开销绝对爆炸。
我最终决定利用untiy自带的MeshCollider完成按钮检测，至于mesh文件，其实可以由美术来制作，但考虑到那几乎爆炸的工作量，实际项目中应该是由程序来完成的。所以我打算根据一块“真实”的地图通过代码来绘制mesh。方案初步定为使用区域填充算法获取边界点+利用这些边界点绘制mesh（此方案并非最终方案！）
三．使用区域填充算法获取边界点
区域填充算法是计算机图形学的一个很基础算法，初始随机选择一个的点，如果非边界点，则将其染色，否则不进行其他处理，然后对于上下左右四个方向（四连通，也可以八连通，具体看项目要求）的点重复此操作，直到递归结束。不了解的可以看这篇文章。当然，本项目可不能完全使用这种方式，我们需要再此基础上加一段代码——将边界点添加进列表中，这样我们就能获得“需要的”边界点了。
下图分别为原始地图，正在填充的地图和填充完成的地图
当然，如果只是区域填充算法是无法在unity中达到演示效果的，所以我们需要用到协程，并利用列表（最好是队列）将递归解开，下面是具体代码。
设置像素点
void SetPixel(int x, int y)
｛
GenerateMap.GetGenerateMap.map.SetPixel(x, y, GenerateMap.GetGenerateMap.changeColor);
｝
添加边界点
void TryAddPoint(int x, int y)
｛
if (GenerateMap.GetGenerateMap.map.GetPixel(x, y) == GenerateMap.GetGenerateMap.mapColor)
｛
GenerateMap.GetGenerateMap.pointList.Add(new Vector2(x, y));
｝
｝
对每一个边界点的处理
void TrySetPixel(int x, int y)
｛
if (GenerateMap.GetGenerateMap.map.GetPixel(x, y) == GenerateMap.GetGenerateMap.mapColor)
｛
SetPixel(x, y);
TryAddPoint(x – 1, y);
TryAddPoint(x + 1, y);
TryAddPoint(x, y + 1);
TryAddPoint(x, y – 1);
｝
else
｛
GenerateMap.GetGenerateMap.borderPointList.Add(new Vector2(x, y));
｝
｝
使用协程和列表解递归
public IEnumerator GetCityFromPoint(int x, int y)
｛
GenerateMap.GetGenerateMap.pointList.Add(new Vector2(x, y));
GenerateMap.GetGenerateMap.borderPointList.Clear();
int timer = 0;
while (GenerateMap.GetGenerateMap.pointList.Count > 0)
｛
Vector2 point = GenerateMap.GetGenerateMap.pointList[0];
TrySetPixel((int)point.x, (int)point.y);
GenerateMap.GetGenerateMap.pointList.RemoveAt(0);
if (timer > 100)
｛
timer = 0;
GenerateMap.GetGenerateMap.map.Apply();
yield return new WaitForFixedUpdate();
｝
timer++;
｝
GenerateMap.GetGenerateMap.isGetPointOver = true;
｝
四．绘制mesh
有了边界点，我们就可以绘制网格了，思路很简单，就是将每两个边界点和我们初始的“种子点”组成一个三角面，没什么说的，上图和代码
public IEnumerator makeCityMesh(int x, int y)
｛
GameObject go = GameObject.Instantiate(BaseMeshObject, GenerateMap.GetGenerateMap.transform);
Mesh mesh = go.GetComponent<MeshFilter>().mesh;
Vector3[] m_vertices;
Vector2[] m_uv;
int[] m_triangles;
//Color[] m_color;
//Vector3[] m_normals;
m_vertices = new Vector3[GenerateMap.GetGenerateMap.borderPointList.Count + 1];
m_uv = new Vector2[GenerateMap.GetGenerateMap.borderPointList.Count + 1];
m_triangles = new int[GenerateMap.GetGenerateMap.borderPointList.Count * 3];
m_uv[0] = Vector2.zero;
m_vertices[0] = new Vector3(x, y, 0);
yield return new WaitForFixedUpdate();
int i = 0;
foreach (Vector2 vec in GenerateMap.GetGenerateMap.borderPointList)
｛
m_vertices[i + 1] = new Vector3(vec.x, vec.y, 0);
m_uv[i + 1] = new Vector2(1, i / GenerateMap.GetGenerateMap.borderPointList.Count);
if (i < GenerateMap.GetGenerateMap.borderPointList.Count)
｛
m_triangles[i * 3] = 0;
m_triangles[i * 3 + 1] = i + 1;
m_triangles[i * 3 + 2] = i + 2;
if (i == GenerateMap.GetGenerateMap.borderPointList.Count-1)
m_triangles[i * 3 + 2] = 1;
｝
i++;
if (i % 100 == 0)
yield return new WaitForFixedUpdate();
｝
mesh.Clear();
mesh.vertices = m_vertices;
mesh.uv = m_uv;
mesh.triangles = m_triangles;
mesh.name = GenerateMap.GetGenerateMap.provinceNum.ToString() + “_mesh”;
//mesh.colors = m_color;
//mesh.normals = m_normals;
mesh.RecalculateNormals();
LoadMesh(mesh);
GenerateMap.GetGenerateMap.isMakeMeshOver = true;
｝
五．“处理”凹多边形
你可识此图？没错，这是新疆，是新疆，新疆
不要打我，我这是在扩充祖国领土，认真脸
所以到底是什么原因使新疆变大了呢？
凹多边形，没错，就是他，新疆这块地左上方是凹进去的，我们用三角化凸多边形的方法来处理当然会出问题，解决方案就是割耳法，于是我找到了这篇文章。但我把文章贴这里不是来感谢的，而是来告诉大家这文章有多坑的。
思路没有问题，结果也没问题，但是，但是，但是，你的过程呢？
这张图该不会是盗的吧？
为何我能确定他图是盗的呢？因为他的方案是基于判断点与多边形的关系判断此点是凸点还是凹点（或者是线段与多边形关系？我猜的，这部分代码原作者没有贴出来），然而。。。多边形上的哪个点哪条边不在多边形上？
虽然这部分有些坑，但其他代码没有太大问题，如果想了解这方面的知识也可以去看一下。。。。。。
贴一下“待修改”的代码吧，思路“没”问题，换一下判断方法就基本能成。
public void MakeCityMesh()
｛
List<Vector3> m_vertices = new List<Vector3>();
List<int> m_triangles = new List<int>();
List<PointF> polygon = new List<PointF>();
foreach (Vector2 vec in GenerateMap.GetGenerateMap.borderPointList)
｛
polygon.Add(new PointF(vec.x, vec.y));
｝
while (polygon.Count > 0)
｛
List<PointF> nPolygon = new List<PointF>();
m_vertices.Clear();
m_triangles.Clear();
for (int j = 1; j < polygon.Count – 1; j++)
｛
bool isIn = false;
PointF pointF = new PointF(polygon[j + 1].X – polygon[j – 1].X, polygon[j + 1].Y – polygon[j – 1].Y);
for (int k = 1; k < 10; k++)
｛
if (GeometryHelper.IntersectionOf(new PointF(polygon[j].X + k * pointF.X, polygon[j].Y + k * pointF.Y), new Line(polygon[j – 1], polygon[j + 1])) != GeometryHelper.Intersection.None)//此判断方法是错的！！！！
｛
isIn = true;
break;
｝
｝
if (isIn)
｛
nPolygon.Add(polygon[j]);
polygon.Remove(polygon[j]);
j–;
｝
else
｛
Vector3 fVec = new Vector3(polygon[j – 1].X, polygon[j – 1].Y, 0);
Vector3 nVec = new Vector3(polygon[j].X, polygon[j].Y, 0);
Vector3 lVec = new Vector3(polygon[j + 1].X, polygon[j + 1].Y, 0);
if (!m_vertices.Contains(fVec))
m_vertices.Add(fVec);
if (!m_vertices.Contains(nVec))
m_vertices.Add(nVec);
if (!m_vertices.Contains(lVec))
m_vertices.Add(lVec);
for (int i = 0; i < m_vertices.Count; i++)
if (Vector3.Equals(fVec, m_vertices[i]))
m_triangles.Add(i);
for (int i = 0; i < m_vertices.Count; i++)
if (Vector3.Equals(nVec, m_vertices[i]))
m_triangles.Add(i);
for (int i = 0; i < m_vertices.Count; i++)
if (Vector3.Equals(lVec, m_vertices[i]))
m_triangles.Add(i);
polygon.Remove(polygon[j]);
j–;
｝
｝
if (m_vertices.Count != 0)
｛
GameObject go = GameObject.Instantiate(BaseMeshObject, GenerateMap.GetGenerateMap.transform);
Mesh mesh = go.GetComponent<MeshFilter>().mesh;
mesh.Clear();
mesh.vertices = m_vertices.ToArray();
mesh.triangles = m_triangles.ToArray();
mesh.RecalculateNormals();
｝
polygon.ToArray();
polygon = nPolygon;
｝
｝
六．“标准化”边界点
细心的朋友看了上面几张图应该会发现填充的图形也有些怪怪的，具体怎么怪呢？
仔细看白色区域，他是方的，方的，方的
这意味着可能有两个完全不相邻的边界点在列表中是相邻的，多边形并不是真正地图上所展示的多边形，利用这些千奇百怪边界点所绘制出来的mesh当然也是千奇百怪的。
思路也相对简单，可以说是“区域填充”算法的变形，只需利用当前边界点向外“延伸”就行了，下面是代码。
对于每个边界点相邻八个点进行判断与处理
bool AddMorePoint()
｛
int x, y;
for (int i = GenerateMap.GetGenerateMap.borderPointList.Count – 1; i > -1; i–)
｛
x = (int)GenerateMap.GetGenerateMap.borderPointList[i].x – 1;
y = (int)GenerateMap.GetGenerateMap.borderPointList[i].y;
if (IsBorderPoint(x, y))
｛
GenerateMap.GetGenerateMap.borderPointList.Add(new Vector2(x, y));
SetPixel(x, y);
return true;
｝
x = (int)GenerateMap.GetGenerateMap.borderPointList[i].x – 1;
y = (int)GenerateMap.GetGenerateMap.borderPointList[i].y + 1;
if (IsBorderPoint(x, y))
｛
GenerateMap.GetGenerateMap.borderPointList.Add(new Vector2(x, y));
SetPixel(x, y);
return true;
｝
x = (int)GenerateMap.GetGenerateMap.borderPointList[i].x;
y = (int)GenerateMap.GetGenerateMap.borderPointList[i].y + 1;
if (IsBorderPoint(x, y))
｛
GenerateMap.GetGenerateMap.borderPointList.Add(new Vector2(x, y));
SetPixel(x, y);
return true;
｝
x = (int)GenerateMap.GetGenerateMap.borderPointList[i].x + 1;
y = (int)GenerateMap.GetGenerateMap.borderPointList[i].y + 1;
if (IsBorderPoint(x, y))
｛
GenerateMap.GetGenerateMap.borderPointList.Add(new Vector2(x, y));
SetPixel(x, y);
return true;
｝
x = (int)GenerateMap.GetGenerateMap.borderPointList[i].x + 1;
y = (int)GenerateMap.GetGenerateMap.borderPointList[i].y;
if (IsBorderPoint(x, y))
｛
GenerateMap.GetGenerateMap.borderPointList.Add(new Vector2(x, y));
SetPixel(x, y);
return true;
｝
x = (int)GenerateMap.GetGenerateMap.borderPointList[i].x + 1;
y = (int)GenerateMap.GetGenerateMap.borderPointList[i].y – 1;
if (IsBorderPoint(x, y))
｛
GenerateMap.GetGenerateMap.borderPointList.Add(new Vector2(x, y));
SetPixel(x, y);
return true;
｝
x = (int)GenerateMap.GetGenerateMap.borderPointList[i].x;
y = (int)GenerateMap.GetGenerateMap.borderPointList[i].y – 1;
if (IsBorderPoint(x, y))
｛
GenerateMap.GetGenerateMap.borderPointList.Add(new Vector2(x, y));
SetPixel(x, y);
return true;
｝
x = (int)GenerateMap.GetGenerateMap.borderPointList[i].x – 1;
y = (int)GenerateMap.GetGenerateMap.borderPointList[i].y – 1;
if (IsBorderPoint(x, y))
｛
GenerateMap.GetGenerateMap.borderPointList.Add(new Vector2(x, y));
SetPixel(x, y);
return true;
｝
｝
return false;
｝
根据颜色判断是否为边界点
bool IsBorderPoint(int x, int y)
｛
Color color;
color = GenerateMap.GetGenerateMap.map.GetPixel(x, y);
if (color == GenerateMap.GetGenerateMap.mapColor)
｛
color = GenerateMap.GetGenerateMap.map.GetPixel(x – 1, y);
if (color != GenerateMap.GetGenerateMap.mapColor && color != GenerateMap.GetGenerateMap.changeColor)
return true;
color = GenerateMap.GetGenerateMap.map.GetPixel(x, y + 1);
if (color != GenerateMap.GetGenerateMap.mapColor && color != GenerateMap.GetGenerateMap.changeColor)
return true;
color = GenerateMap.GetGenerateMap.map.GetPixel(x + 1, y);
if (color != GenerateMap.GetGenerateMap.mapColor && color != GenerateMap.GetGenerateMap.changeColor)
return true;
color = GenerateMap.GetGenerateMap.map.GetPixel(x, y – 1);
if (color != GenerateMap.GetGenerateMap.mapColor && color != GenerateMap.GetGenerateMap.changeColor)
return true;
｝
return false;
｝
Vector2 GetBorderPoint(int x,int y)
｛
while (!IsBorderPoint(x, y))
｛
x–;
｝
return new Vector2(x, y);
｝
获取所有边界点
public IEnumerator GetCityFromPoint(int x, int y)
｛
GenerateMap.GetGenerateMap.borderPointList.Clear();
GenerateMap.GetGenerateMap.borderPointList.Add(GetBorderPoint(x, y));
bool isMore = true;
int timer = 0;
while (isMore)
｛
isMore = false;
if (AddMorePoint())
｛
isMore = true;
｝
if (timer > 1)
｛
timer = 0;
GenerateMap.GetGenerateMap.map.Apply();
yield return new WaitForFixedUpdate();
｝
timer++;
｝
GenerateMap.GetGenerateMap.isGetPointOver = true;
｝
有的时候，地图可能很规则，规则到有一段可能成为直线，对于直线上的边界点，我们只需要保留收尾端的点，中间部分的皆可删掉，思路就是利用向量的角度完成计算，因为是浮点数，所以允许有一定的误差，下面是详细代码。
public void NormalizeBorderPoint()
｛
Debug.Log(GenerateMap.GetGenerateMap.borderPointList.Count);
for (int i = 1; i < GenerateMap.GetGenerateMap.borderPointList.Count – 1; i++)
｛
Vector2 firstPoint = GenerateMap.GetGenerateMap.borderPointList[i – 1];
Vector2 nowPoint = GenerateMap.GetGenerateMap.borderPointList[i];
Vector2 lastPoint = GenerateMap.GetGenerateMap.borderPointList[i + 1];
if (Vector2.Angle(nowPoint – firstPoint, lastPoint – nowPoint) < 1)
｛
GenerateMap.GetGenerateMap.borderPointList.RemoveAt(i);
i–;
｝
｝
Debug.Log(GenerateMap.GetGenerateMap.borderPointList.Count);
｝
七．一些瞎扯
本项目并非一次完成，现在所用到的方案部分是错的，请不要将其当作最终方案，以后会慢慢改掉。
之所以不直接写最终的方案，是希望大家能根上我的思路，更容易理解。
如果不想看思路，只想要结果，请移步GitHub。
项目仍在开发中，如果有更好的方案，或者发现我的代码实现有错误，欢迎指出，感激不尽。
区域填充+协程
mesh的绘制
引入点与多边形关系“解决”凹多边形问题
新的边界点绘制
以上不同阶段的工程文件，可点击阅读原文获取。
———————-
今日推荐
《王牌英雄》匹配系统分析
腾讯游戏程序面经+面试官建议！
游戏编程中的数学：如何解决任天堂的CodinGame挑战？
添加小编微信，可享双重福利
1.加入GAD程序猿交流基地
获取行业干货资讯，观看大牛分享直播
2.领取60G独家程序资料，地址在小编朋友圈
包括腾讯内部分享、文章教程、视频教程等全套资料
↓长按添加小编GAD苏苏↓
