用LP推箱子解决复杂的难题#（译文）

原文地址：https://www.codeproject.com/Articles/17187/Tackle-Complex-Puzzles-with-LP-Sokobansharp

原文作者：Luc Pattyn

译文由本站 robot-v1.0 翻译

前言

A simple Sokoban implementation in C# with some extras

一个简单的C#Sokoban实现,带有一些额外功能

• 下载源28.2 KB(Download source - 28.2 KB)
• 下载演示项目-18.9 KB(Download demo project - 18.9 KB)

介绍(Introduction)

这是我在CodeProject上的第一篇文章.我想开发一个简单的Sokoban程序,并添加一些功能.我需要用它来解决一些复杂的难题(This is my first article on CodeProject. I wanted to develop a simple Sokoban program with some added features; I needed this to solve some complex puzzles as can be found) 这里(here) (其中一些需要数百步).我看到了机会来展示一些在CodeProject留言板上流行的问题的解决方案.((some of these need hundreds of moves). And I saw the opportunity to demonstrate some solutions to issues that seem popular on the CodeProject message boards.)

推箱子游戏(The Sokoban Game)

推箱子是一种棋盘游戏,具有一个玩家,多个盒子(黄色)和必须移动到相同数量的正方形(“目标”,粉红色).第一个屏幕截图显示了正在进行的游戏.第二个屏幕截图显示了另一个游戏的初始状态;它还具有可见的日志记录列表框.(Sokoban is a board game with one player, a number of boxes (yellow) and an equal number of squares the boxes must be moved to (the “goals”, in pink). The first screen shot shows a game in progress. The second screen shot shows the initial state of another game; it also has the logging listbox visible.) 玩家(红色三角形)可以使用箭头键在板上四处移动:他可以移动到一个空的正方形,也可以在向同一方向推动该盒子的同时移动到一个盒子所占据的正方形(前提是该正方形)盒子前面是空的.一次不能移动两个或更多盒子.播放器的强度不足以一次推入两个箱子,也不能将一个箱子压入墙壁.(The player (the red triangle) can move around on the board by using the arrow keys: he can move to an empty square, or he can move onto a square occupied by a box while pushing the box in the same direction, provided the square ahead of the box is empty. It is impossible to move two or more boxes at a time; the player is not strong enough to push two boxes at once, or to squash a box into the wall.) 挑战在于找到哪个盒子去哪个目标,以什么顺序去.另一个挑战是,移动次数可能会受到限制.(The challenge consists of finding which box goes to which goal, and in what order. As an additional challenge, the number of moves may be restricted.)

该程序(The Program)

该程序非常简单.它不包含任何算法,因为它不能解决难题.它仅显示一个难题,并在用户尝试解决难题时处理用户的移动.(The program is fairly simple. It does not include any algorithm, since it does not solve the puzzle. It merely shows a puzzle and processes the user’s moves while he attempts to solve the puzzle.) 主要分为四类:(There are four major classes:)

• MainForm
• Sokoban
• History
• Board

主窗体(MainForm)

主窗体包含菜单,并处理所有用户输入(菜单单击和键盘输入).它是使用Visual Studio Designer创建的.除了我添加实例的方式外,这里没有什么特别之处(The main form holds the menus, and processes all user input (menu clicks and keyboard input). It was created with the Visual Studio Designer. There is not much special here, except for the way I added an instance of my) Board 类.由于这是从(class. Since this inherits from) Panel ,但并非以(, but was not built as a) Component ,我无法让Designer添加它的实例.所以我只是添加了一个常规(, I could not get the Designer to add an instance of it. So I just added a regular) Panel ,然后以编程方式创建一个(, and then programmatically create a) Board ,给它一样(, gave it the same) Bound s,删除了占位(s, removed the place holding) Panel 并添加了(and added the) Board 到(to the) Control 的集合.(s collection.)

// create a Board panel and replace preliminary panel by it
board=new Board(this, new Logger(log), sokoban);
board.Bounds=prelimBoard.Bounds;
Controls.Remove(prelimBoard);
Controls.Add(board);

