游戲排行榜設(shè)計(jì)

前言

游戲排行榜是每個(gè)游戲都必備的一個(gè)功能。有日常常駐的排行榜，比如游戲的戰(zhàn)力排行榜，游戲的財(cái)富排行榜等。還有就是各種排行活動(dòng)中的排行榜。我們隨便舉幾個(gè)游戲中排行榜的例子。

我們可以看到一般游戲只會(huì)列舉排行前100或者200名的名單，之外的就是暫未上榜，不給出具體排名，上述游戲中有的榜單會(huì)實(shí)時(shí)更新，有的會(huì)定時(shí)更新。

思考和設(shè)計(jì)

根據(jù)一般游戲的需求，我提煉出一個(gè)游戲排行榜需要具備一下功能

  • 前100或者200（數(shù)值可指定，一般小于200）的排名是精準(zhǔn)無(wú)誤的，并且能夠有足夠的信息展示給玩家
  • 排行榜的排名最好可以做到實(shí)時(shí)更新
  • 對(duì)于未上榜的排名能夠給出一個(gè)比較準(zhǔn)確的估計(jì)值將是更好的
  • 具備高性能
  • 支持并發(fā)

看到高性能 、并發(fā) 等字眼，感覺(jué)好像很困難，但萬(wàn)事開頭難，我們先不關(guān)心這個(gè)，我們先考慮怎么保證業(yè)務(wù)。

如果設(shè)計(jì)一個(gè)通用的排行榜呢？那首先需要一個(gè)通用的排行數(shù)據(jù)，對(duì)于排行數(shù)據(jù)我抽象為下面這個(gè)類

基準(zhǔn)排行類設(shè)計(jì)

public class RankData : IComparable<RankData>, IEquatable<RankData>, ICloneable
{
    /// <summary>
    /// 排序主鍵
    /// </summary>
    public long Id { get; set; }
    /// <summary>
    /// 排序值
    /// </summary>
    public long Value { get; set; }
    /// <summary>
    /// 附加參數(shù) - int類型
    /// </summary>
    public int[] Params { get; set; }
    /// <summary>
    /// 附加參數(shù) - object類型
    /// </summary>
    public object[] ExtraParams { get; set; }
    /// <summary>
    /// 達(dá)到該分?jǐn)?shù)的時(shí)間
    /// </summary>
    public long UpdateTime { get; set; }

    public bool Equals(RankData other)
    {
        if (null == other)
        {
            return false;
        }

        return Id == other.Id;
    }

    public int CompareTo(RankData other)
    {
        if (null == other)
        {
            return 1;
        }

        // 分?jǐn)?shù)高的排前面
        if (Value > other.Value)
        {
            return -1;
        }
        if (Value < other.Value)
        {
            return 1;
        }

        // 更新時(shí)間早的排前面
        if (UpdateTime > other.UpdateTime)
        {
            return 1;
        }
        if (UpdateTime < other.UpdateTime)
        {
            return -1;
        }

        // Id小的排前面
        if (Id < other.Id)
        {
            return -1;
        }
        return Id == other.Id ? 0 : 1;
    }

    public object Clone()
    {
        return new RankData
        {
            Id = Id, Value = Value, Params = Params, StrParams = StrParams,
        };
    }
}

對(duì)于這個(gè)類的設(shè)計(jì)意圖如下：

  • Id 是排行對(duì)象的唯一標(biāo)識(shí)，比如如果是游戲內(nèi)的排行榜一般是玩家Id
  • Value 是用于排行的數(shù)值，數(shù)值越大排行越靠前。比如戰(zhàn)力排行榜就是戰(zhàn)力值
  • Params 是用于排行的附加數(shù)據(jù)，一般用于輔助顯示，假設(shè)一個(gè)足球游戲的聯(lián)賽排行榜，積分是用于排行，那Params 里可以存儲(chǔ) 勝場(chǎng)次、負(fù)場(chǎng)次，平場(chǎng)次 用于輔助排行榜顯示
  • ExtraParams 和Params是類似用途
  • UpdateTime 是用于記錄玩家達(dá)到該排行榜分?jǐn)?shù)的時(shí)間戳，對(duì)于相同分?jǐn)?shù)的玩家我們可以根據(jù)該字段判斷達(dá)成時(shí)間越早的排在越前面

我想大部分的排行榜都可以轉(zhuǎn)化為該對(duì)象，再交給專用的排行榜管理類統(tǒng)一進(jìn)行排序，這樣我們邁進(jìn)了第一步，有了統(tǒng)一的基準(zhǔn)排序?qū)ο蟆?/p>

