Subscribe: C++博客-游戏人生-随笔分类-G游戏编程
http://www.cppblog.com/Fox/category/5794.html/rss
Added By: Feedage Forager Feedage Grade B rated
Language: Chinese simplified
Tags:
Rate this Feed
Rate this feedRate this feedRate this feedRate this feedRate this feed
Rate this feed 1 starRate this feed 2 starRate this feed 3 starRate this feed 4 starRate this feed 5 star

Comments (0)

Feed Details and Statistics Feed Statistics
Preview: C++博客-游戏人生-随笔分类-G游戏编程

C++博客-游戏人生-随笔分类-G游戏编程



游戏人生 != ( 人生 == 游戏 )



Published: Mon, 19 May 2008 13:56:21 GMT

Last Build Date: Mon, 19 May 2008 13:56:21 GMT

 



编程之美:一摞烙饼的排序(未完成)

Sun, 20 Apr 2008 06:59:00 GMT

Author: Fox 首先声明:本人没有解决掉这个问题。 相比第一道让CPU占用率曲线听你指挥对Windows系统中CPU占有率概念的考察和对API的使用,以及第二道中国象棋将帅问题对抽象建模的考察。这道题目才算是一道算法题吧?之前那两道尤其是中国象棋将帅问题总有点脑筋急转弯的味道。 题目:星期五的晚上,一帮同事在希格玛大厦附近的“硬盘酒吧”多喝了几杯。程序员多喝了几杯之后谈什么呢?自然是算法问题。有个同事说: “我以前在餐馆打工,顾客经常点非常多的烙饼。店里的饼大小不一,我习惯在到达顾客饭桌前,把一摞饼按照大小次序摆好——小的在上面,大的在下面。由于我一只手托着盘子,只好用另一只手,一次抓住最上面的几块饼,把它们上下颠倒个个儿,反复几次之后,这摞烙饼就排好序了。 我后来想,这实际上是个有趣的排序问题:假设有n块大小不一的烙饼,那最少要翻几次,才能达到最后大小有序的结果呢? 你能否写出一个程序,对于n块大小不一的烙饼,输出最优化的翻饼过程呢? 排序问题是数据结构和算法中比较重要的一个了,之前在一篇被同事成为标题党的文章中因为提到排序中关于(非)稳定排序的概念还被很多TX鄙视了一番,甚至引来人身攻击,现在想来都有些后怕。 这道题目一眼看上去最先让我想到的居然是那道经典的汉诺塔(Tower of Hanoi)问题(当然,汉诺塔不算排序问题)。 1) 相似点★: a. 都要不断调整位置,最终实现从小到大排好; b. 都要借助中间量进行调整。 2) 不同处★: a. 汉诺塔有多出来的两根针,翻烙饼只有一只手,明确说明没有第三只手; b. 汉诺塔一次只能移动一个,翻烙饼没限制; c. 汉诺塔要保证小的始终在上面,翻烙饼没限制; d. 汉诺塔移动之前就有序,所以其移动次数是固定的,算法的逻辑也固定(不管是递归还是栈操作),翻烙饼没有这个前提。 3) 把题目用程序语言描述一下吧★: a. Input : n. b. Process : generate n random number 0-(n-1), sortting. c. Output : 0, 1, ..., n-1, and move times num. 4) 存储结构★★★: 我最开始想到的是:这一摞烙饼其实就是一个双链表,每翻一次相当于将头节点H与某非头节点N进行如下变换: H->next = N->next N->prior = H->prior = NULL N->next->prior = H 如果使用普通的双链表,这儿就有一个很明显的问题,H和N之间的所有节点(如果有的话)的前趋prior和后继next互换了,对于n比较大的情况,这个操作明显浪费时间啊(交换前趋prior和后继next和题目要求的翻几次似乎也没有关系吧?只是我作为一个一线的Coder考虑的太具体了)。如果摒弃前趋和后继的概念,又该怎样描述呢? 唐朝禅宗大师青原行思曾说:参禅之初,看山是山,看水是水;禅有悟时,看山不是山,看水不是水;禅中彻悟,看山仍然山,看水仍然是水。 俗:日,扯那么多,什么意思? 师:前趋不是前趋,后继不是后继。 俗:日,前趋不是前趋,难道是后继吗? 师:然也。 Fox:O, my God!整点实际的吧!翻转一次之后,前趋视为后继,后继视为前趋,第奇数次翻转的前趋是后继,第偶数次翻转的后继是前趋。 整个链表的形态如下: H:Head, F:First, G:F's next, B:C's prior, C:Change, D, C's next, L:Last. H<==>F<==>G<=...=>B<==>C<==>D<=...=>L F与C交换的操作如下(Word、PS画图),n表示next,p表示prior: 这里只需要修改F、D节点的prior,H、C节点的next,其他节点不变。 后面想了一下,这种方式很难在不添加flag或者对换n、p的情况下正常操作,没有找到好的方法L,如果你[...]



如何产生随机数

Tue, 15 Apr 2008 06:01:00 GMT

Author: Fox

John von Neumann说:Any one who considers arithmetical methods of producing random digits is , of course, in a state of sin.

所以,在讨论算法实现随机数的时候,总是说“伪随机数”。

现在,应用最广的随机数生成算法是由Derrick Henry Lehmer1951年给出的线性同余法

              Xn+1 = ( aXn + c ) mod m,  n>=0.

上一篇伪随机数的论述中,并没有给出X0, a, c, m的取值规则,只是给出了ANSI CMicrosoft Visual C++的实现。

在这儿我们可以自己先思考一下,我们期望从上式中得到的随机数应该满足:

1) 上式的输出足够随机,这是最基本的要求;

2) 上式给出尽量多的输出,越接近m个越好(不可能超过m),即周期尽量长,最好为m,这样才能保证上式满足均匀分布m个数在周期m中各出现一次m个数出现的概率相等);

3) 上式的生成速度足够快。

最容易想到的,m的取值为计算机字大小(如2^32或2^64)

但是这儿有个很严重的问题:Xn低位的随机性很弱。原因如下:

令d|m, 且

              Yn = Xn mod d

              Yn+1 = ( ( aXn + c ) mod m ) mod d

                      = ( aYn + c ) mod d

