iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 7
5
Software Development

遊戲之美 - 連連看經典遊戲開發系列 第 7

[7 - 遊戲邏輯] 電腦搜尋路徑

判斷是否存在任一條路徑

在這個連連看遊戲中,是有可能存在死局的,也就是沒有任何兩個圖案可以用兩個轉彎內的線連接起來時。這時我們需要讓電腦能夠自動判斷這種狀況並做出反應,讓玩家可以更明確知道是否有可行的路徑。

那要如何判斷是否存在任一可能路徑呢?有幾個條件:

  • 第一點:電腦能夠判斷連線是否合法
  • 第二點:遍歷所有可能的圖案去確認是否存在可能路徑

第一點在上一篇我們已經做到了,因此在這一篇,我們要找到一個較省時的方式去遍歷所有可能的連線是否存在。

搜尋方法構思

下圖是我在思考電腦自動搜尋時的搜尋邏輯:

因為我希望電腦在搜尋時,能夠避免搜尋已搜尋過的路徑,因此應要紀錄已搜尋過的組合有那些。

為了方便紀錄與判別是否已搜尋過,我決定以圖案來做搜尋依據,由最盤面最左上開始,每遇到一個符號,就判別該符號是否有任何可能可以連線的兩個圖案。

所以我們會需要下面幾件事情:

  • 遍歷盤面,並在找到路徑時停止搜尋
  • 紀錄已搜尋過的符號並避免重複搜尋
  • 列出現有符號可能兩兩連線的所有排列組合
  • 判別兩點間能否連線

程式實作

第四點我們在上一篇文章裡已經完成該功能,因此現在我們應該要做的有1~3項,這部份的程式碼如下:

   //取得第一條搜尋到的已知存在路徑
    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這個函數主要是要取得盤面上所有這個符號的位置,方法內容如下:

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個所有可能的排列組合

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;
}

如果傳入的是4,也就是C4取2=6,一共會有六種排序的可能性。

查一下維基百科,裡面有相關的解釋:排列組合
因為兩點間的路徑不會受到先後順序的影響而影響是否能連線,並且相同的點不可連線,這邊我一律讓第一個數字(index)小於第二個數字(index),因此用這個判斷式i != j && i <= j來排除重覆的組合。
用下面的函數,若是同樣的符號有4個,則輸入值為4,輸出值會是[[0,1],[0,2],[0,3],[1,2],[1,3],[2,3]]

上面做完了電腦自動搜尋路徑的功能,可以使用在兩個地方,第一個地方是,當盤面沒有任何路徑可以走時,要自動重整盤面。
這部份的程式碼如下:

//判斷還有沒有路走
if(board.gameRoundEnd()){
    alert("恭喜完成遊戲!");
    board = new Board();
    vm.boardContent = board.board;
}else if(board.getFirstExistPath() == null){
    vm.reloadTimes++;
    board.rearrangeBoard();//重整盤面
}

而重整盤面的程式碼如下:

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


上一篇
[6 - 遊戲邏輯] 連線消除程式撰寫
下一篇
[8 - 遊戲介紹] 遊戲歷史簡介
系列文
遊戲之美 - 連連看經典遊戲開發31

尚未有邦友留言

立即登入留言