[4 – 遊戲邏輯] 產生初始盤面

棋盤設計

用一個陣列來代表盤面,裡面儲存1~N來代表不同的圖形

隨機產生盤面

觀察連連看遊戲裡,同樣的圖形通常會有四個,因此如果盤面是10×10的話,總共會有100的icon,一種icon會有四個,則代表會有25種不同的icon。

一開始為了方便測試,先製作6*6=36的棋盤,這樣會有36/4=9種不同的icon。

這時候可以看到已經會有一個隨機產生不同資料的6×6盤面了

呈現陣列內容

接著在邏輯撰寫的版本因為為了測試方便,我們使用angularJS來呈現這個棋盤,因為angular有bindle資料的功能,可以讓棋盤消除更加的容易。
html檔案的內容如下:

js檔案的內容如下:

上面的程式碼可以產生一個符合陣列內容的table盤面,裡面標明數字,如果任選一個數字,底部會反紅做提示,若選擇的第二個數字與第一個所選的數字相同,則會把所選的值存在select2,並且把selected的標籤設定為false。
上面程式碼的產出如下:

這邊是js bin的連結:https://jsbin.com/raqilezuye/edit?html,js

改使用Typescript開發

因為後面的程式邏輯將會越來越複雜,因此要將上面在JS Bin開發的程式碼搬到本地端的project上。

改好後的專案在此:ironman2018-3

下載後請執行下列指令安裝

安裝後可以用下列指令來打開網站

就可以成功打開網頁看到專案的結果了。

[3 – 環境設定] 開發環境介紹

VS Code

Visual Studio Code(簡稱VS Code)是一個由微軟開發的IDE,它最大的優點就是它是完全免費且Open Source的。它支援偵錯,並內建了Git版本控制功能,同時也具有開發環境功能。我個人覺得他在算是滿方便好用的,自動提示、自動補完和顏色選擇功能都很強大。

這邊是下載連結:Download Visual Studio Code

NPM

NPM 是 Node Package Manager 的簡稱,它是一個線上套件庫,可以下載各式各樣的 Javascript 套件來使用。

過去如果我們想要使用jQuery,就會需要去下載一個JQuery的Library檔案放進專案目錄裡。但是當這樣的Library庫檔案越來越大,而且越來越多時,就會較難管理,也會造成svn或git等版本管理系統要多去管控一些根本不屬於這個專案的程式碼,Library之間的版本管理也會較為困難。另外很多元件庫或許只需要在開發時期用到,在部署時不需要用到。這些都會讓套件的管理增加複雜度。因此現在大多數的前端工程師都會使用npm來做套件管理的工具,能夠解決上述的那些問題。

安裝npm要先去安裝Node.js。Node.js 在 0.6.3 版本開始內建 npm,讀者安裝的版本若是此版本或更新的版本,就可以略過以下安裝說明。

若要檢查 npm 是否正確安裝,可以使用以下的指令:

要初始化一個npm專案,則使用下列指令,然後依序出現相關項目來讓我們填寫


按下enter後就會在資料夾目錄裡面看到資料夾內增加了一個名為package.json的檔案,這個檔案會紀錄這個專案的許多相關資訊。

下面為一個簡單的package.json的範例

TypeScript

TypeScript是一種由微軟開發的自由和開源的程式語言。它是JavaScript的一個嚴格超集,並添加了靜態型別和類別基礎的物件導向特性。TypeScript是由C#的首席架構師以及Delphi和Turbo Pascal的創始人安德斯·海爾斯伯格參與了TypeScript的開發。

TypeScript設計目標是開發大型應用,然後轉譯成JavaScript。由於TypeScript是JavaScript的嚴格超集,任何現有的JavaScript程式都是合法的。TypeScript程式物件導向的特性能讓我們在寫TypeScript的時候,有像是寫強型別的語言一樣輕鬆自在,IDE 也可以幫你檢查基本的錯誤。在將TypeScript編譯成JS時,也可以設定是要轉成那種版本的JS,如:EC5、EC6。避免在寫程式還要去注意不同版本JS的兼容性。