上述表达式的意义即:Yn为Xn低k位(d=2^k),这样的Yn序列形成周期为d甚至更短的同余序列。举例说明:d为2^1时,Yn为Xn的最低位(可假定为1或0),若Yn+1 != Yn,则Yn+2 == Yn必定成立,仅当a、c皆为奇数时Yn、Yn+1将0、1交替,否则,为常数(0或1)。

暂时抛开随机性不管,先找到周期为m的随机序列中的取值规则。

Donald KnuthThe Art of Computer Programming, Volume 2: Seminumerical Algorithms中的3.2.1.2节对m, a, c和X0取值规则的表述:

1) gcd(c, m) = 1. 即c, m互素,再白一点,c, m除1之外没有其他公因子;

2) 任给质数p, p|m ==> p|(a-1). 即m%p==0,则(a-1)%p==0。

3) 4|m ==> 4|(a-1). 即m%4==0,则(a-1)%4==0。

这个证明过程对于我这样的数论基础不是很扎实的搞应用技术的人来说有点难以理解了。有兴趣的话,还是去看3.2.1.2的证明吧:-)。

上面的规则告诉我们,满足了上述规则后,可以保证序列周期为m。对于前面提到的关于随机性的问题,既然Xn低位的随机性比较弱,可以只取Xn的高位作为输出。高位的随机性和统计意义由a, c确定,其取值涉及统计检验,具体的也还是看3.3吧。

这篇文章解决了具有统计意义的随机数的部分理论问题。

PS: 之前曾经BS过Windows Live Writer,当时觉得Writer编辑功能太少,不能直接设定链接文字的字体颜色,知道CSS可以设定之后,又觉得Word 2007编辑的Blog转成html之后太大,而且也知道Word 2007上面是可以设置链接的target为_blank的。现在发现Writer还是很不错的了,原来是可以设定格式的,也可以直接编辑html,而且可以Web预览,链接还可以加入到链接词汇表,挺方便的。

越来越发现Wikipedia是个和Google一样的好东西!

(image)

Fox 2008-04-15 14:01 发表评论



网络游戏安全思考——伪随机数篇

Wed, 02 Apr 2008 18:35:00 GMT

Author: Fox 一、随机数 软件实现的随机数生成器(random number generator, RNG)生成的随机数列大多是惟定数列,因此一般被称作伪随机数(pseudorandom number, PRN),而基于热噪声(thermal noise)、光电效应(photoelectric effect)、放射性衰变(radioactive disintegration)等不可预知的物理现象实现的硬件随机数生成器(hardware random number generator)生成的随机数才被认为是真随机数(truly random number)。PRN在计算机领域主要用于仿真(simulation)和密码学(cryptography)。 本文仅讨论伪随机数软件实现算法,并且仅讨论满足均匀分布(uniform distribution, UD)的伪随机数发生器(pseudorandom number generator, PRNG)。非均匀分布(non-uniform distribution, NUD)的PRNG可通过满足均匀分布的PRNG与非线性函数生成。 本文讨论的PRNG应满足以下三点: a. 在取值空间内满足UD,即等概率取得取值空间内任意值。 b. 充分随机,即该随机数列周期(period)应尽量长。此点由所谓的熵(entropy)度量。 c. 唯一输入或称种子(seed)对应唯一输出PRN。这一点ms是计算机的强项,也是PRN惟定的根源,也是算法被破解的根源。 由于PRN sequence(PRNS)惟定,所以算法的安全性主要取决于熵的选择和算法的复杂性。 二、可预测PRNG与不可预测PRNG 所谓可预测(determined)PRNG,也被称为统计意义上的PRNG(statistic PRNG),一般只有一个seed,而对于同一个seed,生成的PRNS是惟定的。 不可预测(indetermined)PRNG,从理论上讲,不可预测的PRNG是不存在的,这儿指密码学安全的PRNG(cryptographically secure PRNG, CSPRNG)。 三、常用PRNGs 1、线性同余发生器(linear congruential generators, LCG) 单博伟在标准库rand()函数的缺陷以及Blitz++随机数生成的简介中给出了The C Programming Langurage 2nd的实现,我手头没有这本书,所以无从查证,FallHunter应该还有吧。  1 unsigned  int  next  =   1 ;  2  3 /**/ /*  rand: return pseudo-random integer on 0..32767  */  4 int  rand( void )  5 {  6  next  =  next  *   1103515245   +   12345 ;  7   return  (unsigned  int )(next / 65536 )  %   32768 ;  8 }  9 10 /**/ /*  srand: set seed for rand()  */ 11 void  srand(unsigned  int  seed) 12 { 13  next  =  seed; 14 } VS2003中给的实现是:  1 /**/ /* **  2 *rand.c - random number generator  3 *  4 *       Copyright (c) Microsoft Corporation. All rights reserved.  5 *  6 *Purpose:  7 *       defines rand(), srand() - random number generator  8 *  9 ****************************************************************************** */ 10 11 #include  < cruntime.h > 12 [...]



MMORPG网络模型剖析——网络连接实例分析

Thu, 27 Mar 2008 17:41:00 GMT