那接下來(lái)就是選用什么數(shù)據(jù)結(jié)構(gòu)去用于排序，我選用的是大家最常用的數(shù)據(jù)結(jié)構(gòu)List , List基于數(shù)組實(shí)現(xiàn)，有高效的訪問(wèn)效率。我們維護(hù)一個(gè)有序的數(shù)組，那么對(duì)于后續(xù)插入數(shù)據(jù)只需要采用二分查找找到合適的插入位置，整個(gè)排行榜在運(yùn)行期間，無(wú)需做任何一次排序運(yùn)算，性能是很高的。

對(duì)于排名我是分為精確排名 + 估計(jì)排名

  • 精確排名，RankData 存儲(chǔ)在List中
  • 估計(jì)排名，我們根據(jù)他的排行分?jǐn)?shù)已一個(gè)固定分?jǐn)?shù)間隔進(jìn)行分桶，記錄每個(gè)桶中玩家數(shù)量

排行榜類設(shè)計(jì)

對(duì)于排行類（Rank）我的設(shè)計(jì)如下

public class Rank : IDisposable
{
    private int _pointInterval; // 分?jǐn)?shù)區(qū)間基準(zhǔn)
    private readonly int _maxNum; // 精確排名最大值
    private int _totalNum; // 參與排行玩家總數(shù)
    private readonly List<RankData> _rankList; // 精確排名列表
    private List<int> _extraRankList; // 非精確排名列表
    private volatile bool _stopRankFlag; // 停止排名標(biāo)志
    private readonly ReaderWriterLockSlim _rwLock; // 讀寫鎖
    private readonly int _maxExtraRankRangeCount; // 默認(rèn)非精確排名最大區(qū)間數(shù)量

    /// <summary>
    /// 構(gòu)造函數(shù)
    /// </summary>
    public Rank(int maxNum, int pointInterval, int maxExtraRankRangeCount = 10000)
    {
        _rwLock = new ReaderWriterLockSlim();
        _maxNum = maxNum;
        _pointInterval = pointInterval;
        _rankList = new List<RankData>();
        _extraRankList = new List<int>();
        _stopRankFlag = false;
        _maxExtraRankRangeCount = maxExtraRankRangeCount;
    }
}
  • _rankList 用于存儲(chǔ)精確排名的玩家，存儲(chǔ)了完整的RankData
  • _extraRankList 用于存儲(chǔ)精確排名之外的每個(gè)桶中玩家數(shù)量
  • _maxExtraRankRangeCount 用于限制桶的最大數(shù)量，用于提高性能
  • _maxNum 用于定義精確排名的最大數(shù)量
  • _pointInterval 用于定義分桶基準(zhǔn)

排行榜類API設(shè)計(jì)

對(duì)于排行榜我定義了一下接口

/// <summary>
/// 更新排行數(shù)據(jù)
/// </summary>
public void AddRankData(RankData data);
/// <summary>
/// 更新排行數(shù)據(jù)
/// </summary>
public void UpdateRankData(RankData data, long srcValue, long srcUpdateTime);
/// <summary>
/// 從排行榜中剔除
/// </summary>
public void RemoveRankData(RankData data);
/// <summary>
/// 獲取自身排名
/// </summary>
public int GetMyRank(RankData data);
/// <summary>
/// 獲取排行榜數(shù)據(jù)
/// </summary>
public List<RankData> GetRankList(int start, int end);

下面我們一個(gè)一個(gè)來(lái)看每個(gè)API的具體實(shí)現(xiàn)

  1. 添加排行數(shù)據(jù)

用于系統(tǒng)啟動(dòng)時(shí)候初始化排行榜，或者新進(jìn)榜玩家

public void AddRankData(RankData data)
{
    if (_stopRankFlag)
    {
        return;
    }

    _rwLock.EnterWriteLock();
    try
    {
        _totalNum++;
        if (_rankList.Count >= _maxNum)
        {
                        // 精確排行榜已滿，與隊(duì)尾比較
            var last = _rankList[_rankList.Count - 1];
            if (data.Value <= last.Value)
            {
                                // 不滿足上榜需求，直接添加到非精確排名
                AddToExtraRankList(data);
            }
            else
            {
                              // 可以上榜，添加到排行榜，并且淘汰隊(duì)尾
                AddToRankList(data);
                RemoveTail();
            }
            return;
        }
                // 未滿情況下直接進(jìn)入精確排行榜
        AddToRankList(data);
    }
    finally
    {
        _rwLock.ExitWriteLock();
    }
}