安裝TypeScript的命令行工具安裝方法如下:

編譯ts文件的方法如下

但是當我們在開發一個較大型的專案時,一般我們不可能一個一個檔案用上面的指令去complier,這時候我們會設定一個typescript的config檔案:tsconfig.json
這邊是關於這個config的設定教學:tsconfig.json

下面是一個tsconfig.json的簡單範例,compilerOptions用來設定如何來編譯ts文件

這個手冊有更詳細的解說每一個設定的意義:TypeScript配置文件tsconfig简析

Gulp

安裝完node.js後,就是使用 windows 的 cmd 或 Mac 的 Termial 來安裝 Gulp,首先我們先輸入以下的指令,把 Gulp 安裝好,並且設定是只有在開發時期會使用到。
首先要先將gulp安裝到全域領域,這樣我們才能使用cmd等去呼叫gulp執行工作(若mac環境前面要加sudo)

然後在剛剛設定好的專案裡,設定我們的專案要使用到gulp模組。至於為什麼要有-save-dev呢?當我們寫-save-dev,會將這個模組添加到package.json的devDependencies裏頭,如果寫-save,就會添加到dependencies裡,這兩個的差異在於讓使用具備這個package.json專案的人,可以清楚的知道這個模組,是開發使用,還是執行專案時使用的。

因為我們是使用typescript,因此也要安裝gulp-typescript

下面是我們所設定的gulpfile.js,這個檔案主要是要設定我們部署時要做的動作。
例如下面的範例可以在呼叫gulp default時自動做下面的幾個步驟

  • 編譯ts檔案
  • copy相關資源/li>
  • bundle
  • 使用browserSync來開啟並同步更新網頁

GitHub

這一個專案的所有程式碼我都會放在這個gitHub儲存庫:https://github.com/cochiachang/ironman2018

因為Git使用主題太大了,所以不熟悉的讀者可參考此文:30 天精通 Git 版本控管

參考資料

[2 – 演算法] 演算法介紹

何為演算法

演算法的簡單定義輸入 + 演算法 = 輸出
這一篇文章有非常詳細的介紹演算法是什麼:初學者學演算法-談什麼是演算法和時間複雜度

一般判斷演算法的好壞是使用『空間複雜度』和『時間複雜度』來評估,

時間複雜度

所謂時間複雜度,指的是執行一段演算法,跑完整個運算邏輯所要花的時間。
雖然這個複雜度名為『時間複雜度』,但實際上,我們要真正衡量某個演算法時,是以步驟次數來看。

如果一個演算法執行的步驟是固定的,無關輸入的值而改變,那我們會記成 O(1),例如:

而下面這個演算法:

這個演算法則是依據輸入的 n 的數量會跑 n 次,所以是 O(n)

有時若跑的次數較不固定,如:

這個演算法雖然跑了 n×(n−1)=n2−n 次,但我們還是會記做 O(n2) ,也就是說,只要找出最高次方,並且把係數拿掉即可。

空間複雜度

而一個程式的空間複雜度是指完全地執行程式所需的記憶體量

例如下面這個函式,不管程式跑了幾遍,都不會影響使用的變數數量:

故該函式的空間複雜度記做 O(1)

但下面這個函式,會隨著丟進去的數字而影響變數的量,例如:

故該函式空間複雜度為 O(n)

遞迴的空間複雜度一般是與最深的呼叫深度成正比,若遞迴中有局部的變數或參數,所需的空間複雜度會更高

演算法的經典例子

人工智慧也是演算法的一種,如著名的旅行推銷員問題(Travelling salesman problem, TSP),在假定已知每個城市間的距離,在不重複訪問同一個城市下,如何求出最快速的行程組合,這就已經是電腦科學中著名的難解問題。

(Source:By Saurabh.harsh)