Author: Fox 在以前写 MMORPG中游戏世界的构建 时,提到服务器架构的分类。大多数情况下,每一种不同的服务器只会与其对应的一个服务器和多个客户端通信。比如,GameServer(GS)只会与WorldServer(WS)通信,也就是说GS只作为WS的客户端。这次,由于项目需求,新增加了一个SomeServer(SS)作为GS的服务器。 一、SS网络连接分析 由于需要和大量GS建立网络连接,所以SS使用了IOCP模型。鉴于 上一次写IOCP 时遭到 Kevin TX的鄙视,所以决定今天多写一点。SS的网络模型大致如下: 0、服务器主线程启动; 1、初始化Winsock,SDK func: WSAStartup (); 2、创建一个使用overlapped I/O的socket,SDK func: WSASocket(); 3、绑定端口,将本地地址与创建的socket关联起来,SDK func: bind(); 4、创建IOCP对象,SDK func: CreateIoCompletionPort(); 5、创建工作者线程,CreateWorkerThreads(); 6、开始监听,SDK func: listen(); 7、接受客户端连接,SDK func: WSAAccept(); 8、当有新的连接请求到达时,将WSAAccept返回的对应的客户端socket关联到IOCP; 9、处理WSASend() or WSARecv()。 在实际处理时,可能会根据需要建立额外的线程处理socketopt命令,甚至建立专门处理WSAccept的线程。 关于工作者线程WorkerThread: 通过GetQueuedCompletionStatus(),获取I/O类型和对应的socket,如果为接收则通知接收完成并继续新的WSARecv(),如果为发送则通知发送完成。 二、GS网络连接分析 GS上对于SS客户端采用的是WSAEventSelect模型,通过网络事件触发相应操作。 0、服务器主线程启动; 1、初始化Winsock,SDK func: WSAStartup (); 2、创建一个使用overlapped I/O的socket,SDK func: WSASocket(); 4、绑定端口,将本地地址与创建的socket关联起来,SDK func: bind(); 5、创建网络事件,SDK func: CreateEvent(); 6、设置网络事件的响应,SDK func: WSAEventSelect(); 7、等待网络事件,SDK func: WSAWaitForMultipleEvents(); 8、分析网络事件类型并处理,SDK func: WSAEnumNetworkEvents()。 这里之所以采用CreateEvent而不是WSACreateEvent,是因为由CreateEvent创建的事件允许为auto reset的,而WSACreateEvent创建的事件是manually reset的。 三、实现过程中的小插曲 在GS的客户端实现中遇到几个问题。 首先是在消息处理上,GS发到SS的消息,SS并没有完全接受到,而SS发送到GS的消息一切正常。后来跟了一下SS消息队列,发现SS居然可以收到GS发送到WS的消息!然后就在GS上找原因,原来是WS在和SS共用消息队列,以前GS只对应一个服务器,无所谓共用。现在加了SS,自然要分开处理,否则WS和SS都可能收到发给对方的消息。 后面一个bug从周一开始已经强奸了我四天了。即使SS已经关闭,WSAEnumNetworkEvents返回的事件对应FD_CONNECT的iErrorCode值始终为0。因为中间涉及到多线程和多个服务器分别对应的客户端,连接到WS的没有问题,就是SS的客户端有问题。到今天上午为止,我已经把GS的网络处理逻辑全部静态分析了一遍,没有任何发现。临近中午吃饭的时候,不得已只好用WS的客户端socket去连接SS,居然出现同样问题!而我的WS和SS都是放在我机器上的,这样来看,就只有端口不同了! 果然,当我把SS的监听端口[...]



不怕无知,但怕无畏

Thu, 20 Mar 2008 13:17:00 GMT

Author: Fox 昨天越俎代庖面试了一个家伙。 看完了他的笔试题目,感觉后背有点凉,但这些东西看看也就过去了,说实话,那些C++的题目多少有点BT。 但我一直觉得DS的东西,如果你当初学的时候是很认真学习过并思考过的,其实是不需要去记忆的,所以我就问了一个关于稳定排序和不稳定排序的问题。我想,只要你理解了各种排序算法的思想,很easy。 只是这哥们儿忘记了什么是稳定排序,我还以为他把快速排序、堆排序当作稳定排序只是没记住。看来,老师从小教育的"一道题目你即使不会也要尽量去答"这种思想遗毒颇深。如果抱着这种思想做程序员,公司多半要垮掉。 想一想稳定排序的概念吧:两个同值元素(不知为什么,我一直记得严老师书上用的是49,看来我还是在读死书、死读书,最后可能会读书死L)在排序前后相对位置保持不变,即本来在前面的还在前面(所谓"尘归尘,土归土",看来最近思想有点消极,难怪没有激情L)。再想想各种排序的思想,我们很容易得到这样的结论:最普通的O(n2)的算法,一个一个从前比到后,自然不会影响到同值元素的相对位置,而O(nlogn)的算法,由于多路比较,可能导致本来相对位于后面的元素先比较和移动,造成不稳定。这样一想,自然知道简单的插入、选择、归并排序都是稳定的,而改进的高效率的算法则不稳定。 后面另一个同事在询问他做的Demo的事情,因为是DX的东西,我不懂,没插嘴,就随便看他的简历。 看到其中一项,有提到他曾经给大一、大二的学生做过C++培训。我本没打算提他笔试中的C++部分的,但既然曾经为人师表(因为我曾经做过学生、也做过老师),C++基础掌握到这种程度就不对了。尤其对于一个空的C++类默认生成哪些成员函数居然写的一塌糊涂(友情提示:你也不用BS他,如果你没有看过Lippman的《Inside of the C++ Object Model》,建议你先不要发言J)。 我一般对语言特性不太敢发表观点(因为我的C++基础不扎实L),但我对简单的算法或思想小有兴趣(没有你想象中那么高)。可是,笔试中唯一的一个需要coding的题目他又没写。我只好说,C++的东西你掌握怎么样我也可以不看,但这个memcpy的实现,你怎么也得有点想法吧?不然怎么去写代码呢?刚好在面他之前,还和同事讨论过memcpy的问题(如果你给出one byte by one byte的实现会遭BS的J,因为你居然没有考虑过计算机系统本身的数据处理)。 本来还想问他一个关于sizeof()的问题,后来觉得也没什么必要,关于union的对齐,要按照单位最长的成员对齐这一点自己都觉得有点BT就算了。 其实,我想说的是,很多东西,你不能认为你掌握的很好(除非你真的掌握的很好),所谓很好,拿C++来说,就是把你认为你好的地方,你可以不翻其他东西,把它写下来,基本跟ISO C++保持90%以上的相似度就可以了。当然,这样说有点贱了。 毕竟,做游戏程序员(其他也差不多吧)需要的是: 带着激情去编码,带着虚心去学习,带着挑战去交流,带着压力去工作。 激情,能让你的思维满具创意,代码极其飘逸; 虚心,能让你的知识不断积累,从而达到厚积薄发; 挑战,能让你的团队充满活力,交流活泼严谨; 压力,能让你的心态保持平衡,胜不妄喜,败不惶馁。 因为自己这两周心态受到非智力因素干扰,日子过得有点浑噩。写下来,主要是为了放松一下,也提醒自己。 不怕无知,但怕无畏。 ---------[...]



MMORPG网络模型剖析——IOCP篇

Wed, 05 Mar 2008 17:18:00 GMT

