最近心血来潮，突然想写一个2048小游戏。于是搜索了一个在线2048玩玩，熟悉熟悉规则。
只谈核心规则：(以左移为例)
以行为单位，忽略0位，每列依次向左进行合并，且每列只能合并一次。被合并列置0。
每列依次向左往0位上移动，不限次数。
[成功]就是合并后值为2048，[失败]则是没有任何一个方向上能进行合并或者移动了。
成品截图如下
一样只谈核心的东西。网上大多数的实现算法有这么几种。
这种太过繁琐，其实算法逻辑都差不多，只是方向不同而已，冗余代码太多
这种做到了各个方向上一定的通用，但是增加了额外的两次矩阵运算。
其实只需实现一个方向的算法，然后抽离出和方向有关的变量，封装为参数，通过参数控制方向。
比如左方向：以行为单位，处理每列的数据。那么第一层循环将是按行的数量进行迭代。处理列索引将是0-最后一列。
比如右方向：以行为单位，处理每列的数据。那么第一层循环将是按行的数量进行迭代。处理列索引将是最后一列-0。
比如上方向：以列为单位，处理每行的数据。那么第一层循环将是按列的数量进行迭代。处理列索引将是0-最后一行。
比如下方向：以列为单位，处理每行的数据。那么第一层循环将是按列的数量进行迭代。处理列索引将是最后一行-0。
变量抽取为：
第一层循环的loop，可以传入行或者列数量。
第二层循环的起始值starti，结束值endi，因为有正和反两个方向，所以还需要一个步长step来控制方向，+1为正，-1为反。
因为是二维数组，所以还需要一个委托，来重定义[x,y]的取值和设置值。比如以行为外层循环的，返回[x,y],以列为外层循环的，返回[y,x]
因为涉及到取值和赋值，用到了指针，也可以用两个方法替代取值和赋值。
代码如下
1 private unsafe bool Move(int loop, int si, int ei, int step, Func<int, int, IntPtr> getInt) 2 { 3 //算法基于左向移动 4 5 bool moved = false; 6 7 for (int x = 0; x < loop; x++) 8 { 9 //第一步 合并10 for (int y = si; y * step < ei; y+=step)11 {12 var val1 = (int*)getInt(x, y);13 14 if (*val1 != 0)15 {16 for (var y2 = y + step; y2 != ei + step; y2 += step)17 {18 var val2 = (int*)getInt(x, y2);19 //忽略020 if (*val2 == 0) continue;21 //合并22 if (*val1 == *val2)23 {24 *val1 *= 2;25 *val2 = 0;26 moved = true;27 28 Score += *val1;29 30 if (*val1 == 2048) State = GameState.Succ;31 32 //移动处理列索引33 y = y2;34 }35 else y = y2 - step;//不相等36 break;37 }38 }39 40 }41 42 //第二步 往0位上移动43 int? lastY = null;44 for (int y = si; y != ei; y += step)45 {46 var val1 = (int*)getInt(x, y);47 48 if (*val1 == 0)49 {50 var y2 = lastY ?? y + step;51 for (; y2 != ei + step; y2 += step)52 {53 var val2 = (int*)getInt(x, y2);54 55 if (*val2 != 0)56 {57 *val1 = *val2;58 *val2 = 0;59 moved = true;60 61 lastY = y2 + step;62 break;63 }64 }65 //最后一列了66 if (y2 == ei) break;67 }68 }69 }70 71 return moved;72 }
View Code
调用的核心代码：
1 switch (direction) 2 { 3 case MoveDirection.Up: 4 move = Move(C, 0, R - 1, 1, (x, y) => { 5 fixed (int* _ = &_bs[0, 0]) 6 { 7 return (IntPtr)(_ + y * C + x); 8 } 9 });10 break;11 case MoveDirection.Down:12 move = Move(C, R - 1, 0, -1, (x, y) => {13 fixed (int* _ = &_bs[0,0])14 {15 return (IntPtr)(_ + y * C + x);16 }17 });18 break;19 case MoveDirection.Left:20 move = Move(R, 0, C - 1, 1, (x, y) => {21 fixed (int* _ = &_bs[0, 0])22 {23 return (IntPtr)(_ + x * C + y);24 }25 });26 break;27 case MoveDirection.Right:28 move = Move(R, C - 1, 0, -1, (x,y)=> { 29 fixed(int* _ = &_bs[0, 0])30 {31 return (IntPtr)(_ + x * C + y);32 }33 });34 break;35 }
View Code
网上大多数的算法都是复制一份矩阵数据，然后依次从各个方向上进行合并和移动，之后和原矩阵进行比较，如果数据相同则说明没有变化，从而判定失败。
这种太复杂，太死板了，太低效了。仔细分析可知，失败的判定其实很简单：
1.已经没有空位可以随机数字了，说明不可移动。
2.每个坐标的数字和它旁边的数字都不相等。说明不可合并。
代码如下：
1 /// <summary> 2 /// 判断是否可以合并 3 /// </summary> 4 private void CheckGame() 5 { 6 //是否已经填满 并且无法移动 7 for (int x = 0; x < R; x++) 8 { 9 for (int y = 0; y < C; y++)10 {11 if (y < C - 1 && _bs[x, y] == _bs[x, y + 1]) return;12 if (x < R - 1 && _bs[x, y] == _bs[x + 1, y]) return;13 }14 }15 16 State = GameState.Fail;17 }18 19 /// <summary>20 /// 随机在空位生成一个数字21 /// </summary>22 /// <returns></returns>23 private int GenerateNum()24 {25 var ls = new List<(int x, int y)>(R * C);26 for (int x = 0; x < R; x++)27 {28 for (int y = 0; y < C; y++)29 {30 if (_bs[x, y] == 0) ls.Add((x,y));31 }32 } 33 34 var xy = ls[_rnd.Next(ls.Count)];35 _bs[xy.x, xy.y] = _rnd.Next(10) == 9 ? 4 : 2;36 return ls.Count - 1;37 38 }
View Code
因为这个判定必然发生在随机生成数字之后，即上面move返回true时，那么调用代码：
1 if (move && State != GameState.Succ)2 { 3 //有移动 随机在空位生成数字4 var emptyNum = GenerateNum();5 6 //判断是否结束7 if(emptyNum == 0) CheckGame();8 }
View Code
Game类：
1 using System; 2 using System.Collections.Generic; 3 using System.Linq; 4 using System.Text; 5 using System.Threading.Tasks; 6 7 namespace _2048 8 { 9 public enum MoveDirection{ 10 Up, 11 Down, 12 Left, 13 Right 14 } 15 16 public enum GameState 17 { 18 None, 19 Fail, 20 Succ, 21 } 22 23 public class Game 24 { 25 public static int R = 4, C = 4; 26 27 private int[,] _bs; 28 private Random _rnd = new Random(); 29 public GameState State = GameState.None; 30 public int Score, Steps; 31 public (MoveDirection direction, int[,] data)? Log; 32 public bool ShowPre; 33 34 public Game() 35 { 36 Restart(); 37 } 38 39 public unsafe void Move(MoveDirection direction) 40 { 41 if (State != GameState.None) return; 42 43 var move = false; 44 var bs = (int[,])_bs.Clone(); 45 46 switch (direction) 47 { 48 case MoveDirection.Up: 49 move = Move(C, 0, R - 1, 1, (x, y) => { 50 fixed (int* _ = &_bs[0, 0]) 51 { 52 return (IntPtr)(_ + y * C + x); 53 } 54 }); 55 break; 56 case MoveDirection.Down: 57 move = Move(C, R - 1, 0, -1, (x, y) => { 58 fixed (int* _ = &_bs[0,0]) 59 { 60 return (IntPtr)(_ + y * C + x); 61 } 62 }); 63 break; 64 case MoveDirection.Left: 65 move = Move(R, 0, C - 1, 1, (x, y) => { 66 fixed (int* _ = &_bs[0, 0]) 67 { 68 return (IntPtr)(_ + x * C + y); 69 } 70 }); 71 break; 72 case MoveDirection.Right: 73 move = Move(R, C - 1, 0, -1, (x,y)=> { 74 fixed(int* _ = &_bs[0, 0]) 75 { 76 return (IntPtr)(_ + x * C + y); 77 } 78 }); 79 break; 80 } 81 82 if (move && State != GameState.Succ) 83 { 84 Steps++; 85 86 Log = (direction, bs); 87 88 //有移动 随机中空位生成数字 89 var emptyNum = GenerateNum(); 90 91 //判断是否结束 92 if(emptyNum == 0) CheckGame(); 93 } 94 } 95 96 /// <summary> 97 /// 判断是否可以合并 98 /// </summary> 99 private void CheckGame()100 {101 //是否已经填满 并且无法移动102 for (int x = 0; x < R; x++)103 {104 for (int y = 0; y < C; y++)105 {106 if (y < C - 1 && _bs[x, y] == _bs[x, y + 1]) return;107 if (x < R - 1 && _bs[x, y] == _bs[x + 1, y]) return;108 }109 }110 111 State = GameState.Fail;112 }113 114 /// <summary>115 /// 随机在空位生成一个数字116 /// </summary>117 /// <returns></returns>118 private int GenerateNum()119 {120 var ls = new List<(int x, int y)>(R * C);121 for (int x = 0; x < R; x++)122 {123 for (int y = 0; y < C; y++)124 {125 if (_bs[x, y] == 0) ls.Add((x,y));126 }127 }128 129 Shuffle(ls);130 131 var xy = ls[_rnd.Next(ls.Count)];132 _bs[xy.x, xy.y] = _rnd.Next(10) == 9 ? 4 : 2;133 return ls.Count - 1;134 135 }136 137 private IList<T> Shuffle<T>(IList<T> arr)138 {139 for (var i = 0; i < arr.Count; i++)140 {141 var index = _rnd.Next(arr.Count);142 var tmp = arr[i];143 arr[i] = arr[index];144 arr[index] = tmp;145 }146 147 return arr;148 }149 150 /// <summary>151 /// 152 /// </summary>153 /// <param name="si">开始索引</param>154 /// <param name="ei">结束索引</param>155 /// <param name="step">方向</param>156 /// <param name="getInt">取值(重定义[x,y]可以保持算法通用 同时满足x,y方向的移动)</param>157 /// <returns></returns>158 private unsafe bool Move(int loop, int si, int ei, int step, Func<int, int, IntPtr> getInt)159 { 160 //算法基于左向移动161 162 bool moved = false; 163 164 for (int x = 0; x < loop; x++)165 { 166 //第一步 合并167 for (int y = si; y * step < ei; y+=step)168 {169 var val1 = (int*)getInt(x, y);170 171 if (*val1 != 0)172 {173 for (var y2 = y + step; y2 != ei + step; y2 += step)174 { 175 var val2 = (int*)getInt(x, y2);176 //忽略0177 if (*val2 == 0) continue;178 //合并179 if (*val1 == *val2)180 {181 *val1 *= 2;182 *val2 = 0;183 moved = true;184 185 Score += *val1;186 187 if (*val1 == 2048) State = GameState.Succ;188 189 //移动处理列索引190 y = y2;191 }192 else y = y2 - step;//不相等193 break;194 }195 } 196 197 }198 199 //第二步 往0位上移动 200 int? lastY = null;201 for (int y = si; y != ei; y += step)202 {203 var val1 = (int*)getInt(x, y);204 205 if (*val1 == 0)206 {207 var y2 = lastY ?? y + step;208 for (; y2 != ei + step; y2 += step)209 {210 var val2 = (int*)getInt(x, y2);211 212 if (*val2 != 0)213 {214 *val1 = *val2;215 *val2 = 0;216 moved = true;217 218 lastY = y2 + step;219 break; 220 }221 }222 //最后一列了223 if (y2 == ei) break;224 } 225 }226 } 227 228 return moved;229 } 230 231 /// <summary>232 /// 重启游戏233 /// </summary>234 public void Restart()235 {236 Score = Steps = 0;237 State = GameState.None;238 Log = null;239 240 _bs = new int[R, C];241 242 for (int i = 0; i < 2; i++)243 {244 var x = _rnd.Next(R);245 var y = _rnd.Next(C);246 if (_bs[x, y] == 0) _bs[x, y] = _rnd.Next(10) == 0 ? 4 : 2;247 else i--;248 }249 }250 251 public void RandNum()252 {253 for (int x = 0; x < R; x++)254 {255 for (int y = 0; y < C; y++)256 {257 _bs[x, y] = (int)Math.Pow(2, _rnd.Next(12));258 } 259 }260 }261 262 public void Show()263 {264 Console.SetCursorPosition(0, 0);265 266 Console.WriteLine($"得分：{Score} 步数：{Steps} [R]键显示上一步操作记录(当前：{ShowPre}) ");267 268 Console.WriteLine();269 270 271 Console.WriteLine(new string(‘-‘, C * 5));272 for (int x = 0; x < R; x++)273 {274 for (int y = 0; y < C; y++)275 {276 var b = _bs[x, y];277 Console.Write($"{(b == 0 ? " " : b.ToString()),4}|");278 } 279 Console.WriteLine();280 Console.WriteLine(new string(‘-‘, C * 5)); 281 }282 283 if (ShowPre && Log != null)284 {285 Console.WriteLine();286 Console.WriteLine(new string(‘=‘, 100));287 Console.WriteLine();288 289 var bs = Log?.data;290 291 Console.WriteLine($"方向：{Log?.direction} ");292 Console.WriteLine();293 294 Console.WriteLine(new string(‘-‘, C * 5));295 for (int x = 0; x < R; x++)296 {297 for (int y = 0; y < C; y++)298 {299 var b = bs[x, y];300 Console.Write($"{(b == 0 ? " " : b.ToString()),4}|");301 }302 Console.WriteLine();303 Console.WriteLine(new string(‘-‘, C * 5));304 } 305 }306 307 }308 309 }310 }
View Code
Main入口：
1 static void Main(string[] args) 2 { 3 Game.R = 4; 4 Game.C = 4; 5 6 var game = new Game(); 7 8 while (true) 9 {10 game.Show();11 12 var key = Console.ReadKey();13 switch (key.Key)14 {15 case ConsoleKey.UpArrow:16 game.Move(MoveDirection.Up);17 break;18 case ConsoleKey.DownArrow:19 game.Move(MoveDirection.Down);20 break;21 case ConsoleKey.RightArrow:22 game.Move(MoveDirection.Right);23 break;24 case ConsoleKey.LeftArrow:25 game.Move(MoveDirection.Left);26 break;27 case ConsoleKey.R:28 game.ShowPre = !game.ShowPre;29 break;30 31 }32 if (game.State == GameState.None) continue;33 34 game.Show();35 36 var res = MessageBox.Show("需要重新开始吗？", game.State == GameState.Succ ? "恭喜你！！！成功过关！！！" : "很遗憾！！！失败了！！！",MessageBoxButtons.YesNo);37 if (res == DialogResult.Yes)38 {39 game.Restart();40 continue;41 }42 break;43 }44 45 Console.ReadKey();46 }
View Code
![[acwing#24]机器人的运动范围（BFS-DFS）](https://www.winkp.com/wp-content/themes/ZTMao.com-M1-V2.5.1-1230/timthumb.php?src=https://www.winkp.com/wp-content/themes/ZTMao.com-M1-V2.5.1-1230/img/random/1.jpg&w=218&h=124&zc=1)
