最近，使用 C# 開發(fā)了一款智能手機軟件：推箱子。先介紹一下這款軟件的特點：
1. 可以在智能手機上運行，也可以在計算機上運行。
2. 退出程序時可保護現(xiàn)場，下次再運行自動恢復(fù)到原來的狀態(tài)。
3. 玩家通關(guān)后可以使用“錄像”功能保存通關(guān)步驟，以便將來“回放”。
4. 可以自由設(shè)計關(guān)卡，批量進行數(shù)據(jù)導(dǎo)出和導(dǎo)入。
如下圖的“解決方案資源管理器”所示，該程序的源程序主要分布在“Window”和“Common”兩個文件夾中。其中“Window”文件夾存放的是程序主窗體和各個對話框的源代碼。而“Common”文件夾存放的是公用的源代碼，包括各種數(shù)據(jù)結(jié)構(gòu)，尋找最短路線的算法，讀寫配置文件和數(shù)據(jù)文件等。
我將在隨后的文章中詳細介紹各個源程序文件。
對了，推箱子程序的下載地址為：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 /// 獲取為此環(huán)境定義的換行字符串。-- Environment
14 ///
15 public static string NewLine { get { return "\r\n"; } }
16
17 ///
18 /// 打開一個文本文件，將文件的所有行讀入一個字符串，然后關(guān)閉該文件。-- 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 /// 創(chuàng)建一個新文件，在其中寫入指定的字符串，然后關(guān)閉該文件。-- 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 /// 加法運算的結(jié)果
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 /// 將一維數(shù)組的大小更改為指定的新大小。-- Array
61 ///
62 /// 數(shù)組元素的類型
63 /// 要調(diào)整大小的一維數(shù)組
64 /// 新數(shù)組的大小
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 的一個子集，她省略了一些不常用的功能。但是，如果我們恰好需要這些功能，只好自己重新實現(xiàn)一下了。這個 Fcl 靜態(tài)類就是起這個作用的。源程序代碼的注釋已經(jīng)寫得很清楚了。
Fcl.NewLine 我原本是想寫成這樣的：
以下是引用片段：
static class Fcl
{
static static string newLine;
///
/// 獲取為此環(huán)境定義的換行字符串。-- 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 操作系統(tǒng)為 Unix。
Win32NT 操作系統(tǒng)為 Windows NT 或較新的版本。
Win32S 操作系統(tǒng)為 Win32s(Win32 子集)類型。
Win32Windows 操作系統(tǒng)為 Windows 95 或較新的版本。
WinCE 操作系統(tǒng)為 Windows CE。
PlatformID.Unix 并不被 .NET CF 所支持。這實在是一件很奇怪的事，既然 .NET CF 都支持 PlatformID 的 Win32NT、Win32S、Win32Windows、WinCE 成員，為什么就不能支持 Unix 成員呢?這樣，這個程序?qū)硪浦驳?Linux 操作系統(tǒng)時就有些小麻煩了。
要知道，這在主窗體的代碼中用以下一段代碼來實現(xiàn)在智能手機上禁用“前端顯示”功能。
以下是引用片段：
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 }
靜態(tài)類 Block 用來表示基本單元格: 空地、槽(箱子最終要存放的目的地)、墻、磚(在本程序中等同于“墻”，一般放在墻的外圍，使圖形看起來漂亮些)、箱子、工人。其中“箱子”和“工人”都可以位于“空地”或“槽”上，所以總共有八種狀態(tài)，用 0 到 7 表示，總共只需要三個二進位，可以放入一個字節(jié)中。在數(shù)據(jù)文件(*.bxb)中，每個基本單元格就是用一個字節(jié)儲存的，這在以后介紹的 Common/DataFile.cs 源程序文件中會看到。但是為什么靜態(tài)類 Block 的大多數(shù)方法的參數(shù)都是 ushort 類型呢?這是為了尋找工人最短移動路線算法的需要，看了下一篇介紹 Common/FindPath.cs 源程序文件的文章就會明白了。
這個類還是比較簡單的，現(xiàn)簡要說明如下：
GetPenName 方法返回在設(shè)計關(guān)卡時所用畫筆的名稱。
Update 方法用來在設(shè)計關(guān)卡時更新地圖中的基本單元格。
GetChar 方法返回將數(shù)據(jù)文件(data/*.bxb)導(dǎo)出為文本文件(text/*.bxa)所用的字符。
GetByte 方法返回將文本文件(text/*.bxa)導(dǎo)入為數(shù)據(jù)文件(data/*.bxb)所用的字節(jié)。
IsOk 方法判斷表示基本單元格的字節(jié)是否合法，也用在數(shù)據(jù)導(dǎo)入時。
Mark 方法在尋找工人最短移動路線算法中用來標記已經(jīng)搜索過的基本單元格。
CleanAllMark 方法在上述算法結(jié)束時用來清除地圖中的所有基本單元格的標記。
Value 方法返回上述算法搜索過程中所作的標記。
ManIn、ManOut、BoxIn、BoxOut 方法用來更新推箱子過程中地圖各基本單元格的狀態(tài)。
IsSlot、IsBlank、IsBox、IsMan 方法用來判斷各基本單元格的類型。
補充：尋找工人最短移動路線的算法已經(jīng)作了改進，地圖使用 byte 存儲就行了，所以靜態(tài)類 Block 中的所有“ushort”都要修改為“byte”。請參見“使用 C# 開發(fā)智能手機軟件：推箱子(五)”中的說明。
在這篇文章中，介紹 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 };
///
/// 尋找最短路線
///
/// 地圖
/// 出發(fā)點
/// 目的地
/// 最短路線
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; // 出發(fā)點(即工人的位置)
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; // 繼續(xù)前進
}
}
Block.CleanAllMark(map); // 清除所有標志,恢復(fù)現(xiàn)場
return moveQueue; // 所尋找的路線,如果無法到達目的地則為該路線的長度為零
}
///
/// 尋找最短路線,使用廣度優(yōu)先搜索
///
/// 地圖
/// 目的地
/// 輸出:路線的長度(加1)
/// 是否成功
static bool Seek(ushort[,] map, Point to, out int value)
{
Queue q = new Queue();
Block.Mark(ref map[to.Y, to.X], 1); // 從目的地開始往回尋找出發(fā)點,目的地標記為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; // 到達出發(fā)點(即工人的位置)
if (Block.IsBlank(map[nbr.Y, nbr.X])) // 可以走的路
{
Block.Mark(ref map[nbr.Y, nbr.X], value); // 標記,防止以后再走這條路
q.Enqueue(nbr); // 加入隊列,等待以后繼續(xù)尋找
}
}
if (Block.IsMan(map[nbr.Y, nbr.X])) break; // 到達出發(fā)點
if (q.Count == 0) return false; // 無法到達出發(fā)點
to = q.Dequeue(); // 出隊,繼續(xù)尋找,這是廣度優(yōu)先搜索,因為前面已經(jīng)把四周能夠走的路全部加入隊列中了.
}
return true; // 找到一條路線
}
}
}
靜態(tài)類 FindPath 是用來尋找工人移動到鼠標點擊的目的地的最短路線的。她采用一種廣度優(yōu)先搜索算法，使用循環(huán)，沒有使用遞歸，而且地圖上已經(jīng)搜索過的路線決不再走第二遍。該算法分兩個階段進行：首先是尋找并標記最短路線，由該類的第二個 Seek 方法實現(xiàn)，這個私有的方法返回一個布爾值表明是否成功。然后，如果在第一階段中找到了一條路線，則根據(jù)第一階段所做的標記生成最短路線并將該路線返回給調(diào)用者。我們來看幾個實例：
在該算法中，是從要到達的目的地開始往回尋找出發(fā)點。首先，將目的地標記為1，然后查看周圍的四個鄰居(按南、東、北、西的順序)是否是“空白”(即“地”和“槽”，使用 Block.IsBlank 方法來判斷)，如是，則表明這是可以走的路，將其作上標記(使用 Block.Mark 方法，標記的數(shù)值等于離開目的地的距離加一)，然后加入隊列。這有兩個作用，首先，標記過的單元格將不再被認為是可以走的路，防止重復(fù)搜索。其次，在第二階段中要根據(jù)標記的值來生成最短路線。如果發(fā)現(xiàn)周圍的鄰居中有一個是工人(用 Block.IsMan 方法來判斷)，說明到達出發(fā)點，則立即結(jié)束搜索，退出循環(huán)，返回成功。否則，就檢查隊列是否為空，如果為空，則說明無法到達出發(fā)點，返回失敗。如果不為空，則出隊，從這一點繼續(xù)開始搜索。如此一直循環(huán)。
這個算法是廣度優(yōu)先的，如上面的兩個圖所示，該算法是按標記的值從小到大進行遍歷的，而該標記的值表示的是離開目的地的距離加一。
第二個階段，如果在第一階段返回失敗，則返回一條空的路線(長度為零)給調(diào)用者。否則，從出發(fā)點(即工人的位置)開始，查看周圍的四個鄰居(按南、東、北、西的順序)，如果其標記的值(使用 Block.Value 方法來獲得)為到目的地的距離加一(至少可以找到一個，可能有多個，可以任取一個，程序中使用第一個)，就往這個方向走。如此一直循環(huán)，直到到達目的地。然后返回這條路線給調(diào)用者。
從這里可以看出，為什么地圖(即 ushort[,] map)要使用 ushort 而不使用 byte。因為在該算法需要在地圖中作標記，而且標記的值還必須是到目的地的距離加一(如果只須判斷目的地是否可達，而不要求給出到達目的地的具體路線，則在算法中標記的值可全部都為1，這樣用 byte 就足夠了)。地圖中總共有八種類型的單元格，需要用三個二進位表示。而 byte 只有八個二進位，那么，只剩下五個二進位，25=32，也就是說，目的地在工人32步以外該算法就無能為力了。而 ushort 有十六個二進位，減去三個，還有十三個二進位，213=8192，這應(yīng)該足夠了。讓我們看看下圖吧：
這是一個 9x9 的地圖，共有81個單元格，其中49個是空地，假設(shè)目的在地圖的右上角(標記為1的地方)，則工人需要48步才能到達目的地。根據(jù)計算，如果是 NxN (這里N是奇數(shù))的地圖，工人在最壞的情況下需要 (N2 - 1)/2 + N -1 步(走最短路線)才能到達目的地。這就是說，在 127x127 的地圖上，工人最多只需要 8190 步就可以到達目的地，這剛好在我們算法的范圍之內(nèi)。如果地圖再大，我們的算法就可能(只是可能，因為在大地圖上一般情況下并不會出現(xiàn)超過 8192 步的最短路線)無能為力了。
在這篇文章中介紹經(jīng)過改進后的 Common/FindPath.cs 源程序文件。也就是說，已經(jīng)實現(xiàn)了“使用 C# 開發(fā)智能手機軟件：推箱子(四)”的第二個評論中的想法，將地圖 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 /// 出發(fā)點
20 /// 目的地
21 /// 最短路線
22 public static Queue Seek(byte[,] map, Point from, Point to)
23 {
24 Queue moveQueue = new Queue(); // 路線
25 int value; // 與離目的地距離相關(guān)的一個量,變化規(guī)律: => 2 => 1 => 3 => 2 => 1 => 3 => 2 => 1
26 if (Seek(map, to, out value)) // 找到了一條路線
27 {
28 Point here = from; // 出發(fā)點(即工人的位置)
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; // 繼續(xù)前進
42 }
43 }
44 Block.CleanAllMark(map); // 清除所有標志,恢復(fù)現(xiàn)場
45 return moveQueue; // 所尋找的路線,如果無法到達目的地則為該路線的長度為零
46 }
47
48 ///
49 /// 尋找最短路線,使用廣度優(yōu)先搜索
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); // 從目的地開始往回尋找出發(fā)點,目的地標記為1
59 Point nbr = Point.Empty; // 四周的鄰居
60 for (; ; )
61 {
62 value = Block.Value(map[to.Y, to.X]) % 3 + 1; // 與離目的地距離相關(guān)的一個量,用作標記,變化規(guī)律:
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; // 到達出發(fā)點(即工人的位置)
67 if (Block.IsBlank(map[nbr.Y, nbr.X])) // 可以走的路
68 {
69 Block.Mark(ref map[nbr.Y, nbr.X], value); // 標記,防止以后再走這條路
70 q.Enqueue(nbr); // 加入隊列,等待以后繼續(xù)尋找
71 }
72 }
73 if (Block.IsMan(map[nbr.Y, nbr.X])) break; // 到達出發(fā)點
74 if (q.Count == 0) return false; // 無法到達出發(fā)點
75 to = q.Dequeue(); // 出隊,繼續(xù)尋找,這是廣度優(yōu)先搜索,因為前面已經(jīng)把四周能夠走的路全部加入隊列中了.
76 }
77 return true; // 找到一條路線
78 }
79 }
80 }
上面的源程序已經(jīng)對搜索算法作了很好的注釋。我們還是來看兩幅反映算法運行時地圖上各標記值的圖片吧：
圖中，帶圓圈的紅色的數(shù)字“1”是“目的地”，也就是算法開始的地方，因為該算法是從目的地開始往回尋找出發(fā)點。在改進后的算法中，標記值始終是在“1、2、3”這三個數(shù)中循環(huán)，而不是象以前一樣一直增大。在圖中，算法按“紅、黃、綠、藍、粉紅、青”的順序從目的地往外搜索，直到遇到“工人”而返回成功，或者填滿能夠到達的空地而返回失敗。
算法經(jīng)過這次改進，搜索的距離就不象原來一樣受限于 8192 步。而且也將地圖所占用的內(nèi)存空間減少到原來的二分之一。
這次改進，除了仔細重寫了 FindPath 類以外，程序其余地方只是將所有的“ushort”替換為“byte”就行了，因為本程序只在涉及地圖的地方使用過“ushort”。