这花了4行代码,避免了整个DLL文件.它还允许我首先创建一个实例(That took 4 lines of code and avoided an entire DLL file. It also allowed me to first create an instance of the) Sokoban 类,这是该类的输入参数(class, which is an input parameter to the) Board 构造函数.(constructor.) 的(The) MainForm ,以及(, as well as the) Board 在其中,它是可伸缩的:您可以调整表单的大小,然后即时调整木板(和工程图的比例).打印拼图时,将生成一个页面,其中包含一行文本标题和面板,并按比例缩放以利用大部分页面区域.(in it, are scalable: you can resize the form, and the board (and the scale of the drawing) will be adapted instantaneously. When printing a puzzle, a single page is generated containing a one line text header and the board, scaled to utilize most of the page area.)

推箱子(Sokoban)

的(The) Sokoban 类从文件中读取拼图并实现游戏规则.(class reads puzzles from a file and implements the game rules.) XML文件用于容纳一个或多个难题.(An XML file is used to hold one or more puzzles.) XMLDocument 和(and) XMLReader 类用于获取内存中文件内容的结构化表示.使用与Sokoban Pro中相同的文件结构(请参见确认),因此这两个程序可以共享拼图定义.作为一项附加功能,可以限制移动次数:可选(classes are used to get a structured representation of the file content in memory. The same file structure is used as in Sokoban Pro (see acknowledgements), so both programs can share puzzle definitions. As an added feature, the number of moves can be limited: an optional) MaxMoves 字段已添加到XML文件格式;任何超越(field has been added to the XML file format; any moves beyond) MaxMoves 仍被处决,但会伴有蜂鸣声.(are still executed but get accompanied by a beep.) 游戏规则主要由(The game rules are implemented mainly by the) TryMove(int dx, int dy) 方法,在哪里(method, where) dx 和(and) dy 指示尝试的移动方向(-1\0或+1).由于所有四个方向都使用相同的代码,因此使其正常工作变得很容易.(indicate the attempted move direction (either -1, 0 or +1). Since all four directions use the same code, it becomes rather easy to get them working correctly.) 的(The) Sokoban 类不依赖于二维数组来表示板;相反,它使用了几个(class does not rely on a two-dimensional array to represent the board; instead it uses a couple of) ArrayList ,用于存放Item类的实例,这些实例代表框,目标或玩家本人.这被认为有利于代码的简化和性能.它确实需要一些附加功能,例如:(s to hold instances of the Item class, which represent boxes, goals or the player himself. This was considered beneficial for code simplicity and performance; it did require some additional functions though, such as:)

// is there a goal at (x,y) ?
public bool IsOnGoal(int x, int y) {
   foreach (Item item in goals) 
      if (item.x==x && item.y==y) return true;
   return false;
}

历史(History)

