【原创】快速除以255的方法

经过若干次试验修改,研究出下面这个快速/255的宏,可以在 X属于[0,65536]的范围内误差为零:

#define div_255_fast(x)    (((x) + (((x) + 257) >> 8)) >> 8)

传统来说,人们习惯于将 /255改为 >> 8,但是这样误差挺大的,比如先乘以255再除以255,连续做十次,如果用>>8来代替除法,那么十次之后,误差为10. 另外一种常见的近似法是((x) + 255) >> 8,这种累积误差也挺厉害的。 因此>>8代替/255结果是比较粗糙的。而这个宏的开销比起>>8来说成本大12%。 经过测试65536000次计算中,使用/255的时间是325ms, 使用div_255_fast的时间是70ms,使用>>8的时间是62ms,div_255_fast的时间代价属于可以接受的范围。 下面是测试程序

……

阅读全文

CYGWIN 环境搭建记录

[sshd]

ssh-host-config /var/empty目录的拥有者必须是sshd进程的拥有者, 而且权限必须是700; 如果sshd进程的拥有者不是SYSTEM, 则只有这个拥有者可以通过ssh登录系统, 因为sshd需要执行seteuid, 非系统账户执行seteuid将自己有效id设为其他用户时会被拒绝。 如果是在 Win7下面需要建立一个独立的用户,这时CYGWIN终端需要以管理员权限运行,否则用户设置失败,无法安装sshd服务。

[svnserve]

cygrunsrv -I svnserve -d "CYGWIN svnserve" --chdir /data/svnroot --path /usr/bin/svnserve \
	  --args "--foreground --daemon --root=/data/svnroot --listen-port=3690" \
	  --neverexits --type auto -o 

如果发现svnserve.exe无法监听在相应端口, 需要添加额外参数(–args中): –listen-host=0.0.0.0 (或监听在特定的ip或主机名上).

[passwd]

如果在cygwin中发现自己所在的组变成了”mkpaswd”, 这说明/etc/passwd或者/etc/group需要重建了, 运行:

mkpasswd -l >/etc/passwd; mkgroup -l >/etc/group

[httpd]

启动httpd服务时可能会报告”Bad system call”错误, 这是由于apache2需要cygserver, 运行: cygserver-config 而且环境变量 $CYGWIN 中包含server, 参见 [The CYGWIN environment variable].

[init]

配置启动 systemv 的 init 服务,管理员启动cygwin,并运行:

init-config 

然后查看 /etc/inittab 和 /etc/rc.d/rc 两个文件,根据需要编辑,首先是 /etc/inittab:

# id:runlevels:action:process
id:3:initdefault:
rc::bootwait:/etc/rc
l0:0:wait:/etc/rc.d/rc 0
l3:3:wait:/etc/rc.d/rc 3
#S0:2345:respawn:/sbin/agetty -L -T vt100 -n ttyS0 9600 ttyS0

接下来是 /etc/rc.d/rc:

……

阅读全文

美术资源超级压缩方法

如何在质量下降不大的情况下降低一倍的占用?如何让臃肿的美术资源压缩再压缩?

JPEG->WDP/WEBP

大部分项目都陆续废掉了JPEG,而最好的代替品是微软的HD Photo,wdp格式,在PSNR差不多的情况下,wdp能比JPEG小一倍多。

(wdp的encoder/decoder不好找的话,我这里有一份微软的库)

观察下面的演示图片不要缩放PDF,用100%显示才看得清楚差别

image

image

JPEG 16.18 KB,可以看出脸部方块已经很严重,头发等高频部分已经看不清楚,帽子和墙面质量损失严重,而下面这张WDP文件(HDPHOTO,XnView可以转换)只有13.85KB大小,质量却比JPEG好很多。(通常情况下峰值信噪比差不多的话,WDP能够小一倍):

压缩比从强到弱依次是:WDP>WEBP>JPEG2000>JPEG。因此换用WDP格式能缩小不少资源。

……

阅读全文

体育竞技游戏的团队AI

很多人问游戏AI该怎么做?随着游戏类型的多元化,非 MMO或者卡牌的游戏越来越多,对AI的需求也越来越强了。而市面上关于 AI的书,网上找得到的文章,也都流于一些只言片语的认识,理论化的套路,和一些简单的 DEMO,离真正的项目差距甚远,无法前后衔接成一条线,更无法真正落地到编码。

国内真正做过游戏AI的少之又少,东拉西扯的人很多,真正做过项目的人很少,因为国内主要以MMO为主,RTS比较少,体育竞技类游戏更少,而从AI的难度上来看,应该是:MMO < FPS < RTS < 体育竞技。作为实际开发过AI的人,给大家科普一下,什么叫做硬派AI。

硬派游戏AI,不是虚无缥缈的神经网络,用神经网络其实是一个黑洞,把问题一脚踢给计算机,认为我只要训练它,它就能解决一切问题的懒人想法。更不是遗传算法和模糊逻辑,你想想以前8位机,16位机上就能有比较激烈对抗的足球游戏、篮球游戏,那么差的处理器能做这些计算么? 硬派游戏AI,就是状态机和行为树。状态机是基本功,行为树可选(早年AI没行为树这东西,大家都是hard code的)。大部分人说到这里也就没了,各位读完还是无法写代码。因为没有把最核心的三个问题讲清楚,即:分层状态机、决策支持系统、以及团队角色分配。下面以我之前做的篮球AI为例,简单叙述一下: 何为分层状态机? 每个人物身上,有三层状态机:基础层状态机、行为层状态机、角色层状态机。每一层状态机解决一个层次的复杂度,并对上层提供接口,上层状态机通过设置下层状态机的目标实现更复杂的逻辑。

  • 基础状态机:直接控制角色动画和绘制、提供基础的动作实现,为上层提供支持。
  • 行为状态机:实现分解动作,躲避跑、直线移动、原地站立、要球、传球、射球、追球、打人、跳。
  • 角色状态机:实现更复杂的逻辑,比如防射球、篮板等都是由N次直线运动+跳跃或者打人完成。

image

……

阅读全文

山寨的GameLoft

既山寨又垃圾的GameLoft游戏,吃过亏后,我也长记性了,下游戏之前先看是不是有GameLoft字样,有的话,立马跳过。但前两天,我居然忘了看厂商,花了若干美刀下了个封面漂亮的游戏,打开游戏一看,我立马傻了,下意识的觉得不好!GameLoft!,仔细一看,果不其然。所以说好了伤疤忘了疼,吸取教训呀。……

阅读全文

参考ZeroMQ改进服务器

今天参考 ZeroMQ的观点为我们的网络模块增加了一个“订阅模式”,及客户端包头用四字节表示,低24位为长度,高八位为“消息分类”。后端连接网络层的若干“频道”可以根据自己的喜好订阅“分类消息”,那么客户端发送该分类消息到网络层的时候,将会被抄送到订阅过该分类的频道。每个频道还可以订阅若干系统消息,比如连接开始、断开、时钟等等。

我们的服务器自2004年底到现在,一直是网络和逻辑分离在不同的进程(主机)中间,网络模块可以连接多个提供服务的“频道”,只是配合休闲游戏的模型,当前只有一个频道可以和特定玩家进行交互。不过其基于多频道的模型使得这次改进很容易,改了三个小时,又跑了几个小时的测试用例,基本通过。

以后交易,聊天,逻辑等,都可以分布在不同的频道里面同时为玩家提供服务了。

……

阅读全文