基于权重的随机选择算法

知乎

基于权重 的随机选择算法 - co lin的文章 - 知乎 https://zhuanlan.zhihu.com/p/146216606

游戏开发中经常会碰到这样的需求：从一系列道具中随机抽出一个发给玩家，由于道具的价值不一样，所以抽取的概率并不是平均的。后台会处理成高价值的东西很难得到，要实现这种效果，需要给每个道具指定一个权重。比如道具A的权重是99，道具B的权重是1，那么99%的概率会抽到道具A，这就是基于权重的随机算法。

实现按权重随机的最简单方法是线性扫描，大概过程是先计算出所有道具的权重总和S，然后调用随机函数得到一个区间在[0, S)的随机值，接着从头向后扫描道具列表，并不断从S减掉每个道具的权重值，当S小于某个道具的权重值时，这个道具就是抽中的那一个。逻辑代码如下：

-- 线性扫描
local function prepare_weighted_random1(values, weights)
    assert(#values == #weights)
    local sum = 0       -- 计算总权重
    for _, wt in ipairs(weights) do
        sum = sum + wt
    end
    return function()
        local n = math.random(1, sum)       -- 线性扫描
        for idx, wt in ipairs(weights) do
            if n <= wt then
                return values[idx], weights[idx]
            end
            n = n - wt
        end
    end
end

引用项目的实际需求

可以被随机到的权重。用于控制动作资源被随机到的概率。当前期望动作幅度大的权重小，被随机到的概率小；动作幅度小的权重大，被随机到的概率大。

FBlendSpaceParam UInworldCharacterAnimationsLib::WeightedRandom(TArray<FBlendSpaceParam>& RandomPool, TArray<FBlendSpaceParam>& BlendSpaces)
{
    if (RandomPool.Num() == 0 || BlendSpaces.Num() == 0)
    {
        return FBlendSpaceParam();
    }

    int32 TotalWeight = 0;
    for (const auto& bl : RandomPool)
    {
        TotalWeight += bl.Weight;
    }

    int32 RandomNumber = FMath::RandRange(0,TotalWeight - 1);

    float WeightSum = 0.0f;

    RandomPool.Sort(CompareWeight);

    for (int i = 0;i < RandomPool.Num();i++)
    {
        WeightSum += RandomPool[i].Weight;
        if (WeightSum >= RandomNumber)
        {
            for (int j = 0;j < BlendSpaces.Num();j++)
            {
                if (BlendSpaces[j] == RandomPool[i])
                {
                    BlendSpaces[j].MaxTimes--;
                    /*if (BlendSpaces[j].MaxTimes == 0)
                    {
                        BlendSpaces.RemoveAt(j);
                    }*/
                }
            }
            return RandomPool[i];
        }
    }

    return RandomPool[0];
}