概率选中的算法实现

一个常见的场景，在游戏中打一个怪物，10%几率出现miss，那么这次攻击是命中还是miss呢？我们可以用随机数来实现，miss的范围是[1,10]，命中的范围是[11,100]，然后我们取一个随机数，比如60就是命中了，如果不幸取到8就是miss了。只要测试的次数足够多，那么miss的比例将会趋向于10%。

再举多个候选数的例子。比如a概率为20%，b概率为30%，c概率为40%，d概率为10%，那么他们的概率值范围分别是：
a[1,20]
b[21,50]
c[51,90]
d[91,100]
然后取一个[1,100]的随机数，落到谁的范围谁就是选中了。

算法描述如下：
1.依次（顺序可随机）将各项按概率值从原点开始放在一维坐标上首尾相连，这样每一项对应一个取值区间
2.在总区间范围内随机选取一个点，落在哪一项对应的区间就选中哪一项

java实现：

public class RandomEngine {
     /**
     * 概率选择
     * @param keyChanceMap key为唯一标识，value为该标识的概率，是去掉%的数字
     * @return 被选中的key。未选中返回null
     */
     public static String chanceSelect(Map<String, Integer> keyChanceMap) {
          if(keyChanceMap == null || keyChanceMap.size() == 0)
               return null;
          
          Integer sum = 0;
          for (Integer value : keyChanceMap.values()) {
               sum += value;
          }
          // 从1开始
          Integer rand = new Random().nextInt(sum) + 1;
          
          for (Map.Entry<String, Integer> entry : keyChanceMap.entrySet()) {
               rand -= entry.getValue();
               // 选中
               if(rand <= 0) {
                    return entry.getKey();
               }
          }
          
          return null;
     }
}

测试（次数足够多时，各值出现的比例跟概率是基本一致的）：

public class RandomEngineTest {
     public static void main(String[] args) {
          Map<String, Integer> keyChanceMap = new HashMap<String, Integer>();
          keyChanceMap.put("a", 30);
          keyChanceMap.put("b", 10);
          keyChanceMap.put("c", 40);
          keyChanceMap.put("d", 20);
          
          Map<String, Integer> count = new HashMap<String, Integer>();
          for (int i = 0; i < 100000; i++) {
               String key = RandomEngine.chanceSelect(keyChanceMap);
               if(count.containsKey(key)) {
                    count.put(key, count.get(key) + 1);
               }
               else {
                    count.put(key, 1);
               }
          }
          
          // print
          for (String key : count.keySet()) {
               System.out.println(key + ":" + count.get(key));
          }
     }
}

参考：http://blogread.cn/it/article.php?id=4102