在這篇文章中，介紹 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 步的最短路線)無能為力了。