Author: Fox //----------------------------------------------------------------------------------------------------- 夜深了,随便写写…… //----------------------------------------------------------------------------------------------------- 大凡学过编程语言和网络的TX应该都写过自己的聊天程序,那时候大家都知道了套接字怎么select、connect、bind、listen、accept、send、recv,也知道了TCP和UDP的区别……稍微用功的TX或许还写过多人聊天程序,知道了什么是阻塞I/O,真正致力于向QQ、MSN等即时聊天工具靠齐的大牛对本文提到的IOCP更是了然于胸。更多的TX或者有兴趣继续看下去。 一、阻塞I/O(主要指TCP) 1、当socket的recv buff为空时,进程会wait直到新数据到达; 2、当socket的send buff已满时,进程会wait直到空间足够; 3、当socket的accept没有新连接到达,进程会wait直到新连接到达; 4、当socket的connect没有收到ACK,进程会wait直到收到ACK。 而非阻塞I/O则是致力于提供高效的异步I/O。 二、IOCP(I/O Completion Port,I/O完成端口) IOCP是MS提供的Windows内核对象,内部使用线程池管理,并根据CPU的个数确定线程个数。当数据到达后,统一投递到唯一的IOCP队列,对应的若干工作线程用于处理这些数据,从而实现非阻塞异步I/O。 简单了解了IOCP的功能和原理,下面提供几点线索,供有兴趣的TX整理思绪J。 1、OVERLAPPED结构: 2、CreateIoCompletioPort:用于创建IOCP,关联连接来的socket句柄,用于接收数据; 3、GetQueuedCompletionStatus:供工作线程调用,取到数据的线程会加入I/O完成队列,IOCP的线程池管理这些工作线程。 三、深入学习和使用 1、Jeffrey Richter的《Advanced Windows》,第15章,谁看谁知道J; 2、Jim Beveridge & Robert Wiener的《Multithreading Applications in Win32》,第6章,谁看谁知道J; 3、Google。 //----------------------------------------------------------------------------------------------------- 感觉用Office 2007编辑和发布Blog比Live Writer要方便很多,主要是Live Writer的编辑功能太少了,如果2007能够对链接进行target设置,再支持EntryName就perfact了J。从新公司回来,还没有完全适应这边宽松的环境,这几天好似梦游一般,先是IE出问题,Ghost了一道,后面是Outlook收邮件出问题。还是夜深人静的时候,一个人燃着烟、听着歌、喝着茶、敲着键盘有感觉…… //----------------------------------------------------------------------------------------------------- Fox 2008-03-06 01:18 发表评论[...]



网络游戏安全思考——IPSec篇

Thu, 28 Feb 2008 12:54:00 GMT

Author: Fox

//-----------------------------------------------------------------------------------------------------
关于反外挂,这两天在和几位同事和网友讨论的结果依然是,更多的要从策划角度解决……
//-----------------------------------------------------------------------------------------------------

最近在考虑安全问题的时候,在《游戏编程精粹3》中看到Pete Isensee的《安全套接字》(即通常所说的Secure Socket Layer, SSL技术),又Google了一些IPSec的相关资料。尽管IPSec是部署在IP层的协议,但它还是可以为我们提供一些思路。

一、IPSec的认证安全(AH+ESP)

1、不可否认性:采用公钥加密的数字签名具有抗抵赖性。

2、防止报文重放:使用序列号和滑动窗口以保证数据包的唯一性,即使数据包被截获重发,也会因序列号的相同或者错误而被抛弃。

3、完整性:IPSec使用单独的鉴别头部(Authentication Header, AH)信息进行校验,防止报文篡改,校验的算法主要是MD5、SHA-1等单向哈希算法。

4、可靠性:通过加密封装安全有效载荷(Encapsulating Security Payload, ESP),IPSec对传输数据进行保护,加密算法除了MD5、SHA-1,还有加密块链接(Cipher Block Chaining, CBC)模式加密算法等。

二、IPSec的数据加密

在数据加密上,IPSec使用的主要是DES(Data Encryption Standard)和3DES(Triple Data Encryption Standard)算法。

三、IPSec的密钥管理

为了保证数据传输安全,IPSec使用由IKE(Internet Key Exchange)提供的动态密钥更新机制,Diffie-Hellman算法提供密钥生成策略,通信两端需要维持一个安全关联(Security Association),为两端通信指定认证及加密所用算法和密钥,并提供序列号和滑动窗口等。

需要注意的是,IPSec并没有提供数据产生到发送之前的保护机制。举例来说,就是IPSec可以在最大程度上保证你输入的帐号密码在传输过程中的安全,但并不能防止钓鱼软件和其他木马在你输入这些信息时被截获L,那应该是你要注意的。

对IPSec有兴趣的TX可以到http://www.ietf.org上下载相关的RFC文档研究研究J

//-----------------------------------------------------------------------------------------------------
本以为手上工作完成,可以偷时间看看安全方面的东西,不曾想Joe又分下了新任务L……
//-----------------------------------------------------------------------------------------------------

(image)

Fox 2008-02-28 20:54 发表评论



网络游戏安全思考——反外挂篇

Tue, 26 Feb 2008 08:04:00 GMT

Author: Fox

//-----------------------------------------------------------------------------------------------------
此篇仅是对反脱机外挂的一点思考,其他安全问题如登录验证、消息验证等更多的是涉及逻辑功能。
//-----------------------------------------------------------------------------------------------------

春节刚回来的时候,回公司去和Soft聊到了自己的毕业论文的问题,因为专业的关系,我必须给出一些安全方面的考虑,正是因为这一点,我当时开题时就立足对安全的无缝游戏世界进行思考。只是在游戏本身的安全性上,一直也没有一个好的出发点,这两周还是在考虑这个问题。

这一点,有我入行时间不长,对于游戏本身、玩家与开发者(含游戏及外挂、木马开发者)之间的关系并没有一个很好的把握,更多的是由于我对游戏中的可用的安全技术不了解,尤其是对应用层安全协议不了解,对破解技术也不了解,导致无所适从。

《游戏编程精粹1》中Andrew Kirmse在《在线游戏的网络协议》一文中对常见的篡改报文、报文重放和逆向工程有讲述。预防报文篡改的有效防御是哈希校验,现在大多游戏是使用MD5算法,而且网上开源的MD5代码也很多。对于报文重放,Andrew提到了使用线性叠加随机数的状态机,具体原理和实现方式因为没有提到太详细,还要针对实际应用继续学习L。然而,由于客户端既是报文的接收者也是发送者,因此,客户端包括了完整的加解密算法。一旦客户端被逆向,上述措施就变成了破解者背后的烟雾弹,完全失去意义。

