判斷是否存在任一條路徑
在這個連連看遊戲中，是有可能存在死局的，也就是沒有任何兩個圖案可以用兩個轉彎內的線連接起來時。這時我們需要讓電腦能夠自動判斷這種狀況並做出反應，讓玩家可以更明確知道是否有可行的路徑。
那要如何判斷是否存在任一可能路徑呢？有幾個條件：
- 第一點：電腦能夠判斷連線是否合法
- 第二點：遍歷所有可能的圖案去確認是否存在可能路徑
第一點在上一篇我們已經做到了，因此在這一篇，我們要找到一個較省時的方式去遍歷所有可能的連線是否存在。
搜尋方法構思
下圖是我在思考電腦自動搜尋時的搜尋邏輯：
因為我希望電腦在搜尋時，能夠避免搜尋已搜尋過的路徑，因此應要紀錄已搜尋過的組合有那些。
為了方便紀錄與判別是否已搜尋過，我決定以圖案來做搜尋依據，由最盤面最左上開始，每遇到一個符號，就判別該符號是否有任何可能可以連線的兩個圖案。
所以我們會需要下面幾件事情：
- 遍歷盤面，並在找到路徑時停止搜尋
- 紀錄已搜尋過的符號並避免重複搜尋
- 列出現有符號可能兩兩連線的所有排列組合
- 判別兩點間能否連線
程式實作
第四點我們在上一篇文章裡已經完成該功能，因此現在我們應該要做的有1~3項，這部份的程式碼如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
//取得第一條搜尋到的已知存在路徑 public getFirstExistPath():Path{ var searchedValue = [];//用以紀錄已搜尋過符號 //由最左上開始做判斷 for (var i =0;i<this.board.length;i++){ for (var j = 0; j<this.board[i].length;j++){ let value = this.board[i][j]; //判斷盤面上現在是有符號的（null代表沒有符號） //並且這個符號之前還沒有被搜尋過 if(value!= null && searchedValue.indexOf(value) == -1){ searchedValue.push(value); let positionsArr = this.getPositionByValue(value);//取得盤面上所有這個符號的位置 let permutationsArr = this.getPairNumPermutations(positionsArr.length);//取得可能存在的連線的點的排列組合 //getPairNumPermutations回傳的格式是[[0,1],[0,2],[0,3],[1,2],[1,3],[2,3]]，裡面數字為index //嘗試每一個可能的排列組合 for(var k = 0;k<permutationsArr.length;k++){ let v = permutationsArr[k]; let path = new Path(positionsArr[v[0]], positionsArr[v[1]],this); if(path.canLinkInLine()){ return path; } } } } } return null; } |
getPositionByValue這個函數主要是要取得盤面上所有這個符號的位置，方法內容如下：
|
1 2 3 4 5 6 7 8 9 10 11 |
public getPositionByValue(value:number):Array<Point>{ let arr = new Array<Point>(); for (var i =0;i<this.board.length;i++){ for (var j = 0; j<this.board[i].length;j++){ if (this.board[i][j] == value){ arr.push(new Point(i, j)); } } } return arr; } |
getPairNumPermutations這個函數則是在列出，相同圖案任選2個所有可能的排列組合
如果傳入的是4，也就是C4取2=6，一共會有六種排序的可能性。
查一下維基百科，裡面有相關的解釋：排列組合
因為兩點間的路徑不會受到先後順序的影響而影響是否能連線，並且相同的點不可連線，這邊我一律讓第一個數字(index)小於第二個數字(index)，因此用這個判斷式i != j && i <= j來排除重覆的組合。
用下面的函數，若是同樣的符號有4個，則輸入值為4，輸出值會是[[0,1],[0,2],[0,3],[1,2],[1,3],[2,3]]
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
private pairNumPermutations = {}; /** * 取得輸入的index中，2個2個一組的所有可能排列組合 * 回傳的格式是[[0,1],[0,2],[0,3],[1,2],[1,3],[2,3]] */ public getPairNumPermutations(num:number){ if(this.pairNumPermutations[num] != null){ return this.pairNumPermutations[num]; } let data = []; for(var i = 0; i <num;i++){ for(var j = 0; j <num;j++){ if(i != j && i <= j){ data.push([i,j]); } } } this.pairNumPermutations[num] = data; return data; } |
可行路徑提示
上面做完了電腦自動搜尋路徑的功能，可以使用在兩個地方，第一個地方是，當盤面沒有任何路徑可以走時，要自動重整盤面。
這部份的程式碼如下：
|
1 2 3 4 5 6 7 8 9 |
//判斷還有沒有路走 if(board.gameRoundEnd()){ alert("恭喜完成遊戲!"); board = new Board(); vm.boardContent = board.board; }else if(board.getFirstExistPath() == null){ vm.reloadTimes++; board.rearrangeBoard();//重整盤面 } |
而重整盤面的程式碼如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
public rearrangeBoard(){ let values = this.getAllValueInBoard().sort((a, b) => (Math.random() > .5) ? 1 : 0); for (var i =0;i<this.board.length;i++){ for (var j = 0; j<this.board[i].length;j++){ if(this.board[i][j] != null){ this.board[i][j] = values.pop(); } } } } private getAllValueInBoard(){ let values = []; for (var i =0;i<this.board.length;i++){ for (var j = 0; j<this.board[i].length;j++){ if(this.board[i][j] != null){ values.push(this.board[i][j]); } } } return values; } |
首先先把現有的所有圖案都搜集起來放在一個陣列裡，也就是getAllValueInBoard()所做的事情。
然後再隨機打亂陣列排序，再依序填入盤面上所有有圖案的格子內，就可以達到重整盤面但是不影響到空格的位置。
今日成果
連連看遊戲邏輯至此已大致完成囉！下一篇開始我們會實際開始製作一款實際上具有畫面、音效、特效等真正的網頁連連看遊戲
LIVE DEMO: 今日成果展示
完整程式碼可由此下載：ironman20181022