【算法】从推箱子的解答步骤还原关卡地图 - 银河 - 博客园
推箱子游戏简介 是一款经典的电子游戏，要求玩家在二维地图上把箱子推到指定地点，当中牵涉到大量的空间逻辑推理。 是一个非常不错的在线推箱子的网页。推箱子关卡一般用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.T
using System.D
namespace Skyiv.Ben.Game
public sealed class Lurd2Xsb
void SetBrick(byte[,] map, int x, int y) { map[x, y] = 8; }
void SetFloor(byte[,] map, Point pt) { map[pt.X, pt.Y] |= 1; }
void SetGoal(byte[,] map, Point pt) { map[pt.X, pt.Y] |= 2; }
void SetBox(byte[,] map, Point pt) { map[pt.X, pt.Y] |= 4; }
void UnsetBox(byte[,] map, Point pt) { map[pt.X, pt.Y] &= 0xFB; }
bool HasBox(byte[,] map, int x, int y) { return (map[x, y] & 4) != 0; }
bool IsGoal(byte[,] map, int x, int y) { return (map[x, y] & 2) != 0; }
bool IsFloor(byte[,] map, int x, int y) { return (map[x, y] & 1) != 0; }
bool IsBrick(byte[,] map, int x, int y) { return map[x, y] == 8; }
bool IsWall(byte[,] map, int x, int y) { return map[x, y] == 0; }
bool IsBrickOrWall(byte[,] map, int x, int y) { return IsBrick(map, x, y) || IsWall(map, x, y); }
void MarkBrick(byte[,] map, int x, int y)
if (!IsWall(map, x, y)) return;
if (!IsBrickOrWall(map, x - 1, y - 1)) return;
if (!IsBrickOrWall(map, x - 1, y + 1)) return;
if (!IsBrickOrWall(map, x + 1, y - 1)) return;
if (!IsBrickOrWall(map, x + 1, y + 1)) return;
if (!IsBrickOrWall(map, x - 1, y)) return;
if (!IsBrickOrWall(map, x + 1, y)) return;
if (!IsBrickOrWall(map, x, y - 1)) return;
if (!IsBrickOrWall(map, x, y + 1)) return;
SetBrick(map, x, y);
int GetX(byte[,] map, int y0, int y1, int x, int x2)
for (var y = y0; y & y1; y++)
if (!IsBrick(map, x, y)) return x;
return x2;
int GetY(byte[,] map, int x0, int x1, int y, int y2)
for (var x = x0; x & x1; x++)
if (!IsBrick(map, x, y)) return y;
return y2;
Rectangle GetRectangle(byte[,] map)
int x0 = 1, y0 = 1, x1 = map.GetLength(0) - 2, y1 = map.GetLength(1) - 2;
x0 = GetX(map, y0, y1, x0, x0 + 1);
x1 = GetX(map, y0, y1, x1, x1 - 1);
y0 = GetY(map, x0, x1, y0, y0 + 1);
y1 = GetY(map, x0, x1, y1, y1 - 1);
return Rectangle.FromLTRB(x0, y0, x1, y1);
string GetXsb(byte[,] map, Point man)
var rect = GetRectangle(map);
for (var y = rect.T y &= rect.B y++)
for (var x = rect.L x &= rect.R x++)
MarkBrick(map, x, y);
rect = GetRectangle(map);
var xsb = new StringBuilder();
for (var y = rect.T y &= rect.B y++)
for (var x = rect.L x &= rect.R x++)
if (IsGoal(map, x, y))
if (man.X == x && man.Y == y) xsb.Append('+');
else if (HasBox(map, x, y)) xsb.Append('*');
else xsb.Append('.');
else if (IsFloor(map, x, y))
if (man.X == x && man.Y == y) xsb.Append('@');
else if (HasBox(map, x, y)) xsb.Append('$');
else xsb.Append('-');
else if (IsBrick(map, x, y)) xsb.Append('_');
else xsb.Append('#');
xsb.AppendLine();
return xsb.ToString();
void LeftOrRight(byte[,] map, ref Point man, int step)
if (HasBox(map, man.X, man.Y)) UnsetBox(map, man);
else SetGoal(map, man);
SetBox(map, man);
SetFloor(map, man);
void UpOrDown(byte[,] map, ref Point man, int step)
if (HasBox(map, man.X, man.Y)) UnsetBox(map, man);
else SetGoal(map, man);
SetBox(map, man);
SetFloor(map, man);
byte[,] GetMap(string lurd, Size size, ref Point man)
var map = new byte[size.Width, size.Height];
SetFloor(map, man);
for (var i = lurd.Length - 1; i &= 0; i--)
switch (lurd[i])
case 'l': man.X++; SetFloor(map, man); break;
case 'r': man.X--; SetFloor(map, man); break;
case 'u': man.Y++; SetFloor(map, man); break;
case 'd': man.Y--; SetFloor(map, man); break;
case 'L': LeftOrRight(map, ref man, -1); break;
case 'R': LeftOrRight(map, ref man, 1); break;
case 'U': UpOrDown(map, ref man, -1); break;
case 'D': UpOrDown(map, ref man, 1); break;
Rectangle GetBoundary(string lurd)
var boundary = new Rectangle(0, 0, 1, 1);
var man = new Point();
for (var i = lurd.Length - 1; i &= 0; i--)
switch (lurd[i])
case 'l': case 'L': man.X++; if (boundary.Right &= man.X) boundary.Width++; break;
case 'r': case 'R': man.X--; if (boundary.Left & man.X) { boundary.Width++; boundary.X--; } break;
case 'u': case 'U': man.Y++; if (boundary.Bottom &= man.Y) boundary.Height++; break;
case 'd': case 'D': man.Y--; if (boundary.Top & man.Y) { boundary.Height++; boundary.Y--; } break;
public string GetXsbFromLurd(string lurd)
var boundary = GetBoundary(lurd);
var size = new Size(boundary.Width + 6, boundary.Height + 6);
var man = new Point(3 - boundary.X, 3 - boundary.Y);
var map = GetMap(lurd, size, ref man);
return GetXsb(map, man);
static void Main()
Console.Write(new Lurd2Xsb().GetXsbFromLurd(Console.In.ReadToEnd()));
简要说明：
GetXsbFromLurd 方法根据输入的LURD数据还原出XSB格式的最简关卡地图。
GetBoundary 方法根据输入的LURD数据计算出地图的边界。
GetMap 方法根据输入的LURD数据生成关卡地图的二维字节数组表示。
LeftOrRight 和 UpOrDown 方法处理LURD数据中推动箱子的步骤。
GetXsb 方法根据关卡地图的二维字节数组表示生成XSB格式数据。
GetRectangle 方法判断二维字节数组中实际表示数据的边界范围。
MarkBrick 方法标记砖块(相当于人不可到达的空地，作用和墙是一样的)。
第 9 到 19 行的一系列 SetXXX 和 IsXXX 等方法都是简单地对二维字节数组操作。
这个程序的主要算法体现在 GetMap 方法中，要点是：
整个地图初始化为 wall 。
从解法步骤的最后一步往前倒推，直到第一步。
人所走过的每一步的位置都标记为 floor。
如果步骤是大写字母，即有推动箱子，则人的当前位置标记为箱子。根据前进方向上是否有箱子设置该前进方向的位置：
有箱子，则移出箱子。
无箱子，则标记为 goal。
程序使用示例
网页上 m1 关卡集第 12 关如下所示：
经过49步后通关，其LURD数据如下所示(m1-12.lurd)：uululldRdRluurDrDDrddlluRuuulldRurDDrrrddllUdlluR
那么，我们执行以下命令：Lurd2Xsb.exe & m1-12.lurd & m1-12.xsb
得到的XSB数据如下所示：#####____
将以上XSB数据在
网页上载入关卡，如下图所示：
可见该程序较好地还原了关卡地图。
不能准确还原的情况
网页中 m1 关卡集的第 107 关。右图是使用本程序还原以下解法步骤(44 moves, 10 pushs)的结果：lllURuulDrddrruuuuullDDDuuulllddRRdrUllluurD
可以看出，这两个图有很大的不同。原因是该关卡中有十个箱子已经在目标点中，而且其中的六个箱子在解答过程中没有被推动过，自然就被本程序判断为墙了。如果需要准确还原出左图的关卡地图，可以使用以下解法步骤(138 moves, 22 pushs)：lllURuulDrddrruuuuulllDurrrdddddlluulUrdddrruuuuullDDDuuulllddRRdrUllluurrrrrddLrdLruuulDrddlUruulllllddrrRldRlulldRlddrUluurDurrdLulluurD
解法步骤不合法的情况
上面三幅关卡地图分别是从“LURD”、“Rrr”和“RL”解法步骤中还原出来的。对于这些不合法的解法步骤，本程序也不报错。本程序只保证合法的解法步骤能够还原出正确的关卡地图。此外，本程序还忽略解法步骤中“lurdLURD”以外的所有字符。
智能手机上的推箱子程序
2007年10月我还写了系列随笔：。当时使用的数据格式有所不同，但是可以写一个简单的 Xsb2Bxa 程序来进行转换。下图就是转换后载入到 PushBox 软件中的其中一个关卡：
下面就是 Xsb2Bxa.cs 程序：01:
using System.IO;
using System.T
namespace Skyiv.Ben.Game
sealed class Xsb2Bxa
void TransformXsb(string name, StringBuilder sb)
foreach (var line in File.ReadLines(name + ".xsb"))
if (line.Length == 0) continue;
foreach (var c in line)
switch (c)
case '#': sb.Append('#'); break;
case '@': sb.Append('('); break;
case '+': sb.Append(')'); break;
case '$': sb.Append('x'); break;
case '*': sb.Append('X'); break;
case '.': sb.Append('+'); break;
case '-': sb.Append('-'); break;
case ' ': sb.Append('-'); break;
case '_': sb.Append('%'); break;
sb.AppendLine();
void TransformLurd(string name, StringBuilder sb)
var file = name + ".lurd";
if (!File.Exists(file)) return;
sb.Append(':');
foreach (var c in File.ReadAllText(file))
switch (c)
case 'l': sb.Append('N'); break;
case 'u': sb.Append('O'); break;
case 'r': sb.Append('L'); break;
case 'd': sb.Append('M'); break;
case 'L': sb.Append('S'); break;
case 'U': sb.Append('T'); break;
case 'R': sb.Append('Q'); break;
case 'D': sb.Append('R'); break;
sb.AppendLine();
string GetBxaFromXsbAndLurd(string name)
var sb = new StringBuilder();
TransformXsb(name, sb);
TransformLurd(name, sb);
return sb.ToString();
void Run()
using (var sw = new StreamWriter("ben.bxa", false, Encoding.GetEncoding("GB2312")))
sw.WriteLine("!银河");
var count = 0;
foreach (var file in Directory.GetFiles(".", "*.xsb"))
var name = Path.GetFileNameWithoutExtension(file);
sw.WriteLine("'[{0}] {1}",
++count, name);
sw.WriteLine(GetBxaFromXsbAndLurd(name));
static void Main()
new Xsb2Bxa().Run();
catch (Exception ex)
Console.WriteLine(ex.Message);
源代码下载
本文中的所有源代码可以到
页面下载。
也可以使用 hg clone
命令下载。
关于 hg ，请参阅 。 上传我的文档
 下载
 收藏
该文档贡献者很忙，什么也没留下。
 下载此文档
正在努力加载中...
[精品]推箱子游戏需求分析报告
下载积分：420
内容提示：[精品]推箱子游戏需求分析报告
文档格式：DOC|
浏览次数：6|
上传日期： 01:23:20|
文档星级：
该用户还上传了这些文档
[精品]推箱子游戏需求分析报告
官方公共微信