教你用C#開(kāi)發(fā)智能手機(jī)游戲:推箱子

2010-08-28 10:52:28來(lái)源:西部e網(wǎng)作者:

  最近,使用 C# 開(kāi)發(fā)了一款智能手機(jī)軟件:推箱子。先介紹一下這款軟件的特點(diǎn):

  1. 可以在智能手機(jī)上運(yùn)行,也可以在計(jì)算機(jī)上運(yùn)行。

  2. 退出程序時(shí)可保護(hù)現(xiàn)場(chǎng),下次再運(yùn)行自動(dòng)恢復(fù)到原來(lái)的狀態(tài)。

  3. 玩家通關(guān)后可以使用“錄像”功能保存通關(guān)步驟,以便將來(lái)“回放”。

  4. 可以自由設(shè)計(jì)關(guān)卡,批量進(jìn)行數(shù)據(jù)導(dǎo)出和導(dǎo)入。

  如下圖的“解決方案資源管理器”所示,該程序的源程序主要分布在“Window”和“Common”兩個(gè)文件夾中。其中“Window”文件夾存放的是程序主窗體和各個(gè)對(duì)話框的源代碼。而“Common”文件夾存放的是公用的源代碼,包括各種數(shù)據(jù)結(jié)構(gòu),尋找最短路線的算法,讀寫配置文件和數(shù)據(jù)文件等。

  我將在隨后的文章中詳細(xì)介紹各個(gè)源程序文件。

  對(duì)了,推箱子程序的下載地址為:http://ben.skyiv.com/PushBox

  以下是部分軟件界面截圖:

 C#開(kāi)發(fā)的推箱子

C#開(kāi)發(fā)的推箱子

  

C#開(kāi)發(fā)的推箱子

  

C#開(kāi)發(fā)的推箱子

  

C#開(kāi)發(fā)的推箱子        C#開(kāi)發(fā)的推箱子

  C#開(kāi)發(fā)的推箱子  C#開(kāi)發(fā)的推箱子

這次,我先介紹 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 /// 打開(kāi)一個(gè)文本文件,將文件的所有行讀入一個(gè)字符串,然后關(guān)閉該文件。-- File
  19 /// 
  20 /// 要打開(kāi)以進(jìn)行讀取的文件
  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)建一個(gè)新文件,在其中寫入指定的字符串,然后關(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 /// 加法運(yùn)算的結(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 }


  俗話說(shuō),工欲善其事,必先利其器。我們知道,Microsoft .NET Compact Framework 只是 Microsoft .NET Framework 的一個(gè)子集,她省略了一些不常用的功能。但是,如果我們恰好需要這些功能,只好自己重新實(shí)現(xiàn)一下了。這個(gè) Fcl 靜態(tài)類就是起這個(gè)作用的。源程序代碼的注釋已經(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;
  }
  }
  }


  可惜的是,這段代碼無(wú)法在 .NET Compact Framework 下通過(guò)編譯(如果是 .NET Framework 則沒(méi)有問(wèn)題)。原因是 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 所支持。這實(shí)在是一件很奇怪的事,既然 .NET CF 都支持 PlatformID 的 Win32NT、Win32S、Win32Windows、WinCE 成員,為什么就不能支持 Unix 成員呢?這樣,這個(gè)程序?qū)?lái)要移植到 Linux 操作系統(tǒng)時(shí)就有些小麻煩了。

  要知道,這在主窗體的代碼中用以下一段代碼來(lái)實(shí)現(xiàn)在智能手機(jī)上禁用“前端顯示”功能。

