用JavaScript玩转游戏编程(一)掉宝类型概率

标签: javascript 游戏编程 类型 | 发表时间:2010-04-21 06:50 | 作者:Milo Yip vento
出处:http://www.cnblogs.com/miloyip/

问题定义

游戏(和一些模拟程序)经常需要使用随机数,去应付不同的游戏(或商业)逻辑。本文分析一个常见问题:有N类物件,设第i类物件的出现概率为P(X=i),如何产生这样的随机变量X?

例如对概率的要求是

P(X=0)=0.12
P(X=1)=0.4
P(X=2)=0.4
P(X=3)=0.07
P(X=4)=0.01

输入数组<0.12, 0.4, 0.4, 0.07, 0.01> 输出符合以上概率的随机数序列,如<1, 4, 2, 1, 2, 2, 1, 0, ...> 。

以下先谈一些统计学背景知识,再给这问题的可行解法。

概率分布

这问题要产生一个随机变量,接近指定的概率分布(probability distribution)。大部份程序语言都提供接近均匀分布(uniformly distributed)的伪随机数产生器(pseudorandom number generator, PRNG),例如JavaScript提供的Math.random()函数,可传回 [0, 1)半开区间的均匀分布伪随机数。

密度分布函数

现在,不仿测试一下JavaScript的Math.random()函数,看看它是否均匀分布。一个变数的分布以密度分布函数(probability density function, PDF)定义,一般写作f_X(x),随机变量X在区间[a,b]上的概率为定积分:

P(a\leq x\leq b)=\int_{a}^{b} f_X(x)dx

为了把PDF视觉化,可以把X分为若干区间,统计各区间X出现的频率,绘画其直方图(histogram)。笔者写了一个简单的JavaScript框架,用HTML5 Canvas绘画直方图。以下测试代码,可绘画Math.random()的PDF估值(estimate)。

function step() { var x = Math.random(); var bin = Math.floor(x * frequency.length); frequency[bin]++; sampleCount++; plotPdf(frequency, sampleCount, 1/frequency.length, "Estimated pdf of Math.random (n=" + sampleCount + ")"); } var frequency = new Array(10); var sampleCount = 0; for (var i = 0; i < frequency.length; i++) frequency[i] = 0; start("canvas1", step);
Run Stop

在统计学中,每个数据称为取样(sample),当取样数目n越大,可以看到其PDF估值越接近平均。

读者可以试试,把x的赋值改为Math.pow(Math.random(), 2)。你会发现,PDF的分布改变了,其密度更集中于左边。读者也可以改为其他表达式(只要其输出在[0, 1)的范围),看看其分布。如果想看精确一点,也可以加大frequency数组。

累积分布函数

密度分布函数,可以变换为累积分布函数(cumulative distribution function, CDF),代表随机变量X小于x的概率:

F_X(x)=P(X\leq x)

在X为连续(continuous)的情况下,CDF可用PDF定义:

F_X(x)=\int_{-\infty }^{x}f_X(t)dt

在X为离散(discrete)的情况下,CDF可定义为:

F_X(x)=\sum_{x_i\leq x}{P(X=x_i)}

以下的pdf2cdf()函数,能把离散的PDF数组,转换为CDF数组。由于浮点小数相加会有误差,最后的值可能少于1,有机会产生bug,函数里强制指定最后一个元素为1。

function pdf2cdf(pdf) {
    var cdf = pdf.slice();
    
    for (var i = 1; i < cdf.length - 1; i++)
        cdf[i] += cdf[i - 1];

    // Force set last cdf to 1, preventing floating-point summing error in the loop.
    cdf[cdf.length - 1] = 1;
    
    return cdf;
}

以下代码测试绘画Math.random()的CDF估值(只把plotPdf改了為plotCdf):

function step() { var x = Math.random(); var bin = Math.floor(x * frequency.length); frequency[bin]++; sampleCount++; plotCdf(frequency, sampleCount, "Estimated cdf of Math.random (n=" + sampleCount + ")"); } var frequency = new Array(10); var sampleCount = 0; for (var i = 0; i < frequency.length; i++) frequency[i] = 0; start("canvas2", step);
Run Stop

均匀分布的Math.random(),其CDF估值接近斜线。

题解

这问题其实正式来说,可称为模拟离散取样(simulated discrete sampling),跟据有限类别的指定概率,来模拟取样。

要制造指定的概率分布随机变量,关键就是如何把均匀分布变换。

逆变换取样

