廣度優先演算法實作-國際象棋最短路徑

摘要:

第一步:
本研究比照國際象棋8*8的規格還原出黑白相間的棋盤格作為最先生成的影像。並且我們預留了800(pixels)*100(pixels)的畫布大小輸出隨機生成的起點與終點座標，因此最終生成的棋盤格大小應為800(pixels)*900(pixels)，而每個棋盤格子將賦予100(pixels)*100(pixels)的面積共64格。接下來一樣運用cv2模組去賦予棋盤格子x向及y向的座標標示方便定位座標。
第二步:
我們需要建置棋子，這部分就必須考慮棋子的走法，由於西洋棋子多數不是一格一格走的，於是我們採用相對特殊走法的「騎士」去製作它所有方向的走法，我們以座標向量來表示棋子的位移，並對此建立元組(Tuple)，並將八個方向的位移組合成一個列表(List)，接下來結合先前製作的BFS演算法並將棋子的位移向量dx,dy結合進演算法的運算。最後再以cv2生成出起點為紅色圓點、終點為藍色圓點、路徑為灰色圓點的圖像輸出在對應座標的棋盤格之上，並依序標上棋子位移的步數。
第三步:
加入自行設定不能通行區塊(阻攔格)，並為棋子設計判斷式，使棋子在尋找最短路徑時必須規避掉阻攔格。

心得:

在經歷過這麼多堂課過後，原先還對一些演算法不怎麼清楚，但經過這次的專題實作過後，一切的不清楚都一掃而空了，經過了實際製作演算法並實際應用在生活上，讓我更加理解了哪種演算法應該在哪種情境下使用，並且也學會了如何依當下的問題挑選演算法。專題製作過程中，常常因為自定義判別函數的判定錯誤又或者出生點與與終點亂生成導致一大堆奇特又搞笑的狀況發生，雖然每次都搞得焦頭爛額，但每次成功解決BUG時又覺得一切都值得，同時我也相信這些經歷也會成為我更進一步的墊腳石，以後再做相似的程式設計時也會記得要把cv2視窗關閉便免資源占用、也會知道程式判別函式要在一開始先定義，不然無法生效，當然還有很多，但這些都是這次專題我所得到的寶貴經驗。其中我個人覺得最奇特的體驗是，因為設計過程中常常會不知道接下來的邏輯該如何設計才能讓程式順利跑出來，每次想的心力交瘁的時候，我就想者先休息明天繼續吧!結果隔天一覺醒來後，靈感就源源不絕的跑出來了，這才發現原來昨天搞了一整個晚上非常困難的問題其實可以利用我們已經學過的知識很簡單的解決，這應該是這次專題過程中我覺得最有趣的部分吧。雖然演算法不簡單，但這次專題絕對不會是終點，在未來我希望我能做出更複雜更有趣的演算法，同時也希望能繼續完成這次的專題實作，將這次的專題帶到一個更高更遠的層次。