發佈日期: 發佈留言

[8 – 遊戲介紹] 遊戲歷史簡介

遊戲的要素

前一篇的成果是連連看的純邏輯程式,沒有具備一般遊戲必備的遊戲畫面、動畫、音效、特效等…。
其成果看起來是這樣的:

只有數字的畫面、沒有連線效果只有文字,一般人很難能夠有耐性的持續玩它,去享受其中遊戲的樂趣。

其實,一款成功的遊戲應有幾個不可或缺的要素:

  • 要素一:畫面及音效
  • 要素二:內容架構
  • 要素三:收費機制
  • 要素四:耐玩度及娛樂性

在前一個單元裡,我們完成了這個遊戲內容架構(遊戲邏輯)的部份,這當然是一款遊戲最核心的部份。但是只有這樣,還沒辦法成為一個真正能夠吸引人的遊戲。一個真正能夠吸引人並要能夠持續經營、生存下去的遊戲,上述的四個要點都是不可或缺的。

以智冠的四川省3000來說,就在相同的連連看機制上加了許多額外的遊戲規則和元素,增加遊戲的遊戲性。

例如在一般的過關模式,增加了角色動畫來加強遊戲視覺的享受,並有時間上的限制來增加遊戲緊張感:

並新增了對戰模式,消除特定的圖示來獲得勝利,並要阻擋對方消除到目標的圖示

增加競賽的元素例如高分榜等,也可以增加玩家競爭的動機,讓黏著度提高。

看到上面的遊戲畫面,是不是覺得比起前一篇的成果更吸引你想要去玩看看呢?

在後面的章節中,我們會慢慢將這些遊戲元素加進我們的連連看遊戲裡面。
現在先讓我們來更深入的從「遊戲的發展歷史」來更深入的了解遊戲產業以及相關成功作品所具備的特色。

喜愛遊戲的我們,就讓我們一起回到年輕時代的我們所熱愛過的遊戲吧!Let’s Go!

遊戲的回憶櫥窗

1970-1983年代

1970年代較流行的是大型的遊戲機台,在那個年代的小朋友,下課時總喜歡跑去遊戲機的店裡投幾個硬幣,來玩幾場遊戲,當作下課最開心的休閒娛樂(然後再被大人抓回家)。

在1980年開始有了掌上型的遊戲機,任天堂的Game & Watch開始生產,這是首次有較小型的遊戲機,如下圖:

Game & Watch遊戲機

1983-1990年代

1983年末至1984年早期,製造北美家庭電腦電子產品的幾間公司紛紛破產,終結了電子遊戲的第二世代。隨著1983年的蕭條,電腦遊戲市場於1984年取代了家用機市場。當時電腦提供同等能支援遊戲的硬體能力,並且因為它們簡單的設計允許遊戲在電腦一開機就完全取得硬體的控制,這種方式相當接近如玩家用機般的簡單直接。

家用遊戲機1983年7月15日在日本以「Family Computer」(FC)為名推出,1985年起在歐美以「Nintendo Entertainment System」(簡稱「NES」)為名發行。紅白機是當時最暢銷的遊戲機,全球累計銷量超過了6100萬台。紅白機出現對電子遊戲產生了十分深遠的影響,讓美國電子遊戲界從1983年的崩潰中恢復過來,1985年發售的超級瑪琍,奠定了FC的初步成功。

後續1986年《勇者鬥惡龍系列》第一部《勇者鬥惡龍》發行,這款遊戲在當時風行了很長的一段時間,相信很多讀者也都對這款遊戲很有印象。這款遊戲在日本文化上造成有史以來的奇蹟,又稱國民RPG。

經典的勇者鬥惡龍

在1987年,最終幻想的第一代出現在市場上,這款遊戲至今仍然是許多人心目中最棒的遊戲,它至今已經出到第15代了,這款遊戲的畫面與音效都獲得很大的好評。它是個效法《勇者鬥惡龍》的角色扮演遊戲 (RPG)。《Final Fantasy系列》的賣座拯救了史克威爾公司免於破產,也是遊戲商心裡最成功的RPG角色扮演遊戲。那時的任天堂在家用遊戲機裡一枝獨秀,奠定了任天堂在當今遊戲界的地位。遊戲機的後續機種為1990年推出的超級任天堂。

最終幻想1

約於同時,《薩爾達傳說系列》首部《薩爾達傳說》在1986年於FC遊戲機上登場。這款遊戲也是很經典且在Wii、DS、3DS等都有製作其續集,近年新出的Switch也有推出『薩爾達傳說 曠野之息』,依然獲得了極高的評價。

1990-2000年代

而在1990年代,隨著個人電腦處理器計算能力的增加以及成本降低,開始出現了使用3D運算的遊戲。在1996年後,隨著個人電腦上使用的平價3D加速卡,3D的遊戲包括RTS遊戲如微軟《世紀帝國》、暴雪娛樂的《魔獸爭霸》與《星海爭霸》系列、以及回合制的遊戲如《魔法門之英雄無敵》,都陸續出現在市場上。

微軟《世紀帝國》遊戲截圖

1990開始也是台灣本土遊戲最興盛的時期,智冠的神州八劍與大宇的軒轅劍都在此時發行。

1995年大宇資訊所開發的經典遊戲《仙劍奇俠傳》,故事裡,李逍遙與林月如、趙靈兒、阿奴的浪漫戀情感動了許多的玩家,堪稱台灣最經典的遊戲。這款遊戲在很長的一段時間都非常的受歡迎,也是當時我非常喜歡的遊戲之一。近年也被製作成3D線上遊戲版本,也有以遊戲故事為主軸所翻拍的電視劇。

1996年的金庸群俠傳也是非常有名的遊戲,玩家不再以旁觀者的身份而進行遊戲,而是真正的融入遊戲之中,在完全自由的金庸武俠世界創造自己的歷史。雖然遊戲的畫面效果在當時看來已經略顯粗糙,但是超強的遊戲性完全彌補了這個缺陷,成為第一款能與《仙劍奇俠傳》相提並論的國產遊戲。

此時期其他台灣遊戲如軒轅劍、神鵰俠侶、天之痕、新絕代雙嬌、大富翁系列等等,也都有了很好的成績。

2000-2010年代

2000年以後的時期,隨著網際網路的普及,BBS開始流行,網路應用也被應用在遊戲上,MMORPG(大型多人在線角色扮演遊戲)開始流行。

早期的線上遊戲有許多是半3D的(俗稱2.5D),因為在此時的機器運算能力下,3D畫面無法製作到很精緻,但是又希望能夠有3D的玩家視角。如【仙境傳說】其背景為3D製作、而遊戲角色的動作等則以2D連續圖為主,我們稱之為2.5D,但其本質仍為3D引擎。

