憤怒的小鳥的關卡如何保證有解？怎麼確定最優解？

01-14

比如1星 2星 3星。tnt的作用，擊碎木板時掉落的作用等等。

蒙特卡洛啊。

關卡測試不需要自己在屏幕上面去戳的，只要隨機出大量的變數值，（怒鳥非常簡單，只有發射位置和爆發時機兩個變數），每組變數的結果都是一定的，而且不需要花像現實中玩一次那麼長的時間，瞬間就能計算出結果了。最後根據這些隨機變數模擬出的結果是否有三星來判斷該關卡能不能過，三星的比例則代表關卡難度。

憤怒的小鳥的關卡如何保證有解？

身邊有幾個人都將所有關卡都拿到3星，實驗證明解是一定有的。

怎麼確定最優解？

我有幾個方案，但一直沒有機會去嘗試。如果您有更好的方案或是嘗試了以下的某一種方法，請一定第一時間通知我哦！

系統分析：

由於每一個關卡的小鳥類型，建築結構等都不一樣，每一個關卡都是一個獨立的系統，不存在一個對所有關卡都適用的共同解。

從系統的角度分析，輸入這個系統的是手指（或滑鼠）在釋放前的位置，以及一些小鳥使用特技的位置，輸出的是得分。

釋放的位置提供了兩個參數，一個是水平角度θ，另一個是沿彈弓皮筋方向上的位移r。（就是以小鳥初始位置為原點的，對該位置的極坐標描述）

使用特技的位置，其實僅僅由距離釋放時刻的時間差決定，所以第三個輸入參數就是這個時間差t.

假設有n只小鳥，系統可以量化為：

(θ1,r1,t1,θ2,r2,t2,...,θn,rn,tn) ==== &> ???未知系統內部??? ==== &> 得分

由於這個系統是非線性的，所以一點的偏差之後的結果可以截然不同（蝴蝶效應）。

上面其實都是廢話。。。關鍵問題在於系統內部是對我們是未知的。

通過解決這個未知可有以下兩個方案：

方案一：查看源碼，得出它背後的公式，然後再對每一個關卡建模寫方程，最後求解（八成是要用數值方法求解的）

方案二：對每一個關卡運行多次，收集數據，作曲線擬合得出經驗公式。

如此分析這個遊戲，想必你已經覺得我很蛋疼了（我也覺得自己蛋疼），利用上面兩種方案就更2了，建議您也不要嘗試，價值不大，除非您真的非常感興趣。

但是，世界上不是所有問題必須已知才可以被解決的。如何避開這個未知的系統解決這個最優解的問題呢？以下兩個方案都是比較可行的，但是您得會編程。

方案三：窮舉法。窮舉 (θ1,r1,t1,θ2,r2,t2,...,θn,rn,tn)，然後模擬，最大分值的解就是最優解。（對於一兩個鳥就可以搞定的這個可以考慮）

方案四：遺傳演算法(genetic algorithm)。通過遺傳演算法，建立 (θ1,r1,t1,θ2,r2,t2,...,θn,rn,tn) 種群，然後通過許多代隨機的淘汰、遺傳和變異，最終可以得出最優解。（判據和初始參數的設置很重要，否則可能會陷入局部的最優而不是全局的）

總結哥：

作為一個遊戲嘛，還是用我們的手指演算法去尋找最優解才會有意思。只有Pirate Henry這樣蛋疼的nerd才會為遺傳演算法的求解而興奮到睡不著覺。

QA;:

Q: 1星 2星 3星

A: 通過觀察得知，純粹由分數決定，不同關卡根據難度有不同的閾值。

Q: tnt的作用，擊碎木板時掉落的作用等等?

A: 這些物理方程都是在源碼里寫定的，我不知道，如果有看過源碼的高人，一定要補充啊~

參考資料：