提到反外挂,Joe的看法也是说这个东西和具体某一个技术关系不大,还是要从机制上去看。加不加密对于普通玩家没有意义,对于专业从事逆向的人更是也没有意义,所有单纯考虑加密是没有效果的。对于免费游戏,外挂往往是打钱公司的工具,你封他的号,他再建就是了,代价几乎为0,而一般付费游戏(像魔兽世界)一个帐号对应一个CDKey,一个CDKey就要几十块钱,这个封起来就有点咬牙了。

说到这里,不妨换个思路:为免费游戏加入CDKey。我一款游戏从内测、封测到公测,让玩家充分参与体验,在被逆向且外挂横行之前,按正常逻辑运营。进而假定我这一款游戏在公测之后,让玩家感觉魅力十足。引导玩家并实施CDKey,一个CDKey大约会需要玩家付出些许Money以示诚意,在玩家游戏过程中,会阶段性向玩家赠送部分增值道具。老玩家在进入新区时,需要申请继续使用原CDKey。这样一来,外挂就不会肆无忌惮了。

BTW,这个思路没有从技术角度解决问题,下面再来看一种略微关乎技术实现的解决方案:动态验证。在游戏运行期间,会不定期的向玩家发送验证码,客户端在收到消息后,必须在一定时间内响应,向服务器确认收到的验证码,否则将被强制下线,再次登录后将更加频繁的收到验证码,直到用其良好的回复次数累积消除其不良记录为止。为了尽量减少因此给玩家造成的不友好体验,在任务场景、重要PK场景或者高等级玩家活动场景,验证码的发送和确认可适当放宽

当然,如果外挂中加入了图形识别,这一招也未必奏效。

不知是道高还是魔高,可以肯定的一点是:大家都是在利益的驱动下绞尽脑汁。

//-----------------------------------------------------------------------------------------------------
春节回来之后,一直比较忙(确切的说是比较懒),没有更新,宜更加勤奋。
最近工作涉及到数据库编程,一点点对数据库的读写居然耗掉我3天时间,汗!
//-----------------------------------------------------------------------------------------------------

(image)

Fox 2008-02-26 16:04 发表评论



异步回调的一种封装——续

Fri, 25 Jan 2008 03:27:00 GMT

Author: Fox

终于赶在周末之前调通了,现在来总结一下我这个项目中对于异步回调的应用背景。

这个项目的内容就是在游戏中使用第三方库为所有玩家提供更好的服务,当server启动后,加载dll,初始化该模块,当server退出时,结束模块功能,卸载dll。

当玩家提出请求后,server在main thread中通过lib转发玩家请求,lib处理完毕,在其独立thread中回调server为其实现的callback function。此时,server需要将返回的result转到main thread中对result及其相关的玩家数据进行处理。

第三方库的需求是很明确的,在合适的地方发送请求,在合适的地方处理响应。

Joe对我的要求也是很明确的,响应处理时采用server当前架构(这个架构在上一篇文中有提到),使我的编码不涉及任何游戏功能逻辑处理,并使整个处理流程细节对后续应用开发透明。

二者结合起来,就为这个项目融入整个server的架构提供了完美的需求,也为我的编码提供了最小限度的选择空间:(,好处是后续功能开发可以完全无视我的编码,只需实现对回调响应后的功能,只有server底层知悉如何调用。

给出序列图:

 

(image)

为了保持对上层开发透明,OnCallback需要封装。

//-------------------------------------------------------------------------------
// 一年来,我主要参与了两款游戏,确切的说是半年,前面半年并没有真正涉及运营产品的开发,只是做工具。
// 现在这个模块是我做的最快,也是压力最大的一个。现在想来,原因在于此模块涉及到游戏主逻辑底层和
// 第三方动态链接库的通信及处理。
// 在短短几天的时间内让你的设计满足第三方库的应用需求并符合游戏自身底层逻辑的设计风格,的确有些痛苦,
// 好在有Joe的指点,让我在完成工作的同时又学到了一些方法:)。
//-------------------------------------------------------------------------------

(image)

Fox 2008-01-25 11:27 发表评论



异步回调的一种封装

Wed, 23 Jan 2008 03:04:00 GMT

Author: Fox 前段时间写过一篇关于线程安全的文字,有TX觉得不深入。因为本来就没想写的太具体,只是随便说说,今天就想说点具体的技术。 //-------------------------------------------------------------------------------// 动态链接库 (Dynamic Link Library) 1) 动态链接; 2) 跨语言; 3) Win32平台可用;  1 //  静态链接库.h文件中对函数的声明:  2 // dllExam.h  3 extern "C" void /*__stdcall*/ Func( int  nParam );  4   5 //  动态链接库.h文件中对函数的声明:  6 // dllExam.h  7 extern "C" void __declspec( dllexport ) /*__stdcall*/ Func( int  nParam );  8   9 // 动态链接库的静态调用: 10 #pragma comment(lib,"dllExam.lib" )  11 extern "C" __declspec(dllimport) /*__stdcall*/ Func( int  nParam ); 12  13 dllFun(0 ); 14  15 //  动态链接库的动态调用: 16 // useDllExam.cpp 17 typedef void(/*__stdcall*/ *CallFun )( int );    // 宏定义,方便使用 18  19 HINSTANCE hDll;                        // DLL句柄 20 CallFun dllFun;                        // 库函数指针 21 hDll = LoadLibrary( "dllExam.dll"  ); 22 if ( hDll ) 23  { 24     dllFun = (CallFun)GetProcAddress(hDll, "Func" ); 25     if  ( dllFun ) 26      { 27         dllFun(0 ); 28      } 29      FreeLibrary(hDll); 30 } 动态链接库的一般应用都在这儿了,更加具体的就要去问google了:)。 //-------------------------------------------------------------------------------// 异步回调 ( Asynchronism Callback ) 今天想说的主要内容是异步回调。大致结构是: //-------------------------------------------------------------------------------//                           IAsyncCaller  IAsyncCallback//                                         \    /// CManager --> CSession --> CEvent//-------------------------------------------------------------------------------// class :  CManager// function : Singleton实现,管理所有CSession对象 // class :  CSession// function : 处理会话,关联事务 // class :  CEvent// function : Session的关联对象,处理异步回调// base class: IAsyncCaller, IAsyncCallback 在发起session的时候,new一个CSession对象,为其分配一[...]



门窥多线程安全

Wed, 09 Jan 2008 20:02:00 GMT

Author: Fox

一、多线程安全的引入:

关于什么是多线程、为什么使用多线程的问题,大家可以看看Jim Beveridge & Robert Wiener的《Win32多线程程序设计》(侯捷 译),或者其他随便一本提到多线程的书或文章。这里只是提到Windows环境下多线程容易引发的问题和解决办法。

1、线程在时间片结束时退出做不到

由于Windows属于分时操作系统,系统会为每个线程分配响应的时间片使其工作,绝大多数线程不可能在时间片结束的时候完成其工作,而下一个时间片就有可能分配给其他线程。

2、线程独立做不到

如果线程间不存在依赖关系,即线程A的执行不依赖于线程B的执行,此时即使线程B被打断,由于线程独立,所以二者也可以相安无事。

然而,在多线程解决方案中,线程间的通信是频繁而且必要的。线程通信主要有两种情况:

1) 多个线程共享相同资源;