以下是引用片段:
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)文件用,依次代表以上各項(xiàng)
  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 用來(lái)表示基本單元格: 空地、槽(箱子最終要存放的目的地)、墻、磚(在本程序中等同于“墻”,一般放在墻的外圍,使圖形看起來(lái)漂亮些)、箱子、工人。其中“箱子”和“工人”都可以位于“空地”或“槽”上,所以總共有八種狀態(tài),用 0 到 7 表示,總共只需要三個(gè)二進(jìn)位,可以放入一個(gè)字節(jié)中。在數(shù)據(jù)文件(*.bxb)中,每個(gè)基本單元格就是用一個(gè)字節(jié)儲(chǔ)存的,這在以后介紹的 Common/DataFile.cs 源程序文件中會(huì)看到。但是為什么靜態(tài)類 Block 的大多數(shù)方法的參數(shù)都是 ushort 類型呢?這是為了尋找工人最短移動(dòng)路線算法的需要,看了下一篇介紹 Common/FindPath.cs 源程序文件的文章就會(huì)明白了。

  這個(gè)類還是比較簡(jiǎn)單的,現(xiàn)簡(jiǎn)要說(shuō)明如下:

  GetPenName 方法返回在設(shè)計(jì)關(guān)卡時(shí)所用畫筆的名稱。

  Update 方法用來(lái)在設(shè)計(jì)關(guān)卡時(shí)更新地圖中的基本單元格。

  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)入時(shí)。

  Mark 方法在尋找工人最短移動(dòng)路線算法中用來(lái)標(biāo)記已經(jīng)搜索過(guò)的基本單元格。

  CleanAllMark 方法在上述算法結(jié)束時(shí)用來(lái)清除地圖中的所有基本單元格的標(biāo)記。

  Value 方法返回上述算法搜索過(guò)程中所作的標(biāo)記。

  ManIn、ManOut、BoxIn、BoxOut 方法用來(lái)更新推箱子過(guò)程中地圖各基本單元格的狀態(tài)。

  IsSlot、IsBlank、IsBox、IsMan 方法用來(lái)判斷各基本單元格的類型。

  補(bǔ)充:尋找工人最短移動(dòng)路線的算法已經(jīng)作了改進(jìn),地圖使用 byte 存儲(chǔ)就行了,所以靜態(tài)類 Block 中的所有“ushort”都要修改為“byte”。請(qǐng)參見(jiàn)“使用 C# 開(kāi)發(fā)智能手機(jī)軟件:推箱子(五)”中的說(shuō)明。