一筆畫問題也是很經典的演算法議題。一筆畫問題是柯尼斯堡七橋問題經抽象化後的推廣,是圖遍歷問題的一種。在柯尼斯堡問題中,如果將橋所連接的地區視為點,將每座橋視為一條邊,那麼問題將變成:對於一個有著四個頂點和七條邊的連通圖G(S,E),能否找到一個恰好包含了所有的邊,並且沒有重複的路徑。歐拉將這個問題推廣為:對於一個給定的圖,怎樣判斷是否存在著一個恰好包含了所有的邊,並且沒有重複的路徑?這就是一筆畫問題。

(Source:By 維基百科)

這個問題的解答是:如果一個圖能一筆畫成,那麼對每一個頂點,要麼路徑中「進入」這個點的邊數等於「離開」這個點的邊數:這時點的度為偶數。要麼兩者相差一:這時這個點必然是起點或終點之一。注意到有起點就必然有終點,因此奇頂點的數目要麼是0,要麼是2

程式之美-微軟技術面試心得裡,也給了讀者了許多很經典的演算法題目,例如:構造數獨遊戲、一疊蔥油餅的排序、一排石頭的遊戲、俄羅斯方塊遊戲、踩地雷遊戲的機率、連連看遊戲,都是我感到十分有興趣的演算法議題。

連連看遊戲的演算法設計方向

後來因為我小時候很喜歡玩kawai連連看,所以就選擇這款遊戲做為這次鐵人賽的題目,書中對於連連看遊戲所給的思考方向如下:

假如讓你來設計一個連連看遊戲的演算法,你會怎麼做呢?要求如下:

  • 如何用簡單的電腦模型來描述這個問題?
  • 如何判斷兩個圖形能否相消?
  • 如何求出兩個相同圖形間的最短路徑?(轉彎數最少、路徑經過的格子數目最少)
  • 如何確定目前是處於僵局狀態,並設計演算法來解除僵局?

在經典的最短路徑當中,需要求出經過格子數目最小的路徑。這邊為了確保轉彎次數最少,需要把最短路徑問題的目標函數修改為從一個點到另一個點。雖然目標函數修改了,但演算法的框架仍然可以保持不變。廣度優先搜尋是解決經典最短路徑問題的一個思考方向。

根據上面的說明,我們若想要做一個連連看的遊戲,需要思考解決下列問題:

  • 產生遊戲初始局面:如何用電腦資料格式來儲存一個圖形資料
  • 判斷是否可相消:每次使用者選擇兩個圖形,如果圖形滿足一定條件(兩個圖形相同,且這兩個圖形之間存在少於三個轉彎以下的路徑)則可以消除圖形。
  • 判斷僵局:搜尋全部現有場景上的圖案,並判斷是否能夠相消。當玩家不可能再去消除任意兩個圖像的時候,遊戲進入僵局狀態,就隨機打亂局面,打破僵局。

因此,我們至少會需要使用到圖形(Graph)演算法以及搜尋(包含深度與廣度搜尋)演算法

下面我們便先針對這兩個部份的演算法來做介紹。

Graph 資料結構

一張圖由數個點( vertex )以及數條邊( edge )所構成。點與點之間,得以邊相連接,表示這兩點有關聯、關係。

那要如何利用程式語言來表示一張圖?有下列幾種方法(資料來源於此):

  • 相鄰矩陣(Adjacency Matrix):圖形中最常用的是相鄰矩陣。將各節點當做矩陣的行和列的 index,若頂點間有連接則 array[i][j] = 1,反之 array[i][j] = 0。這個方法的缺點在於若遇到稀疏矩陣將浪費許多空間給不存在邊,且頂點可能數量會改變,使用二維矩陣就相對不彈性。
  • 相鄰串列(Adjacency Lists):把一張圖上的點依序標示編號。每一個點,後方串連所有相鄰的點。例如第 4 列之中所列的數字,即是與第 4 點相鄰的點。
  • 關聯矩陣:最簡單的方式,就是用個陣列,記錄所有點與點之間的邊。這種方式相當直觀,也非常節省空間。