2) 一个线程的执行依赖于其他线程的结果或执行情况。

这时,我们就需要实现共享资源及线程执行的同步。

二、多线程安全的解决方案:

因此,多线程安全的目标就是实现共享资源的互斥访问和线程执行的同步通信。

通过对操作系统的学习,我们知道线程同步主要有以下方法:

1) 临界段(Critical Section)

a) 临界资源的取舍,宜少不宜多,宜短不宜长,一个线程只能最多等待一个临界段;

b) 无法侦测一个临界段是否已经被放弃;

c) 临界段属于用户对象。

2) 互斥锁(Mutex)

同临界段一样,互斥锁也主要用于保证资源的原子访问,二者的不同之处在于:

a) 互斥锁属于可具名内核对象;

b) 互斥锁可以跨进程使用,临界段只能用于同一进程内;

c) 互斥锁可以指定等待时间,而且可以等待其他内核对象。

3) 事件(Event)

a) 事件重置具有人工重置和自动重置两种方式,简单说来,二者分别用于多读和单写;

b) 事件主要用于线程间相互通知(唤醒);

C) 事件属于可具名内核对象。

4) 信号量(Semaphore)

a) 信号量属于可具名内核对象;

b) 信号量没有拥有者,可被任一线程释放;

关于Win32中这四种对象的使用和要点,更详细的介绍可以参照《Win32多线程程序设计》或《Windows核心编程》(Jeffrey Richter)等。

三、多线程安全的实现:

将对数据(对象、模型、消息、Socket)的I/O处理放在同一个I/O线程中,保证如队列的push/pop操作、链表的insert/delete操作、文件的write操作、socket的recv/send操作、全局变量的write操作等的互斥访问。

新建独立模块,尤其是使用第三方库的独立模块,大多会创建独立的新线程。此时就需要对新线程中的数据操作加以注意,可以通过对操作数据的加锁访问解决同步问题,当然,更常见的处理方式是将新线程中的数据操作发送到专门的I/O线程中处理。

总之,多线程安全是个常说常新的话题,现在有人提出Lock-Free数据结构的解决方案(Maged M. Michael),也有所谓的Wait-Free的解决方案(Maurice Herlihy),而国内网游界的大牛云风同学更是提出了单线程多进程的观点和解决方案(因为不了解,按字面有可能存在断章取义之嫌)。但不管怎么样,从中至少可以看出,多线程,说来话长。

零零散散、东拉西扯、不知所云的讲了一些东西,未必正确,更不能当作知识。全当是对上次的承诺有个交代。

/*****************************************************************************
 想把多线程的问题搞明白,不是说看看操作系统教材,写点多线程读写的代码就够的。且不论孰是孰非,
 单就网上诸多高手新学对加锁策略铺天盖地的争执说辞甚至相互批判指责,足可见多线程开发并非只言
 片语即可挑明。
 为防止陷入细节争论,这里先作声明:小文仅就所学略抒拙见,无意引起争端……
*****************************************************************************/

(image)

Fox 2008-01-10 04:02 发表评论



调整思路——2008年继续努力

Tue, 01 Jan 2008 18:43:00 GMT

Author: Fox

元旦放假3天,本来想把前面写的一个存在线程安全隐患的模块推倒重来的,可是改着改着就觉得不对劲了。

既然是返工,就想尽量把现在的理解完全加进去,让后面的人看了不要骂。可是想把几千行的代码改得面目全非并且更加安全准确也并不是一件容易的事,虽然对于功能和逻辑的认识比以前要清晰的多。

拿到一个新的模块,上面一般会给个大致的deadline。除非你对这个模块和整个项目的依赖关系(接口、逻辑、功能)有很好的把握,否则,你根本不知道到底有多少东西是已经实现的,有多少东西是可以复用的,有多少东西是需要修改的,有多少东西是要重写的,有多少东西是要新加的,仅仅根据需求预估的进度是不可能恰到好处的。而脱离了整个项目实现的模块是非常可能出问题的,尤其是在使用多线程的项目中。

当我的这个模块完成并上马之后,我沾沾自喜的跟上面说,应该是不会有问题了,上面跟我说了一句:如果不出问题就是奇迹了,我当时颇不以为然。在后面一两周之内真的就是没有什么问题,我真想告诉他是我创造了奇迹。

“奇迹”在2007年的最后一周破灭了。在我从西岭雪山回来的那天,为了增加新功能把代码修改了一些,结果第二天更新之后,服务器就老是有问题,找了一下午,才发现在修改代码的时候居然忘记对一个pointer做NULL判定!我心想,这种错误居然都出来了!死了算了!而且这个问题出在非主线程中。然后就和同事在考虑,这个东西如果线程同步出现问题,你就是每次使用前都做NULL判定也没用,所以就决定把这个模块重写了。

在这儿我就不想就线程安全问题多说了,以后想好了再专门去写点多线程的东西吧,今天只是想说点琐碎的东西。

因为是放假,心思未必就全部放在上面了,代码没改多少,倒是玩了很长时间的游戏。后来想想,也不全是时间问题,几千行的代码改来改去,难保不出现更多的问题。必须把它当作一个新的模块去写,先要把逻辑结构完全理出来,能多细化就多细化,最好能够精确到变量的使用,而且把文档做细,这样就可以在写文档的过程中把问题尽可能想全想清楚。改代码先改文档,这几乎是所有学过软件工程并写过项目的同学都能认识并理解的常识,可是在实际工作中,上有任务催赶,下有闲心杂念,很难把文档和注释写好。而做不到这一点的话,你就不敢保证你的模块不出差错。

所以,对于一个一般的需求,如果deadline是2个月的话。读需求、评估依赖关系、量进度要花掉1周,画逻辑结构、写文档要花掉3周,相当于前面一半的时间没有动手写代码,然后写代码大概只用1周,甚至更少,其他时间就留给测试和修改文档、代码了。从软件工程的角度,这样的分配是合理的,而且是应该的,但到了实际项目里面,又做不到!看来,不管是manager,还是coder,都不能急,软件工程不能白学了。

我发现,我的软件工程就是白学了,以后得改改。

/*****************************************************************************
 不想回头去动以前的代码,每次看以前写过的东西,都有一种想把它彻底删除的冲动。
 把需求看好、文档写好、时间安排好,这才是硬道理……

 毕竟是新年,还是祝大家:新年快乐!
 重要的是,新的一年,别荒废了……
*****************************************************************************/

(image)

Fox 2008-01-02 02:43 发表评论



也说说级数求和(1+2+3...N)和其他

Fri, 21 Dec 2007 02:19:00 GMT

Author: Fox 对于(1+2+...+N) 的求和,最早就是看高斯的故事,而且说实话,我是没有这样的智商的:                 sum(1+2+...+N) = N*(N+1)/2 刚看了一篇研究该级数求和的文章,虽为调侃,但实在感觉文中纰漏太多,不禁在此多言。 文中的第一种方法自称标准,而且还能使“全班2/3的同学都用俺的标准应付老师和试卷”,我大为惊诧: 1 int i, sum = 0 ; 2 for(i = 1;i < N;i ++)sum +=  i; 3 printf("1-N的级数和是: %i",sum); 显然,printf的结果是N-1个数的和,此处,我更愿意相信是文中的笔误而已。 第二种和第三种方法让人觉得奇怪: 1 float  sum; 2 sum = (N ^ 2) / 2 + N / 2 ; 3 printf("1-N的级数和是: %i",(int )sum); 4  5 float  sum; 6 sum = N * (N / 2 + 0.5 ); 7 printf("1-N的级数和是: %i",(int)sum); 前面的写法纯属恶搞,^在C/C++中是异或位操作,相信接触过位运算的人都知道这一点,而且当N为奇数时,sum的结果将比真实值少1。后面的写法更是荒唐,当N为奇数时,sum的结果将比真实值相去更远(有兴趣的可以仔细看看)。 对于后面两种写法,我想说的重点不是这些明显的错误,因为这样的错误只可博众君一笑。但文中定义sum使用float的做法,让我百思不得其解。对于计算机的运算,浮点运算的耗时和整型运算的耗时,那不是一个数量级的。对于该级数运算,我们完全可以避免浮点运算,而且方法在文章一开始,就已经给出了: 1 int  sum; 2 sum = N*(N+1)/2 ; 3 printf("1-N的级数和是: %i", sum); 无论N为奇数还是偶数,N*(N+1)一定是偶数,因此,上述方法不存在浮点运算,而且系统会自动将/2的操作优化为右移1位。 不知怎么,忽然就想到了递归,想到了Fibonacci数列。讲递归的教材都会拿上面的级数求和和Fibonacci数列做例子。其实,我个人感觉这是不恰当的,但想想为了让学生掌握递归算法,也只能举类似的简单的例子。我们也知道,递归计算对于堆栈调用是非常频繁而耗时的,对于求Hanoi塔这样的复杂问题,我不知道不用递归有没有更好的方法,但如果计算Fibonacci数列还是使用递归,在初学递归时是可以原谅的。简单点的方法可以是这样:  1 int fib_odd = 0, fib_even = 1  ;  2 int n = (N+1)/2 ;  3 for(int i=0; i



反外挂的一点牢骚

Wed, 19 Dec 2007 18:08:00 GMT

Author: Fox

俗话说,道高一尺,魔高一丈。

今天在一个群里,有人提到某某算法(3DES)可以杜绝外挂。我当时心里苦笑一声:哥们儿,太逗了。这年头,中国人已经被忽悠怕了。我信鬼信魔,就是不信佛……

不过想想,如果能在一定程度上打击外挂,也不错,可是讨论了半天,愣是没有给出具体的方案,最后还是不了了之。

不过,有时间把思路整理整理,提一个稍微好一点的方法也好。

王城里面,一排排的外挂小号像阅兵一样,嚣张成马了,完全不把我们放在眼里。

话说回来,连个脱机外挂都防不住,别人还确实没必要把你放在眼里。

这边Login Server搞了两三个月的验证码,感觉不错,因为不使用外挂的玩家每次都要折腾半天,我们自己人员输入验证码输的都烦,结果没出半个月外挂又开始横行了,感觉比以前还嚣张。

我是外挂,我得意的笑,我得意的笑……

敢情是防贼没防住,把贼扔屋里,自己被锁在外面了!

/*****************************************************************************
  晚上本来想自己写个内挂,可以偷偷懒,可惜对这东西实在是从来没有过研究。
  折腾了一晚上,郁郁而终。
  技不如人啊!想来都觉得可笑……
*****************************************************************************/

(image)

Fox 2007-12-20 02:08 发表评论



游戏脚本变量存取优化

Mon, 17 Dec 2007 11:55:00 GMT

Author: Fox

在MMORPG中,存在大量的数据文件和脚本文件,这些文件涉及很多变量,当玩家信息需要存取时(上线、下线、保存、服务器交互),即伴随着大量的读写操作。随着游戏中游戏任务的增加,每一个玩家对应的需要数据库存取的脚本变量的数据量也随之线性增长,随着玩家数量的增加,在服务器保存玩家角色信息的时候,通信量的大小是相当可观的,使用多线程读写,可以使服务器的处理能力大幅增强,但网络和数据库承受的压力也会大幅增加。

当然现在有很多的脚本语言为我们设计任务系统提供了便利,像Lua、Python、Ruby这些动态语言的功能越来越强,而且可以肯定的是,会有越来越多的产品采用这些优秀的语言。但我今天要谈的不是如何使用动态语言,也不是讨论动态语言孰优孰劣的问题,而是对于大量的脚本变量的存取优化。说白了,这对于使用自定义脚本语言的游戏开发人员才更有参考价值。而且我要说的问题很小,小到我只是讲一点点内容,只是我今天下午的一点活,总结下来更多只是为了让自己记住,并不是教育别人。

假设在整个脚本系统中,存在500个与玩家相关而且需要数据库存取的脚本变量,如果一个游戏世界中拥有3000个在线玩家,平均每个玩家的脚本变量大小为10KB,如果服务器同时保存这3000个玩家的数据(那可不仅仅是脚本变量,当然脚本变量所占的分量比较大就是了),3000×10KB,哦……与此同时,服务器还要进行其实正常的网络通信和逻辑处理(虽然不可能是同一个线程),但服务器承受的压力已经不小了吧,为了减少这种压力,脚本变量成为了一种稀缺资源。
为了对脚本变量的存取进行优化,我想到了一个最容易实现的方法。通过对数据库的观察(其实想也想也想得到:)),我发现玩家数据中大量的脚本变量的值都是0或者空字符串,这就为优化提供了很大的一个空间。

服务器一般都保存有一个脚本变量的配置文件,在这个文件中列出了所有的脚本变量及其默认值。当玩家登录时,服务器将为其依据这个文件为其建立一份拷贝,并从数据库读取这些变量的真实值填充之。因为大量的变量值都是默认值,所以在往数据库保存的时候,是没有必要全部保存的,而只需保存那些不同于默认值的变量名和变量值以及该变量对应的下标即可。下一次从数据库读入的时候根据下标确定哪些变量值需要从数据库中读取就可以了。

很简单的一个操作,虽然做到了这一点优化,但是对于500个变量的线性读取和其他操作,依然不是一个好的处理方法。

几点改进的方向,目前只是有个想法:

1、将玩家与其脚本变量解耦

并不是所有的玩家都需要500个脚本变量的,不同等级的玩家可以参与的任务和活动是完全不同的,我们显然没有必要为每一个玩家从生到死都保持这500个变量。这样考虑下来,估计一个玩家的脚本变量数可以减少300-400个,从而实现了“垃圾”回收再利用。OMG!

想法是非常具有诱惑力的,但这一优化同时涉及到脚本策划和程序,而且稍有不慎(对某一变量重复使用),全盘皆输,在“稳定压倒一切”的大方针下,这样的优化需要给出一个系统的策略,玩家等级、职业因素的影响都要考虑进去。

2、对玩家脚本变量实现压缩存储

未经压缩的脚本变量,每个大概有几十Bytes,如果采用一个好的压缩算法,能不能减少到10Bytes呢?什么又是一个好的压缩算法呢?压缩解压缩的成本和直接存取成本比起来哪个更高呢?想想这些的确也都是问题呢。

/*****************************************************************************
  这只是我工作中的一个总结,问题很简单,也很琐碎,正如我前面所提的,仅仅是提供一个参考。
*****************************************************************************/

(image)

Fox 2007-12-17 19:55 发表评论



MMORPG中游戏世界的构建

Sat, 15 Dec 2007 21:24:00 GMT

Author: Fox一个MMORPG(Massively Multiplayer Online Role Playing Game)的架构包含客户端和服务器两部分。客户端主要涉及计算机图形学、物理学、多媒体技术等,服务器主要涉及网络通信技术、数据库技术,而人工智能、操作系统等计算机基础学科知识的应用体现在MMORPG开发过程中的方方面面。 一、游戏世界的划分 理想状态的游戏世界仅由一个完整的场景组成,在《魔兽争霸 III 》、《 CS 》这样的单机游戏中,所有玩家位于该场景中,在理论上,位于该场景中的任意玩家都可以看到游戏中所有玩家并与之交互,出于公平性和游戏性(而不是技术上)的考虑,游戏中并不会这样做。 然而,目前的 MMORPG 中,几乎没有任何一款可以做到整个游戏世界只包含一个场景,因为在一款 MMORPG 中,同时在线的玩家数量成百上千,甚至是数万人同时在一个游戏世界中交互。以现在的网络技术和计算机系统,还无法为这么多玩家的交互提供即时处理。因此, MMORPG 的游戏世界被划分为大小不等、数量众多的场景,游戏服务器对于这些场景的处理分为分区和无缝两种。 在分区式服务器中,一个场景中的玩家无法看到另一个场景中的玩家,当玩家从一个场景到另外一个场景跨越时,都有一个数据转移和加载的过程(尤其是从一个分区服务器跨越到另外一个服务器时),玩家都有一个等待的时间,在这段时间内,服务器的主要工作是实现跨越玩家数据的转移和加载以及后一个场景中玩家、 NPC 等数据的传输,客户端的主要工作是实现新场景资源的加载和服务器通信。主要时间的长短主要取决于后一个场景中资源数据的大小。分区式服务器的优点主要是各分区服务器保持相对独立,缺点是游戏空间不够大,而且,一旦某个分区服务器中止服务,位于该服务器上的所有玩家将失去连接。 所谓无缝服务器,玩家几乎察觉不到场景之间的这种切换,在场景间没有物理上的屏障,对于玩家而言,众多场景构成了一个巨大的游戏世界。场景之间,甚至服务器之间“没有了”明确的界线。因此,无缝服务器为玩家提供了更大的游戏空间和更友好的交互,实现了动态边界的无缝服务器甚至可以在某个服务器中止服务时,按一定策略将负载动态分散到其他服务器。因此,无缝服务器在技术上要比分区服务器更加复杂。 目前国内上市的 MMORPG ,大多采用分区式服务器,做到无缝世界的主要有《完美世界》和《天下贰》等,国外的 MMORPG 中,像《魔兽世界》、《 EVE 》等,都实现了无缝世界。 无缝服务器与分区式服务器在技术上的主要区别是,当位于场景 S1 中的玩家 P1 处于两个(甚至更多)场景 S1 、 S2 的边界区域内时,要保证 P1 能够看到场景 S2 中建筑、玩家、 NPC 等可感知对象。而且边界区域的大小要大于等于 P1 可感知的范围,否则就可能发生 S2 中的可感知对象突然闪现在 P1 视野中的异常。 无疑,无缝世界为玩家提供了更人性化和更具魅力的用户体验。 二、无缝世[...]