在這篇文章中,介紹 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ā)點(diǎn)
  /// 目的地
  /// 最短路線
  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ā)點(diǎn)(即工人的位置)
  Point nbr = new Point(); // 四周的鄰居
  for (value--; value > 0; value--) // 逐步走向目的地
  {
  for (int i = 0; i < offsets.Length; i++)
  {
  nbr = Fcl.Add(here, offsets[i]); // 開(kāi)始尋找四周的鄰居
  if (Block.Value(map[nbr.Y, nbr.X]) == value) // 就往這個(gè)方向走
  {
  moveQueue.Enqueue(directions[i]); // 路線向目的地延伸一步
  break;
  }
  }
  here = nbr; // 繼續(xù)前進(jìn)
  }
  }
  Block.CleanAllMark(map); // 清除所有標(biāo)志,恢復(fù)現(xiàn)場(chǎng)
  return moveQueue; // 所尋找的路線,如果無(wú)法到達(dá)目的地則為該路線的長(zhǎng)度為零
  }
  /// 
  /// 尋找最短路線,使用廣度優(yōu)先搜索
  /// 
  /// 地圖
  /// 目的地
  /// 輸出:路線的長(zhǎng)度(加1)
  /// 是否成功
  static bool Seek(ushort[,] map, Point to, out int value)
  {
  Queue q = new Queue();
  Block.Mark(ref map[to.Y, to.X], 1); // 從目的地開(kāi)始往回尋找出發(fā)點(diǎn),目的地標(biāo)記為1
  Point nbr = Point.Empty; // 四周的鄰居
  for (; ; )
  {
  value = Block.Value(map[to.Y, to.X]) + 1; // 離開(kāi)目的地的距離(加1),用作標(biāo)記
  for (int i = 0; i < offsets.Length; i++)
  {
  nbr = Fcl.Add(to, offsets[i]); // 開(kāi)始尋找四周的鄰居
  if (Block.IsMan(map[nbr.Y, nbr.X])) break; // 到達(dá)出發(fā)點(diǎn)(即工人的位置)
  if (Block.IsBlank(map[nbr.Y, nbr.X])) // 可以走的路
  {
  Block.Mark(ref map[nbr.Y, nbr.X], value); // 標(biāo)記,防止以后再走這條路
  q.Enqueue(nbr); // 加入隊(duì)列,等待以后繼續(xù)尋找
  }
  }
  if (Block.IsMan(map[nbr.Y, nbr.X])) break; // 到達(dá)出發(fā)點(diǎn)
  if (q.Count == 0) return false; // 無(wú)法到達(dá)出發(fā)點(diǎn)
  to = q.Dequeue(); // 出隊(duì),繼續(xù)尋找,這是廣度優(yōu)先搜索,因?yàn)榍懊嬉呀?jīng)把四周能夠走的路全部加入隊(duì)列中了.
  }
  return true; // 找到一條路線
  }
  }
  }

  靜態(tài)類 FindPath 是用來(lái)尋找工人移動(dòng)到鼠標(biāo)點(diǎn)擊的目的地的最短路線的。她采用一種廣度優(yōu)先搜索算法,使用循環(huán),沒(méi)有使用遞歸,而且地圖上已經(jīng)搜索過(guò)的路線決不再走第二遍。該算法分兩個(gè)階段進(jìn)行:首先是尋找并標(biāo)記最短路線,由該類的第二個(gè) Seek 方法實(shí)現(xiàn),這個(gè)私有的方法返回一個(gè)布爾值表明是否成功。然后,如果在第一階段中找到了一條路線,則根據(jù)第一階段所做的標(biāo)記生成最短路線并將該路線返回給調(diào)用者。我們來(lái)看幾個(gè)實(shí)例:

  c#開(kāi)發(fā)手機(jī)游戲推箱子c#開(kāi)發(fā)手機(jī)游戲推箱子

  在該算法中,是從要到達(dá)的目的地開(kāi)始往回尋找出發(fā)點(diǎn)。首先,將目的地標(biāo)記為1,然后查看周圍的四個(gè)鄰居(按南、東、北、西的順序)是否是“空白”(即“地”和“槽”,使用 Block.IsBlank 方法來(lái)判斷),如是,則表明這是可以走的路,將其作上標(biāo)記(使用 Block.Mark 方法,標(biāo)記的數(shù)值等于離開(kāi)目的地的距離加一),然后加入隊(duì)列。這有兩個(gè)作用,首先,標(biāo)記過(guò)的單元格將不再被認(rèn)為是可以走的路,防止重復(fù)搜索。其次,在第二階段中要根據(jù)標(biāo)記的值來(lái)生成最短路線。如果發(fā)現(xiàn)周圍的鄰居中有一個(gè)是工人(用 Block.IsMan 方法來(lái)判斷),說(shuō)明到達(dá)出發(fā)點(diǎn),則立即結(jié)束搜索,退出循環(huán),返回成功。否則,就檢查隊(duì)列是否為空,如果為空,則說(shuō)明無(wú)法到達(dá)出發(fā)點(diǎn),返回失敗。如果不為空,則出隊(duì),從這一點(diǎn)繼續(xù)開(kāi)始搜索。如此一直循環(huán)。

  這個(gè)算法是廣度優(yōu)先的,如上面的兩個(gè)圖所示,該算法是按標(biāo)記的值從小到大進(jìn)行遍歷的,而該標(biāo)記的值表示的是離開(kāi)目的地的距離加一。

  第二個(gè)階段,如果在第一階段返回失敗,則返回一條空的路線(長(zhǎng)度為零)給調(diào)用者。否則,從出發(fā)點(diǎn)(即工人的位置)開(kāi)始,查看周圍的四個(gè)鄰居(按南、東、北、西的順序),如果其標(biāo)記的值(使用 Block.Value 方法來(lái)獲得)為到目的地的距離加一(至少可以找到一個(gè),可能有多個(gè),可以任取一個(gè),程序中使用第一個(gè)),就往這個(gè)方向走。如此一直循環(huán),直到到達(dá)目的地。然后返回這條路線給調(diào)用者。

  從這里可以看出,為什么地圖(即 ushort[,] map)要使用 ushort 而不使用 byte。因?yàn)樵谠撍惴ㄐ枰诘貓D中作標(biāo)記,而且標(biāo)記的值還必須是到目的地的距離加一(如果只須判斷目的地是否可達(dá),而不要求給出到達(dá)目的地的具體路線,則在算法中標(biāo)記的值可全部都為1,這樣用 byte 就足夠了)。地圖中總共有八種類型的單元格,需要用三個(gè)二進(jìn)位表示。而 byte 只有八個(gè)二進(jìn)位,那么,只剩下五個(gè)二進(jìn)位,25=32,也就是說(shuō),目的地在工人32步以外該算法就無(wú)能為力了。而 ushort 有十六個(gè)二進(jìn)位,減去三個(gè),還有十三個(gè)二進(jìn)位,213=8192,這應(yīng)該足夠了。讓我們看看下圖吧:

c#開(kāi)發(fā)手機(jī)游戲推箱子

  這是一個(gè) 9x9 的地圖,共有81個(gè)單元格,其中49個(gè)是空地,假設(shè)目的在地圖的右上角(標(biāo)記為1的地方),則工人需要48步才能到達(dá)目的地。根據(jù)計(jì)算,如果是 NxN (這里N是奇數(shù))的地圖,工人在最壞的情況下需要 (N2 - 1)/2 + N -1 步(走最短路線)才能到達(dá)目的地。這就是說(shuō),在 127x127 的地圖上,工人最多只需要 8190 步就可以到達(dá)目的地,這剛好在我們算法的范圍之內(nèi)。如果地圖再大,我們的算法就可能(只是可能,因?yàn)樵诖蟮貓D上一般情況下并不會(huì)出現(xiàn)超過(guò) 8192 步的最短路線)無(wú)能為力了。

 

