在該算法中,是從要到達的目的地開始往回尋找出發點。首先,將目的地標記為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 步的最短路線)無能為力了。