暴击的伪随机算法--PRD算法【转载】

93 阅读 0 评论 62 点赞

我是靠谱客的博主超级大白，最近开发中收集的这篇文章主要介绍暴击的伪随机算法--PRD算法【转载】，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

PRD伪随机算法常用于游戏中的暴击算法，因此本文的标题将其称为 PRD暴击算法。

诞生与应用

PRD算法诞生与《魔兽争霸3》，可以说其诞生就是为了解决游戏中暴击概率所存在的问题。现在其广泛应用与Dota2、LoL等MOBA游戏和其它竞技性较高的游戏暴击概率运算中。

为何诞生？

如果暴击概率采用真实的算法，那么是会存在一些影响玩家游戏体验甚至游戏平衡的问题的，我们可以计算一下：

设一个角色的暴击率为50%，即 0.5。那么该角色进行100次攻击，理想状态下，应该会产生50次暴击，那么这50次暴击都会在哪次攻击时产生呢？对于这个假设，一次攻击暴击与不暴击的概率都为0.5，那么对于100次攻击，暴击50次的情况而言，不论把这50次暴击放在哪里，其概率都是0.5^100。这样就会产生一个怪异的情况：这50次暴击均匀的分布在100次攻击中这一情况的概率，与一开始就连续暴击50次的情况还有最后再连续暴击50次的情况，它们出现的概率都是相同的。

可以推算，即使暴击概率为0.3、0.7... 等，上述结论都是一定的。

这对于竞技性较强的游戏而言是应当避免的。以MOBA游戏为例，在比赛中，决定最终胜负的往往就是一两波的关键团战，那么如果根据上面的概率运算结论，玩家的运气因素就很有可能影响了一两波团战，最终决定了整局游戏的胜负。

因此，对于竞技游戏，我们应当让暴击的分布尽可能是均匀的，即还是对于上面说的100次攻击中，50次暴击的情况，我们希望这50次暴击均匀的分布在100次攻击中的情况的概率远远大于 50次暴击集中分布在某一区域的情况的概率。

更简单的说，对于 0.5 的暴击率，我们希望，玩家每隔一次攻击就会暴击一次，也就是玩家的攻击始终是暴击、不暴击、暴击、不暴击....

但这样做仍有弊端。我们游戏设立暴击率这一数值的目的本身就是为了给游戏添加随机性，只是我们不希望玩家的运气对于游戏结果产生过大的影响。如果按照上面的运算方式，那么当玩家角色暴击率为0.5时，如果玩家这次攻击没有暴击，那么玩家就可以准确地知道，他的下次攻击一定会暴击。那这样我们的游戏就失去了暴击率带来的随机性，就会失去一定的游戏性。

因此，我们需要想出一个能在随机性和均匀性之前取得一个良好平衡的随机运算方法，PRD算法也就应运而生了。

算法

PRD算法的表示非常简单：

P(N) = C * N

N表示当前攻击的次数，P(N)表示当前攻击的暴击率，C为概率增量。如果我们这次攻击产生了暴击，则需要将 N 重置为 1，如果这次攻击没有产生暴击，则 N + 1。

为了便于理解，这里直接给出一个具体例子：

设我们当前玩家角色暴击率还是0.5，那么对于 PRD算法，此时的 C = 0.3

此时第一次攻击时的实际暴击几率，即 P(1) = 0.3 * 1 = 0.3，若没有暴击，则 N + 1，N = 2

此时第二次攻击时的实际暴击几率，即P(2) = 0.3 * 2 = 0.6，若没有暴击，则 N + 1，N = 3

此时第三次攻击时的实际暴击几率，即P(3) = 0.3 * 3 = 0.9，此时对于大部分玩家而言这一次攻击就会产生暴击了，而如果玩家是个非酋，这次仍没有暴击，没关系，N + 1，N = 4

第四次攻击，P(4) = 0.3 * 4 = 1.2 >= 1，这一次是一定会暴击的。

可以看到，使用 PRD 算法，对于攻击是否会暴击这一问题，仍然是存在着随机性即玩家的运气因素的，但即使是运气最差的玩家，仍然也会在第四次攻击时产生暴击，因此PRD算法可以在保存随机性的同时，减少玩家运气因素对游戏结果的影响。

上面的例子展示了PRD算法会避免玩家一直不出现暴击的情况，同样PRD算法也会避免玩家一直出现暴击的情况。

还是同样的例子：

P(1) = 0.3 * 1 = 0.3，如果没有暴击 N + 1