在這篇文章中介紹經(jīng)過(guò)改進(jìn)后的 Common/FindPath.cs 源程序文件。也就是說(shuō),已經(jīng)實(shí)現(xiàn)了“使用 C# 開(kāi)發(fā)智能手機(jī)軟件:推箱子(四)”的第二個(gè)評(píng)論中的想法,將地圖 ushort[,] map 改為 byte[,] map 了。下面就是改進(jìn)后的 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ā)點(diǎn)
  20 /// 目的地
  21 /// 最短路線
  22 public static Queue Seek(byte[,] map, Point from, Point to)
  23 {
  24 Queue moveQueue = new Queue(); // 路線
  25 int value; // 與離目的地距離相關(guān)的一個(gè)量,變化規(guī)律:  => 2 => 1 => 3 => 2 => 1 => 3 => 2 => 1
  26 if (Seek(map, to, out value)) // 找到了一條路線
  27 {
  28 Point here = from; // 出發(fā)點(diǎn)(即工人的位置)
  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]); // 開(kāi)始尋找四周的鄰居
  35 if (Block.Value(map[nbr.Y, nbr.X]) == value) // 就往這個(gè)方向走
  36 {
  37 moveQueue.Enqueue(directions[i]); // 路線向目的地延伸一步
  38 break;
  39 }
  40 }
  41 here = nbr; // 繼續(xù)前進(jìn)
  42 }
  43 }
  44 Block.CleanAllMark(map); // 清除所有標(biāo)志,恢復(fù)現(xiàn)場(chǎng)
  45 return moveQueue; // 所尋找的路線,如果無(wú)法到達(dá)目的地則為該路線的長(zhǎng)度為零
  46 }
  47
  48 /// 
  49 /// 尋找最短路線,使用廣度優(yōu)先搜索
  50 /// 
  51 /// 地圖
  52 /// 目的地
  53 /// 輸出:搜索完成時(shí)標(biāo)記的值
  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); // 從目的地開(kāi)始往回尋找出發(fā)點(diǎn),目的地標(biāo)記為1
  59 Point nbr = Point.Empty; // 四周的鄰居
  60 for (; ; )
  61 {
  62 value = Block.Value(map[to.Y, to.X]) % 3 + 1; // 與離目的地距離相關(guān)的一個(gè)量,用作標(biāo)記,變化規(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]); // 開(kāi)始尋找四周的鄰居
  66 if (Block.IsMan(map[nbr.Y, nbr.X])) break; // 到達(dá)出發(fā)點(diǎn)(即工人的位置)
  67 if (Block.IsBlank(map[nbr.Y, nbr.X])) // 可以走的路
  68 {
  69 Block.Mark(ref map[nbr.Y, nbr.X], value); // 標(biāo)記,防止以后再走這條路
  70 q.Enqueue(nbr); // 加入隊(duì)列,等待以后繼續(xù)尋找
  71 }
  72 }
  73 if (Block.IsMan(map[nbr.Y, nbr.X])) break; // 到達(dá)出發(fā)點(diǎn)
  74 if (q.Count == 0) return false; // 無(wú)法到達(dá)出發(fā)點(diǎn)
  75 to = q.Dequeue(); // 出隊(duì),繼續(xù)尋找,這是廣度優(yōu)先搜索,因?yàn)榍懊嬉呀?jīng)把四周能夠走的路全部加入隊(duì)列中了.
  76 }
  77 return true; // 找到一條路線
  78 }
  79 }
  80 }

  上面的源程序已經(jīng)對(duì)搜索算法作了很好的注釋。我們還是來(lái)看兩幅反映算法運(yùn)行時(shí)地圖上各標(biāo)記值的圖片吧:

  

c#開(kāi)發(fā)手機(jī)游戲推箱子

c#開(kāi)發(fā)手機(jī)游戲推箱子

  圖中,帶圓圈的紅色的數(shù)字“1”是“目的地”,也就是算法開(kāi)始的地方,因?yàn)樵撍惴ㄊ菑哪康牡亻_(kāi)始往回尋找出發(fā)點(diǎn)。在改進(jìn)后的算法中,標(biāo)記值始終是在“1、2、3”這三個(gè)數(shù)中循環(huán),而不是象以前一樣一直增大。在圖中,算法按“紅、黃、綠、藍(lán)、粉紅、青”的順序從目的地往外搜索,直到遇到“工人”而返回成功,或者填滿能夠到達(dá)的空地而返回失敗。

  算法經(jīng)過(guò)這次改進(jìn),搜索的距離就不象原來(lái)一樣受限于 8192 步。而且也將地圖所占用的內(nèi)存空間減少到原來(lái)的二分之一。

  這次改進(jìn),除了仔細(xì)重寫了 FindPath 類以外,程序其余地方只是將所有的“ushort”替換為“byte”就行了,因?yàn)楸境绦蛑辉谏婕暗貓D的地方使用過(guò)“ushort”。

關(guān)鍵詞:C#