最近用纯C作了一个dict,根据试验,比 stl的 map快 2.3-2.5倍,比 hash_map快 1.3倍,主要用到的优化策略如下:
因为希望将图片转换成字符以后可以方便的帖到论坛或者BBS上,所以画时间写了这个算法。现有很多算法都是将一个点匹配成一个字符,这样转换工作只是简单的将点亮度查表后换成ASCII字符而已,但是其实这样做的效果并不十分好,首先80×25的字符屏幕就只能表示80×25个点,无法充分发挥单个字符的字形特点,而且图片很多精度和细节都丢失了。比如下面这个连接:
1. 比尔·云风刚出生便会说话,邻居描述,刚落地时他就向东南方向走了七步,每走一步地上就出现一个“@”符号,只见他七步之后,伸左手指天,伸右手指地,开口说道:“2D/3D唯我独尊”。。。。
2. 《徐庶走马荐比尔,刘玄德三顾茅庐》:徐庶:“主公不必难过,五步之内必有芳草,远来的和尚,未必念得了真经,蜀国如要上市,庶愿保举一人”,刘备:“知道是你好朋友诸葛孔明,这人人品不行,我面试过。他要我联伊抗美,与基地组织共出奇兵占领NASDAQ机房,奉股市而令不臣,控制所有上市公司。靠!备乃仁义之团队,向来讲求信誉,强调共赢,怎忍心做此等伤天害理之事”,徐庶:“是是是,主公是讲求信誉,力主双赢的仁义团队,但是我要推荐的另有其人”, “哦,应届生?现在何处?开口多少?”,“这人复姓比尔,双名云风,家住荆州长沙郡,现在幽州雪碧九游戏当差。”,备:“哦,没听过”,庶:“这位好汉十八般语言门门精通,上能构架操作系统;下能设计嵌入芯片!”,备:“有这种怪人?”,庶:“不当如此,比尔·云风左手提一百二十斤混铁鼠标,右手抱三百五十斤工学键盘,竞争对手虽有千军万马,近不得他办公桌前一步!三十六小时持续编码依旧气定神闲,体力耐力无人能及。”,刘备:“赞!是块加班的好料,想起来了,水镜先生也向我推荐过,说他‘手握设计无数种,胸中代码千万行’,备若得此一人,何患《汉室》30万在线!他在雪碧九拿多少?”徐庶:“XXX”,刘备:“大伯如何?”徐庶:“至少再多500元”,刘备:“恩,只要他证明他的能力,再多600都不在乎,我们向来尊重人才,QQ,MSN,MAIL统统给我”,徐庶:“听说他最近ADSL欠费,手机停机,就连email都发不出去,主公要见,恐怕只有亲自前往”,刘备:“如此说来,备当前往看看”。。。。
(未完,待续)
游戏设计需要基础性理论,Richard A. Bartle,第一款MUD(被称为MUD1)的开发者,该文章起于1990年,经作者多次整理而成。在游戏设计“难有统一理论”的情况下,该文论点受到了决大多数开发者的一致接受和好评。可见基础性理论不但有利于我们的分析与设计,更重要的是大家能在同一层面上用同样的术语进行更有效的沟通:
http://www.skywind.me/resource/hcdsc.htm
最近在阅读 XBOX360 Live方面的文档,作为其中提及的一个重要概念“Bartle’s player type”的论文,似乎影响了整个第四代Live的设计,恰巧最近我也在整理一些Live相关资料,就顺带将这个基础理论进行了翻译。
Achievements and Gamerscore: Best Practices
—- By Jeff Sullivan, Developer Relations Manager, Microsoft Game Technology Group
— 翻译(参与先后):skywind,cjx,ltt,fanlix,jericho
http://www.skywind.me/blog/archives/346
1. 参考游戏 vs 参考生活:
以前人做游戏,参考的是生活;现在人做游戏,参考的是游戏。前者作出来的游戏属于创新,后者作出来的游戏最多属于“综合+改良”,这还是比较好的了,最差的情况还有抄袭的嫌疑,感觉作者设计出来的内容宏大而没有主题,似乎只是个“游戏大杂烩”是个把自己记忆中好玩的游戏全部杂凑在一起的“六十四合一”。
艺术的本源来自于生活,不管电影、文学、还是游戏,这点在我玩ndsl游戏时候特别有感触,最近国外出了个很火的游戏InkLink–画图猜词,就有点象我们年会上的游戏,一个人描述一个人猜成语,只不过该游戏用画画的方式进行,界面就像一个带聊天框的画板,万家轮流在上面用图画描述系统给他的单词,然后所有玩家根据他正在画的内容猜,越快猜出来的得分越高。这个游戏不大,但是的确让人眼前一亮的感觉。
2. 电影选材 vs 游戏选材:
前段时间王朔跳出来还说:“只写自己经历过的事情”,刘欢在回答自己为什么很长时间不出专辑以及评价现在流行音乐不成熟的时候说:“成熟的行业,绝不做前人做过的事情”。参考电影和音乐我们可以简单的画出一个发展脉络:
创新阶段 -> 改良阶段(商业化阶段) -> 抄袭阶段(泛滥阶段) -> 枯竭阶段
目前游戏选材是第二到第三阶段的过度,而电影选材早在95年就出现了选材枯竭现象,但是经历了10年的沉淀与反思,相信下一个电影创作高峰不会太远,而游戏也会象电影一样,过几年将进入一个题材休眠期。
3. 创新 vs 改良:
之前读到姚壮宪一篇文章,文中主张不要轻提“创新”因为游戏历史已经有三十多年,“今后大部分制作都是一边看着前人的游戏,一边想着自己的设计”“人類既是依賴習慣的動物,也是追求新鮮感的動物”认为“综合+改良”是上乘功夫,若只是混合属于一般功夫,“若学其形而无其实,乃摸象之流”。。。
姚壮宪这个话放在《仙剑奇侠》的单机游戏时代,是很正确的,当时创新太多,意再规劝人们“改良”,而放在现在改良期已经进入尾声再来说这个话的时候,便会适得其反,因为现在的人太习惯改良了,再劝说他们改良,只能禁锢思想,因为习惯改良的成功就代表害怕新的设计。
4. 现代题材 vs 古典题材:
国内那批六十年代电影学院毕业的第四代导演们被评价位“中国电影创作的主力军”,那我们的游戏设计者究竟还要经过几代,才能迎来一个崭新的全盛时期?
问题之一是古典游戏题材泛滥了,为什么古典题材会放浪呢?抛开审批问题,因为做古典题材相对容易,太多东西可以参考了,几大名著,二十六史,各类神怪传说全部是现成的;而相对来讲作现实题材确难的多,因为游戏设计者的思路会受到文学和电影发展束缚,不是需不需要避讳的问题,而是没有现成资料需要游戏设计者自己挖掘的问题。
5. 五千年的文化成为包袱:
帧锁定算法解决游戏同步
早期 RTS,XBOX360 LIVE 游戏常用同步策略是什么?格斗游戏多人联机如何保证流畅性和一致性?如何才能像单机游戏一样编写网游?敬请观看《帧锁定同步算法》
《帧锁定同步算法》转载请注明出处:https://skywind.me/blog/archives/131
算法概念
该算法普遍要求网速 RTT 要在 100ms 以内,一般人数不超过 8 人,在这样的情况下,可以像单机游戏一样编写网络游戏。所有客户端任意时刻逻辑都是统一的,缺点是一个人卡机,所有人等待。
1.客户端定时(比如每五帧)上传控制信息。
2.服务器收到所有控制信息后广播给所有客户。
3.客户端用服务器发来的更新消息中的控制信息进行游戏。
4.如果客户端进行到下一个关键帧(5帧后)时没有收到服务器的更新消息则等待。
5.如果客户端进行到下一个关键帧时已经接收到了服务器的更新消息,则将上面的数据用于游戏,并采集当前鼠标键盘输入发送给服务器,同时继续进行下去。
6.服务端采集到所有数据后再次发送下一个关键帧更新消息。
这个等待关键帧更新数据的过程称为“帧锁定”
应用案例:大部分 RTS 游戏,街霸II(xbox360),Callus 模拟器。
算法流程
客户端逻辑:
服务端逻辑:
1.收集所有客户端本关键帧 K1 的 CTRL 数据(Ctrl-K)等待知道收集完成所有的 CTRL-K。
2.根据所有 CTRL-K,计算下一个关键帧 K2 的 Update,计算再下一个关键帧的编号 K3。
3.将 Update 发送给所有客户端
4.令 K1=K2
5.跳转(1)
服务器根据所有客户端的最大 RTT,平滑计算下一个关键帧的编号,让延迟根据网络情况自动调整。
算法演示
我根据该算法将街机模拟器修改出了一个可用于多人对战的版本,早期有一个叫做 kaillera 的东西,可以帮助模拟器实现多人联机,但是并没有作帧锁定,只是简单将键盘消息进行收集广播而已,后来 Capcom 在 PSP 和 360 上都出过街霸的联网版本,但是联网效果不理想。这个算法其实局域网有细就经常使用了,只是近年来公网速度提高,很容易找到 RTT<50ms 的服务器,因此根据上述算法,在平均 RTT=100ms(操作灵敏度 1/10 秒),情况下,保证自动计算关键帧适应各种网络条件后,就能够像编写单机游戏一样开发网游,而不需状态上作复杂的位置/状态同步。
从上图的演示中可以看到,两个模拟器进程都在运行1941这个游戏,两边客户端使用了该算法,将逻辑统一在一个整体中。
最后这张图是运行KOF99的效果图,两边完美同步。
乐观帧锁定
针对传统严格帧锁定算法中网速慢会卡到网速快的问题,实践中线上动作游戏通常用 “定时不等待” 的乐观方式再每次 Interval 时钟发生时固定将操作广播给所有用户,不依赖具体每个玩家是否有操作更新:
单个用户当前键盘上下左右攻击跳跃是否按下用一个 32 位整数描述,服务端描述一局游戏中最多 8 玩家的键盘操作为:int player_keyboards[8];
服务端每秒钟 20-50 次向所有客户端发送更新消息(包含所有客户端的操作和递增的帧号):
update=(FrameID,player_keyboards)
客户端就像播放游戏录像一样不停的播放这些包含每帧所有玩家操作的 update消息。
客户端如果没有 update 数据了,就必须等待,直到有新的数据到来。
客户端如果一下子收到很多连续的 update,则快进播放。
客户端只有按键按下或者放开,就会发送消息给服务端(而不是到每帧开始才采集键盘),消息只包含一个整数。服务端收到以后,改写 player_keyboards
————-
虽然网速慢的玩家网络一卡,可能就被网速快的玩家给秒了(其他游戏也差不多)。但是网速慢的玩家不会卡到快的玩家,只会感觉自己操作延迟而已。另一个侧面来说,土豪的网宿一般比较快,我们要照顾。
随机数需要服务端提前将种子发给各个客户端,各个客户端算逻辑时用该种子生成随机数,另外该例子以键盘操作为例,实际可以以更高级的操作为例,比如 “正走向A点”,“正在攻击” 等。该方法目前也成功的被应用到了若干实时动作游戏中。
指令缓存
针对高级别的抽象指令(非前后可以覆盖的键盘操作),比如即时战略游戏中,各种高级操作指令,在 “乐观帧锁定” 中,客户端任何操作都是可靠消息发送到服务端,服务端缓存在对应玩家的指令队列里面,然后定时向所有人广播所有队列里面的历史操作,广播完成后清空队列,等待新的指令上传。客户端收到后按顺序执行这些指令,为了保证公平性,客户端可以先执轮询行每个用户的第一条指令,执行完以后弹出队列,再进入下一轮,直到没有任何指令。这样在即时战略游戏中,选择 250ms 一个同步帧,每秒四次,已经足够了。如果做的好还可以象 AOE 一样根据网速调整,比如网速快的时候,进化为每秒 10 帧,网速慢时退化成每秒 4 帧,2 帧之类的。
————–
PS:可以把整段战斗过程的操作和随机数种子记录下来,不但可以当录像播放,还可以交给另外一台服务端延迟验算,还可以交给其他空闲的客户端验算,将验算结果的 hash值进行比较,如果相同则认可,如果不通则记录或者处理,服务端如果根据游戏当前进程加入一些临时事件(比如天上掉下一个宝箱),可以在广播的时候附带。
(完)
周末读了一下Py2Exe的代码,偶然发现Py2Exe的实现,是一套很成熟的客户端发布方式,不限于只有
Python项目可以参考,Py2exe启动步奏如下:
Py2exe启动步奏方式参考:
1. 主程序启动,尝试在本EXE的资源中找到zip过后的PythonXX.dll的数据
2. 如果找到 PythonXX.dll数据则unzip后以memory dll方式加载并导出接口
3. 初始化 memoryimporter,给python提供在内存中import一个pyc或者dll的功能
4. 利用memoryimporter加载_ctypes.pyd模块
5. 利用py2exe_util.c中的方法,加载程序所需要的资源:ICON等
6. 在资源中初始化 zlib.pyd等必要模块
7. 在资源中找到初始化,以”__main__”的命名开始转入Python脚本