的(The) history 类将移动存储在(class stores the moves in an) ArrayList .它提供撤消/重做功能,因为它可以返回上一个动作或之前已执行的下一个动作.的(. It offers undo/redo functionality, in that it can return the previous move, or the next move that had been executed before. The) History 类本身与应用程序无关,在这种情况下,它跟踪对象(class itself is application independent, it keeps track of objects, in this case) Move 对象((objects () Move 是一门小课程,可以记住dx-dy方向和推入框.(is a little class that remembers a dx-dy direction and a pushed box).)

板(Board)

的(The) Board 课程提供(class offers a) Panel 显示推箱子游戏的当前状态.我选择将可视化与游戏逻辑分开;这样,将来在不损害其他类别的情况下更容易替换一个或另一个.(that displays the current state of the Sokoban game. I have chosen to keep the visualization separate from the game logic; in this way, it should be easier to replace one or the other in future without compromising the other class.) 的(The) Board 是一个轻量级的对象:它不使用控件集合来汇总完整图片,而只是通过使用GDI +调用绘制所有必要的部分(即(is a lightweight object: it does not use a collection of controls to aggregate the complete picture, it merely draws all the necessary parts by using GDI+ calls (i.e., the) Graphics 类).如果您希望用户与这些控件进行交互,则汇总控件非常有用,因为可以为您调度鼠标(和其他)事件.该程序没有鼠标输入(菜单除外),因此如果有的话,板上的控件也不会提供太多优势.(class). Aggregating Controls is great if you want user interaction with those controls, since the mouse (and other) events get dispatched for you; this program does not have mouse input (except for the menus), so controls within the board would not offer much advantage, if any.) 目前,(Currently, the) Board 不使用图像,它仅绘制直线和矩形,如果需要,可以很容易地用更精美的东西代替.(does not use images, it merely draws lines and rectangles, which could easily be replaced by something more fancy, if that is required.)

一些额外的功能(Some Extra Features)

除了基本的显示和移动功能外,还添加了一些功能,这些功能有助于探索并有望解决难题.这些包括撤消/重做,剪切/粘贴和打印.(On top of the basic display and move functionality, some features got added that help exploring and hopefully also solving a puzzle; these include undo/redo, cut/paste and printing.) 编辑菜单项"(The Edit menu items “)撤消(Undo)"(CTRL/Z)和”(" (CTRL/Z) and “)重做(Redo)"(CTRL/Y)将撤消或重做一次移动.将保留完整的移动历史记录,并且可以在路径上回溯并尝试其他操作,而不必从第一个方框重新开始拼图.(” (CTRL/Y) will undo or redo a move. A complete move history is maintained and one can backtrack on a path and try something else, without having to restart the puzzle from square one.) 解决方案尝试被编码为(The solution attempt gets encoded as a) string ,使用字符UDLR表示上/下/左/右.例如,在执行"(, using the characters UDLR for up/down/left/right. For example, the first screen shot was obtained after executing the moves “) DDDLULLULLDDDUUURRDRRDDDLLLLL “.(”. Such a) string 可以使用"编辑"菜单项复制和粘贴”(can be copied and pasted with the Edit menu items “)复制(Copy)"(CTRL/C)和”(" (CTRL/C) and “)糊(Paste)(CTRL/V),因此可以使用某些外部编辑器(如记事本)在文本文档中存储和检索一系列动作.在粘贴一系列动作时,稍有延迟可确保显示中间板状态,从而产生动画效果.(” (CTRL/V), so a series of moves can be stored in, and retrieved from, a text document by using some external editor such as Notepad. While pasting a sequence of moves, a small delay makes sure intermediate board states are shown, resulting in an animation effect.)备注(Remark):您可能想在粘贴解决方案尝试之前执行级别重新启动.(: You may want to perform a Level Restart before pasting a solution attempt.) 以下代码段显示了粘贴处理程序创建的后台线程,在该线程上运行的方法以及该方法(The following code snippet shows the paste handler creating the background thread, the method running on that thread, and the method) pasteOneMove() 它使用委托在UI线程上进行自身调用.与其使用输入参数,(that uses a delegate to Invoke itself on the UI thread. Rather than using input parameters, the) pasteSequencer() 方法使用实例字段((method uses an instance field () pasteString )以获取其数据.这是安全的,因为在后台线程运行时禁用了"粘贴"菜单项.() to get its data. This is safe since the Paste menu item is disabled while the background thread is running.)

private void menuPaste_Click(object sender, System.EventArgs e) {
    IDataObject data=Clipboard.GetDataObject();
    if (data.GetDataPresent(DataFormats.Text)) {
        pasteString=data.GetData(DataFormats.Text).ToString();
        menuPaste.Enabled=false; // prevent multiple execution
        log("Pasting "+pasteString);
        Thread thread=new Thread(new ThreadStart(pasteSequencer));
        thread.IsBackground=true;
        thread.Start();
    }
}

private void pasteSequencer() {
    string s=pasteString.ToUpper();
    foreach (char c in s) {
        pasteOneMove(c);
        Thread.Sleep(100);          // slow down for animation
    }
    pasteOneMove(char.MaxValue);    // last paste action (reenable menu)
}

private delegate void MovePaster(char c);

private void pasteOneMove(char c) {
    if (this.InvokeRequired) {
        Invoke(new MovePaster(pasteOneMove), new object[]{c});
    } else {
        if (c==char.MaxValue) {
            menuPaste.Enabled=true;
        } else {
            Move move=null;
            if (c=='U') move=sokoban.TryMove(0,-1,true);
            else if (c=='D') move=sokoban.TryMove(0,1,true);
            else if (c=='L') move=sokoban.TryMove(-1,0,true);
            else if (c=='R') move=sokoban.TryMove(1,0,true);
            else log("*** bad character in paste: "+c);
            if (move!=null) postProcessMove(move);
        }
    }
}

作为最后一个附加功能,(As a last extra feature, the) Board 可以整齐地打印在一页上.因此,您甚至可以尝试解决纸上的难题,或保留中间状态的打印输出.(can be printed, fitting neatly on one page. So you can even try to solve a puzzle on paper, or keep a printout of an intermediate state.)

兴趣点(Points of Interest)

以下某些项目与CodeProject留言板上的最新主题相关:(Some of the following items relate to recent topics on one of the CodeProject message boards:)

• 的(The) Board 面板使用图形基元组成图形.(panel uses graphical primitives to make up a drawing.)
• 的(The) Board 面板是双缓冲的,以避免屏幕闪烁.(panel is double-buffered to avoiding screen flickering.)
• 的(The) Board 面板是可扩展的,因此可以将程序的视图容纳到可用的屏幕区域.(panel is scalable, so one can accommodate the program’s view to the available screen area.)
• 的(The) MainForm 具有内置的日志记录;它使用一个(has built-in logging; it uses a) listbox 显示日志.视图菜单控制该菜单的可见性(to display the log. The view menu controls the visibility of that) listbox 和(, and the) listbox 继续向下滚动以使最新消息可见.委托也使log方法也可用于其他主要类.(keeps scrolling down to keep the most recent messages visible. A delegate is used to make the log method available to the other major classes too.)
• 的(The) MainForm 使用后台线程粘贴一系列移动;此线程为每个单独的调用调用UI线程,因此UI控件得到正确处理.(uses a background thread to paste a sequence of moves; this thread invokes the UI thread for each individual move, so UI Controls are handled correctly.)
• 的(The) MainForm 使用约五(uses about five) string Windows注册表中的,以记住最新的程序设置.它们存储在(s in the Windows Registry to remember the most recent program settings. They are stored under)HKEY_CURRENT_USER/软件/LP/Sokoban(HKEY_CURRENT_USER/Software/LP/Sokoban).(.) 该程序可在.NET Framework 1.1和2.0上运行.(This program runs on both .NET Framework 1.1 and 2.0.) 尽管此程序支持打印,并访问剪贴板,XML文件和Windows注册表,并使用委托甚至PInvoke调用本机方法((Although this program supports printing, and accesses the Clipboard, an XML file and the Windows Registry, and uses delegates and even PInvoke to call a native method () MessageBeep ),它包含少于1600行的源代码.(), it consists of fewer than 1600 lines of source code.)

致谢(Acknowledgements)

谢谢:(Thanks to:)

• 贾斯珀范登`伯格(Jasper van den Bergh) 谁写了这篇文章(who wrote the article on) 推箱子Pro(Sokoban Pro) 以及共享的代码和问题文件(and shared code and problem files)
• 马克`克利夫顿(Marc Clifton) 谁在(who wrote the article on an) 撤消/重做缓冲区框架(Undo/Redo Buffer Framework)

历史(History)

• LP推箱子#1.0(第一版)(LP Sokoban# 1.0 (first release))

许可

本文以及所有相关的源代码和文件均已获得The Code Project Open License (CPOL)的许可。