论坛首页 综合技术论坛

概率选中的算法实现

浏览 1862 次
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
作者 正文
   发表时间:2011-10-10  
一个常见的场景,在游戏中打一个怪物,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
论坛首页 综合技术版

跳转论坛:
Global site tag (gtag.js) - Google Analytics