游戏概率算法实现

问题描述

最近一直在着手一个新游戏的开发,其中很多地方都会涉及概率问题,由于当时只是为了完成功能,并没有在这一块考虑过多,现在回过来再看这个问题,感觉有必要深入一下,如果是你,你会如果实现一套概率呢?

解决方案

首先我们要知道什么是概率算法,概率算法就是在算法的过程中引入随机数,使得算法在执行的过程中随机选择下一个计算步骤,而它最后可能导致结果是不确定的.
由比,我们可以假设一个概率问题,例如杀boss过程中有10%的概率出物品A,20%的概率出物品B,30%的概率出物品C,40%的概率出物品D,我们应该如何下手呢?此时我脑子里最先想到的就是划分区间,然后丢色子.

• 方案一

我们首先划分出4个区间代表A,B,C,D四个物品的概率,即A[1,10],B[11,31],C[31,60],D[61,100],然后取一个[1,100]的随机数,该随即数落到哪个区间就是哪个物品.


Java

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

public class Interval {   private int id;   private int min;   private int max;   public boolean belong(int seed) { return seed >= min && seed <= max; }   // constructor setter getter toString ... }

Java

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

@Test public void testProbability() { final Interval a = new Interval(1, 1, 10); final Interval b = new Interval(2, 11, 31); final Interval c = new Interval(3, 31, 61); final Interval d = new Interval(4, 61, 100);   final List<Interval> list = new ArrayList<Interval>() {   { add(a); add(b); add(c); add(d); } };   Random rnd = new Random(); int seed = rnd.nextInt(100); if (seed == 0) { // 如果随机到0 则直接随机集合 System.out.println(list.get(rnd.nextInt(list.size()))); }   for (Interval interval : list) { if (interval.belong(seed)) { System.out.println(interval); } } }

这个方案最大的优点就是简单,容易理解,但它的缺点也是显而易见的,如果概率区间很多的话需要配置的工作量就比较大,那么我们有没有更好那容易扩展的方法呢,答案是肯定的.

• 方案二

我们还用上面的例子,同样的四个区间,首先我们设定一个索引值为0,然后取一个[1,100]的随机数,将索引值与随机数相加,然后再判断当前概率是否已经大于该值,如果大于,则该随机数就落在此区间,否则再用此值加上下一层的概率继续判断,直到结束.

Java

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

public class Probability extends HashMap<Integer, Integer> {   private final static Random RANDOM = new Random();   public Integer roll() { int rnd = RANDOM.nextInt(100); if (rnd == 0) { rnd = RANDOM.nextInt(this.size()); }   int value = 0; for (Map.Entry<Integer, Integer> entry : this.entrySet()) { value += entry.getValue(); if (rnd <= value) { return entry.getKey(); } }   return new ArrayList<Integer>(this.keySet()).get(rnd); }   }

Java

1 2 3 4 5 6 7 8 9 10 11 12

@Test public void testProbability() { Probability p = new Probability(); p.put(1, 10); p.put(2, 20); p.put(3, 30); p.put(4, 40);   System.out.println(p.roll()); }

这种方式较上一种理解起来就有点点难度,但实现上无明显差异,而且这种方式的扩展性更好,不需要定义很多概率区间.

总结

其实这两种概率实现各有优势,如果是做社交游戏或者休闲游戏对概率要求没有这么严,并且概率区间不会频繁更新,那么第一种方式更能快速实现,而第二种更适用于动态的概率配置,当然,这里的概率都不是绝对,如果想要做数值控制,那么还需要引入其它数值做校准,这已经不在本篇讨论范围内,大家还有更好的概率实现方式么?