仙境傳說遊戲畫面

其他如石器時代、天堂、魔獸世界說都是這個時期非常流行的線上遊戲。

石器時代遊戲畫面
天堂遊戲畫面

魔獸世界遊戲畫面

在線上遊戲風行的時期裡,台灣的遊戲產業因為未能跟上多人線上遊戲的風潮,單機遊戲的盜版問題日益嚴重,導致台灣本土的遊戲產業漸漸沒落。

2010年至今

在2010年之後智慧型手機、平板電腦、智能電視讓遊戲產業有了許多的挑戰,家用遊戲機也在此時變得更加流行,如任天堂3DS、Wii、任天堂Switch、Xbox One、PlayStation 4都讓遊戲有了更多元的發展,近年來虛擬實境的遊戲也是眾家遊戲廠商注目和投資研發的焦點。。

在手機遊戲上,由於是新的市場,在智能手機剛普及時,有許多的獨立遊戲開發者或是小的遊戲製作團隊,得以加入市場一起競爭,憤怒鳥系列是芬蘭遊戲公司Rovio娛樂出品的電子遊戲系列,便在此時紅了起來。

憤怒鳥遊戲

後來網路遊戲免費模式也開始慢慢佔據一片天,比起計時模式,免費遊戲最大的特點就是不再依據玩家上線時間收費,而是賣出遊戲內特殊道具、SKIN、時裝、遊戲內的特殊幣等來收取費用,而這種商業方式後來在手機遊戲也獲得巨大的成功。

一開始的手機遊戲主要是以下載時付費以下載量來賺取營收,如當時的憤怒鳥、植物大戰僵屍等,以新奇的遊戲方式,且低於5美元甚至1美元的價格,吸引消費者購買,當遊戲下載次數高的時候,營收就非常亮眼,例如憤怒鳥1代於2009年底推出,及至2012年下載次數已突破10億次。後來開始有了遊戲內購買的機制,讓玩家能先免費下載遊戲,增加遊戲的普及度,再藉由遊戲內購機制來獲取營收,後來的遊戲扭蛋抽獎機制更成為手遊市場最大商機。

這個收費模式的興起是因為當時的大部分大陸玩家都無法負擔正版正價遊戲而選擇購買盜版,於是發行商放棄傳統販賣遊戲的模式,改而在免費遊戲中設置商城販賣虛擬商品,其中有部份遊戲提供抽獎箱以此來盈利,結果此抽獎系統大大成功,例如日本的龍族拼圖、怪物彈珠還有這兩年爆紅的FGO,芬蘭的部落衝突-皇室戰爭,香港開發的神魔之塔都屬此一商業模式,他們靠著遊戲黏著度還有不斷更新的新技能或高強度的卡牌(或扭蛋),吸引玩家花更多的錢去抽卡,獲得非常巨大的成功。

但此一商業模式由於機率無法透明,且有賭博的成份,因此歐美中各國紛紛以不同的法律來約束或是禁止,APPLE STORE與GOOGLE STORE也要求軟體供應商必須公布抽獎箱的抽出機率,但抽獎箱無保底機制還是讓許多玩家所詬病,因此有些遊戲有幾連抽(通常需30~50)必有SSR卡(Special Super Rare)的保底機制來吸引玩家抽卡,有些玩家因為無保底機制,花了幾百抽的錢但卻連一張SSR卡都沒有,怒刪遊戲、要求退費或是憤而提告的舉動也屢見不鮮

台灣的手機遊戲公司在這個時期較能成功占領市場的為雷亞遊戲,製作了許多經典的音樂手機遊戲,成為台灣遊戲產業的一顆新星。

在2015後隨著手機越來越普及,線上多人的手機遊戲也更為普及,有更多經典的線上遊戲也都紛紛推出手遊版本,如天堂M、仙境傳說M、石器時代M等。

在下一篇文章裡,我們會介紹現在在開發遊戲時常會用到的幾種技術。

參考資料

發佈日期: 發佈留言

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



判斷是否存在任一條路徑

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

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

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

搜尋方法構思

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

因為我希望電腦在搜尋時,能夠避免搜尋已搜尋過的路徑,因此應要紀錄已搜尋過的組合有那些。
為了方便紀錄與判別是否已搜尋過,我決定以圖案來做搜尋依據,由最盤面最左上開始,每遇到一個符號,就判別該符號是否有任何可能可以連線的兩個圖案。
所以我們會需要下面幾件事情:

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

程式實作

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

    //取得第一條搜尋到的已知存在路徑
    public getFirstExistPath():Path{
        var searchedValue = [];//用以紀錄已搜尋過符號
        //由最左上開始做判斷
        for (var i =0;i<this.board.length;i++){
            for (var j = 0; j<this.board&#91;i&#93;.length;j++){
                let value = this.board&#91;i&#93;&#91;j&#93;;
                //判斷盤面上現在是有符號的(null代表沒有符號)
                //並且這個符號之前還沒有被搜尋過
                if(value!= null && searchedValue.indexOf(value) == -1){
                    searchedValue.push(value);
                    let positionsArr = this.getPositionByValue(value);//取得盤面上所有這個符號的位置
                    let permutationsArr = this.getPairNumPermutations(positionsArr.length);//取得可能存在的連線的點的排列組合
                    //getPairNumPermutations回傳的格式是&#91;&#91;0,1&#93;,&#91;0,2&#93;,&#91;0,3&#93;,&#91;1,2&#93;,&#91;1,3&#93;,&#91;2,3&#93;&#93;,裡面數字為index
                    //嘗試每一個可能的排列組合
                    for(var k = 0;k<permutationsArr.length;k++){
                        let v = permutationsArr&#91;k&#93;;
                        let path = new Path(positionsArr&#91;v&#91;0&#93;&#93;, positionsArr&#91;v&#91;1&#93;&#93;,this);
                        if(path.canLinkInLine()){
                            return path;
                        }
                    }
                }
            }
        }
        return null;
    }&#91;/code&#93;
<code>getPositionByValue</code>這個函數主要是要取得盤面上所有這個符號的位置,方法內容如下:
[code lang="js"]    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&#91;i&#93;.length;j++){
                if (this.board&#91;i&#93;&#91;j&#93; == value){
                    arr.push(new Point(i, j));
                }
            }
        }
        return arr;
    }&#91;/code&#93;
