推箱子游戏简介
推箱子是一款经典的电子游戏,要求玩家在二维地图上把箱子推到指定地点,当中牵涉到大量的空间逻辑推理。HTML5 Sokoban 是一个非常不错的在线推箱子的网页。推箱子关卡一般用XSB格式来保存和交流,解答步骤则使用LURD格式,请参见:XSB和LURD格式简介。
XSB格式规定使用以下符号:
- @ ==> 人 man
- + ==> 人在目标点 man on goal
- $ ==> 箱子 box
- * ==> 箱子在目标点 box on goal
- # ==> 墙 wall
- . ==> 目标点 goal
- - ==> 地板 floor,还可以使用空格或者下划线表示。
LURD格式规定使用以下八个拉丁字母(小写字母表示移动,大写字母表示推动):
- l 或 L ==> 左 Left
- r 或 R ==> 右 Right
- u 或 U ==> 上 Up
- d 或 D ==> 下 Down
从解答步骤还原关卡地图
有一天,我突然想到,能不能从推箱子的解答步骤还原出关卡地图来呢?因为LURD数据已经包含了足够的信息,可以据此还原出一个最简的关卡地图出来。下面就是实现这个想法的 Lurd2Xsb.cs 程序:
001: using System; 002: using System.Text; 003: using System.Drawing; 004: 005: namespace Skyiv.Ben.Game 006: { 007: public sealed class Lurd2Xsb 008: { 009: void SetBrick(byte[,] map, int x, int y) { map[x, y] = 8; } 010: void SetFloor(byte[,] map, Point pt) { map[pt.X, pt.Y] |= 1; } 011: void SetGoal(byte[,] map, Point pt) { map[pt.X, pt.Y] |= 2; } 012: void SetBox(byte[,] map, Point pt) { map[pt.X, pt.Y] |= 4; } 013: void UnsetBox(byte[,] map, Point pt) { map[pt.X, pt.Y] &= 0xFB; } 014: bool HasBox(byte[,] map, int x, int y) { return (map[x, y] & 4) != 0; } 015: bool IsGoal(byte[,] map, int x, int y) { return (map[x, y] & 2) != 0; } 016: bool IsFloor(byte[,] map, int x, int y) { return (map[x, y] & 1) != 0; } 017: bool IsBrick(byte[,] map, int x, int y) { return map[x, y] == 8; } 018: bool IsWall(byte[,] map, int x, int y) { return map[x, y] == 0; } 019: bool IsBrickOrWall(byte[,] map, int x, int y) { return IsBrick(map, x, y) || IsWall(map, x, y); } 020: 021: void MarkBrick(byte[,] map, int x, int y) 022: { 023: if (!IsWall(map, x, y)) return; 024: if (!IsBrickOrWall(map, x - 1, y - 1)) return; 025: if (!IsBrickOrWall(map, x - 1, y + 1)) return; 026: if (!IsBrickOrWall(map, x + 1, y - 1)) return; 027: if (!IsBrickOrWall(map, x + 1, y + 1)) return; 028: if (!IsBrickOrWall(map, x - 1, y)) return; 029: if (!IsBrickOrWall(map, x + 1, y)) return; 030: if (!IsBrickOrWall(map, x, y - 1)) return; 031: if (!IsBrickOrWall(map, x, y + 1)) return; 032: SetBrick(map, x, y); 033: } 034: 035: int GetX(byte[,] map, int y0, int y1, int x, int x2) 036: { 037: for (var y = y0; y < y1; y++) 038: if (!IsBrick(map, x, y)) return x; 039: return x2; 040: } 041: 042: int GetY(byte[,] map, int x0, int x1, int y, int y2) 043: { 044: for (var x = x0; x < x1; x++) 045: if (!IsBrick(map, x, y)) return y; 046: return y2; 047: } 048: 049: Rectangle GetRectangle(byte[,] map) 050: { 051: int x0 = 1, y0 = 1, x1 = map.GetLength(0) - 2, y1 = map.GetLength(1) - 2; 052: x0 = GetX(map, y0, y1, x0, x0 + 1); 053: x1 = GetX(map, y0, y1, x1, x1 - 1); 054: y0 = GetY(map, x0, x1, y0, y0 + 1); 055: y1 = GetY(map, x0, x1, y1, y1 - 1); 056: return Rectangle.FromLTRB(x0, y0, x1, y1); 057: } 058: 059: string GetXsb(byte[,] map, Point man) 060: { 061: var rect = GetRectangle(map); 062: for (var y = rect.Top; y <= rect.Bottom; y++) 063: for (var x = rect.Left; x <= rect.Right; x++) 064: MarkBrick(map, x, y); 065: rect = GetRectangle(map); 066: var xsb = new StringBuilder(); 067: for (var y = rect.Top; y <= rect.Bottom; y++) 068: { 069: for (var x = rect.Left; x <= rect.Right; x++) 070: { 071: if (IsGoal(map, x, y)) 072: { 073: if (man.X == x && man.Y == y) xsb.Append(\'+\'); 074: else if (HasBox(map, x, y)) xsb.Append(\'*\'); 075: else xsb.Append(\'.\'); 076: } 077: else if (IsFloor(map, x, y)) 078: { 079: if (man.X == x && man.Y == y) xsb.Append(\'@\'); 080: else if (HasBox(map, x, y)) xsb.Append(\'$\'); 081: else xsb.Append(\'-\'); 082: } 083: else if (IsBrick(map, x, y)) xsb.Append(\'_\'); 084: else xsb.Append(\'#\'); 085: } 086: xsb.AppendLine(); 087: } 088: return xsb.ToString(); 089: } 090: 091: void LeftOrRight(byte[,] map, ref Point man, int step) 092: { 093: man.X += step; 094: if (HasBox(map, man.X, man.Y)) UnsetBox(map, man); 095: else SetGoal(map, man); 096: man.X -= step; 097: SetBox(map, man); 098: man.X -= step; 099: SetFloor(map, man); 100: } 101: 102: void UpOrDown(byte[,] map, ref Point man, int step) 103: { 104: man.Y += step; 105: if (HasBox(map, man.X, man.Y)) UnsetBox(map, man); 106: else SetGoal(map, man); 107: man.Y -= step; 108: SetBox(map, man); 109: man.Y -= step; 110: SetFloor(map, man); 111: } 112: 113: byte[,] GetMap(string lurd, Size size, ref Point man) 114: { 115: var map = new byte[size.Width, size.Height]; 116: SetFloor(map, man); 117: for (var i = lurd.Length - 1; i >= 0; i--) 118: { 119: switch (lurd[i]) 120: { 121: case \'l\': man.X++; SetFloor(map, man); break; 122: case \'r\': man.X--; SetFloor(map, man); break; 123: case \'u\': man.Y++; SetFloor(map, man); break; 124: case \'d\': man.Y--; SetFloor(map, man); break; 125: case \'L\': LeftOrRight(map, ref man, -1); break; 126: case \'R\': LeftOrRight(map, ref man, 1); break; 127: case \'U\': UpOrDown(map, ref man, -1); break; 128: case \'D\': UpOrDown(map, ref man, 1); break; 129: } 130: } 131: return map; 132: } 133: 134: Rectangle GetBoundary(string lurd) 135: { 136: var boundary = new Rectangle(0, 0, 1, 1); 137: var man = new Point(); 138: for (var i = lurd.Length - 1; i >= 0; i--) 139: { 140: switch (lurd[i]) 141: { 142: case \'l\': case \'L\': man.X++; if (boundary.Right <= man.X) boundary.Width++; break; 143: case \'r\': case \'R\': man.X--; if (boundary.Left > man.X) { boundary.Width++; boundary.X--; } break; 144: case \'u\': case \'U\': man.Y++; if (boundary.Bottom <= man.Y) boundary.Height++; break; 145: case \'d\': case \'D\': man.Y--; if (boundary.Top > man.Y) { boundary.Height++; boundary.Y--; } break; 146: } 147: } 148: return boundary; 149: } 150: 151: public string GetXsbFromLurd(string lurd) 152: { 153: var boundary = GetBoundary(lurd); 154: var size = new Size(boundary.Width + 6, boundary.Height + 6); 155: var man = new Point(3 - boundary.X, 3 - boundary.Y); 156: var map = GetMap(lurd, size, ref man); 157: return GetXsb(map, man); 158: } 159: 160: static void Main() 161: { 162: Console.Write(new Lurd2Xsb().GetXsbFromLurd(Console.In.ReadToEnd())); 163: } 164: } 165: }
简要说明:
- GetXsbFromLurd 方法根据输入的LURD数据还原出XSB格式的最简关卡地图。
- GetBoundary 方法根据输入的LURD数据计算出地图的边界。
- GetMap 方法根据输入的LURD数据生成关卡地图的二维字节数组表示。
- LeftOrRight 和 UpOrDown 方法处理LURD数据中推动箱子的步骤。
- GetXsb 方法根据关卡地图的二维字节数组表示生成XSB格式数据。
- GetRectangle 方法判断二维字节数组中实际表示数据的边界范围。
- MarkBrick 方法标记砖块(相当于人不可到达的空地,作用和墙是一样的)。
- 第 9 到 19 行的一系列 SetXXX 和 IsXXX 等方法都是简单地对二维字节数组操作。
这个程序的主要算法体现在 GetMap 方法中,要点是:
- 整个地图初始化为 wall 。
- 从解法步骤的最后一步往前倒推,直到第一步。
- 人所走过的每一步的位置都标记为 floor。
- 如果步骤是大写字母,即有推动箱子,则人的当前位置标记为箱子。根据前进方向上是否有箱子设置该前进方向的位置:
- 有箱子,则移出箱子。
- 无箱子,则标记为 goal。
程序使用示例
比如说 HTML5 Sokoban 网页上 m1 关卡集第 12 关如下所示:
经过49步后通关,其LURD数据如下所示(m1-12.lurd):
uululldRdRluurDrDDrddlluRuuulldRurDDrrrddllUdlluR
那么,我们执行以下命令:
Lurd2Xsb.exe < m1-12.lurd > m1-12.xsb
得到的XSB数据如下所示:
#####____ #---##___ #-$--#___ ##-$-#### _###@.--# __#--.#-# __#-----# __#######
将以上XSB数据在 HTML5 Sokoban 网页上载入关卡,如下图所示:
可见该程序较好地还原了关卡地图。
不能准确还原的情况
左图是 HTML5 Sokoban 网页中 m1 关卡集的第 107 关。右图是使用本程序还原以下解法步骤(44 moves, 10 pushs)的结果:
lllURuulDrddrruuuuullDDDuuulllddRRdrUllluurD
可以看出,这两个图有很大的不同。原因是该关卡中有十个箱子已经在目标点中,而且其中的六个箱子在解答过程中没有被推动过,自然就被本程序判断为墙了。如果需要准确还原出左图的关卡地图,可以使用以下解法步骤(138 moves, 22 pushs):
lllURuulDrddrruuuuulllDurrrdddddlluulUrdddrruuuuullDDDuuulllddRRdrUllluurrrrrddLrdLruuulDrddlUruulllllddrrRldRlulldRlddrUluurDurrdLulluurD
解法步骤不合法的情况
上面三幅关卡地图分别是从“LURD”、“Rrr”和“RL”解法步骤中还原出来的。对于这些不合法的解法步骤,本程序也不报错。本程序只保证合法的解法步骤能够还原出正确的关卡地图。此外,本程序还忽略解法步骤中“lurdLURD”以外的所有字符。
智能手机上的推箱子程序
2007年10月我还写了系列随笔:使用 C# 开发智能手机软件:推箱子。当时使用的数据格式有所不同,但是可以写一个简单的 Xsb2Bxa 程序来进行转换。下图就是转换后载入到 PushBox 软件中的其中一个关卡:
下面就是 Xsb2Bxa.cs 程序:
01: using System; 02: using System.IO; 03: using System.Text; 04: 05: namespace Skyiv.Ben.Game 06: { 07: sealed class Xsb2Bxa 08: { 09: void TransformXsb(string name, StringBuilder sb) 10: { 11: foreach (var line in File.ReadLines(name + ".xsb")) 12: { 13: if (line.Length == 0) continue; 14: foreach (var c in line) 15: { 16: switch (c) 17: { 18: case \'#\': sb.Append(\'#\'); break; 19: case \'@\': sb.Append(\'(\'); break; 20: case \'+\': sb.Append(\')\'); break; 21: case \'$\': sb.Append(\'x\'); break; 22: case \'*\': sb.Append(\'X\'); break; 23: case \'.\': sb.Append(\'+\'); break; 24: case \'-\': sb.Append(\'-\'); break; 25: case \' \': sb.Append(\'-\'); break; 26: case \'_\': sb.Append(\'%\'); break; 27: } 28: } 29: sb.AppendLine(); 30: } 31: } 32: 33: void TransformLurd(string name, StringBuilder sb) 34: { 35: var file = name + ".lurd"; 36: if (!File.Exists(file)) return; 37: sb.Append(\':\'); 38: foreach (var c in File.ReadAllText(file)) 39: { 40: switch (c) 41: { 42: case \'l\': sb.Append(\'N\'); break; 43: case \'u\': sb.Append(\'O\'); break; 44: case \'r\': sb.Append(\'L\'); break; 45: case \'d\': sb.Append(\'M\'); break; 46: case \'L\': sb.Append(\'S\'); break; 47: case \'U\': sb.Append(\'T\'); break; 48: case \'R\': sb.Append(\'Q\'); break; 49: case \'D\': sb.Append(\'R\'); break; 50: } 51: } 52: sb.AppendLine(); 53: } 54: 55: string GetBxaFromXsbAndLurd(string name) 56: { 57: var sb = new StringBuilder(); 58: TransformXsb(name, sb); 59: TransformLurd(name, sb); 60: return sb.ToString(); 61: } 62: 63: void Run() 64: { 65: using (var sw = new StreamWriter("ben.bxa", false, Encoding.GetEncoding("GB2312"))) 66: { 67: sw.WriteLine("!银河"); 68: var count = 0; 69: foreach (var file in Directory.GetFiles(".", "*.xsb")) 70: { 71: var name = Path.GetFileNameWithoutExtension(file); 72: sw.WriteLine("\'[{0}] {1}", ++count, name); 73: sw.WriteLine(GetBxaFromXsbAndLurd(name)); 74: } 75: } 76: } 77: 78: static void Main() 79: { 80: try 81: { 82: new Xsb2Bxa().Run(); 83: } 84: catch (Exception ex) 85: { 86: Console.WriteLine(ex.Message); 87: } 88: } 89: } 90: }
源代码下载
本文中的所有源代码可以到 https://bitbucket.org/ben.skyiv/lurd2xsb/downloads 页面下载。
也可以使用 hg clone https://bitbucket.org/ben.skyiv/lurd2xsb 命令下载。
关于 hg ,请参阅 Mercurial 备忘录。