TimothyQiu's Blog

keep it simple stupid

各式乱码

烫烫烫与屯屯屯

这两个乱码应该是不少 C/C++ 程序员的必经之路吧。

微软 Visual C++ 的 Debug 模式下,会为未初始化的内存填充一些初始值,以便调试。其中,栈上的内存都用 0xCC 初始化、堆上的内存都用 0xCD 初始化。

而如果把 0xCCCC 作为字符输出,在简体中文的 Windows 系统下,就会根据其使用的 GBK 编码将其解释为「烫」字;0xCDCD 则为「屯」。

变巨

如果你用过南极星,说明你已经老了。

在那个万码奔腾的年代,由于早年的《曹操传》和《三国志》等游戏使用的都是 Big5 编码的文本数据,而简体中文 Windows 系统使用的编码不同于 Big5。用「前朝的剑斩本朝的官」就产生了乱码。

「变巨」的 GBK 编码为 B1E4 BEDE(GB2312 亦然),而在 Big5 编码中这四个字节对应的汉字为「曹操」。

俸俸伲购美病

这是《英雄传说VI 空之轨迹SC》简体中文版中的一句对白,也是最初被玩家讽刺得最惨的地方。

打上官方修正补丁后可以发现原文为「嘿嘿嘿,还好啦。」之所以会产生这样的乱码是因为 GBK 编码:

BA D9 BA D9 BA D9 A3 AC BB B9 BA C3 C0 B2 A1 A3 // 嘿嘿嘿,还好啦。
   D9 BA D9 BA D9 A3 AC BB B9 BA C3 C0 B2 A1    // 俸俸伲购美病

缺了第一个字节……

锟斤拷

相对前面几个乱码的直白,这个乱码是很纠结的存在。

Unicode 中定义了一个特殊字符「�」即 U+FFFD,称作 Replacement Character。用来表示无法显示的字符或是无法解析的数据。

如果一段数据本身是使用 GBK 编码的,那么其中可能有很多部分不符合 UTF-8 编码规则。一个处理 UTF-8 数据的程序得到这段数据后,可以选择将数据中检测到不合 UTF-8 编码规则的部分替换为 UTF-8 编码的 U+FFFDEFBFBD,这样,就在自动消除编码问题的同时对用户给出了数据编码错误的提示。

经过上面这步处理后,数据中就产生了很多 EFBFBD 的序列,此时如果试图以 GBK 将其解码,那么两个这样的序列就成了「锟斤拷」,即 EFBF BDEF BFBD

VPS 自动备份到邮箱

我已经忘了上次备份服务器是什么时候的事了,只记得前不久因为「以为备份过」做错事然后手忙脚乱了。更考虑到自己邮箱那么多空间浪费着也是浪费着,于是就决定抽空写个脚本定期备份一下。

说是「自动」备份,其实一句话解释就是通过 cron 定期执行脚本,对需要备份的目录使用 tar 打包,然后 sendmail 发到邮箱。

这里的操作系统是 CentOS,其它系统应该也是大同小异。以下便是本次行动的流水帐 :)

Sendmail 相关

因为系统里原生没有安装 sendmail,于是

yum install sendmail   # 安装
service sendmail start # 启动服务
chkconfig sendmail on  # 开启自动启动

因为只想使用发信功能,所以也不用花时间改配置(收信功能的默认配置是只接受本地邮件)。确定防火墙允许 25 端口后,就可以使用下面的命令直接发送邮件了。

# 使用交互模式(使用只包含一个句点的行结束正文并发送)
mail <收件人>
# 命令行直接发送
echo <正文> | mail -s <主题> <发件人>

使用这种方法发出的邮件显示发件人地址为「<用户名>@<主机名称>」。因为 sendmail 只支持纯文本,所以需要借助 uuencode 来编码附件,于是:

# 只包含附件
uuencode <文件路径> <文件显示名称> | mail -s <主题> <收件人>
# 正文和附件
(echo <正文>; uuencode <文件路径> <文件显示名称>) | mail -s <主题> <收件人>

备份脚本

