在上篇文章“使用 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 步的最短路線)無能為力了。
