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

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

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

3、分組是使得在一同游戲的玩家的實(shí)力盡可能的接近，成熟是判斷該組是否需要繼續(xù)留在匹配池中繼續(xù)等待新玩家進(jìn)入以期望得到更好的匹配結(jié)果，分隊(duì)是將成熟的組以隊(duì)伍間實(shí)力最接近為目標(biāo)將該組玩家分成A、B兩隊(duì)進(jìn)行對(duì)抗.改進(jìn)后的規(guī)劃匹配算法，將匹配質(zhì)量評(píng)價(jià)指標(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ì)了一種兼顧隨機(jī)性和相關(guān)性的擾動(dòng)機(jī)制以及根據(jù)玩家匹配的特點(diǎn)設(shè)計(jì)局部搜索算子進(jìn)行局部提升增大尋找到局部最優(yōu)解的效率和最優(yōu)解的概率，再者利用成熟機(jī)制對(duì)玩家匹配耗時(shí)進(jìn)行控制.
　　本文以國(guó)內(nèi)某知名MOBA游戲中單臺(tái)匹配服務(wù)器上5V5快速匹配模式某天的線上匹配數(shù)據(jù)作為改進(jìn)后的貪心匹配算法、改進(jìn)后規(guī)劃匹配算法的模擬仿真的數(shù)據(jù)，并將模擬仿真結(jié)果與線上匹配結(jié)果對(duì)比，結(jié)果顯示改進(jìn)后的貪心匹配算法和改進(jìn)后規(guī)劃匹配算法相較于線