【算法】从推箱子的解答步骤还原关卡地图-白红宇

【算法】从推箱子的解答步骤还原关卡地图

阅读量：5934 次

发布时间：2019-06-19

本文共 10915 字，大约阅读时间需要 36 分钟。

推箱子游戏简介

是一款经典的电子游戏，要求玩家在二维地图上把箱子推到指定地点，当中牵涉到大量的空间逻辑推理。是一个非常不错的在线推箱子的网页。推箱子关卡一般用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.Game006:  {007:    public sealed class Lurd2Xsb008:    {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。

程序使用示例

比如说网页上 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;02:  using System.IO;03:  using System.Text;04:  05:  namespace Skyiv.Ben.Game06:  {07:    sealed class Xsb2Bxa08:    {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:        try81:        {82:          new Xsb2Bxa().Run();83:        }84:        catch (Exception ex)85:        {86:          Console.WriteLine(ex.Message);87:        }88:      }89:    }90:  }