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

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

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

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

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