P(2) = 0.3 * 2 = 0.6，如果没有暴击 N + 1

P(3) = 0.3 * 3 = 0.9，如果此时暴击了，我们会把 N 重置为 1 那么

P(4) = 0.3 * 1 = 0.3

可以发现，每次暴击后，下一次的暴击率都会被重置为最开始的暴击率0.3，而这个值也是整个运算过程中最低的暴击率。

因此，在PRD运算中，连续暴击的概率会受到 C 的影响，而 C 是一个小于目标暴击率的值，所以出现连续暴击的概率是较小的。

C 的计算

最后我们再来讨论一下这个 PRD 中的 C 是怎么来的。

在搞清C的由来之前，我们需要确定 N 是什么。

现在我们知道，在玩家暴击后，N 会被重置为 1。且如果经历了连续不暴击的情况，那么在连续不暴击一定次数后，一定是会产生暴击的。

我们设最大的连续不暴击次数为 Nmax。那么这个 Nmax 是多少呢？

Nmax = ceil(1 / C) 其中 ceil 是向上取整的意思。

注意：
一定要明确 Nmax = ceil(1 / C) 而不是 Nmax = ceil(1 / P)
仍是以暴击率为 0.5 举例，如果按照 Nmax = ceil(1 / P) 计算：
Nmax = ceil(1 / 0.5) = ceil( 2 ) = 2，也就是第二次攻击必定暴击，那么可以轻易得出此时 C = P = 0.5
有：P(N) = 0.5 * N
这样确实可以保障我们两次攻击中会有一次暴击，避免了连续不出现暴击的情况。
但是其暴击率增量 0.5 等于我们当前的暴击率 0.5，即 C = P，这会导致我仍有很大的可能性出现连续暴击的情况，所以 Nmax = (1 / P) 的计算方式可以避免连续不出现暴击，但是不能避免连续出现暴击，且会降低游戏的随机性。我们希望的是 C < P

根据上述关于 Nmax 为何是 ceil(1 / C) 而不是 ceil(1 / P) 的讨论，我们可以发现，C 一定是一个 0~P 范围的数值。0~P 范围是一个连续递增的序列，那么在其中要找到一个合适的 C 值，我们就可以使用二分法的方式，来进行查找。

我们在 0~P 范围采取二分，取得第一次的 C = (0 + P) / 2 = P / 2 (下面用 Mid 来表示这个临时的 C)

这样可以计算出 Nmax = ceil(1 / C) = ceil(2 / P)

之后我们计算出 0~Nmax 过程中，暴击率的均值 Ptested，即在必定暴击的最小范围内的平均暴击率，并且这个均值应当是趋近于暴击率 P 的。

我们比较 Ptested 和 P：

如果 Ptested > P 则说明我们当前二分到的 Mid 过大，导致最小暴击范围内的暴击率过大，那么就向 0~Mid 的范围继续二分。

相反我们就向 Mid~P 的范围继续二分。

那么二分的终点是哪里呢？显然，二分的终点我们二分到的值会是一个恒值或者说是在两个非常相近的范围间来回跳跃，此时它们计算出的 Ptested 是非常相近的。那么我们就可以声明一个变量 PLast 来存储上一个 Mid 计算出来的 Ptested，然后和当前的 Ptested 比较，如果差值非常小，则说明我们已经到达了二分的临界了，此时直接输出 Mid 即为我们的 C。

注意：
这里我们让 PLast 的初始值为 1。
因为在最小暴击范围内，最大的暴击概率为 1，那么其平均暴击率就一定小于 1 (且不会与 1 相似)
这样可以保障我们的二分查找至少进行一次查找，不会出现还没有二分程序就直接退出的情况。
即 PLast = 1 可以保障我们程序的严谨和安全(其实我觉得 2 更安全)，当然 PLast 初始只要是个大于 1 的值就行。

这里由于我的数学水平有限，对于 0~Nmax 范围间的平均概率即 Ptested 的计算公式理解不是很深，因此具体细节就不在这里深入讨论了，下面直接给出 PRD算法 C 值计算的完整代码。

PRD算法在概率 P 下的系数 C 的计算代码：

下面给出我在 Unity 中，在 Unity Editor 下编写的计算 P = 0 ~ 100 范围，即暴击率为 0% ~ 100% 范围内在 PRD 中，其对应的 C 值，C 值同样用 0~100 来表示 0% ~ 100%。因为对于C的计算是通过二分法来进行拟合，所以计算过程会很慢，这里使用多线程来计算，并将最终结果输出为 XML 文件进行保存，以便在计算暴击率时，能够直接通过读取配置文件获取 C 值而无需重新计算 C 值。