搜尋演算法

圖的遍歷,也就是指通盤地讀取圖的資訊:決定好從哪裡開始讀,依照什麼順序讀,要讀到哪裡為止。詳細地設計好流程,始能通盤地讀取圖的資訊;如果設計得漂亮,在解決圖的問題時,還可以一邊讀取圖的資訊,一邊順手解決問題呢!利用最簡單的資料結構 queue 和 stack ,就能製造不同的遍歷順序,得到兩種遍歷演算法: Breadth-first Search(廣度優先搜尋) 和 Depth-first Search (深度優先搜尋)。

深度優先搜尋法

下面是這篇文章裡對深度優先搜尋法所給的解釋:

深度優先搜尋法,是一種用來遍尋一個樹(tree)或圖(graph)的演算法。由樹的根(或圖的某一點當成 根)來開始探尋,先探尋邊(edge)上未搜尋的一節點(vertex or node),並儘可能深的搜索,直到該節點的所有邊上節點都已探尋;就回溯(backtracking)到前一個節點,重覆探尋未搜尋的節點,直到找到目 的節點或遍尋全部節點。

深度優先搜尋法屬於盲目搜索(uninformed search)是利用堆疊(Stack)來處理,通常以遞迴的方式呈現。

範例: 以深度優先搜尋法找出下圖的所有節點順序:

假設起始點為 A,且每一節點由左至右的順序來搜尋下個節點,則結果為: A, B, E, F, D, C, G

廣度優先搜尋法

下面是這篇文章裡對廣度優先搜尋法所給的解釋:

廣度優先搜尋法,是一種圖形(graph)搜索演算法。從圖的某一節點(vertex, node)開始走訪,接著走訪此一節點所有相鄰且未拜訪過的節點,由走訪過的節點繼續進行先廣後深的搜尋。以樹(tree)來說即把同一深度(level)的節點走訪完,再繼續向下一個深度搜尋,直到找到目的節點或遍尋全部節點。

廣度優先搜尋法屬於盲目搜索(uninformed search)是利用佇列(Queue)來處理,通常以迴圈的方式呈現。

範例: 廣度優先搜尋法找出下圖的所有節點順序:

假設起始點為 A,且每一節點由左至右的順序來搜尋下個節點,則結果為: A, B, C, D, E, F, G

連連看遊戲的演算法構思

圖形儲存方式

以連連看來說,因為在連連看的棋盤裡,任意兩個同一排或同一列的點,都可以做直線相連,我們若用一個二維陣列直接來儲存棋盤內容,可以用該陣列第一個索引值或第二個索引值是否相同,來判別是否在同一條線上

若圖形為10X10的棋盤,則陣列設計如下:

用這樣的陣列的儲存方式,我們可以注意到,上圖的x,y軸的位置,和一般我們在做遊戲時的x,y軸的方向會剛好相反,這一點要特別注意,才不會在計算點與點間的位置時出錯。

而路徑的部份則使用上面圖演算法中的關連矩陣去紀錄,如[[0,0],[-1,0],[-1,8],[0,8]],在連連看遊戲裡,每一個合法的路徑都應由四個或以內的點所組成成。並且每一個點之間,必定要有相同的x或相同的y。我們可以用這樣的條件去搜尋判斷可能存在的路徑。

路線搜尋方式

在一般我們做最短路徑搜尋的情況,都會以廣度優先搜尋為主。

在連連看裡面,連線的線條不可大於兩個轉彎處,兩個轉彎處的意思,代表連接的線最多只能由三條直線來組成

由上圖可以發現,我們可以以直線做為搜尋單元,先搜尋A點上、下、左、右最遠能到達的點,對比B點上、下、左、右最遠可以到達的點,判斷是否有可能可以形成一條連線,若有可能,再去尋找是否中間存在可能的第二條線。

參考資料