« June 2008 | Main | August 2008 »

July 27, 2008

把 AOI 的部分独立出来

应该是在 blog 上第 2 次讨论 AOI 的问题了,另外还要算上一篇写完没有公开的。

昨天刚出差回来,晚上跟前大唐的服务器主程聊了一下。扯到了 AOI 的问题,我提了个分离这个模块的方案,在此记录一下。

AOI 主要有两个作用,一个是在服务器上的角色(玩家或 NPC )做出动作时,把消息广播到游戏地理上附近的玩家。当进程中负责的玩家不是很多的时候,可以直接对整个进程内的连接广播。这样的处理最简单,随着硬件的提高,可能是未来的主流方法。但是目前,为了减少处理的数据量,尤其是带宽,我们通常需要 AOI 模块裁减一些数据。

第二,当玩家接近 NPC 时,一旦进入 NPC 的警戒区域,AOI 模块将给 NPC 发送消息通知,以适合做一些 AI 的反应。

AOI 的实现算法很多,这里不展开来谈。我目前关心的是,如果 AOI 在游戏中非常重要(尤其对于即时战斗模式的大场景 MMO )能否把这个模块抽离到独立进程中。

首先我们来看第一个需求。其实在游戏中,需要广播的消息大多次序不敏感。比如移动,是 A 先移动还是 B 先移动并不重要;又比如攻击,是先攻击再移动,还是先移动再攻击也不重要。我指的先后是指 client 接收次序。攻击是否启动虽然跟距离有关,但是发出攻击指令前,服务器逻辑已经校验过合法性。也就是说,服务器发过来的信息都是合法的,client 就不用太在意位置改变在攻击前还是攻击后了。

那么,我们把 AOI 广播的这个职责拆分到独立进程做,就不需要跟逻辑进程协调发包的次序。这是个好消息。

设计一个 AOI 进程,让逻辑进程在任何一个对象改变位置时发一个包通知 AOI 进程,这样等于复制一份对象位置状态在 AOI 进程中。以后,当对象需要广播它的状态变化,只需要把需要广播的消息发到 AOI 进程里,然后由 AOI 进程过滤一下(筛出附近的对象,做一个组播)。

需要注意的是,由于消息都是异步发生。我们在 client 接收对象 id 时,应该过滤掉一些过期的 id 号。因为有可能逻辑服务器已经删除了某对象,但是 AOI 服务器迟一些发送了跟这个对象相关的消息。(把对象删除的消息交给 AOI 服务器转发是一个糟糕的想法,因为这增加了 AOI 服务器的职责,增加了复杂度)

对于 AOI 消息通知的问题,可以让 AOI 服务器在检测到对象侵入别人的警戒区时,向逻辑服务器发会一条消息。这个消息不需要实时反应。比如,策划要求一个 NPC 有 20 米的警戒区,其实不必在玩家刚好 20 米的边界上触发,稍微延迟半秒是无所谓的。而且警戒区越大,允许的延迟时间就越长。

单独的 AOI 服务,可以根据警戒区的半径,进行优先级排序。然后有条不紊的通知消息一个个发回。

对比单独的 AOI 模块,独立 AOI 进程有更低的耦合度。通过协议耦合而不是接口耦合。更容易维护和日后的优化。没有和逻辑部分的共享状态,减少了 bug 滋生的可能。


ps. 最近跟新同事讲了一节课。其实没讲太多技术上的东西。只是介绍了游戏行业,以及计算机行业的硬件发展历程,以及游戏的进化,还有一点点软件开发上的进步。

我想,一切的历史都在见证,只有把东西设计的足够简洁,才能够顺利的向前发展。如果不够简洁,有一天我们会抛弃它们,或者为之付出代价。希望可以给刚从学习毕业的同学们一些启示。

前天开会前抽空读了一小时新运营的大唐二的服务器代码。追查出一个隐藏很深的 bug 。据说这个项目刚对外开放的这几天情况不太好,老是当机。程序员应该明白,其实也不一定是很多 bug ,但是一个就够你受。

大唐 2 的服务器写的挺“精巧”,C++ 和 lua 之间绕来绕去的,差点没把我绕晕。太复杂了……

July 21, 2008

KISS

Keep it simple , stupid .

stupid 不是愚蠢的愚,而是大智若愚的愚。有时候,我们写程序做设计就是不够智慧,就只有点聪明。觉得自己可以把复杂的问题用巧妙的方法解决。这个巧妙的方法,保正了效率,节约的内存。真可谓聪明。

但聪明不是智慧,真正的智慧是看到将来。在不断的演化中它们还能不能保持这个巧妙。如果不那么巧妙,我们到底会损失些什么,我们真正需要什么,而失去的那些换来的到底是什么。

