這是“使用
C＃ 開發智能手機軟體：推箱子”系列文章的第四篇。
在這篇文章中，介紹 Common/FindPath.cs 源程式檔案。
using System;
using System.Drawing;
using System.Collections.Generic;
namespace Skyiv.Ben.PushBox.Common
{
/// <summary>
/// 尋找最短路線
/// </summary>
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 };
/// <summary>
/// 尋找最短路線
/// </summary>
/// <param name="map">地圖</param>
/// <param name="from">出發點</param>
/// <param name="to">目的地</param>
/// <returns>最短路線</returns>
public static Queue<Direction> Seek(ushort[,] map, Point from, Point to)
{
Queue<Direction> moveQueue = new Queue<Direction>(); // 路線
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; // 所尋找的路線,假設無法到達目的地則為該路線的長度為零
}
/// 尋找最短路線,使用廣度優先搜尋
/// <param name="value">輸出:路線的長度(加1)</param>
/// <returns>是否成功</returns>
static bool Seek(ushort[,] map, Point to, out int value)
Queue<Point> q = new Queue<Point>();
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 步的最短路線)無能為力了。