编写 Shell 脚本实现对 Web 目录的备份和发送工作,因为博客使用的是 SQLite 数据库,直接打包即可,不需要先用 mysqldump 导出。(新手上路,表示快被引号什么的弄疯了,于是大多数情况下都为变量加上了引号。另外邮件正文纯属无聊,完全可以不加 = =)

#!/bin/sh

# 备份文件存放目录
BACKUP_DIR="/path/to/backup/directory"

# 备份文件邮件接收地址
BACKUP_MAIL_RECEIVER="example@example.com"

# =====================================

# 保证目录存在
[ ! -d "$BACKUP_DIR" ] &&  mkdir -p "$BACKUP_DIR"

# 需要备份的路径
WEB_DIR="/path/to/web/root"

BACKUP_DATE="`date +%Y-%m-%d`"

BACKUP_FILE_NAME="$BACKUP_DATE.tar.gz"
BACKUP_FILE_FULLNAME="$BACKUP_DIR/$BACKUP_FILE_NAME"

cd $WEB_DIR
    tar czpf "$BACKUP_FILE_FULLNAME" *

BACKUP_MAIL_SUBJECT="VPS Backup: $BACKUP_DATE"
BACKUP_MAIL_MESSAGE=$(
    echo "Sir,";
    echo "";
    echo "Backup file $BACKUP_FILE_FULLNAME created.";
)

(echo "$BACKUP_MAIL_MESSAGE"; uuencode "$BACKUP_FILE_FULLNAME" "$BACKUP_FILE_NAME") \
    | mail -s "$BACKUP_MAIL_SUBJECT" "$BACKUP_MAIL_RECEIVER"

保存后给脚本加上执行权限,就可以直接运行试一下,应该会有邮件发到邮箱了。

chmod u+x <脚本名>

定时执行

定时执行肯定就是 cron 了,这个不用多说,直接 crontab -e 然后添加一行:

0 0 * * 2 /path/to/script

就大功告成鸟~从此,每周二午夜就会有一封谜之信件安静地躺到你的邮箱里……

Lua 学习笔记:协程

协程(coroutine)并不是 Lua 独有的概念,如果让我用一句话概括,那么大概就是:一种能够在运行途中主动中断,并且能够从中断处恢复运行的特殊函数。(嗯,其实不是函数。)

举个最原始的栗子

下面给出一个最简单的 Lua 中 coroutine 的用法演示:

function greet()
    print "hello world"
end

co = coroutine.create(greet) -- 创建 coroutine

print(coroutine.status(co))  -- 输出 suspended
print(coroutine.resume(co))  -- 输出 hello world
                             -- 输出 true (resume 的返回值)
print(coroutine.status(co))  -- 输出 dead
print(coroutine.resume(co))  -- 输出 false    cannot resume dead coroutine (resume 的返回值)
print(type(co))              -- 输出 thread

协程在创建时,需要把协程体函数传递给创建函数 create()。新创建的协程处于 suspended 状态,可以使用 resume 让其运行,全部执行完成后协程处于 dead 状态。如果尝试 resume 一个 dead 状态的,则可以从 resume 返回值上看出执行失败。另外你还可以注意到 Lua 中协程(coroutine)的变量类型其实叫做「thread」Orz...

乍一看可能感觉和线程没什么两样,但需要注意的是 resume() 只有在 greet() 以某种形式「返回」后才会返回(所以说协程像函数)。

函数执行的中断与再开

单从上面这个例子,我们似乎可以得出结论:协程果然就是某种坑爹的函数调用方式啊。然而,协程的真正魅力来自于 resumeyield 这对好基友之间的羁绊。

函数 coroutine.resume(co[, val1, ...])

开始或恢复执行协程 co

如果是开始执行,val1 及之后的值都作为参数传递给协程体函数;如果是恢复执行,val1 及之后的值都作为 yield() 的返回值传递。

第一个返回值(还记得 Lua 可以返回多个值吗?)为表示执行成功与否的布尔值。如果成功,之后的返回值是 yield 的参数;如果失败,第二个返回值为失败的原因(Lua 的很多函数都采用这种错误处理方式)。

当然,如果是协程体函数执行完毕 return 而不是 yield(),那么 resume() 第一个返回值后跟着的就是其返回值。