結(jié)合注釋應(yīng)該很容易看懂，后續(xù)會(huì)給出幾個(gè)通用方法的實(shí)現(xiàn)代碼

  1. 更新排行榜數(shù)據(jù)

用于已經(jīng)進(jìn)行過(guò)排行的玩家，排行數(shù)值發(fā)生變化，需要更新排行榜

/// <summary>
/// 更新排行數(shù)據(jù)
/// </summary>
public void UpdateRankData(RankData data, long srcValue, long srcUpdateTime)
{
    if (_stopRankFlag)
    {
        return;
    }

    _rwLock.EnterWriteLock();
    try
    {
                // 構(gòu)造變更前的排行數(shù)據(jù)，該數(shù)據(jù)必須準(zhǔn)確，一般可以根據(jù)數(shù)據(jù)庫(kù)記錄
        var srcData = data.Clone() as RankData;
        srcData.Value = srcValue;
        srcData.UpdateTime = srcUpdateTime;

        var last = _rankList[_rankList.Count - 1];
        if (_rankList.Count >= _maxNum && data.Value < last.Value && rcData.Value < last.Value)
        {
            // 精確排名已滿，老值和新值都不足以進(jìn)入精確排名
            AddAndRemoveExtraRankList(data, srcData);
        }
        else
        {
                      // 查找之前的排名數(shù)據(jù)
            var myIndex = _rankList.BinarySearch(srcData);
            if (myIndex >= 0)
            {
                // 在精確排名中
                _rankList.RemoveAt(myIndex);
                AddToRankList(data);
            }
            else
            {
                myIndex = _rankList.BinarySearch(data); // 獲取實(shí)時(shí)排名
                if (Math.Abs(myIndex) <= _maxNum)
                {
                    // 晉升到精確排名
                    AddToRankList(data);
                    // 從非精確排名剔除自己
                    RemoveExtraRankList(srcData);
                    // 移除精確排名隊(duì)尾，保證數(shù)量
                    RemoveTail();
                }
                else if (_rankList.Count < _maxNum)
                {
                    AddToRankList(data);
                }
                else
                {
                    AddAndRemoveExtraRankList(data, srcData);
                }
            }
        }
    }
    finally
    {
        _rwLock.ExitWriteLock();
    }

}
  1. 從排行榜中移除

這個(gè)操作一般很少用到

/// <summary>
/// 從排行榜中剔除
/// </summary>
public void RemoveRankData(RankData data)
{
    if (_stopRankFlag)
    {
        return;
    }

    _rwLock.EnterWriteLock();
    try
    {
        _totalNum--;
        var last = _rankList[_rankList.Count - 1];
        if (_rankList.Count >= _maxNum && data.Value < last.Value)
        {
            RemoveExtraRankList(data);
        }
        else
        {
            var myIndex = _rankList.BinarySearch(data);
            if (myIndex >= 0)
            {
                _rankList.RemoveAt(myIndex);
            }
        }
    }
    finally
    {
        _rwLock.ExitWriteLock();
    }
}
  1. 獲取指定區(qū)間的排行數(shù)據(jù)

用于展示前100名排行榜數(shù)據(jù)

/// <summary>
/// 獲取排行榜數(shù)據(jù)
/// </summary>
public List<RankData> GetRankList(int start, int end)
{
    var resultList = new List<RankData>();
    if (start >= end)
    {
        return resultList;
    }

    _rwLock.EnterReadLock();
    try
    {
        end = Math.Min(end, _rankList.Count);
        for (var i = start; i < end; i++)
        {
            resultList.Add(_rankList[i]);
        }

        return resultList;
    }
    finally
    {
        _rwLock.ExitReadLock();
    }
}
  1. 獲取自身排名

用于獲取特定玩家的排行榜

/// <summary>
/// 獲取自身排名
/// </summary>
public int GetMyRank(RankData data)
{
    if (data == null || _rankList.Count <= 0)
    {
        return -1;
    }

    _rwLock.EnterReadLock();
    try
    {
        var last = _rankList[_rankList.Count - 1];
        int index;
        if (data.Value >= last.Value)
        {
            // 在精確排名中
            index = _rankList.BinarySearch(data);
            if (index >= 0)
            {
                return index + 1;
            }
        }

        // 在非精確排名中
        return GetRankFromExtraRankList(data);
    }
    finally
    {
        _rwLock.ExitReadLock();
    }
}
  1. 內(nèi)部方法