/*********************************************************
	文件：PRDCalcC
	作者：dell
	邮箱：630276388@qq.com
	日期：2020/9/3 9:19:06
	功能：计算PRD算法的C值
***********************************************************/
using System;
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using UnityEditor;
using System.IO;
using System.Text;
using System.Threading;

public class PRDCalcC : EditorWindow
{
    private static readonly string obj = "lock";
    private static Dictionary<int, int> prdDic = new Dictionary<int, int>();
    private string infoStr = "";
    private string dataStr = "数据运算中....";

    [MenuItem("Tools/PRD_C")]
    static void ShowWindow()
    {
        GetWindow<PRDCalcC>();
    }

    private void OnGUI()
    {
        EditorGUILayout.BeginVertical();
        if (GUILayout.Button("运算数据"))
        {
            // 计算 1% - 100% 暴击率范围所有的 PRD C值
            for (int i = 0; i <= 100; ++i)
            {
                int j = i;
                // 创建线程负责具体计算 C 值
                Thread thread = new Thread(() =>
                {
                    double p = i * 1d / 100d; // 显示给玩家的暴击率
                    double c = CFromP(p); // PRD算法 暴击增量
                    int ic = (int)Math.Round(c * 100, 0); // 将百分数小数转换为整数
                    lock (obj)
                    {
                        prdDic[j] = ic; // 计算结果存放在字典中
                    }
                });
                thread.Start();
            }
        }
        GUILayout.Label(dataStr);
        if (prdDic.Count == 101)
        {
            dataStr = "数据运算完毕";
            if (GUILayout.Button("点击生成配置文件"))
            {
                try
                {
                    CreateXml();
                    infoStr = "配置文件生成成功！";
                }
                catch (Exception e)
                {
                    infoStr = "配置文件生成失败！错误为：" + e;
                }
            }
        }

        GUILayout.Label(infoStr);

        EditorGUILayout.EndVertical();
    }

    // 生成 XML 文件
    private void CreateXml()
    {
        string path = EditorUtility.OpenFolderPanel("选择目标文件夹", "", "") + @"/prd.xml";
        StringBuilder sb = new StringBuilder();
        sb.Append(@"<?xml version=""1.0"" encoding=""UTF - 8"" standalone=""yes""?>");
        sb.Append('n');
        sb.Append(@"<root xmlns:xsi=""http://www.w3.org/2001/XMLSchema-instance"">");
        sb.Append('n');

        string xml = null;
        lock (obj)
        {
            // 在主线程中 从字典中拿出多线程放入的数据，进行解析
            foreach(var pair in prdDic)
            {
                sb.Append("<item>n");
                sb.Append("    <p>" + pair.Key + "</p>n");
                sb.Append("    <c>" + pair.Value + "</c>n");
                sb.Append("</item>n");
            }
            xml = sb.ToString();
            sb.Clear();
            xml.Remove(xml.Length - 1);
        }
        using(FileStream fs = Directory.Exists(path) ? File.OpenWrite(path) : File.Create(path))
        {
            byte[] bytes = Encoding.UTF8.GetBytes(xml);
            fs.Write(bytes, 0, bytes.Length);
            fs.Flush();
            fs.Close();
        }
        lock (obj)
        {
            prdDic.Clear();
        }
    }

    // 根据 传入 C 值，计算该C值下，最小暴击范围的平均暴击率
    private static double PFromC(double c)
    {
        double dCurP = 0d;
        double dPreSuccessP = 0d;
        double dPE = 0;
        int nMaxFail = (int)Math.Ceiling(1d / c);
        for (int i = 1; i <= nMaxFail; ++i)
        {
            dCurP = Math.Min(1d, i * c) * (1 - dPreSuccessP);
            dPreSuccessP += dCurP;
            dPE += i * dCurP;
        }
        return 1d / dPE;
    }

    // 根据传入的暴击率，计算 PRD 算法中的系数 C
    private static double CFromP(double p)
    {
        double dUp = p;
        double dLow = 0d;
        double dMid = p;
        double dPLast = 1d;
        while (true)
        {
            dMid = (dUp + dLow) / 2d;
            double dPtested = PFromC(dMid);

            if (Math.Abs(dPtested - dPLast) <= 0.00005d) break;

            if (dPtested > p) dUp = dMid;
            else dLow = dMid;

            dPLast = dPtested;
        }

        return dMid;
    }
}