函数 coroutine.yield(...)

中断协程的执行,使得开启该协程的 coroutine.resume() 返回。再度调用 coroutine.resume() 时,会从该 yield() 处恢复执行。

当然,yield() 的所有参数都会作为 resume() 第一个返回值后的返回值返回。

OK,总结一下:当 co = coroutine.create(f) 时,yield()resume() 的关系如下图:

lua yield resume

How coroutine makes life easier

如果要求给某个怪写一个 AI:先向右走 30 帧,然后只要玩家进入视野就往反方向逃 15 帧。该怎么写?

传统做法

经典的纯状态机做法。

-- 每帧的逻辑
function Monster:frame()
    self:state_func()
    self.state_frame_count = self.state_frame_count + 1
end

-- 切换状态
function Monster:set_next_state(state)
    self.state_func = state
    self.state_frame_count = 0
end

-- 首先向右走 30 帧
function Monster:state_walk_1()
    local frame = self.state_frame_count
    self:walk(DIRECTION_RIGHT)
    if frame > 30 then
        self:set_next_state(state_wait_for_player)
    end
end

-- 等待玩家进入视野
function Monster:state_wait_for_player()
    if self:get_distance(player) < self.range then
        self.direction = -self:get_direction_to(player)
        self:set_next_state(state_walk_2)
    end
end

-- 向反方向走 15 帧
function Monster:state_walk_2()
    local frame = self.state_frame_count;
    self:walk(self.direction)
    if frame > 15 then
        self:set_next_state(state_wait_for_player)
    end
end

协程做法

-- 每帧的逻辑
function Monster:frame()
    -- 首先向右走 30 帧
    for i = 1, 30 do
        self:walk(DIRECTION_RIGHT)
        self:wait()
    end

    while true do
        -- 等待玩家进入视野
        while self:get_distance(player) >= self.range do
            self:wait()
        end

        -- 向反方向走 15 帧
        self.direction = -self:get_direction_to(player)
        for i = 1, 15 do
            self:walk(self.direction)
            self:wait()
        end
    end
end

-- 该帧结束
function Monster:wait()
    coroutine.yield()
end

额外说一句,从 wait() 函数可以看出,Lua 的协程并不要求一定要从协程体函数中调用 yield(),这是和 Python 的一个区别。

字符动画的制作方法

字符画版本的 Bad Apple 的流行应该是好多年以前的事情了吧……虽然当时也想过自己做一个,但一直觉得图片转字符画是一个很神秘的过程(据说 mplayer 可以直接把视频按字符画输出)。前两天做完 ssoaag 发现,貌似可以用这个东西的原理输出字符动画,于是就有了下面这个视频 = =

【似乎是教程】如何制作字符动画

看到最后的效果你会发现最终产出的字符动画最右一列字符是略有问题的,在视频里也注明了,是那个 GetColor 函数里有个失误 = = 会导致某些情况下取到下一行的颜色,需要 continue 掉,并且把最后除以的 w * h 变成真正有效的像素数。

我们仍未记住那年所学到的线性代数的知识

不少知识都是毕业了才知道为什么要学,继而有了学习的动力。想标题的时候发现连这门学科叫什么都反应不过来了……先后想起「离散数学」「高等数学」等等不忍回首的课程,最后终于憋出来正确的「线性代数」四个字。以下便是今回复习这个看了又忘忘了又看了不知道多少遍的东西的笔记。

前情提要,简称前提

左右手坐标系:手指沿 X 轴方向伸展,卷向 Y 轴正方向,大拇指的方向是 Z 轴正方向。

向量 Vector

向量是表示大小和长度的几何对象,有一个起点和一个终点。向量有一种重要的分类方法,下面会反复提到:

至于向量相加、相减、与标量相乘、取长度、标准化,这些都是很显而易见的操作,此处省略一万字。

点乘

向量 $\vec{a}=[a_1,a_2,\cdots,a_n]$$\vec{b}=[b_1,b_2,\cdots,b_n]$ 点乘的定义如下:

$$ \vec{a} \cdot \vec{b} = \sum_{i=1}^n a_ib_i = a_1b_1 + a_2b_2 + \cdots + a_nb_n $$