simple 也不是为了避免麻烦。保持 simple 比解决麻烦要麻烦的多。


最近老有人跟我说啥 2.5D 3D 什么的,有点反感这个词。纯属不懂瞎参合。当然我也知道名词就是用来区分不同事物的,不能强求。

人就是奇怪,明明不相信数学可以解释这个世界,偏偏又喜欢拿数值去套所有的概念。一切都是一维数轴上的点。不是多一点,就是少一点。

我决定改天也造个新词儿出来。

嗯,我们不做 3d 游戏,多俗。2.5D ? 太土了。我们是 2.71828 D 。哦,记不住没关系,反正也没做完,暂时称为 2.7D 吧。

July 20, 2008

一个简单的寻路算法

周末跟同事聊天,问了一下最近公司新项目的一些需求。发现现在无论是玩家还是策划,纷纷要求引擎可以实现自动寻路。虽然我对此不以为然,但其实这也不是什么难题,打算随便做一个好了。

我们现在的 engine 是用矢量线段描述场景中的障碍的。这些线段无所谓人工标记还是从场景模型中自动生成出来,又或者是用传统的打格子的方法变换出来。在这些障碍线构成的矢量场景中寻路其实不是什么难事。

我们只需要在场景中标记出若干 waypoint ,这些 waypoint 一般在大片无障碍区域的中央,以及分叉路口。游戏中故意设计迷宫为难玩家绕来绕去又没有什么玩点内容在里面是没有什么意义的。(除非是“不可思议的迷宫”这种以迷宫为重要玩法的游戏)所以,大多数游戏场景,路径的拓扑关系复杂度非常有限。 waypoint 靠人工设置就足够了。

btw, 自动生成 waypoint 也不是难事,反正这个东西不会是性能要点,机器生成 waypoint 不会比人工设置的糟糕太多。算法就不展开谈了。waypoint 的设置要点是:场景中所有可达区域都能看到至少一个 waypoint ,这个要求可以用程序检测。

我们把所有 waypoint 间可以直线连接的线路连起来,得到一张图。可以预存下这张图,以后的工作则非常简单。

每次需要得到场景中任意两点间的路径,就从起始点和目标点各取一个临近可见的 waypoint 。之后求这两个 waypoint 间在图上的最短路径。Dijkstra 算法即可。

得到路径后,角色在场景中行走时,间隙的判断是否可以直接看到路径上的下一个 waypoint ,只要可以看到,就沿直线方向朝路径上最远可见的 waypoint 移动。最终可以得到一条较为自然的运动轨迹。

嗯,没啥高深的算法,随便写写就能实现了吧。


最近在公司附近的一个小区会所办了张健身年卡。几年没动了,体力和力量都下降了不少。关键是平时精神不太好,感觉没前几年有活力。是应该每天流点汗,吃好睡好,这样脑子更好使。

已经坚持去了三次了,重量大了会有点头晕,得控制一下。刚开始恢复,浑身肌肉酸痛。昨天做了几组深蹲,今天走路都有点痛。不过这几天居然有了不小的食欲。白切牛肉可以吃一大盘,冰箱里的鸡蛋一扫而光。是个好兆头。

July 14, 2008

周末

这个周末尽力的离开办公室,离开网络,离开计算机。

今年第一次逛超市(似乎去年也没去过),买了点吃的。离开零食很久了,都不知道没什么好。

看了一场电影,当然不是《赤壁》。因为听说很雷,我怕被雷到了。所以我选择了《功夫熊猫》。

去剪了头发,很久没去理发了,开叉的许多,修理了一番,不过没换发型。当然我从来就没换过。

想约人吃饭,但这好象很不容易,想必周末大家都有安排吧。

开车去玩桌游,一路上很顺利,居然都是绿灯。这次尝试了几个新游戏。《电力大亨》不错,设计的很精巧,规则也不复杂。不过另一个《吸血鬼》,让我啃了一个半小时的规则书硬是没弄明白。本来想尝试一下另一个二战的游戏。老板说,还是等下次吧。早上过来,估计到吃夜宵的时候可以完成一局的。

我想我会试试,就冲着那满地图的塑料小兵人了。

一个放松的周末。

谢谢。

July 10, 2008

闲扯几句

最近事情比较杂,所以没心情写 blog 。

travian 玩了一年多,终于快结束了。奇迹修好就解脱了。这个游戏教了我许多设计思路,并展示了一些问题,需要好好盘点一下。

这两天有人问我,为啥我玩了二十多年电脑,眼睛就不近视呢?这个问题好多人问过了,我也想过好几次,终于有了个结论。就是因为我从小玩电脑,所以才没近视的。

道理其实很简单啊。这么多年,坐在电脑前,干的最多的事情是写程序。这当然不同于大多数非程序员的电脑使用者。非程序员用电脑,需要眼睛需要专注的看屏幕,是屏幕对人体的信息输入。而写程序是个相反的过程,是人体对计算机输入,基本是在用脑而不是用眼。眼睛自然没那么疲劳啦。而正是从小到大坐在显示器前,电视也没怎么看。当然比那些小时候泡在电视前的小孩子们把眼睛保养的好啦。

同事做的天下2又一次开始试玩期了,据说从玩家数字和收入情况上看还可以。虽然比前一个版本更泡菜,但是这也是大众口味了。大众口味被骂是正常的。不是现在的玩家越来越喜欢快餐式游戏,而是玩家群体扩大了。我相信作为个体的玩家是会有越来越高的游戏追求的,但群体则不然。

前两天跟人聊天,说大街上美女身边几乎都不是帅哥,所以长的丑更容易找个美女当老婆。我说,这是青蛙们用来安慰自己的。学过点概率的同学稍微想一下就能明白,帅哥配不到美女,不是因为美女倾向于找青蛙,也不是帅哥喜欢恐龙。根本原因是因为帅哥美女在人群中出现的比例太小了。

长的漂亮,找到相貌出众的配偶的概率一定比普通人高,这是生物学规律。但是概率比别人高,不等于这件事发生的概率就高。

假设一个美女有 100 个追求者,其中一个是帅哥,另外 99 个是青蛙。即使帅哥追到美女的概率比他的竞争者高 10 倍,那么他成功的概率也不过 9% 而已。所以美女最后选择的更有可能不是他了。

其实我想说的是,无论做什么有竞争性质的事情,提高自己的竞争力是可以加大相对于别的竞争者胜利的概率。但并不一定保证你能成功。好比买彩票,你花一万块下注,比花 10 块钱下注的人更容易中奖。但是事实是,往往出现只花 10 块钱的就中了大奖的人。这绝对不能说明,花 10 块钱下注的人比花一万块的人更有优势。而只能说明,花点小钱玩彩票的人比倾家荡产买彩票的人多的多;或者说明买彩票的人大多数都是穷人。

如果你尽力了却失败了,不用太怨天尤人,抱怨 RP 不好,老天不公。其实这个世界的物理法则是公平的,只是你没理解公平的规则而已。


说起公平,看到天下2 里做了个很可笑的开宝箱的设定。可以先让玩家看一眼宝箱里有些什么,然后转轮盘。通常箱子里有很多垃圾,也有一些好东西。游戏还允许玩家自己事先调整一下那些东西的位置再转。我还没问开发组是不是在程序里作弊,但是据玩家说,宝箱里一般大约有 50% 的垃圾物品,但是转轮盘转到垃圾的概率是远远大于 50% 的。

我想这个设计应该就是个幌子了。这种东西也就骗骗小学生吧。想想也是,宝箱以 50% 概率开出好东西,这个概率的确也太高了。我们是不是应该想个更好的点子来让玩家的感觉上的概率和实际的一致?

这让我想起密码学里的一个交换信息的学问了。就是我先把信息交给你,但是你不能看,事后大家在核对。保证双方都没有作弊。

密码学里这样的策略有很多,不过不太好解释给玩家。以众多玩家的小学数学水平(非贬义,根实际统计数据,现在网游玩家中低学历人群比例相当的大)很难理解并自行校验。

我想了个法子,让玩家信任服务器没有作弊。

当玩家转轮盘之前,系统先把结果产生出来,并随机发给一个玩家。并告诉这个转轮盘的这个人,结果提前发给了谁。玩家需要在一秒内下注,然后得到结果。

事后,玩家可以向那个事先得到结果的玩家确认系统是否作弊。

这个过程的时间很短,短到不可能针对性的询问特定玩家结果就够了。再加上系统信息都加上时间,可以方便事后核查。

当然这只是一个草案,实际想做的话,需要完善许多。比如加入竞争关系,阻止提前收到信息的人广告结构等等。就不展开讨论了。

别的方案也有许多,比如由服务器发一个 100 位的整数,问玩家这个数字模 7 等于几。如果限制时间回答,假设玩家没有外挂帮他计算的话,也能起到同样效果。(因为以人脑的计算能力,不可能在很短的时间内得到答案,只能考猜)

我们还可以综合以上两个方案,玩家在转轮盘之前,把这个 100 位整数发给随机一个玩家。并告诉转轮盘者发给了谁。并允许他们事后相互验证。这样,靠一个人做外挂作弊得到答案也就几乎不可能了。