Archive

Archive for August, 2011

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

August 31st, 2011 No comments

经过若干次试验修改,研究出下面这个快速/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的时间代价属于可以接受的范围。

下面是测试程序(点击more展开):

Read more…

Categories: 编程技术 Tags:

测试了一下:TT达到64

August 18th, 2011 3 comments

image

记录一下。

Categories: 未分类 Tags:

CYGWIN 环境搭建记录

August 12th, 2011 No comments

[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, 参见[he 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:

#! /bin/bash
# Now find out what the current and what the previous runlevel are.
argv1="$1"
set `/sbin/runlevel`
runlevel=$2
previous=$1
export runlevel previous

# Source function library.
. /etc/rc.d/init.d/functions

# Get first argument. Set new runlevel to this argument.
[ -n "$argv1" ] && runlevel="$argv1"

# echo "rc $runlevel" >> /tmp/rc.log

# Is there an rc directory for this new runlevel?
if [ -d /etc/rc.d/rc$runlevel.d ]; then
        # First, run the KILL scripts.
        for i in /etc/rc.d/rc$runlevel.d/K*; do
                # Check if the script is there.
                [ ! -f $i ] && continue

                # stop script
                $i stop
        done

        # Now run the START scripts.
        for i in /etc/rc.d/rc$runlevel.d/S*; do
                # Check if the script is there.
                [ ! -f $i ] && continue

                # start script
                $i start
        done
fi

 

不要直接复制上面的代码,最好照着用手敲,页面上 copy/paste 经常会把 indent 搞乱,bash脚本的缩进一乱就没法运行了。使用时把启动停止脚本放到 /etc/rc/init.d 下面,然后启动时候做软连接:

/etc/rc.d/rc0.d/K*     # 停止脚本
/etc/rc.d/rc3.d/S*     # 启动脚本
别忘记 init-config 时候把 init 安装成 windows 服务,如此,可以自由的增加自动启动脚本了。
 

[supervisor]

 
安装 python2-setuptools 然后:
easy_install_2.7 pip
pip install supervisor
mkdir /etc/supervisor
mkdir /etc/supervisor/conf.d
mkdir /var/log/supervisor
编辑 /etc/supervisor/supervisord.conf :
[unix_http_server]
file=/var/run/supervisord.sock
chmod=666

[supervisord]
logfile=/var/log/supervisor/supervisord.log
logfile_maxbytes=50000000
logfile_backup=10
loglevel=info
pidfile=/var/run/supervisord.pid
nodaemon=false
minfds=2048
minprocs=200
childlogdir=/var/log/supervisor

[rpcinterface:supervisor]
supervisor.rpcinterface_factory = supervisor.rpcinterface:make_main_rpcinterface

[supervisorctl]
serverurl=unix:///var/run/supervisord.sock

[include]
files=/etc/supervisor/conf.d/*.conf

然后就可以使用了

Categories: 未分类 Tags:

美术资源超级压缩方法

August 7th, 2011 No comments

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

 

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格式能缩小不少资源。

 

PNG->WEBP

非界面元素,仅仅是为了使用ARGB32的资源,可以用webp的带alpha有损格式代替,能节省不少。

 

实时纹理压缩

PS Vita里面已经大范围用到了实时纹理压缩方法,DXT格式存储纹理仅仅是为了方便显卡,但是它的地压缩率却害苦了硬盘。废除DXT格式,用wdp格式或者webp格式有损保存图片(不要用JPEG了,JPEG太差)。运行时动态载入并且动态生成dxt格式再载入显卡。如此在质量微弱损失的情况下,可以至少获得4-5倍的空间节省。

PS Vita使用的动态生成dxt的库叫:

Read more…

Categories: 图形编程 Tags:

体育竞技游戏的团队AI

August 5th, 2011 1 comment

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

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

硬派游戏AI,不是虚无缥缈的神经网络,用神经网络其实是一个黑洞,把问题一脚踢给计算机,认为我只要训练它,它就能解决一切问题的懒人想法。更不是遗传算法和模糊逻辑,你想想以前8位机,16位机上就能有比较激烈对抗的足球游戏、篮球游戏,那么差的处理器能做这些计算么?

硬派游戏AI,就是状态机和行为树。状态机是基本功,行为树可选(早年AI没行为树这东西,大家都是hard code的)。大部分人说到这里也就没了,各位读完还是无法写代码。因为没有把最核心的三个问题讲清楚,即:分层状态机决策支持系统、以及团队角色分配。下面以我之前做的篮球AI为例,简单叙述一下:

 

何为分层状态机?

每个人物身上,有三层状态机:基础层状态机、行为层状态机、角色层状态机。每一层状态机解决一个层次的复杂度,并对上层提供接口,上层状态机通过设置下层状态机的目标实现更复杂的逻辑。

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

每一层状态机都是通过为下一层状态机设定目标来实现控制(目标设定后,下层状态机将自动工作,上层不用关心动画到底播到哪了,现在到底是跑是跳),从而为上层提供更加高级拟人化的行为,所有状态机固定频率更新(如每秒10次),用于判断状态变迁和检查底层目标完成情况。最高层的角色状态机的工作由团队AI来掌控,即角色分配的工作。而行为状态机以上的状态抉择,比如回防,到底是跑到哪一点,射球,到底在哪里起跳,路径是怎样的,则由决策支持系统提供支持。

Read more…

Categories: 人工智能, 游戏开发 Tags: ,

山寨的GameLoft

August 5th, 2011 1 comment

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

Categories: 未分类 Tags: