程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> 用C#開發智能手機軟件:推箱子(四)(2)

用C#開發智能手機軟件:推箱子(四)(2)

編輯:關於C語言
態類 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 步的最短路線)無能為力了。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved