2014年7月14日

UI Test Script for Android - 以Puzzle And Dragons自動轉珠為範例 (下)

By 標籤 , , ,

PAD自動轉珠

在最後一篇文章當然就要來講最重要的, 怎麼做到自動轉珠
(主題明明就是UI Test Script, 什麼時候副標題變成重點了)
想要達到自動轉珠, 我們可以把事情分成兩個部分:
1. 如何分析遊戲盤面上的珠子
2. 如何透過盤面的狀況來自動轉珠

分析遊戲盤面

enter image description here
當你進到遊戲看到上面的盤面時, 首先當然是要根據他是哪個種類的珠子做分類, 做完分類我們才有辦法針對它們來產生自動轉珠的路徑。
那麼, 該怎麼做呢? 什麼方法會比較有效率呢?
方法一: 一開始不用想太多, 就用最簡單的方法吧, 反正我們有FindImage的API,那就對每一個珠子去做template matching, 那就可以把盤面資訊全部解析出來了吧。不過, 這個想法當然沒什麼問題, 不過這樣做似乎不是一個很有效率的方法, 所以再想看看別的方法吧。既然每個珠子的顏色都差很多, 那麼用顏色來判斷應該是個好方法吧? 不過一個珠子範圍那麼大, 你要怎麼算整個區域的顏色來做比對咧? 算平均值應該就可以求出珠子的顏色範圍吧! 基於這個想法, 所以我們就得到了方法二囉。
方法二: 盤面其實是一個6*5的map, 所以我們可以直接將上面的圖片縮小到6*5的大小, 那麼我們就簡單的可以取得如下圖所示的一個6*5的顏色矩陣, 然後就能發現用人眼就可以簡單的分別出不同的色塊了。
enter image description here
當然, 電腦不像人眼那麼強大, 可以簡單的分辨出哪幾個區域是屬於同一區塊的, 電腦只能知道這個顏色代表的值為何, 相信有做過影像處理的人都會直覺想到, 該是HSV ( Hue,Saturation,Value 色相,飽和度,明度 ) 出場的時候了。
為什麼要用HSV, 用下面的範例來做個解釋吧, 對人眼來說, 下面的這兩個顏色就人眼來說會被視為相似的, 但是對 電腦來說沒辦法利用RGB的值簡單的將他們歸類為同一類, 只能知道Blue的值會比Red,Green來得高, 但是一旦我們將RGB轉成HSV之後, 你會發現紅色字體(色相)數值的部分相當接近, 我們就可以透過這個數值來做為分類的標準了。
      RGB=(055,164,255)
      RGB=(134,198,220)
      HSV=(207,078,100)
      HSV=(195,039,086)


透過盤面來自動轉珠

enter image description here


既然我們已經將遊戲盤面給數值化了, 那麼就可以開始來撰寫自動轉珠的路徑了, 但是要怎麼樣才可以算出高Combo的路徑或是傷害最高的路徑呢? 首先我們要知道PAD裡面傷害計畫的公式:
基礎攻擊力 x 消珠倍率(+寶珠強化) x COMBO倍率 x 隊長技和主動技倍率 = 寵物傷害 (資料來源: ptt.cc)
接下來是最重要的演算法的部分, 如何設計一個好的演算法來求得傷害最高的路徑, 說真的, 我覺得要想到一個很好的演算法頗困難的, 還好目前的電腦cpu都還蠻強的, 加上其實盤面並不會很大, 只有6*5的大小, 所以在這邊我直接使用BFS方式來求解。實作的方式為: 針對盤面上的每一個珠子, 計算它可以往外前進的八個方向, 每走一步之後就計算目前盤面可以消除區域, 並計算落下之後是否造成下次的消除, 再代入上述的公式, 並且設定一個珠子最多可以走幾步, 最後就我們就可以得到每一個起始珠子走過的路徑的Combo數及攻擊力的權重表格, 透過這個表格我們就可以取到一個攻擊力最高的路徑了, 下面為pseudocode:
for row=1, 5 
    for col=1, 6
        solutions.add(new Solution(cursor(row, col));
while not solutions.isEmpty()
    solution = solutions.pop()
    if solution.depth >= MAX_DEPTH
        continue
    for move=1, 8
        newSolution = moveOrbs(solution, move)
        calculateWeight(newSolution)
        solutions.add(newSolution)
在取得一個路徑之後, 我們就可以透過之前講過的API- Drag來移動珠子了。後來發現其實網路上還蠻多自動轉珠的演算法, 不過實作方法大致上都差不多, 有興趣的人可以去研究一下原始碼: pndopt。
中間其實省略過不少過程, 不過大方向都已經提出來了 XD
總之, 最後就用自動轉珠的影片來做個結尾吧~(用SCR Screen Recorder Free 預設的設定錄下來的, 有點頓)



沒有留言:

張貼留言

訂閱： 張貼留言 (Atom)