基于鄰域搜索的MOBA游戲玩家實時匹配算法研究.pdf

1、隨著目前人們休閑娛樂的方式日漸多元化，Multiplayer Online Battle Arena Games，中文譯名多人在線競技游戲，簡稱MOBA，因其極高的趣味性和耐玩性收到人們的追捧.對于MOBA游戲來說游戲的平衡性是貫穿整個游戲過程的核心系統(tǒng)，而玩家匹配是MOBA游戲平衡中其中重要的一環(huán).玩家匹配是讓多名在線等待開始多人競技游戲的玩家自動匹配到隊友和對手的技術(shù)，涉及玩家與玩家之間的相互合作或者相互競爭的交互，希望玩家們能得到

2、一場有趣且平衡的游戲體驗.目前玩家匹配作為一個新興領(lǐng)域隨著MOBA游戲的火熱也越來越引起學(xué)者的興趣，該領(lǐng)域目前較為流行的匹配方法有基于玩家水平的匹配方法和基于玩家角色的匹配方法，其中基于玩家水平的匹配方法已經(jīng)在線上主流MOBA類游戲中的得到驗證.因此本文在基于玩家水平上為進(jìn)一步增強(qiáng)玩家匹配效果和玩家游戲體驗進(jìn)行研究分析，創(chuàng)新性的提出了改進(jìn)后的貪心匹配算法和規(guī)劃匹配算法.改進(jìn)后的貪心匹配算法，將玩家匹配過程分成：分組-成熟-分隊三個過程，

3、分組是使得在一同游戲的玩家的實力盡可能的接近，成熟是判斷該組是否需要繼續(xù)留在匹配池中繼續(xù)等待新玩家進(jìn)入以期望得到更好的匹配結(jié)果，分隊是將成熟的組以隊伍間實力最接近為目標(biāo)將該組玩家分成A、B兩隊進(jìn)行對抗.改進(jìn)后的規(guī)劃匹配算法，將匹配質(zhì)量評價指標(biāo)以一定權(quán)重線性組合作為適應(yīng)度函數(shù)，通過一種改進(jìn)的局部搜索迭代算法（Iterated-Local-Search,ILS）進(jìn)行求解以求得到適應(yīng)度較高的匹配方案，該算法基于破壞重構(gòu)（ruin and re

4、cecrate）的思想設(shè)計了一種兼顧隨機(jī)性和相關(guān)性的擾動機(jī)制以及根據(jù)玩家匹配的特點設(shè)計局部搜索算子進(jìn)行局部提升增大尋找到局部最優(yōu)解的效率和最優(yōu)解的概率，再者利用成熟機(jī)制對玩家匹配耗時進(jìn)行控制.
　　本文以國內(nèi)某知名MOBA游戲中單臺匹配服務(wù)器上5V5快速匹配模式某天的線上匹配數(shù)據(jù)作為改進(jìn)后的貪心匹配算法、改進(jìn)后規(guī)劃匹配算法的模擬仿真的數(shù)據(jù)，并將模擬仿真結(jié)果與線上匹配結(jié)果對比，結(jié)果顯示改進(jìn)后的貪心匹配算法和改進(jìn)后規(guī)劃匹配算法相較于線