如果 θ 是它们的夹角,那么:

$$ \vec{a} \cdot \vec{b} = \left\|\vec{a}\right\| \left\|\vec{b}\right\| \cos\theta $$

当两个向量的长度均为 1(单位向量)时,点乘结果即 $\cos\theta$,则可以由此判断两者的位置关系(垂直、平行、……)。

叉乘

叉乘的结果是一个同时垂直于两个向量的向量,至于朝向那一边,敬请参照左手定则。

$$ \vec{w} = \vec{u} \times \vec{v} = (u_y v_z - u_z v_y, u_z v_x - u_x v_z, u_x v_y - u_y v_x) $$

如何改变向量的参考系

对于向量 $\vec{p}$,如何将其从参考系 A 中的 $\vec{p}_A = (x,y)$ 变换到参考系 B 中的 $\vec{p}_B = (x',y')$ 呢?

自由向量

对于自由向量,我们关心的是其长度和方向,参考系改变后只要这两者没有改变就是成功。

那么我们只需要把原向量的起点拉回原点,然后把两个参考系的原点重合,用单位向量 $\vec{u}$$\vec{v}$ 在参考系 B 中表示参考系 A 的 X 轴 Y 轴正方向,那么:

$$ \vec{p}_B = (x',y') = x\vec{u} + y\vec{v} $$