下面給出上述對(duì)外API用的內(nèi)部方法實(shí)現(xiàn)

/// <summary>
/// 從非精確排名中獲取評(píng)估排名
/// </summary>
private int GetRankFromExtraRankList(RankData data)
{
    int myRank;
    var index = (int)(data.Value / _pointInterval);
    var beforeNum = _rankList.Count;
    var lowPoint = (index + 1) * _pointInterval - 1;

    for (var i = _extraRankList.Count - 1; i > index; i--)
    {
        beforeNum += _extraRankList[i];
    }

    if (index <= _extraRankList.Count - 1)
    {
        var avg = _pointInterval * 1.0 / (_extraRankList[index] + 1);
        beforeNum += (int)Math.Floor((lowPoint - data.Value) / avg);
        myRank = beforeNum;
    }
    else
    {
        myRank = beforeNum + 1;
    }

    return myRank;
}

private void RemoveExtraRankList(RankData data)
{
    var index = (int)(data.Value / _pointInterval);
    if (_extraRankList.Count > index)
    {
        _extraRankList[index] -= 1;
    }
}

private void AddAndRemoveExtraRankList(RankData newData, RankData oldData)
{
    var newIndex = (int)(newData.Value / _pointInterval);
    var oldIndex = (int)(oldData.Value / _pointInterval);
    if (newIndex != oldIndex)
    {
        RangeCehck(oldIndex, _extraRankList);
        _extraRankList[oldIndex] -= 1;
        RangeCehck(newIndex, _extraRankList);
        _extraRankList[newIndex] += 1;
    }

    AdjustExtraRankList();
}

private void AddToExtraRankList(RankData data)
{
    var index = (int)(data.Value / _pointInterval);
    RangeCehck(index, _extraRankList);
    _extraRankList[index] += 1;

    AdjustExtraRankList();
}

private void AddToRankList(RankData data)
{
    var myIndex = _rankList.BinarySearch(data);
    if (myIndex >= 0)
    {
        _rankList[myIndex] = data;
    }
    else
    {
        _rankList.Insert(~myIndex, data);
    }
}

private void RemoveTail()
{
    if (_rankList.Count >= _maxNum)
    {
        var data = _rankList[_rankList.Count - 1];
        _rankList.RemoveAt(_rankList.Count - 1);
        AddToExtraRankList(data);
    }
}

private void RangeCehck(int index, List<int> rankList)
{
    if (rankList.Count <= index)
    {
        for (var i = rankList.Count; i <= index; i++)
        {
            rankList.Add(0);
        }
    }
}

/// <summary>
/// 動(dòng)態(tài)調(diào)整ExtraRankList
/// </summary>
private void AdjustExtraRankList()
{
    if (_extraRankList.Count > _maxExtraRankRangeCount)
    {
        var count = (int)Math.Ceiling(_extraRankList.Count * 1.0 / _maxExtraRankRangeCount);
        _pointInterval *= count;

        var newList = new List<int>(_maxExtraRankRangeCount);
        for (var i = 0; i < _extraRankList.Count; i++)
        {
            var newIndex = i / count;
            if (newList.Count > newIndex)
            {
                newList[newIndex] += _extraRankList[i];
            }
            else
            {
                newList.Add(_extraRankList[i]);
            }
        }
        _extraRankList = newList;
    }
}

排行榜正確性和性能測(cè)試

對(duì)于上述的實(shí)現(xiàn)，是否正確呢？性能是否足夠呢？我設(shè)計(jì)了以下測(cè)試類

