最近,使用 C# 开发了一款智能手机软件:推箱子。先介绍一下这款软件的特点:
1. 可以在智能手机上运行,也可以在计算机上运行。
2. 退出程序时可保护现场,下次再运行自动恢复到原来的状态。
3. 玩家通关后可以使用“录像”功能保存通关步骤,以便将来“回放”。
4. 可以自由设计关卡,批量进行数据导出和导入。
如下图的“解决方案资源管理器”所示,该程序的源程序主要分布在“Window”和“Common”两个文件夹中。其中“Window”文件夹存放的是程序主窗体和各个对话框的源代码。而“Common”文件夹存放的是公用的源代码,包括各种数据结构,寻找最短路线的算法,读写配置文件和数据文件等。
我将在随后的文章中详细介绍各个源程序文件。
对了,推箱子程序的下载地址为:http://ben.skyiv.com/PushBox
以下是部分软件界面截图:
这次,我先介绍 Common/Fcl.cs 源程序文件。
以下是引用片段:
1 using System;
2 using System.IO;
3 using System.Drawing;
4
5 namespace Skyiv.Ben.PushBox.Common
6 {
7 ///
8 /// 这里是 .NET Framework 支持,而 .NET Compact Framework 不支持的东东
9 ///
10 static class Fcl
11 {
12 ///
13 /// 获取为此环境定义的换行字符串。-- Environment
14 ///
15 public static string NewLine { get { return "\r\n"; } }
16
17 ///
18 /// 打开一个文本文件,将文件的所有行读入一个字符串,然后关闭该文件。-- File
19 ///
20 /// 要打开以进行读取的文件
21 /// 包含文件所有行的字符串
22 public static string ReadAllText(string path)
23 {
24 string text = "";
25 if (File.Exists(path))
26 {
27 using (StreamReader sr = new StreamReader(path, Pub.Encode))
28 {
29 text = sr.ReadToEnd();
30 }
31 }
32 return text;
33 }
34
35 ///
36 /// 创建一个新文件,在其中写入指定的字符串,然后关闭该文件。-- File
37 ///
38 /// 要写入的文件
39 /// 要写入文件的字符串
40 public static void WriteAllText(string path, string contents)
41 {
42 using (StreamWriter sw = new StreamWriter(path, false, Pub.Encode))
43 {
44 sw.Write(contents);
45 }
46 }
47
48 ///
49 /// 将指定的 Size 添加到指定的 Point。-- Point
50 ///
51 /// 要添加的 Point
52 /// 要添加的 Size
53 /// 加法运算的结果
54 public static Point Add(Point point, Size size)
55 {
56 return new Point(point.X + size.Width, point.Y + size.Height);
57 }
58
59 ///
60 /// 将一维数组的大小更改为指定的新大小。-- Array
61 ///
62 /// 数组元素的类型
63 /// 要调整大小的一维数组
64 /// 新数组的大小
65 public static void Resize(ref T[] array, int newSize)
66 {
67 if (array != null && array.Length == newSize) return;
68 if (array == null) array = new T[0];
69 T[] newArray = new T[newSize];
70 Array.Copy(array, newArray, Math.Min(array.Length, newArray.Length));
71 array = newArray;
72 }
73 }
74 }
俗话说,工欲善其事,必先利其器。我们知道,Microsoft .NET Compact Framework 只是 Microsoft .NET Framework 的一个子集,她省略了一些不常用的功能。但是,如果我们恰好需要这些功能,只好自己重新实现一下了。这个 Fcl 静态类就是起这个作用的。源程序代码的注释已经写得很清楚了。
Fcl.NewLine 我原本是想写成这样的:
以下是引用片段:
static class Fcl
{
static static string newLine;
///
/// 获取为此环境定义的换行字符串。-- Environment
///
public static string NewLine
{
get
{
if (newLine == null)
{
newLine = (Environment.OSVersion.Platform != PlatformID.Unix) ? "\r\n" : "\n";
}
return newLine;
}
}
}
可惜的是,这段代码无法在 .NET Compact Framework 下通过编译(如果是 .NET Framework 则没有问题)。原因是 PlatformID 枚举的成员:
Unix 操作系统为 Unix。
Win32NT 操作系统为 Windows NT 或较新的版本。
Win32S 操作系统为 Win32s(Win32 子集)类型。
Win32Windows 操作系统为 Windows 95 或较新的版本。
WinCE 操作系统为 Windows CE。
PlatformID.Unix 并不被 .NET CF 所支持。这实在是一件很奇怪的事,既然 .NET CF 都支持 PlatformID 的 Win32NT、Win32S、Win32Windows、WinCE 成员,为什么就不能支持 Unix 成员呢?这样,这个程序将来要移植到 Linux 操作系统时就有些小麻烦了。
要知道,这在主窗体的代码中用以下一段代码来实现在智能手机上禁用“前端显示”功能。
以下是引用片段:
public partial class MainForm : Form
{
protected override void OnLoad(EventArgs e)
{
base.OnLoad(e);
miTopMost.Enabled = (Environment.OSVersion.Platform != PlatformID.WinCE);
env.LoadConfig();
env.LoadGroup();
LoadLevel(true);
if (env.IsSave) Restore(env.Steps);
}
在这篇文章中,介绍 Common/Block.cs 源程序文件。
以下是引用片段:
1 namespace Skyiv.Ben.PushBox.Common
2 {
3 ///
4 /// 基本单元格: 地 槽 墙 砖 箱子 工人
5 ///
6 static class Block
7 {
8 public const byte Land = 0; // 地
9 public const byte Slot = 1; // 槽
10 public const byte Wall = 2; // 墙
11 public const byte Brick = 3; // 砖: 等同于墙,一般放在墙的外围
12 public const byte Box0 = 4; // 箱子放在地上
13 public const byte Box1 = 5; // 箱子放在槽上
14 public const byte Man0 = 6; // 工人站在地上
15 public const byte Man1 = 7; // 工人站在槽上
16
17 const string mask = "-+#%xX()"; // (*.bxa)文件用,依次代表以上各项
18
19 public static string GetPenName(byte block)
20 {
21 return "地槽墙砖箱箱人人"[block & 0x07].ToString();
22 }
23
24 public static char GetChar(ushort block)
25 {
26 return mask[block & 0x07];
27 }
28
29 public static byte GetByte(char block)
30 {
31 return (byte)mask.IndexOf(block);
32 }
33
34 public static bool IsOk(ushort block)
35 {
36 return block <= Man1;
37 }
38
39 public static void CleanAllMark(ushort[,] bb)
40 {
41 for (int i = 0; i < bb.GetLength(0); i++)
42 for (int j = 0; j < bb.GetLength(1); j++)
43 bb[i, j] &= 0x07;
44 }
45
46 public static void Mark(ref ushort block, int value)
47 {
48 block |= (ushort)(value << 3);
49 }
50
51 public static int Value(ushort block)
52 {
53 return block >> 3;
54 }
55
56 public static void Update(ref ushort block, byte pen)
57 {
58 if (IsSlot(block) && pen == Block.Man0) pen = Block.Man1;
59 if (IsSlot(block) && pen == Block.Box0) pen = Block.Box1;
60 block = pen;
61 }
62
63 public static void ManIn(ref ushort block)
64 {
65 block += (Man0 - Land);
66 }
67
68 public static void ManOut(ref ushort block)
69 {
70 block -= (Man0 - Land);
71 }
72
73 public static void BoxIn(ref ushort block)
74 {
75 block += (Box0 - Land);
76 }
77
78 public static void BoxOut(ref ushort block)
79 {
80 block -= (Box0 - Land);
81 }
82
83 public static bool IsSlot(ushort block)
84 {
85 return block == Slot || block == Box1 || block == Man1;
86 }
87
88 public static bool IsBlank(ushort block)
89 {
90 return block == Land || block == Slot;
91 }
92
93 public static bool IsBox(ushort block)
94 {
95 return block == Box0 || block == Box1;
96 }
97
98 public static bool IsMan(ushort block)
99 {
100 return block == Man0 || block == Man1;
101 }
102 }
103 }
静态类 Block 用来表示基本单元格: 空地、槽(箱子最终要存放的目的地)、墙、砖(在本程序中等同于“墙”,一般放在墙的外围,使图形看起来漂亮些)、箱子、工人。其中“箱子”和“工人”都可以位于“空地”或“槽”上,所以总共有八种状态,用 0 到 7 表示,总共只需要三个二进位,可以放入一个字节中。在数据文件(*.bxb)中,每个基本单元格就是用一个字节储存的,这在以后介绍的 Common/DataFile.cs 源程序文件中会看到。但是为什么静态类 Block 的大多数方法的参数都是 ushort 类型呢?这是为了寻找工人最短移动路线算法的需要,看了下一篇介绍 Common/FindPath.cs 源程序文件的文章就会明白了。
这个类还是比较简单的,现简要说明如下:
GetPenName 方法返回在设计关卡时所用画笔的名称。
Update 方法用来在设计关卡时更新地图中的基本单元格。
GetChar 方法返回将数据文件(data/*.bxb)导出为文本文件(text/*.bxa)所用的字符。
GetByte 方法返回将文本文件(text/*.bxa)导入为数据文件(data/*.bxb)所用的字节。
IsOk 方法判断表示基本单元格的字节是否合法,也用在数据导入时。
Mark 方法在寻找工人最短移动路线算法中用来标记已经搜索过的基本单元格。
CleanAllMark 方法在上述算法结束时用来清除地图中的所有基本单元格的标记。
Value 方法返回上述算法搜索过程中所作的标记。
ManIn、ManOut、BoxIn、BoxOut 方法用来更新推箱子过程中地图各基本单元格的状态。
IsSlot、IsBlank、IsBox、IsMan 方法用来判断各基本单元格的类型。
补充:寻找工人最短移动路线的算法已经作了改进,地图使用 byte 存储就行了,所以静态类 Block 中的所有“ushort”都要修改为“byte”。请参见“使用 C# 开发智能手机软件:推箱子(五)”中的说明。
在这篇文章中,介绍 Common/FindPath.cs 源程序文件。
以下是引用片段:
using System;
using System.Drawing;
using System.Collections.Generic;
namespace Skyiv.Ben.PushBox.Common
{
///
/// 寻找最短路线
///
static class FindPath
{
static Size[] offsets = { new Size(0, 1), new Size(1, 0), new Size(0, -1), new Size(-1, 0) };
static Direction[] directions = { Direction.South, Direction.East, Direction.North, Direction.West };
///
/// 寻找最短路线
///
/// 地图
/// 出发点
/// 目的地
/// 最短路线
public static Queue Seek(ushort[,] map, Point from, Point to)
{
Queue moveQueue = new Queue(); // 路线
int value; // 离目的地距离
if (Seek(map, to, out value)) // 找到了一条路线
{
Point here = from; // 出发点(即工人的位置)
Point nbr = new Point(); // 四周的邻居
for (value--; value > 0; value--) // 逐步走向目的地
{
for (int i = 0; i < offsets.Length; i++)
{
nbr = Fcl.Add(here, offsets[i]); // 开始寻找四周的邻居
if (Block.Value(map[nbr.Y, nbr.X]) == value) // 就往这个方向走
{
moveQueue.Enqueue(directions[i]); // 路线向目的地延伸一步
break;
}
}
here = nbr; // 继续前进
}
}
Block.CleanAllMark(map); // 清除所有标志,恢复现场
return moveQueue; // 所寻找的路线,如果无法到达目的地则为该路线的长度为零
}
///
/// 寻找最短路线,使用广度优先搜索
///
/// 地图
/// 目的地
/// 输出:路线的长度(加1)
/// 是否成功
static bool Seek(ushort[,] map, Point to, out int value)
{
Queue q = new Queue();
Block.Mark(ref map[to.Y, to.X], 1); // 从目的地开始往回寻找出发点,目的地标记为1
Point nbr = Point.Empty; // 四周的邻居
for (; ; )
{
value = Block.Value(map[to.Y, to.X]) + 1; // 离开目的地的距离(加1),用作标记
for (int i = 0; i < offsets.Length; i++)
{
nbr = Fcl.Add(to, offsets[i]); // 开始寻找四周的邻居
if (Block.IsMan(map[nbr.Y, nbr.X])) break; // 到达出发点(即工人的位置)
if (Block.IsBlank(map[nbr.Y, nbr.X])) // 可以走的路
{
Block.Mark(ref map[nbr.Y, nbr.X], value); // 标记,防止以后再走这条路
q.Enqueue(nbr); // 加入队列,等待以后继续寻找
}
}
if (Block.IsMan(map[nbr.Y, nbr.X])) break; // 到达出发点
if (q.Count == 0) return false; // 无法到达出发点
to = q.Dequeue(); // 出队,继续寻找,这是广度优先搜索,因为前面已经把四周能够走的路全部加入队列中了.
}
return true; // 找到一条路线
}
}
}
静态类 FindPath 是用来寻找工人移动到鼠标点击的目的地的最短路线的。她采用一种广度优先搜索算法,使用循环,没有使用递归,而且地图上已经搜索过的路线决不再走第二遍。该算法分两个阶段进行:首先是寻找并标记最短路线,由该类的第二个 Seek 方法实现,这个私有的方法返回一个布尔值表明是否成功。然后,如果在第一阶段中找到了一条路线,则根据第一阶段所做的标记生成最短路线并将该路线返回给调用者。我们来看几个实例:
在该算法中,是从要到达的目的地开始往回寻找出发点。首先,将目的地标记为1,然后查看周围的四个邻居(按南、东、北、西的顺序)是否是“空白”(即“地”和“槽”,使用 Block.IsBlank 方法来判断),如是,则表明这是可以走的路,将其作上标记(使用 Block.Mark 方法,标记的数值等于离开目的地的距离加一),然后加入队列。这有两个作用,首先,标记过的单元格将不再被认为是可以走的路,防止重复搜索。其次,在第二阶段中要根据标记的值来生成最短路线。如果发现周围的邻居中有一个是工人(用 Block.IsMan 方法来判断),说明到达出发点,则立即结束搜索,退出循环,返回成功。否则,就检查队列是否为空,如果为空,则说明无法到达出发点,返回失败。如果不为空,则出队,从这一点继续开始搜索。如此一直循环。
这个算法是广度优先的,如上面的两个图所示,该算法是按标记的值从小到大进行遍历的,而该标记的值表示的是离开目的地的距离加一。
第二个阶段,如果在第一阶段返回失败,则返回一条空的路线(长度为零)给调用者。否则,从出发点(即工人的位置)开始,查看周围的四个邻居(按南、东、北、西的顺序),如果其标记的值(使用 Block.Value 方法来获得)为到目的地的距离加一(至少可以找到一个,可能有多个,可以任取一个,程序中使用第一个),就往这个方向走。如此一直循环,直到到达目的地。然后返回这条路线给调用者。
从这里可以看出,为什么地图(即 ushort[,] map)要使用 ushort 而不使用 byte。因为在该算法需要在地图中作标记,而且标记的值还必须是到目的地的距离加一(如果只须判断目的地是否可达,而不要求给出到达目的地的具体路线,则在算法中标记的值可全部都为1,这样用 byte 就足够了)。地图中总共有八种类型的单元格,需要用三个二进位表示。而 byte 只有八个二进位,那么,只剩下五个二进位,25=32,也就是说,目的地在工人32步以外该算法就无能为力了。而 ushort 有十六个二进位,减去三个,还有十三个二进位,213=8192,这应该足够了。让我们看看下图吧:
这是一个 9x9 的地图,共有81个单元格,其中49个是空地,假设目的在地图的右上角(标记为1的地方),则工人需要48步才能到达目的地。根据计算,如果是 NxN (这里N是奇数)的地图,工人在最坏的情况下需要 (N2 - 1)/2 + N -1 步(走最短路线)才能到达目的地。这就是说,在 127x127 的地图上,工人最多只需要 8190 步就可以到达目的地,这刚好在我们算法的范围之内。如果地图再大,我们的算法就可能(只是可能,因为在大地图上一般情况下并不会出现超过 8192 步的最短路线)无能为力了。
在这篇文章中介绍经过改进后的 Common/FindPath.cs 源程序文件。也就是说,已经实现了“使用 C# 开发智能手机软件:推箱子(四)”的第二个评论中的想法,将地图 ushort[,] map 改为 byte[,] map 了。下面就是改进后的 FindPath 类:
以下是引用片段:
1 using System;
2 using System.Drawing;
3 using System.Collections.Generic;
4
5 namespace Skyiv.Ben.PushBox.Common
6 {
7 ///
8 /// 寻找最短路线
9 ///
10 static class FindPath
11 {
12 static Size[] offsets = { new Size(0, 1), new Size(1, 0), new Size(0, -1), new Size(-1, 0) };
13 static Direction[] directions = { Direction.South, Direction.East, Direction.North, Direction.West };
14
15 ///
16 /// 寻找最短路线
17 ///
18 /// 地图
19 /// 出发点
20 /// 目的地
21 /// 最短路线
22 public static Queue Seek(byte[,] map, Point from, Point to)
23 {
24 Queue moveQueue = new Queue(); // 路线
25 int value; // 与离目的地距离相关的一个量,变化规律: => 2 => 1 => 3 => 2 => 1 => 3 => 2 => 1
26 if (Seek(map, to, out value)) // 找到了一条路线
27 {
28 Point here = from; // 出发点(即工人的位置)
29 Point nbr = new Point(); // 四周的邻居
30 for (value = (value + 1) % 3 + 1; here != to; value = (value + 1) % 3 + 1) // 逐步走向目的地
31 {
32 for (int i = 0; i < offsets.Length; i++)
33 {
34 nbr = Fcl.Add(here, offsets[i]); // 开始寻找四周的邻居
35 if (Block.Value(map[nbr.Y, nbr.X]) == value) // 就往这个方向走
36 {
37 moveQueue.Enqueue(directions[i]); // 路线向目的地延伸一步
38 break;
39 }
40 }
41 here = nbr; // 继续前进
42 }
43 }
44 Block.CleanAllMark(map); // 清除所有标志,恢复现场
45 return moveQueue; // 所寻找的路线,如果无法到达目的地则为该路线的长度为零
46 }
47
48 ///
49 /// 寻找最短路线,使用广度优先搜索
50 ///
51 /// 地图
52 /// 目的地
53 /// 输出:搜索完成时标记的值
54 /// 是否成功
55 static bool Seek(byte[,] map, Point to, out int value)
56 {
57 Queue q = new Queue();
58 Block.Mark(ref map[to.Y, to.X], 1); // 从目的地开始往回寻找出发点,目的地标记为1
59 Point nbr = Point.Empty; // 四周的邻居
60 for (; ; )
61 {
62 value = Block.Value(map[to.Y, to.X]) % 3 + 1; // 与离目的地距离相关的一个量,用作标记,变化规律:
63 for (int i = 0; i < offsets.Length; i++) // 1 => 2 => 3 => 1 => 2 => 3 => 1 => 2 => 3 =>
64 {
65 nbr = Fcl.Add(to, offsets[i]); // 开始寻找四周的邻居
66 if (Block.IsMan(map[nbr.Y, nbr.X])) break; // 到达出发点(即工人的位置)
67 if (Block.IsBlank(map[nbr.Y, nbr.X])) // 可以走的路
68 {
69 Block.Mark(ref map[nbr.Y, nbr.X], value); // 标记,防止以后再走这条路
70 q.Enqueue(nbr); // 加入队列,等待以后继续寻找
71 }
72 }
73 if (Block.IsMan(map[nbr.Y, nbr.X])) break; // 到达出发点
74 if (q.Count == 0) return false; // 无法到达出发点
75 to = q.Dequeue(); // 出队,继续寻找,这是广度优先搜索,因为前面已经把四周能够走的路全部加入队列中了.
76 }
77 return true; // 找到一条路线
78 }
79 }
80 }
上面的源程序已经对搜索算法作了很好的注释。我们还是来看两幅反映算法运行时地图上各标记值的图片吧:
图中,带圆圈的红色的数字“1”是“目的地”,也就是算法开始的地方,因为该算法是从目的地开始往回寻找出发点。在改进后的算法中,标记值始终是在“1、2、3”这三个数中循环,而不是象以前一样一直增大。在图中,算法按“红、黄、绿、蓝、粉红、青”的顺序从目的地往外搜索,直到遇到“工人”而返回成功,或者填满能够到达的空地而返回失败。
算法经过这次改进,搜索的距离就不象原来一样受限于 8192 步。而且也将地图所占用的内存空间减少到原来的二分之一。
这次改进,除了仔细重写了 FindPath 类以外,程序其余地方只是将所有的“ushort”替换为“byte”就行了,因为本程序只在涉及地图的地方使用过“ushort”。