<code>getPairNumPermutations</code>這個函數則是在列出,相同圖案任選2個所有可能的排列組合
如果傳入的是4,也就是C4取2=6,一共會有六種排序的可能性。
查一下維基百科,裡面有相關的解釋:<a href="https://zh.wikipedia.org/wiki/%E7%B5%84%E5%90%88" rel="noopener noreferrer" target="_blank">排列組合</a>
因為兩點間的路徑不會受到先後順序的影響而影響是否能連線,並且相同的點不可連線,這邊我一律讓第一個數字(index)小於第二個數字(index),因此用這個判斷式<code>i != j && i <= j</code>來排除重覆的組合。
用下面的函數,若是同樣的符號有4個,則輸入值為4,輸出值會是[[0,1],[0,2],[0,3],[1,2],[1,3],[2,3]]
[code lang="js"]    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(&#91;i,j&#93;);
                }
            }
        }
        this.pairNumPermutations&#91;num&#93; = data;
        return data;
    }&#91;/code&#93;

<h3>可行路徑提示</h3>
上面做完了電腦自動搜尋路徑的功能,可以使用在兩個地方,第一個地方是,當盤面沒有任何路徑可以走時,要自動重整盤面。
這部份的程式碼如下:
[code lang="js"]
                            //判斷還有沒有路走
                            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;igetAllValueInBoard()所做的事情。
然後再隨機打亂陣列排序,再依序填入盤面上所有有圖案的格子內,就可以達到重整盤面但是不影響到空格的位置。

今日成果

連連看遊戲邏輯至此已大致完成囉!下一篇開始我們會實際開始製作一款實際上具有畫面、音效、特效等真正的網頁連連看遊戲

LIVE DEMO: 今日成果展示
完整程式碼可由此下載:ironman20181022

發佈日期: 發佈留言

[6 – 遊戲邏輯] 連線消除程式撰寫

主要遊戲流程

連連看點選兩個圖案後,可消除的邏輯是:

  • 兩個所點擊到的圖案相同
  • 連線不超過兩個轉彎

因此我們先來寫遊戲主流程的部份,玩家會先點第一個圖案,代表他想要消除這個圖案,接著再消第二個圖案,這時再來判斷是否符合可消除,這部份的流程圖如下:

撰寫的程式碼如下

var app = angular.module('LianLianKan', []);
app.controller('myCtrl', function ($scope) {
    $scope.select1 = new Point(-1, -1);
    $scope.select2 = new Point(-1, -1);
    $scope.selected = false;
    let msgArra = [];
    $scope.message = msgArra;
    let board = new Board();
    $scope.boardContent = board.board;
    $scope.click = function (x: number, y: number) {
        if ($scope.selected) {
            $scope.select2 = new Point(x, y);
            if (board.hasSameValue($scope.select1, $scope.select2)) {


                if (! ($scope.select1.x == x && $scope.select1.y == y) ) {//確認所選的兩個點不一樣

                    let path = new Path($scope.select1, $scope.select2, board);
                    if(path.canLinkInLine()){
                        board.clearPoint($scope.select1);
                        board.clearPoint($scope.select2);
                        msgArra.push(path);
                    }
                }
            }
            $scope.selected = false;
        } else {
            $scope.select1 = new Point(x, y);
            $scope.selected = true;
        }
    };
});

判斷所選圖案是否相同

在上面的程式碼中,可以看到我們用board.hasSameValue($scope.select1, $scope.select2)來判斷所選的圖是是否相同。我們可以Board的類別增加public hasSameValue(point1: Point, point2: Point): boolean如下:

    public hasSameValue(point1: Point, point2: Point): boolean {
        return this.board[point1.x][point1.y] == this.board[point2.x][point2.y];
    }

連線邏輯撰寫

新建一個類別Path內容如下
class Path {
public point1: Point;
public point2: Point;
readonly board: Board;
public path_Detail:Array;

constructor(point1: Point, point2: Point, board: Board) {
this.point1 = point1;
this.point2 = point2;
this.board = board;
}

public canLinkInLine(): boolean {

console.log(“board”,this.board);

//從上面消
//兩個點都往上找最遠能到達的距離
let point1UP = this.board.getNearByPointByDirection(this.point1, Direction.UP);
let point2UP = this.board.getNearByPointByDirection(this.point2, Direction.UP);
console.log(“point1UP”,point1UP,”point2UP”,point2UP);
//尋找這之中可能存在的路徑
{
let min = Math.max(point1UP.x,point2UP.x);
let max = Math.min(this.point1.x, this.point2.x);
for (var i = max;i>=min;i–){
if (!this.board.hasMiddleValue(new Point(i, this.point1.y), new Point(i, this.point2.y))){
this.path_Detail = [this.point1,new Point(i, this.point1.y),new Point(i, this.point2.y),this.point2];
console.log(“same up”);
return true;
}
}
}
//從下面消
let point1DOWN = this.board.getNearByPointByDirection(this.point1, Direction.DOWN);
let point2DOWN = this.board.getNearByPointByDirection(this.point2, Direction.DOWN);
console.log(“point1DOWN”,point1DOWN,”point2DOWN”,point2DOWN);
{
let max = Math.min(point1DOWN.x,point2DOWN.x);
let min = Math.max(this.point1.x, this.point2.x);
for (var i = min;i<=max;i++){ if (!this.board.hasMiddleValue(new Point(i, this.point1.y), new Point(i, this.point2.y))){ this.path_Detail = [this.point1,new Point(i, this.point1.y),new Point(i, this.point2.y),this.point2]; console.log("same down"); return true; } } } //從左邊消 let point1LEFT = this.board.getNearByPointByDirection(this.point1, Direction.LEFT); let point2LEFT = this.board.getNearByPointByDirection(this.point2, Direction.LEFT); console.log("point1LEFT",point1LEFT,"point2LEFT",point2LEFT); { let min = Math.max(point1LEFT.y,point2LEFT.y); let max = Math.min(this.point1.y, this.point2.y); for (var i = max;i>=min;i–) {
if (!this.board.hasMiddleValue(new Point(this.point1.x, i), new Point(this.point2.x, i))) {
this.path_Detail = [this.point1, new Point(this.point1.x, i), new Point(this.point2.x, i), this.point2];
console.log(“same left”);
return true;
}
}
}

