首页 > 代码库 > 我的游戏服务器类库 -- 按权重随机选择1个或n个对象

我的游戏服务器类库 -- 按权重随机选择1个或n个对象

按权重选择

在编写游戏服务器的时候,经常会遇到类似的需求:从列表中随机选出1个或多个条目,且条目是有权重的(权重越大,选中它的可能性就越大)。比如说,砍死一个怪物可以从一个装备列表里掉一个装备。这种需求,和现实生活中的幸运大转盘很类似:

算法实现

因为这种需求很常见,所以我想把它写的通用一点。首先,接口Weighted表示有权重值的对象,getWeight()方法返回权重值:

public interface Weighted {
    public int getWeight();
}
WeightedBase是Weighted接口的抽象实现:

public abstract class WeightedBase implements Weighted {
    
    private final int weight;

    public WeightedBase(int weight) {
        if (weight <= 0) {
            throw new IllegalArgumentException("weight <= 0!");
        }
        this.weight = weight;
    }

    @Override
    public int getWeight() {
        return weight;
    }
    
}
WeightedInt表示拥有权重值的整数:

public class WeightedInt extends WeightedBase {

    private final int value;
    
    public WeightedInt(int weight, int value) {
        super(weight);
        this.value = http://www.mamicode.com/value;>

因为并不是每个类都可以实现Weighted接口或继承WeightedBase(比如第三方库里的类),所以增添了WeightFunction接口来表示权重计算函数,apply()方法根据给定对象,计算出其权重值:

public interface WeightFunction<T> {
    public int apply(T t);
}
最后是工具类WeightUtil,具体的选择算法在这个类中实现,下面是这个类的方法列表:

public class WeightUtil {
    public static <T extends Weighted> List<T> select(List<T> list, int n)
    public static <T> List<T> select(List<T> list, int n, WeightFunction<T> wf)
    public static <T extends Weighted> T selectOne(List<T> list)
    public static <T extends Weighted> T selectOne(List<T> list, int randomInt)
    public static <T> T selectOne(List<T> list, WeightFunction<T> wf)
    public static <T> T selectOne(List<T> list, int randomInt, WeightFunction<T> wf)
}
其中最重要的一个方法是接收三个参数的selectOne()方法,其他方法都依赖这个方法,其代码如下所示:

    public static <T> T selectOne(List<T> list, int randomInt, WeightFunction<T> wf) {
        if (list.isEmpty()) {
            throw new IllegalArgumentException("empty list!");
        }
        if (randomInt < 0) {
            throw new IllegalArgumentException("negative randomInt: " + randomInt);
        }
        if (list.size() == 1) {
            return list.get(0);
        }
        
        int weightSum = 0;
        for (T obj : list) {
            weightSum += wf.apply(obj);
            if (weightSum > randomInt) {
                return obj;
            }
        }
        
        String msg = String.format("total weight (%d) <= randomInt (%d)", weightSum, randomInt);
        throw new IllegalArgumentException(msg);
    }

GitHub项目

想要完整的代码,可以clone我的GitHub项目。此文章只是一个开始,希望以后可以把更多的代码放到这个项目里。


我的游戏服务器类库 -- 按权重随机选择1个或n个对象