over 5 years ago

大地遊戲對戰組合產生器

http://ensky.tw/GroundGame/

簡介

最近辦營隊時發現,不少人在設計大地遊戲的時候,覺得最困難的不是怎樣設計活動,反而是如何產生對戰組合。
大地遊戲的對戰組合,通常是兩兩對戰,可以調整的參數有「隊伍數」、「關卡數」、還有「跑幾關」,
而還有一些限制,比如說對戰過得隊伍不能重複對戰、跑過得關卡不能再跑一次之類的限制,
總而言之這種東西人工算起來實在是非常麻煩,而這種暴力解法剛好就是電腦最善長的領域,
我們只要設定好列舉的方法,以及驗證的條件,就可以成功算出結果。

實做

一般而言大家想寫程式,除了特殊考量之外(ex:效能、平台),第一個選擇的就是自己最熟悉的語言,
而我最熟悉的語言便是PHP,因此就直接用他來實做。

演算法說起來也是沒有很複雜,
一開始我打算用隨機產生的方式來製造出對戰組合,沒想到速度慢到誇張,才跑幾個回合就開始需要等待了,
聽從邱渣的建議改採列舉組合的方法,速度才有顯著提昇。

列舉方面我是由回合=>關卡下去遞迴的,一開始先跑第一回合第一關,再來是第一回合第二關,以此類推下去跑到設定的參數為止。
先在每一回合第一關的時候產生出隨機的對戰組合,再來一關關跑下去,若發現條件不合則退後跑下一個組合,如此一來就可以把所有組合全部跑完。

瓶頸

我遇到最大的瓶頸是在於「語言本身」...
因為我和邱渣都對於這個project滿有興趣的,我和他分別採用PHP和C++撰寫,
結果他的硬是快上非常多(即使我跑得次數少很多),
他的大約跑100萬次以內都可以瞬間出來,
我的大約5~10萬就開始要等待時間...

因此最後的成果部份將改成網頁呼叫C++程式來執行。

成果

邱渣那邊還要作一些效能調校&介面整合的步驟,
因此我先用原本寫得php上線,成果如本頁最上方網址所示,
目前是採用ajax longpolling作運算,
未來應該會改成背後的worker作運算,並將結果存到Database,
加快反應速度,也比較能接受龐大的測資。

 
comments powered by Disqus