[1] 有個蛋疼的米國人對飛行過程進行了量化分析，其結論很歡樂：5米高的彈弓+70厘米高又大又憤怒的鳥。（哈哈~ 建議遊戲譯名改成：憤怒的大鳥）

英文原版：http://www.wired.com/wiredscience/2010/10/physics-of-angry-birds/

中文譯版：http://www.cpusky.com/fenxiangrybird.html

你們都想多了。。

最簡單而有效的辦法是，憑直覺隨便設置關卡，然後反覆試玩，調整難度：

1、最重要的：調整小鳥的數目。難了的關卡就多加幾個小鳥~ 所以很顯然每個關卡的小鳥數目是根據目標結構來設定的而不是根據關卡編號來設定的。

2、調整關卡的順序。複雜和難的關卡一般傾向於往後放。

這個過程用人力去完成成本要明顯低於去設計一套複雜的評估演算法。

遊戲裡面添加了不少隨機性(例如我親眼見過一個理應穩定的結構在我還沒出手前就輕微倒塌了...).

最優解不僅僅是要靠技術, 還是要靠人品的...

因為我目前正在跟迪士尼合作一款物理解謎遊戲，學到一些經驗。與小鳥或者其他關卡制的休閒遊戲應該有相通之處。

1。一個關卡制的遊戲必須在前期有所規劃：機關最大尺寸，主角尺寸，最多機關數等一系列問題都是前期就要從理論上確定好的，並總結出一份gdd文檔作為日後關卡設計的準則。

2。根據遊戲的準則由關卡設計師憑經驗設計草圖，經過小組討論後篩選方案。

3。實施真實設計，並進行一輪自我修復。即關卡設計師自己檢查關卡問題。這一步就要保證是一個可以過關的關卡。

4。也是最重要的一點，用戶測試。此類遊戲給玩家的操作相對要寬泛一些，所以要有一定基數的用戶測試保證遊戲的大體思路得到驗證。

5。最後一步最難，根據玩家測試反饋，設計師要真實的對待數據分析並且修改自己的關卡。

經過以上五步基本就可以保證關卡這部分的順利進行了。

個人感覺非線性系統一定是沒錯的，支撐結構相互之間的作用力有很大的隨機性，而且遊戲把結構設定在了暫穩態，即使同一角度同意力度產生的結果也會有很大的不同，所以最優解顯然不是完全確定的。

遊戲設計者也許首先是通過人腦這個計算非線性系統的最佳工具大概的判斷一下難易度，然後通過Pirate Henry所說的演算法進行驗證篩選，得到一個可能解的分布，從而設定關卡的分值，也許這也是不同關卡難易度相差很大並且不穩定的原因。

從關卡設計的角度保證有解個人覺得有兩種辦法：

根據設計師的直覺進行設置，然後手工測試有解，但因為測試量的問題無法保證得到最優解和合適的關卡難度，且在關卡數量較多時導致工作量過大易出錯，勝在快捷易行，最好能結合虞翔的答案，製作一個對應的自動測試工具。
製作一個關卡設計工具，關卡設計師通過調整一系列參數如初始位置，發射角度容錯，距離，物塊數量，小鳥種類和數量等，計算出一些碰撞塊組合結果，然後根據碰撞進行美術補充，會佔用一部分技術資源，但勝在一勞永逸。

這貨用的是牛頓迭代法搞的碰撞檢測也只有兩個基於簡單線性代數的大核心，所以你在遊戲中看到的複雜曲線在設計師眼裡可以調衝量detla t讓它變成一條條明顯直線直接犧牲了精度求近似解，設計成本當然會下降很多，比如給你來個小隧道各種機關怎麼保證你能穿過去你要去試吧很蛋疼的，但迭代精度降低它可能越來越接近線性體系你想穿就比較容易了

最簡單的辦法：隨機角度力度特效時間，然後check一下，check的常數不大，起碼每秒100萬次嘗試是有的。哼，我就不信等個幾分鐘來幾億次組數據都不能出解！