在上节中,显示了CDF的一些特性,例如CDF的范围是[0,1],而且是一个单调递增(monotonic increasing)函数。逆变换取样(inverse transform sampling)利用了这些特性,去解决这个问题。逆变换取样方法其实很简单,给一个目标CDF,只要计算其逆函数(inverse function),就可以把均匀的随机变数转换为目标CDF:

X=F_X^{-1}(Y)

这方法能用在所有CDF(包括连续及离散的)。其数学证明可参考维基百科

下图显示这个方法的直观解读,在Y轴[0,1]范围里均匀取样(y_i),之后向右和CDF取交点,求交点的X轴位置(x_i),X则是符合CDF的概率分布。

这个方法用在离散的情况就更简单,只需搜寻目标的CDF,找出超过均匀取样的元素即可。代码如下:

function discreteSampling(cdf) {
    var y = Math.random();
    for (var x in cdf)
        if (y < cdf[x])
            return x;
            
    return -1; // should never runs here, assuming last element in cdf is 1
}

题目的测试:

var targetPdf = [0.12, 0.4, 0.4, 0.07, 0.01]; var targetCdf = pdf2cdf(targetPdf); function step() { var bin = discreteSampling(targetCdf); frequency[bin]++; sampleCount++; plotPdf(frequency, sampleCount, 0.4, "Estimated cdf of discreteSampling (n=" + sampleCount + ")"); } var frequency = new Array(targetCdf.length); var sampleCount = 0; for (var i = 0; i < frequency.length; i++) frequency[i] = 0; start("canvas3", step);
Run Stop

分析

在离散的情况下(本文题目要求),其时间复杂度是O(N),其中N为类别数目。

读者可能会注意到,这里用了线性搜寻(linear search),如果targetPdf数组是由大至小排列,平均而言会更快找到结果。另外,也可以用二分搜寻(binary search),那么复杂度会降低为O(lg N),这留给读者作为练习。

事实上,这个问题用二分搜寻是标准的方法。那么,还有没有更快的方法呢?答案是肯定的,例如别名方法(alias method)、近似方法等,有兴趣的读者可参考[1]。当然,在N很小的情况下,线性搜寻和二分搜寻也足够。

结语

笔者以前的著作也简单提及过这个问题,不过本文加入理论背景,希望读者能更深入了解。这个问题在游戏中经常使用,例如按设计概率产生怪物、宝物,或是用来控制非玩家角色(non-playable character, NPC)的行为。模拟取样亦使用在计算机图形学上,例如粒子系统,或是采用蒙地卡罗积分法(Monte Carlo integration)的渲染算法。后者大概会在不可预计的将来,于另一系列里探讨。

笔者撰写本文,灵感来自这篇博文。其算法实际上是储存CDF的逆函数取样,利用空间和有限的CDF精确度,换取O(1)的时间复杂度。衡量N的大小、精确度、空间需求、缓存延迟后,或许该方法也能适合某些个别需求。但对于该文作者说N最大为100,二分搜寻只需最多7次迭代,因缓存问题可能二分搜寻更快。有鉴于该文未详细讨论这些需求分析、背后理论、以至代码可能对一些网友来说比较难理解,希望本文能加以补充。

这系列会探讨一些游戏编程相关的问题,例如随机相关(PRNG、洗牌、其他随机取样方法)、游戏机制相关(状态机、细包自动机)等等。网友们也可以提供一些题目,大家互相讨论学习。

本文的JavaScript完整程序可在此下载

参考

更新

  • 2010-04-21 感谢livepine,修正问题定义中,数组最后一个值。
  • 2010-04-26 修正下载连结

作者: Milo Yip 发表于 2010-04-21 14:50 原文链接

评论: 12 查看评论 发表评论


最新新闻:
· Donews:搜狗输入法6.0发布 宣布开放皮肤平台(2011-06-14 15:16)
· 诺基亚与苹果达成专利和解 苹果将支付专利费用(2011-06-14 15:15)
· 赚小钱,才能赚大钱(2011-06-14 15:11)
· 魏武挥:不靠谱的效应(2011-06-14 15:02)
· RMS称私有软件让用户变得无助(2011-06-14 14:52)

编辑推荐:自己动手开发编译器(五)miniSharp语言的词法分析器

网站导航:博客园首页  我的园子  新闻  闪存  小组  博问  知识库

相关 [javascript 游戏编程 类型] 推荐:

用JavaScript玩转游戏编程(一)掉宝类型概率