[TestClass]
public class RankTest
{
    // 正確性測(cè)試
    [TestMethod]
    public void Test()
    {
        
        var rank = new Rank(100, 100);
        var dict = new Dictionary<int, long>();
        var random = new Random();
        var max = 100000;
        
        // 1. 初始化數(shù)據(jù)
        var time = Stopwatch.StartNew();
        time.Start();
        for (int i = 0; i < max; i++)
        {
            dict[i] = random.Next();
        }
        time.Stop();
        Console.WriteLine($"dict add time:{time.ElapsedMilliseconds}");
        
        // 2. 插入到排行榜
        time.Restart();
        for (int i = 0; i < max; i++)
        {
            rank.AddRankData(new RankData { Id = i, Value = dict[i] });
        }
        time.Stop();
        Console.WriteLine($"add time:{time.ElapsedMilliseconds}");

        // 3. 打印排行榜數(shù)據(jù)
        List<RankData> _rankList = rank.GetRankList(0, 100);
        foreach (var data in _rankList)
        {
            Console.WriteLine($"{data.Id},{data.Value}");
        }
        
        Console.WriteLine();
        Console.WriteLine("---------------------------------------");
        
        // 4. 更新排行榜
        time.Restart();
        for (int i = 0; i < max; i++)
        {
            var id = random.Next(max);
            var value = random.Next();
            rank.UpdateRankData(new RankData { Id = id, Value = value }, dict[id]);
            dict[id] = value;
        }
        time.Stop();
        Console.WriteLine($"update time:{time.ElapsedMilliseconds}");
        
        // 5. 獲取排名API測(cè)試
        time.Restart();
        for (int i = 0; i < max; i++)
        {
            var myRank = rank.GetMyRank(new RankData { Id = i, Value = dict[i] });
        }
        time.Stop();
        Console.WriteLine($"get rank time:{time.ElapsedMilliseconds}");
        
        
        // 6. 再次打印排行榜
        _rankList = rank.GetRankList(0, 100);
        foreach (var data in _rankList)
        {
            Console.WriteLine($"{data.Id},{data.Value}");
        }
        
        Console.WriteLine();
        Console.WriteLine("---------------------------------------");
        
        // 7. 計(jì)算估算排名的方差
        var list = dict.Values.ToList();
        list.Sort();
        double sum = 0;
        int n = 10000;
        for (int i = 0; i < n; i++)
        {
            var id = random.Next(max);
            var myRank = rank.GetMyRank(new RankData { Id = id, Value = dict[id] });
            var realRank = list.Count - (list.BinarySearch(dict[id]) + 1);

            sum += Math.Pow(Math.Abs(realRank - myRank), 2);
        }
        
        Console.WriteLine($"方差：{sum/n}");
    }
    
    // 性能測(cè)試
    [TestMethod]
    public void MultiThreadTest()
    {
        
        var rank = new Rank(100, 100);
        var random = new Random();
        var max = 100000;
        var threadNum = 10;

        List<Task> taskList = new List<Task>();
        for (int i = 0; i < threadNum; i++)
        {
            // 每個(gè)線程分別插入1遍數(shù)據(jù)，更新1遍數(shù)據(jù)，獲取1遍排名
            var task1 = Task.Run(() =>
            {
                var start = i * max;
                var end = (i + 1) * max;
                var time = Stopwatch.StartNew();
                time.Start();
                var dict = new Dictionary<int, long>();
                for (int i = start; i < end; i++)
                {
                    dict[i] = random.Next();
                }
                for (int i = start; i < end; i++)
                {
                    rank.AddRankData(new RankData { Id = i, Value = dict[i] });
                }
                for (int i = start; i < end; i++)
                {
                    var id = random.Next(start, end);
                    var value = random.Next();
                    rank.UpdateRankData(new RankData { Id = id, Value = value }, dict[id]);
                    dict[id] = value;
                }
                for (int i = start; i < end; i++)
                {
                    var myRank = rank.GetMyRank(new RankData { Id = i, Value = dict[i] });
                }
                time.Stop();
                Console.WriteLine($"thread:{System.Threading.Thread.CurrentThread.ManagedThreadId}, time:{time.ElapsedMilliseconds}");
            });
            taskList.Add(task1);
        }

        Task.WaitAll(taskList.ToArray());

    }
}

大家可以自己跑一下這個(gè)代碼

  • 基準(zhǔn)測(cè)試得到的精確排名是完全正確的
  • 預(yù)估排名方差大概在3~4之間，我感覺(jué)已經(jīng)足夠了
  • 對(duì)于多線程測(cè)試，對(duì)于這樣的操作我的機(jī)器是2.2s完成，平均每個(gè)線程1s左右。性能夠用了

結(jié)語(yǔ)

至此我們實(shí)現(xiàn)一個(gè)可以實(shí)時(shí)更新的排行榜，并且理論上是可以無(wú)限數(shù)量玩家參與的排行榜。對(duì)于未上榜的玩家也能給出比較準(zhǔn)確的預(yù)估值，可以用于游戲內(nèi)各種排行榜。您是怎么實(shí)現(xiàn)游戲內(nèi)排行榜的內(nèi)，歡迎留言交流！

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容