我的游戏服务器类库 -- 按权重随机选择1个或n个对象
栏目：互联网时间：2014-10-02 08:00:01
按权重选择
在编写游戏服务器的时候，经常会遇到类似的需求：从列表中随机选出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 = value;
}
/**
* 返回整数值.
* @return
*/
public int getValue() {
return 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项目。此文章只是一个开始，希望以后可以把更多的代码放到这个项目里。
------分隔线----------------------------
------分隔线----------------------------