- vento - 博客园-Milo的游戏开发
游戏(和一些模拟程序)经常需要使用随机数,去应付不同的游戏(或商业)逻辑. 本文分析一个常见问题:有N类物件,设第i类物件的出现概率为P(X=i),如何产生这样的随机变量X. 输入数组<0.12, 0.4, 0.4, 0.07, 0.01> 输出符合以上概率的随机数序列,如<1, 4, 2, 1, 2, 2, 1, 0, ...>.

JavaScript类型总览(图)

- Lionheart - aimingoo的专栏
这个图来自于《JavaScript语言精髓与编程实践》第三章P184页. 最近在改第二版,这张图重做了,需要的可以对照着看. 关注这个体系的朋友可以参考如下:. 再谈JavaScript的数据类型问题. 三谈类型问题:ECMAScript为什么错了. 此外,补充一下图中用到的概念:. 1、内置(Build-in)对象与原生(Naitve)对象的区别在于:前者总是在引擎初始化阶段就被创建好的对象,是后者的一个子集;而后者包括了一些在运行过程中动态创建的对象.

再谈JavaScript的数据类型问题

- 茄 - aimingoo的专栏
 JavaScript的数据类型问题已经讨论过很多次了,但许多人还有许多书仍然沿用着错误的、混乱的一些观点,所以就再细讲一回. 提及这个讨论的原因在于argb同学在我的MSN博客(现在变成了wordproess,在这里)上的一段回复,又更早的起源则是两年前关于《JavaScript征途》一书的大讨论:.

Firefox 9中加入类型推断 JavaScript性能将提高20%到30%

- fid - cnBeta.COM
据外媒报道,在历时长达18个月的努力之后,Mozilla终于成功为Firefox的Javascript引擎增加了一个重大的新特性,根据初步测试,至少可以提高20%到30%的Javascript性能. 这个新的特性就是在Firefox的JaegerMonkey JIT编译器中加入的类型推断(Type Inference),它将随同Firefox 9一起提供测试.

Firefox 9将为Javascript加入类型推断,预计性能将提高20%到30%

- Vingel - HTML5研究小组
据外媒报道,在历时长达18个月的努力之后,Mozilla终于成功为Firefox的Javascript引擎增加了一个重大的新特性,根据初步 测试,至少可以提高20%到30%的Javascript性能. 这个新的特性就是在Firefox的JaegerMonkey JIT编译器中加入的类型推断(Type Inference),它将随同Firefox 9一起提供测试.

Javascript诞生记

- Milido - 阮一峰的网络日志
二周前,我谈了一点Javascript的历史. 今天把这部分补全,从历史的角度,说明Javascript到底是如何设计出来的. 只有了解这段历史,才能明白Javascript为什么是现在的样子. 我依据的资料,主要是Brendan Eich的自述. "1994年,网景公司(Netscape)发布了Navigator浏览器0.9版.

JavaScript,你懂的

- dylan - keakon的涂鸦馆
经常有人问我,JavaScript应该怎么学. 先学基本语法,如果曾学过C等语言,应该1小时内就能掌握了. 再去使用内置的函数、方法和DOM API,熟悉它能干什么;而在学习DOM API的过程中,你还不得不与HTML和CSS打交道. 然后弄懂匿名函数和闭包,学会至少一个常用的JavaScript库(例如jQuery).

Javascript 里跑Linux

- rockmaple - Shellex&#39;s Blog
牛逼到暴的大拿 Fabrice Bellard,用Javascript实现了一个x86 PC 模拟器,然后成功在这个模拟器里面跑Linux(请用Firefox 4 / Google Chrome 11打开,Chome 12有BUG). 关于这个东西… 伊说 “I did it for fun“,大大啊大大啊….

高效 JavaScript

- xtps - ITeye论坛最新讨论
传统上,网页中不会有大量的脚本,至少脚本很少会影响网页的性能. 但随着网页越来越像 Web 应用程序,脚本的效率对网页性能影响越来越大. 而且使用 Web 技术开发的应用程序现在越来越多,因此提高脚本的性能变得很重要. 对于桌面应用程序,通常使用编译器将源代码转换为二进制程序. 编译器可以花费大量时间优化最终二进制程序的效率.

你得学JavaScript

- 蒋冰 - 伯乐在线 -博客
  注:本文由 敏捷翻译 - 蒋少雄 翻译自 Kenny Meyers 的博文.   如果三年前你问我应该学什么语言,我会告诉你是Ruby.   如果你现在想学一门语言的话,你应该学习JavaScript..   我认为,每一位Web开发人员都应该学习JavaScript. 目前推出的许多新技术都支持这个观点.