//從右邊消
let point1RIGHT = this.board.getNearByPointByDirection(this.point1, Direction.RIGHT);
let point2RIGHT = this.board.getNearByPointByDirection(this.point2, Direction.RIGHT);
console.log(“point1RIGHT”,point1RIGHT,”point2RIGHT”,point2RIGHT);
{
let max = Math.min(point1RIGHT.y,point2RIGHT.y);
let min = Math.max(this.point1.y, this.point2.y);
for (var i = min;i<=max;i++) { if (!this.board.hasMiddleValue(new Point(this.point1.x, i), new Point(this.point2.x, i))) { this.path_Detail = [this.point1, new Point(this.point1.x, i), new Point(this.point2.x, i), this.point2]; console.log("same right"); return true; } } } //左右連消 if (this.point1.y != this.point2.y){ //先判斷那個點在左,那個點在右 let leftPoint = (this.point1.y < this.point2.y) ? this.point1:this.point2; let rightPoint = (this.point1.y >= this.point2.y) ? this.point1:this.point2;
//取得右邊的點,直線往左最左的那個點
let leftPointRIGHT = this.board.getNearByPointByDirection(leftPoint, Direction.RIGHT);
let rightPointLEFT = this.board.getNearByPointByDirection(rightPoint, Direction.LEFT);
//參考前一篇文章的圖,右邊最左的點不可超過左邊的點,否則會造成誤判
leftPointRIGHT.y = (leftPointRIGHT.y < rightPoint.y) ? leftPointRIGHT.y : rightPoint.y; rightPointLEFT.y = (rightPointLEFT.y > leftPoint.y) ? rightPointLEFT.y : leftPoint.y;
//用迴圈判斷在所有有可能的範圍中是否有可能存在的路徑
if (leftPointRIGHT.y != leftPoint.y && rightPointLEFT.y != rightPoint.y){
for (var i = rightPointLEFT.y; i <= leftPointRIGHT.y; i++) { if (!this.board.hasMiddleValue(new Point(leftPoint.x, i), new Point(rightPoint.x, i))) { this.path_Detail = [leftPoint, new Point(leftPoint.x, i), new Point(rightPoint.x, i), rightPoint]; console.log("same left to right"); return true; } } } } //上下連消 if (this.point1.x != this.point2.x){ let upPoint = (this.point1.x < this.point2.x) ? this.point1:this.point2; let downPoint = (this.point1.x >= this.point2.x) ? this.point1:this.point2;
let upPointDOWN = this.board.getNearByPointByDirection(upPoint, Direction.DOWN);
let downPointUP = this.board.getNearByPointByDirection(downPoint, Direction.UP);
upPointDOWN.x = (upPointDOWN.x < downPoint.x) ? upPointDOWN.x : downPoint.x; downPointUP.x = (downPointUP.x > upPoint.x) ? downPointUP.x : upPoint.x;
if (upPointDOWN.x != upPoint.x && downPointUP.x != downPoint.x){
for (var i = downPointUP.x; i <= upPointDOWN.x; i++) { if (!this.board.hasMiddleValue(new Point(i, upPoint.y), new Point(i, downPoint.y))) { this.path_Detail = [upPoint, new Point(i, upPoint.y), new Point(i, downPoint.y), downPoint]; console.log("same top to down"); return true; } } } } return false; } }[/code] 新增類別Board

class Board {
public board: Array>;

constructor() {
let content = [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];
//產生初始局面
let length = 10;
let data = content.concat(content).concat(content).concat(content).sort((a, b) => (Math.random() > .5) ? 1 : 0);
this.board = []
for (var i = 0;i= 0; i–) {
if (this.board[i][point.y] == null) {
nearByPoint.x = i;
} else {
break;
}
}
if (nearByPoint.x == 0) {
nearByPoint.x = -1;
}
break;
case Direction.DOWN:
//搜尋往下走最遠可到達的點
let maxLengthDOWN = this.board.length;
for (var i = point.x+1; i < maxLengthDOWN; i++) { if (this.board[i][point.y] == null) { nearByPoint.x = i; } else { break; } } if (nearByPoint.x == maxLengthDOWN - 1) { nearByPoint.x = maxLengthDOWN; } break; case Direction.RIGHT: //搜尋往右走最遠可到達的點 let maxLengthRIGHT = this.board[0].length; for (var i = point.y+1; i < maxLengthRIGHT; i++) { if (this.board[point.x][i] == null) { nearByPoint.y = i; } else { break; } } if (nearByPoint.y == maxLengthRIGHT - 1) { nearByPoint.y = maxLengthRIGHT; } break; case Direction.LEFT: //搜尋往左走最遠可到達的點 for (var i = point.y-1; i >= 0; i–) {
if (this.board[point.x][i] == null) {
nearByPoint.y = i;
} else {
break;
}
}
if (nearByPoint.y == 0) {
nearByPoint.y = -1;
}
break;
}
return nearByPoint;
}

//搜尋在兩個點之中是否可以找到一直線可連接
public canFindPath(a: Point, b: Point, direction:string): boolean {
return this.hasMiddleValue(a ,b);
}

//偵測在兩個點中是否可用一條直線做連接
public hasMiddleValue(a: Point, b: Point): boolean {
let arr = [];
if (a.x == b.x) {
if (a.x == -1 || a.x == this.board.length) return false;
let max = Math.max(a.y, b.y);
let min = Math.min(a.y, b.y);
for (var i = min + 1; i < max; i++) { if (this.board[a.x][i] != null) { return true; } } return false; } else if (a.y == b.y) { if (a.y == -1 || a.y == this.board[0].length) return false; let max = Math.max(a.x, b.x); let min = Math.min(a.x, b.x); for (var i = min + 1; i < max; i++) { if (this.board[i][a.y] != null) { return true; } } return false; } else { return true; } } //判斷某兩個點的值是否相同 public hasSameValue(point1: Point, point2: Point): boolean { return this.board[point1.x][point1.y] == this.board[point2.x][point2.y]; } //將盤面上的圖消掉 public clearPoint(point: Point) { this.board[point.x][point.y] = null; point = null; } } [/code] 今日成果:
Live Demo:今日成果展示
今天的專案可至此下載:ironman20181021

發佈日期: 發佈留言

[5 – 遊戲邏輯] 圖形連線消除邏輯發想

搜尋邏輯思考

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

這時候我們來思考該如何找出這兩點間所存在的那條線。先觀察一下棋盤,最多三條直線,代表有可能是一條直線、兩條直線或三條直線來做連接的。
不論如何,兩個點之間的那條線,一定一邊是從第一個點(A)開始,到另一個點(B)結束,因此,可以視為這兩個點之中,有可能存在A點連出的的(C)點B點連出的(D)點,來形成連線。

由上圖我們可以觀察出,A點連出的的(C)點絕對是和開始的(A)點在同一行或同一列,B點連出的(D)點絕對是和結束的點(B)點在同一行或同一列

尋找可能的線的模型

首先,我們來畫出所有有可能連出來的線圖形狀,再來思考該如何去撰寫消除邏輯。

判斷是否存在此圖形的連線

從上面的圖型我們先來分析向左、上、下、右的邊消的情況,要如何去搜尋可能存在的路徑。
讓我們先看這張圖

圖中的(A)為起始點,(B)為終點,(C)為(A)點最左能走到的點,(D)為(B)點最左能走到的點。則淡紅色漸層的部份,就是存在著可能的路徑。
這個可能連線的區塊的座標應為: 左上(A.x,D.y)、右上(A.x, B.y)、右下(D.x,D.y)、左下(B.x,B.y)。
我們應該要取A_C與B_D的橫向座標(y)中,有交集的部份。

