1.分析
最近心血来潮,突然想写一个2048小游戏。于是搜索了一个在线2048玩玩,熟悉熟悉规则。
只谈核心规则:(以左移为例)
1.1合并
以行为单位,忽略0位,每列依次向左进行合并,且每列只能合并一次。被合并列置0。
1.2移动
每列依次向左往0位上移动,不限次数。
1.3判定
[成功]就是合并后值为2048,[失败]则是没有任何一个方向上能进行合并或者移动了。
2.实现
成品截图如下
一样只谈核心的东西。网上大多数的实现算法有这么几种。
2.1为每个方向上的合并和移动实现一个算法。
这种太过繁琐,其实算法逻辑都差不多,只是方向不同而已,冗余代码太多
2.2以某一个方向作为算法基础,其他方向进行矩阵旋转,直到和基础算法方向一致,处理完成之后,再旋转矩阵到原来方向。
这种做到了各个方向上一定的通用,但是增加了额外的两次矩阵运算。
其实只需实现一个方向的算法,然后抽离出和方向有关的变量,封装为参数,通过参数控制方向。
比如左方向:以行为单位,处理每列的数据。那么第一层循环将是按行的数量进行迭代。处理列索引将是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 //忽略0 20 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 }
调用的核心代码:
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 }
2.3结果判定
网上大多数的算法都是复制一份矩阵数据,然后依次从各个方向上进行合并和移动,之后和原矩阵进行比较,如果数据相同则说明没有变化,从而判定失败。
这种太复杂,太死板了,太低效了。仔细分析可知,失败的判定其实很简单:
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 }
因为这个判定必然发生在随机生成数字之后,即上面move返回true时,那么调用代码:
1 if (move && State != GameState.Succ) 2 { 3 //有移动 随机在空位生成数字 4 var emptyNum = GenerateNum(); 5 6 //判断是否结束 7 if(emptyNum == 0) CheckGame(); 8 }
3.完整的代码如下:
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 //忽略0 177 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 }
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 }