推广到 3D 环境,若 $\vec{p}_A = (x,y,z)$ 那么 $\vec{p}_B = (x',y',z') = x\vec{u} + y\vec{v} + z\vec{w}$ 其中 $\vec{u}$$\vec{v}$$\vec{w}$ 是 B 的坐标轴在 A 中的向量表示。

实际上 $\vec{u}$$\vec{v}$$\vec{w}$ 并不一定要是单位向量。如果不是单位向量,则说明这两个参考系的缩放不同。(比如同样的坐标系 A 和 B,只是一个单位是米,一个单位是厘米。)

固定向量

对于固定向量,除了长度和方向,参考系变换后向量的位置也不能发生改变。那么我们用 $\vec{O}=(x,y)$ 表示 A 的原点在 B 中的位置,则

$$ \vec{p}_B = (x',y') = \vec{O} + x\vec{u} + y\vec{v} $$

于是推广到 3D 环境:

$$ \vec{p}_B =(x',y',z') = \vec{O} + x\vec{u} + y\vec{v} + z\vec{w} $$

矩阵 Matrix

一个 m × n 的矩阵是一个有 m 行 n 列的矩阵,其中的元素用 ${M_i}_j$ 表示。

矩阵相乘

假设 A 是一个 m × n 的矩阵,B 是一个 n × p 的矩阵,那么它们相乘的结果是一个 m × p 的矩阵 C,其中 $C_{ij} = \vec{u}_{rowi} \vec{v}_{colj}$

$$ \begin{aligned} AB &= \begin{bmatrix} -1 & 5 & -4 \\ 3 & 2 & 1 \end{bmatrix} \begin{bmatrix} 2 & 1 & 0 \\ 0 & -2 & 1 \\ -1 & 2 & 3 \end{bmatrix}\\ &= \begin{bmatrix} (-1,5,-4)(2,0,-1) & (-1,5,-4)(1,-2,2) & (-1,5,-4)(0,1,3) \\ ( 3,2, 1)(2,0,-1) & ( 3,2, 1)(1,-2,2) & ( 3,2, 1)(0,1,3) \end{bmatrix} \\ &= \begin{bmatrix} 2 & -19 & -7 \\ 5 & 1 & 5 \end{bmatrix} \end{aligned} $$

向量与矩阵相乘

向量与矩阵相乘完全可以按照矩阵与矩阵相乘的常规方法相乘,不过下面的是一种方便后续叙述的方法:

$$ \vec{u} B = [x,y,z] \begin{bmatrix} {v_1}_1 & {v_1}_2 & {v_1}_3 \\ {v_2}_1 & {v_2}_2 & {v_2}_3 \\ {v_3}_1 & {v_3}_2 & {v_3}_3 \end{bmatrix} = x \cdot \vec{v}_{row1} + y \cdot \vec{v}_{row1} + z \vec{v}_{row2} $$

于是很眼熟的两个推导:

$$ \vec{p} C = [x,y,z,1] \begin{bmatrix} u_x & u_y & u_z & 0 \\ v_x & v_y & v_z & 0 \\ w_x & w_y & w_z & 0 \\ O_x & O_y & O_z & 1 \end{bmatrix} = x\vec{u} + y\vec{v} + z\vec{w} + 1\vec{O} = [x',y',z',1] $$
$$ \vec{p} C = [x,y,z,0] \begin{bmatrix} u_x & u_y & u_z & 0 \\ v_x & v_y & v_z & 0 \\ w_x & w_y & w_z & 0 \\ O_x & O_y & O_z & 1 \end{bmatrix} = x\vec{u} + y\vec{v} + z\vec{w} = [x',y',z',0] $$

如果将 3D 向量 $\vec{r}=(x,y,z)$ 增扩到 4D 齐次坐标(提出者是那个莫比乌斯)$\vec{r}=(x,y,z,w)$(w = 1 表示固定向量;w = 0 表示自由向量),那么:

$$ \begin{aligned} \vec{p}_A C &= [x,y,z,w] \begin{bmatrix} u_x & u_y & u_z & 0 \\ v_x & v_y & v_z & 0 \\ w_x & w_y & w_z & 0 \\ O_x & O_y & O_z & 1 \end{bmatrix}\\ &= x\vec{u} + y\vec{v} + z\vec{w} + w\vec{O} \\ &= [x',y',z',w] \\ &= \vec{p}_B \end{aligned} $$

其中 $\vec{O}$$\vec{u}$$\vec{v}$$\vec{w}$ 分别表示 B 中 A 的原点、X轴、Y轴、Z轴的齐次表示(原点表位置,补 1;坐标表方向,补 0)。于是 $\vec{p}_B=\vec{p}_AC$ 就可以进行坐标系转换了。

矩阵相乘与结合性

矩阵相乘的顺序是不能改变的,但可以改变括号。

如果有三个坐标系 F G H,矩阵 A 表示从 F 到 G 的变换,矩阵 B 表示从 G 到 H 的变换。那么矩阵 C=AB 就表示从 F 到 H 的变换。

$$ \vec{p}_F A B = \vec{p}_F (AB) = \vec{p}_H $$

线性变换 Linear Transformations

$T(\vec{u})$ 表示对向量 $\vec{u}$ 进行的线性变换。我们可以把向量写成各坐标轴分量的形式方便后续推导:

$$ \vec{u}=(x,y,z)=x\vec{i}+y\vec{j}+z\vec{k}=x(1,0,0)+y(0,1,0)+z(0,0,1) $$

于是一个针对向量 $\vec{u}$ 的线性变换就可以变为:

$$ T(\vec{u}) = \vec{u}A = (x,y,z) \begin{bmatrix}T(\vec{i}) \\ T(\vec{j}) \\ T(\vec{k}) \end{bmatrix} = (x,y,z) \begin{bmatrix} {a_1}_1 & {a_1}_2 & {a_1}_3 \\ {a_2}_1 & {a_2}_2 & {a_2}_3 \\ {a_3}_1 & {a_3}_2 & {a_3}_3 \\ \end{bmatrix} $$

缩放

因为缩放后的向量应该是 $S(\vec{u}) = (s_x x, s_y y, s_z z)$ 所以

$$ \begin{cases} S(\vec{i}) = (s_x 1, s_y 0, s_z 0) = (s_x, 0, 0) \\ S(\vec{j}) = (s_x 0, s_y 1, s_z 0) = ( 0, s_y, 0) \\ S(\vec{k}) = (s_x 0, s_y 0, s_z 1) = ( 0, 0, s_z) \end{cases} $$

于是缩放矩阵即为 $S = \begin{bmatrix} s_x & 0 & 0 \\\\ 0 & s_y & 0 \\\\ 0 & 0 & s_z \end{bmatrix}$

绕坐标轴旋转

将向量 $\vec{u} = (x,y,z)$ 绕 X 轴顺时针旋转 β 得到 $\vec{u'} = (x',y',z')$

因为是左手坐标系,所以沿着旋转轴向下观察时,以顺时针方向为正角度。假设原向量旋转角度为 α,则可以得出:

$$ \begin{cases} y = - r \sin\alpha \\ z = r \cos\alpha \end{cases} $$

于是将其旋转 β 后:

$$ \begin{cases} x' = x \\ y' = -r \sin(\alpha+\beta) = -r \sin\alpha\cos\beta -r \cos\alpha\sin\beta = y \cos\beta- z \sin\beta \\ z' = r \cos(\alpha+\beta) = r \cos\alpha\cos\beta -r \sin\alpha\sin\beta = z \cos\beta + y \sin\beta \end{cases} $$

于是可以得出旋转函数:

$$ R_x(\vec{u}) = (x, y \cos\beta - z \sin\beta, y \sin\beta + z \cos\beta) $$

将其应用于各个坐标轴分量上:

$$ \begin{cases} R_x(\vec{i}) = (1, 0 \cos\alpha - 0 \sin\alpha,0 \sin\alpha + 0 \cos\alpha) = (1,0,0)\\ R_x(\vec{j}) = (0, 1 \cos\alpha - 0 \sin\alpha,1 \sin\alpha + 0 \cos\alpha) = (0,\cos\alpha,\sin\alpha)\\ R_x(\vec{k}) = (0,0\cos\alpha-1\sin\alpha, 0\sin\alpha + 1 \cos\alpha) = (0,-\sin\alpha,\cos\alpha) \end{cases} $$

(数学推导即是如此。但从更方便的角度看,完全省略推导,直接写出各个单位向量变换后的值是很轻松的。)

以此类推,即可得出沿着每个坐标轴旋转的变换矩阵:

$$ R_x = \begin{bmatrix} 1 & 0 & 0 \\ 0 & \cos\theta & \sin\theta \\ 0 & -\sin\theta & \cos\theta \end{bmatrix} $$
$$ R_y = \begin{bmatrix} \cos\theta & 0 & -\sin\theta \\ 0 & 1 & 0 \\ \sin\theta & 0 & \cos\theta \end{bmatrix} $$
$$ R_z = \begin{bmatrix} \cos\theta & \sin\theta & 0 \\ -\sin\theta & \cos\theta & 0 \\ 0 & 0 & 1 \end{bmatrix} $$

旋转矩阵的特点是每行向量都是单位向量,而且两两垂直(即正交矩阵)。

仿射变换 Affine Transformations

简单地说,仿射变换就是线性变换+平移向量:

$$ T(\vec{u}) = \vec{u}A + \vec{b} = [x,y,z] \begin{bmatrix} {a_1}_1 & {a_1}_2 & {a_1}_3 \\ {a_2}_1 & {a_2}_2 & {a_2}_3 \\ {a_3}_1 & {a_3}_2 & {a_3}_3 \end{bmatrix} + [b_x,b_y,b_z] = [x',y',z'] $$

将其增扩到齐次坐标(w = 1 时表示固定向量,w = 0 时表示自由向量):

$$ [x,y,z,w] \begin{bmatrix} {a_1}_1 & {a_1}_2 & {a_1}_3 & 0 \\ {a_2}_1 & {a_2}_2 & {a_2}_3 & 0 \\ {a_3}_1 & {a_3}_2 & {a_3}_3 & 0 \\ b_x & b_y & b_z & 1 \\ \end{bmatrix} = [x',y',z',w] $$

这里顺带提一句,HTML 5 的 canvas 里,你可以通过函数原型 setTransform(m11, m12, m21, m22, dx, dy) 看出来这一个仿射变换。

平移

平移,即保留原坐标不进行线性变换(乘以单位矩阵),只将其加上一个偏移量:

$$ T(\vec{u}) = \vec{u} \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} + \vec{b} = \vec{u} + \vec{b} $$

增扩为齐次矩阵:

$$ T = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ b_x & b_y & b_z & 1 \end{bmatrix} $$

于是,重要的仿射变换矩阵共有五个:S T Rx Ry Rz,就是平时缩放、平移、旋转操作。