因此這部份的邏輯程式應為

        let potinC = getPathLeftPoint(pointA);
        let pointD = getPathLeftPoint(pointB);
        let min = Math.max(pointC.y,pointD.y);
        let max = Math.min(pointA.y, pointB.y);
        for (var i = max;i>=min;i--) {
            if (!hasMiddleValue(new Point(pointA.x, i), new Point(pointB.x, i))) {
                path = [pointA, new Point(pointA.x, i), new Point(pointB.x, i), pointB];
                return "可消除";
            }
        }

同樣的模型可以套用在向左、向上、向右、向下。
我們可以發現,左右直連可視為A點與C點相疊、B點與D點相疊的向上/向下消除,上下直連亦同。轉折連接可視為A與C或者B與D其中有兩個相疊,另兩個不相疊。都可以用相同的演算法來找出路徑

無法用相同的方式找出來的圖形有這兩個

先來繪製出有可能可以連線的區域

由上圖可知,我們需要找A、B點之間在左邊的(A)點往右可走最多的那個(C)點,然後找A、B點之間在右邊的(B)點往左走最多的(D)點。
然後取出A_C與B_D中y有交集的地方,為有可能可以連線的區域

這部份的邏輯程式碼為
if (pointA.y != pointB.y){
let leftPoint = (pointA.y < pointB.y) ? pointA:pointB; let rightPoint = (pointA.y >= pointB.y) ? pointA:pointB;
let leftPointRIGHT = getPathRightPoint(leftPoint);
let rightPointLEFT = getPathLeftPoint(rightPoint);
leftPointRIGHT.y = (leftPointRIGHT.y < rightPoint.y) ? leftPointRIGHT.y : rightPoint.y; rightPointLEFT.y = (rightPointLEFT.y > leftPoint.y) ? rightPointLEFT.y : leftPoint.y;
if (leftPointRIGHT.y != leftPoint.y && rightPointLEFT.y != rightPoint.y){
for (var i = rightPointLEFT.y; i <= leftPointRIGHT.y; i++) { if (!this.board.hasMiddleValue(new Point(leftPoint.x, i), new Point(rightPoint.x, i))) { this.path_Detail = [leftPoint, new Point(leftPoint.x, i), new Point(rightPoint.x, i), rightPoint]; console.log("same left to right"); return true; } } } } [/code]

發佈日期: 發佈留言

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

棋盤設計

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

隨機產生盤面

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

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

var boardContent = [1,2,3,4,5,6,7,8,9];
//產生初始局面
boardContent = boardContent.concat(boardContent).concat(boardContent).concat(boardContent).sort(() => Math.random() > .5);
boardContent = [boardContent.slice(0,6),
                boardContent.slice(6,12),
                boardContent.slice(12,18),
                boardContent.slice(18,24),
                boardContent.slice(24,30),
                boardContent.slice(30,36)];

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

呈現陣列內容

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

<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  <meta name="viewport" content="width=device-width">
  <title>JS Bin</title>
  <style>.red{background:red;}</style>
<script src="https://code.jquery.com/jquery-3.1.0.js"></script>
<script src="https://ajax.googleapis.com/ajax/libs/angularjs/1.3.15/angular.min.js"></script>
</head>
<body ng-app="myApp" ng-controller="myCtrl">
 select1=<input type="text" ng-model="select1" disabled>
 select2=<input type="text" ng-model="select2" disabled>
<table border="1" width="200">
  <tr ng-repeat="lines in boardContent track by $index">
    <td ng-repeat="x in lines track by $index"
        ng-class="{'red':(select1&#91;0&#93;==$parent.$index&&select1&#91;1&#93;==$index && selected)}"
        ng-click="click($parent.$index,$index)">{{x}}</td>
  </tr>
</table>
</body>
</html>

js檔案的內容如下:

var boardContent = [1,2,3,4,5,6,7,8,9];
//產生初始局面
boardContent = boardContent.concat(boardContent).concat(boardContent).concat(boardContent).sort(() => Math.random() > .5);
boardContent = [boardContent.slice(0,6),
                boardContent.slice(6,12),
                boardContent.slice(12,18),
                boardContent.slice(18,24),
                boardContent.slice(24,30),
                boardContent.slice(30,36)];

//產生盤面
var app = angular.module('myApp', []);
app.controller('myCtrl', function($scope) {
    $scope.select1 = [-1,-1];
    $scope.select2 = [-1,-1];
    $scope.selected = false;

    $scope.boardContent= boardContent;
    $scope.click = function(x,y) {
       if($scope.selected){
         console.log(boardContent[$scope.select1[0]][$scope.select1[1]])
         console.log(boardContent[x][y])
         if(boardContent[$scope.select1[0]][$scope.select1[1]]
           == boardContent[x][y]){
           $scope.select2 = [x,y];
         }
         $scope.selected = false;
       }else{
        $scope.select1 = [x,y];
        $scope.selected = true;
       }
    };
});

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

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

改使用Typescript開發

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

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

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

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

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

發佈日期: 發佈留言

[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 -v

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

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

下面為一個簡單的package.json的範例
{
“name”: “lianliankan”//專案名稱,
“version”: “0.0.1”,//版本號
“scripts”: {//撰寫一些要跑專案要用的指令在這邊,例如這個範例可以用npm lunch去跑gulp launch-web這個指令
“launch”: “gulp launch-web”
},
“license”: “ISC”,
“dependencies”: {//套件管理,這個專案需要用到那些套件在這邊設定
“browser-sync”: “^2.24.7”,
“gulp”: “^3.9.1”,
“gulp-typescript”: “^5.0.0-alpha.3”
}
}

TypeScript

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

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

安裝TypeScript的命令行工具安裝方法如下:
npm install -g typescript
編譯ts文件的方法如下
tsc hello.ts
但是當我們在開發一個較大型的專案時,一般我們不可能一個一個檔案用上面的指令去complier,這時候我們會設定一個typescript的config檔案:tsconfig.json
這邊是關於這個config的設定教學:tsconfig.json

下面是一個tsconfig.json的簡單範例,compilerOptions用來設定如何來編譯ts文件
{
“files”: [
“src/*.ts”//要complier那些ts檔案
],
“compilerOptions”: {
“target”: “es5”,//要complier成的js版本
“module”: “system”,//module用於指定模塊的代碼生成規則,可以使用commonjs,amd,umd,system,es6,es2015,none這些選項。
//選擇commonJS,會生成符合commonjs規範的文件,使用amd,會生成滿足amd規範的文件,
//使用system会生成使用ES6的system.import的代码。使用es6或者是es2015會產生包含ES6特性的代碼。
“moduleResolution”: “node”,
“sourceMap”: false,//sourceMap是當我們使用chrome dev tools時,當有錯誤是否我們能夠直接在js連回ts檔案格式去偵錯
//通常只會在dev環境開啟(為方便偵錯),不然會讓產出的檔案變大
“removeComments”: true,//設置為true代表不輸出注解
“noImplicitAny”: false,//是否在型別設定為any時發出警告
“rootDir”: “src/”,//根目錄
“lib”: [ “es6”, “dom” ],
“allowSyntheticDefaultImports”: true
}
}
這個手冊有更詳細的解說每一個設定的意義:TypeScript配置文件tsconfig简析

Gulp

安裝完node.js後,就是使用 windows 的 cmd 或 Mac 的 Termial 來安裝 Gulp,首先我們先輸入以下的指令,把 Gulp 安裝好,並且設定是只有在開發時期會使用到。
首先要先將gulp安裝到全域領域,這樣我們才能使用cmd等去呼叫gulp執行工作(若mac環境前面要加sudo)
npm install -g gulp
然後在剛剛設定好的專案裡,設定我們的專案要使用到gulp模組。至於為什麼要有-save-dev呢?當我們寫-save-dev,會將這個模組添加到package.json的devDependencies裏頭,如果寫-save,就會添加到dependencies裡,這兩個的差異在於讓使用具備這個package.json專案的人,可以清楚的知道這個模組,是開發使用,還是執行專案時使用的。
npm install gulp –save-dev
因為我們是使用typescript,因此也要安裝gulp-typescript
npm install gulp-typescript –save-dev

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

  • 編譯ts檔案
  • copy相關資源/li>
  • bundle
  • 使用browserSync來開啟並同步更新網頁
var gulp = require("gulp");
var browserify = require("browserify");
var source = require('vinyl-source-stream');
var tsify = require("tsify");
var browserSync = require('browser-sync');

gulp.task("copy-html", function () {
    return gulp.src(['src/*.html','src/libs/*'])
        .pipe(gulp.dest('build'));
});

gulp.task("build", ["copy-html"], function () {
    browserify({
        basedir: '.',
        debug: true,
        entries: ['src/main.ts'],
        cache: {},
        packageCache: {}
    })
    .plugin(tsify)
    .bundle()
    .pipe(source('bundle.js'))
    .pipe(gulp.dest("build"));
});

gulp.task('default',['server'], function() {
    gulp.watch(["src/**/*"], ['build']);
});

gulp.task('server', ['build'], function () {
    browserSync({
        open: true,
        port: 8001,
        files: ["build/**/*.{html,htm,css,js,json}"],
        server: {
            "baseDir": "./build"
        }
    });
});

GitHub

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

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

參考資料

發佈日期: 發佈留言

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

何為演算法

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

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

時間複雜度

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

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

function(int n){
    print(n);
}

而下面這個演算法:
function(int n){
for(i=0;i O(n)。

有時若跑的次數較不固定,如:
function(int n){
for(i=0;i O(n2) ,也就是說,只要找出最高次方,並且把係數拿掉即可。

空間複雜度

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

例如下面這個函式,不管程式跑了幾遍,都不會影響使用的變數數量:
function(int n){
for(int i=0;iO(1)。

但下面這個函式,會隨著丟進去的數字而影響變數的量,例如:
function(int n){
int c[n];
for(int i=0;iO(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點上、下、左、右最遠可以到達的點,判斷是否有可能可以形成一條連線,若有可能,再去尋找是否中間存在可能的第二條線。

參考資料

發佈日期: 發佈留言

[1 – 前言] 連連看遊戲開發

連連看遊戲起源

遊戲《連連看》顧名思義就是找出相關聯的東西連起來,做關連配對的一種益智遊戲

最早是使用在幼兒教育的教具上,由於玩法簡單,常用作兒童啟蒙教育遊戲,建立兒童對物品之間的關連性連結。有一種字圖連連看,是專供幼童識字認圖的遊戲,與一般連連看不同的是它並非以一對相同圖案成對,而是以字配圖成對。相關內容連連看則是以兩張內容相關的卡片(可以是字或圖)配成對代替相同圖案。

後來出現了桌面遊戲的連連看,最早期的形式是一副卡片中每種圖案有相同的兩張,先洗牌,然後排好卡片,背面朝上,玩家輪流揭開卡片,每次揭兩張,如兩張圖案不同則回復背面朝上的狀態,如揭到兩張圖案相同則取走卡片,到桌上所有卡片都被取走時即結束遊戲,手上最多卡片者為勝利者。

隨著電腦的普及,連連看遊戲也成為一款經典的電腦小遊戲。在電腦遊戲中的一種規則則是在找到兩幅相同圖案後,若能用三條以內的直線將兩幅圖案連接起來,分別點一下兩幅圖案,即可消除。連連看遊戲後來經歷了桌面遊戲、在線遊戲、社交遊戲三個過程。

連連看電腦版最初是由台灣的陳一進和簡誠志從街機里的四川省(四川麻將)中國龍改進、移植到PC上的,現在有了各種不同的版本。

台灣的連連看流入大陸以後風靡一時,也吸引眾多程式師開發出多種版本的連連看,其中kawai所開發的《寵物連連看》受到很大的歡迎。隨著Flash應用的流行,網上出現了多種線上Flash版本連連看。如:水晶連連看、果蔬連連看、阿達連連看等,連連看以簡單不無聊的遊戲特色吸引了一大批的女性玩家。2008年,隨著網際網路的普及和開放平台的興起,《連連看》被引入了社交網站,與個人空間相結合,被快速的傳播,成為一款熱門的社交遊戲。

益智遊戲發展介紹

益智遊戲可以是一人玩家,也可以是多人對戰。

連連看是一種益智型遊戲,屬消除型益智遊戲。益智遊戲要求玩家用自己的智慧來解決遊戲中的難題,達到過關的目的。新的商業遊戲通常會加上動作要素,要讓玩家手腦並用,訓練協調性,經典的代表作有俄羅斯方塊、泡泡龍系列、憤怒鳥、Candy Crush以及幾年前很紅的2048。傳統的益智遊戲以動腦為主,如數獨、推箱子等。這類遊戲對玩家而言較難過關,導致大量玩家中途放棄。

後來俄羅斯方塊出現,為落下型遊戲始祖,此遊戲最初是由阿列克謝·帕基特諾夫在蘇聯設計和編寫。此遊戲除了成為一個熱門的家用電腦和街機遊戲外,還成為Game Boy史上最受歡迎的遊戲。《電子遊戲月刊》在2007年將此遊戲列為「最偉大的100個遊戲」中的第1位。直到今日,俄羅斯方塊是有史以來最暢銷的電子遊戲。

最新的許多益智遊戲結合了消除型與落下型遊戲的特色,利用落下隨機元素增加了遊戲的隨機性,並增加遊戲特殊道具,讓遊戲更加有趣。如Candy Crush便為一例,Candy Crush與連連看相同皆為消除遊戲,三個相同顏色的方塊可以互相消除,並會隨機落下新的不同顏色的方塊,特殊的消除模式可以產生特殊道具。這樣的遊戲方式有挑戰性,而且適合打發時間,因此成為Facebook平台上最受歡迎遊戲,擁有4億5千6百萬每月玩家。

後來的神魔之塔Dragon Puzzle更結合了角色扮演與卡牌遊戲及線上對戰的特色,使得益智型遊戲的樣貌更加的多元化。植物大戰殭屍則添加了即時戰略遊戲及卡牌遊戲的特色,讓益智型遊戲的面向變得更多元化,此作品獲得了相當正面的評價,在GameRankings的評分達到89.5%,Metacritic的評分則是88。

下圖為不同遊戲中所包含的遊戲性元素:

由上圖可知益智型遊戲在現今的手機市場上,因手機版面限制與操作便利性的關係,益智遊戲比起傳統RPG遊戲或動作遊戲在手機市場上占上更多的優勢。也因著益智遊戲的市場越來越大,後期的益智遊戲所包含的遊戲元素的面向越來越廣,不論是卡牌元素、即時戰略遊戲元素、操作手感元素等,都可以讓遊戲的趣味性更加提升,線上多人遊戲的模式更能增加玩家的黏著度。

設計一款有趣的益智遊戲,其中的演算法設計十分重要,例如物理遊戲的物理公式設計、相消遊戲的消除條件、每個關卡的過關條件、道具設計、遊戲競爭性,上述的每一個項目若能夠越符合大自然的法則,會讓玩家玩起來更加的直覺,也是遊戲好玩的必要關鍵。當然開發一款大型的遊戲,美術、音效、程式、企劃缺一不可,對於程式開發者而言,學習適合的語言工具也十分重要。這些與遊戲設計相關的元素,在這次的鐵人賽裡面,我都會在不同的章節裡提到。

連連看開發模式規劃

這一次的鐵人賽主題裡,我主要會分為兩個教學線。

主線為連連看遊戲邏輯的分析與程式碼撰寫,目標為撰寫出正確的邏輯,需能正確判別兩個圖形間是否存在小於兩個轉彎處的連線存在,並且能夠隨機產生隨機的遊戲牌面,以陣列來儲存遊戲現在的資料。

副線則為使用Pixi.js來實際開發一款具有畫面、效果及音效,真正具有遊戲性的網頁H5遊戲

在這邊所使用的PixiJS是一款2D的HTML5遊戲引擎,可以利用WebGL的功能來做2D的圖像處理,因此在網頁上能夠有著很不錯的效能表現。PixiJS是採用Javascript來開發的,但我在這邊為了開發容易度及順暢度以及不同版本JS的兼容性考量,我採用了TypeScript版本的PixiJS來做開發,並用npm來做套件管理、利用gulp來做自動化管理工具。

在美術素材來源上,我是至Unity Asset Store尋找並下載免費素材來使用。在遊戲畫面設計及圖片動畫處理上,則是利用Adobe Animate CC來繪圖並產生連續圖檔(同Texture Packer的功能),動態效果則使用了GSAP的Tween工具來實現。

在音效的部份,我滿推薦小森平的免費音效,裡面的音效都有分門別類的整理好,並且可以線上試聽後直接下載,可以很容易的找到適合的音效。程式上的音效處理我則使用howler來做音效載入與播放管理的工具。背景音樂的部份,我則是至Youtube音樂音效庫尋找並下載適合的背景音樂。

在IDE的部份,我是使用VS Code來做開發,配合PixiJS devtoolschrome dev tools來做除錯、測試和畫面檢查。

教學項目

下圖為這30天內,我預計會提到的必要項目,也就是連連看邏輯的教學項目:

下圖為製作真正有音效有畫面的H5遊戲的教學項目:

鐵人賽30天內容規劃

以下為預先規劃的30天的內容,有可能會隨實際情況做更動:

[1 - 前言] 連連看遊戲開發
[2 - 演算法] 演算法介紹
[3 - 環境設定] 開發環境介紹
[4 - 遊戲邏輯] 產生初始盤面
[5 - 遊戲邏輯] 圖形連線消除邏輯發想
[6 - 遊戲邏輯] 連線消除程式撰寫
[7 - 遊戲邏輯] 電腦搜尋路徑
[8 – 遊戲介紹] 遊戲歷史簡介
[9 - 遊戲介紹] 遊戲開發技術介紹
[10- 遊戲製作] PixiJS介紹
[11- 遊戲製作] 使用模組介紹
[12- 遊戲製作] 介面設計
[13- 遊戲製作] 素材處理
[14- Pixi教學] PIXI場景設定
[15- Pixi教學] 載入素材
[16- Pixi教學] 與網頁互動-控制loading page
[17- Pixi教學] 音樂音效設定
[18- Pixi教學] 按鈕製作
[19- Pixi教學] 連連看盤面實作
[20- Pixi教學] 連連看公仔實作
[21- Pixi教學] 連線效果實作-Graphics
[22- Pixi教學] 按鈕動態- Tween
[23- Pixi教學] 復原按鈕功能實作
[24- Pixi教學] 提示按鈕功能實作
[25- Pixi教學] 遊戲開始、結束與過關設定
[26- Pixi教學] 遊戲功能完成
[27- Pixi教學] 連線消除效果- Particles
[28- 相關工具] PixiJS devtools
[29- 相關工具] 效能評估工具
[30- 相關工具] 手機遠程測試

參考資料

發佈日期: 發佈留言

單元測試 – 重構測試

重構test的重要性

好的測試應該要容易維護,容易閱讀,
不應包含程式邏輯在內,因此像是if, while, for迴圈等都不應該出現在測試裡
如果我們驗證的內容會和資料有關,則建議使用Substitute,這樣可以讓我們能夠在每一個測試裡增加不同的資料
而且可以直接在每個測試裡看到資料的內容是什麼
下面是一個範例
private void AmountShouldBe(int expected, DateTime start, DateTime end)
{
IList data = new List()
{
new Budget() {Amount = 310, YearMonth = “201801”},
new Budget() {Amount = 620, YearMonth = “201803”},
new Budget() {Amount = 900, YearMonth = “201804”}
};

var budgetCalculator = new BudgetCalculator(new TestDataBudgetRepository(data));
var budget = budgetCalculator.TotalAmount(start, end);
Assert.AreEqual(expected, budget);
}
91的課程中建議每一次寫成功一個測試案例,就可以先做重構,這樣之後的的開發速度可以更加速

重構測試的步驟

  • 抽出field: mock object(繼承假物件去創建假物件), stub(用Substitute)
  • Setup: SUT初始化(或者[TestInitialize])
  • 抽出方法(用Given為開頭):定義mock object行為,代表假如在跑這個scenario時…
  • Extra Method with “Shouldxxx()” => SUT行為+Assertion

也就是盡可能讓我們的重構能夠符合3A原則,
3A pattern: Arrange, Act, Assert
上面重構後Arrange就用Given…,然後Act就是SUT行為,Assert就是Assertion。

重構的測試的範例

下面為重構後的程式碼:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using NSubstitute;
using NUnit.Framework;
using RsaSecureToken;
using Assert = NUnit.Framework.Assert;

namespace RsaSecureToken.Tests
{
[TestFixture]
public class AuthenticationServiceTests
{
private IProfile _fakeProfile;
private IRsaToken _fakeToken;
private ILogger _logger;
private AuthenticationService _authenticationService;

[SetUp]
public void Given()
{
_fakeProfile = Substitute.For();

_fakeToken = Substitute.For();

_logger = Substitute.For();

_authenticationService = new AuthenticationService(_fakeProfile, _fakeToken, _logger);
}

private void GivenToken(string token)
{
_fakeToken.GetRandom(“”).ReturnsForAnyArgs(token);
}

private void GivenPassword(string account, string password)
{
_fakeProfile.GetPassword(account).Returns(password);
}

private void ShouldBeValid(string account, string password)
{
var actual = _authenticationService.IsValid(account, password, _logger);
Assert.IsTrue(actual);
}

[Test()]
public void IsValidTest()
{
GivenPassword(account: “joey”, password: “91”);
GivenToken(token: “000000”);

ShouldBeValid(account: “joey”, password: “91000000”);
}

[Test()]
public void IsInValidTest()
{
GivenPassword(account: “joey”, password: “91”);
GivenToken(token: “000000”);

ShouldBeInValid(account: “joey”, errorPassword: “error password”);
}

private void ShouldBeInValid(string account, string errorPassword)
{
var actual = _authenticationService.IsValid(account, errorPassword, _logger);
Assert.IsFalse(actual);
}

[Test()]
public void ShouldLog()
{
GivenPassword(account: “joey”, password: “91”);
GivenToken(token: “000000”);

ShouldBeInValid(account: “joey”, errorPassword: “error password”);

//這個可能會有過度指定的問題,或許加一個痘號就會導致測試失敗
//_logger.Received(1).Save(Arg.Is(“account: joey try to login failed”));
_logger.Received(1).Save(Arg.Is(m => m.Contains(“joey”) && m.Contains(“login failed”)));
}
}
}

發佈日期: 發佈留言

單元測試 – 隔離框架Substitute.For

STUB的功能

這邊是NSubstitute的說明:http://nsubstitute.github.io/help/getting-started/
Substitute是.NET裡的一個隔離框架,若要使用,需要額外在測試專案用NUGET去安裝NSubstitute

1. 動態產生假物件
2. 模擬回傳值
3. 測試監聽事件
4. 驗證傳入參數是否正確

使用Subsitute(Sub)
使用方法如下
calculator = Substitute.For();
設定呼叫某個方法應該回傳的值
calculator.Add(1, 2).Returns(3);
Assert.That(calculator.Add(1, 2), Is.EqualTo(3));
下面可以驗證是否Add這個FUNC有被呼叫到
calculator.Add(1, 2);
calculator.Received().Add(1, 2);
calculator.DidNotReceive().Add(5, 7);
下面的程式能夠判別傳入的參數是不是正確
calculator.Add(10, -5);
calculator.Received().Add(10, Arg.Any());
calculator.Received().Add(10, Arg.Is(x => x < 0));[/code] 驗證回傳值是否正確 [code lang="C#"]calculator .Add(Arg.Any(), Arg.Any())
.Returns(x => (int)x[0] + (int)x[1]);
Assert.That(calculator.Add(5, 10), Is.EqualTo(15));

使用Substitute來針對不同狀況實作假介面

這是一個用MOCK方法的範例

using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
//using Microsoft.VisualStudio.TestTools.UnitTesting;
using NUnit.Framework;
using RsaSecureToken;
using Assert = NUnit.Framework.Assert;

namespace RsaSecureToken.Tests
{
    [TestFixture]
    public class AuthenticationServiceTests
    {
        [Test()]
        public void IsValidTest()
        {
            var target = new AuthenticationService(new FakeProfile(), new FakeToken());

            var actual = target.IsValid("joey", "91000000");

            //always failed
            Assert.IsTrue(actual);
        }
    }

    public class FakeProfile:IProfile
    {

        public string GetPassword(string account)
        {
            if (account == "joey")
            {
                return "91";
            }

            throw new Exception();
        }
    }

    public class FakeToken:IRsaToken
    {
        public string GetRandom(string account)
        {
            return "000000";
        }
    }
}

上面做法有什麼問題?

  • 每一個不同的依賴案例就要製作一個不同的FakeObject,會讓寫測試的時間太久
  • 沒辦法直接從程式碼知道為什麼這樣會是Vaild

動態產生物件的使用完整範例

Subsitute.For()
定義假物件行為(stub)
fake.方法(參數).Returns(值)
[Test()]
public void IsValidTest()
{
var fakeProfile = Substitute.For();
fakeProfile.GetPassword(“joey”).Returns(“91”);

var fakeToken = Substitute.For();
fakeToken.GetRandom(“”).ReturnsForAnyArgs(“000000”);

var target = new AuthenticationService(fakeProfile, fakeToken);
var actual = target.IsValid(“joey”, “91000000”);

//always failed
Assert.IsTrue(actual);
}
}

驗證某個函數是否被呼叫

使用mock object assertion
需求:驗證是非法的時候要記一個log
fake.Receive(次數).方法(參數驗證)
不要用太多mock就算要使用要避免過度指定,也就是當prod code小小變動就導致測試程式壞掉

下面的程式碼可以驗證當呼叫SyncBookOrders()時是不是會呼叫Insert這個函數兩次:
[Test]
public void Test_SyncBookOrders_3_Orders_Only_2_book_order()
{
var result = new List
{
new Order
{
Type = “Book”
},
new Order
{
Type = “Book”
},
new Order
{
Type = “Item”
}
};

var target = new OrderServiceForTest();
target.SetOrder(result);

var fakeBookDao = Substitute.For();
target.SetDao(fakeBookDao);

target.SyncBookOrders();

fakeBookDao.Received(2).Insert(Arg.Is(m => m.Type == “Book”));
}

驗證傳入參數

驗證傳入的參數是否包含某些關鍵字
_logger.Received(1).Save(Arg.Is(m => m.Contains(“joey”) && m.Contains(“login failed”)));