基于贪心策略的，游戏战略地图着色算法设计（Unity）

本文主要是介绍基于贪心策略的，游戏战略地图着色算法设计（Unity），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一共有九种颜色，初始化有11个国家，所以相邻国家势必有颜色冲突的可能性（因为随着游戏进程国家有消失或新增的可能，因此不能写死），为此需要设计一种着色算法，因为游戏中的国家数量不会特别多，所以性能不是考虑的首要因素，因此采取贪心策略，最终算法时间复杂度为 $O(n^2)$ 。

初始的游戏地图：
在这里插入图片描述
将其抽象成无向图，存储国家间的邻近关系，如下：
（国家序号从0到10：燕、晋、秦、周、郑、楚、吴、越、宋、鲁、齐）
燕 - 齐（0-10）燕 - 晋(0-1)
晋 - 秦（1-2）晋 - 齐（1-10）晋 - 周（1-3）晋 - 郑（1-4）晋 - 宋（1-8）晋 - 鲁（1-9）
秦 - 周（2-3）秦 - 楚（2-5）
周 - 楚（3-5）周 - 郑（3-4）
郑 - 宋（4-8）郑 - 楚（4-5）郑 - 鲁（4-9）
宋 - 鲁（8-9）宋 - 楚（8-5）宋 - 吴（8-6）
楚 - 吴（5-6）楚 - 越（5-7）
鲁 - 吴（9-6）鲁 - 齐（9-10）
越 - 吴（7-6）
在Start()里面需要把这些关系建立好

无向图定义：

public class stateGraph
{public int[][] Graph;private int stateCount;float[][] color = new float[9][];public stateGraph(int count){stateCount = count;Graph = new int[count][];for (int i = 0; i < count; i++) Graph[i] = new int[count];}//设置邻接关系public bool setNeighbour(int n1, int n2){if (n1 >= stateCount || n2 >= stateCount) return false;Graph[n1][n2] = 1;Graph[n2][n1] = 1;return true;}};

颜色定义：
颜色格式为RGB，一共九种，存储在二维数组当中

 colors[0] = new float[3] { 0.78f, 0.68f, 0.58f };colors[1] = new float[3] { 0.50f, 0.68f, 0.76f };colors[2] = new float[3] { 0.42f, 0.49f, 0.44f };colors[3] = new float[3] { 0.45f, 0.66f, 0.61f };colors[4] = new float[3] { 0.56f, 0.68f, 0.61f };colors[5] = new float[3] { 0.50f, 0.59f, 0.70f };colors[6] = new float[3] { 0.48f, 0.31f, 0.42f };colors[7] = new float[3] { 0.48f, 0.46f, 0.42f };colors[8] = new float[3] { 0.67f, 0.58f, 0.66f };

诸侯国结构：

public class state
{public string name;public string[] regions ;//存储所属地区数组public int regionNum;//地区数量
};

以齐国为例：
下辖五个地区：临淄、高唐、平陆、莒、即墨
上色的步骤
（1）计算出诸侯国的颜色
（2）遍历regions，对同一诸侯国的每一地区上相同的颜色

计算方法
GenerateColor()：

  void GenerateColor(){//将每个诸侯国对应的颜色存储到stateColors数组中，ColorSeq返回对应的颜色序号for (int i = 0; i < StatesNum; i++){stateColors[i] = ColorSeq(i);}//依据statesColors里面的值进行上色int state_seq = 0;foreach (state s in states){for (int j = 0; j < s.regionNum; j++){GameObject.Find(s.regions[j]).GetComponent<Image>().color = new Color(colors[stateColors[state_seq]][0], colors[stateColors[state_seq]][1], colors[stateColors[state_seq]][2]);}state_seq++;}}

colorSeq，返回该诸侯国对应的颜色序号：

 int ColorSeq(int i){int neighbourNum = 0;int[] neighbourSeq = new int[10];//返回与邻近国家不同的颜色序号int randseq = Random.Range(0, 9);//如果没有邻近国家，直接返回randSeqfor (int n = 0; n < StatesNum; n++)if (stategraph.Graph[i][n] != 0) { neighbourSeq[neighbourNum++] = n; }if (neighbourNum == 0) return randseq;//在无向图中检查randSeq是否和相邻诸侯国相同，如果相同重新产生while (!compareNumber(neighbourSeq, neighbourNum, randseq))randseq = Random.Range(0, 9);return randseq;}

compareNumber()：

  //判断颜色序号是否和邻近国家不一样bool compareNumber(int[] Neighbour, int neighbourNum, int ColorSeq){for (int i = 0; i < neighbourNum; i++){if (stateColors[Neighbour[i]] == ColorSeq) return false;}return true;}