游戏开发小记 2.1 玩具游戏引擎

上一篇在这里 游戏开发小记 01

在半年前的上一篇,我还在用 SDL 做为基础,虽然 SDL 有各种缺点,但是呢,我本来想的就是做一个简单的 Roguelike 游戏,图形什么的根本不重要,因为 Roguelike 的画面一般是这样的:

20u1imo

根本不用什么画面对不对?

但是,但是呢,做着做着,我的强迫症之魂又开始燃烧了!SDL 的问题大概有:

  1. 功能太简单,不好定制。
  2. 采样算法是最基础的 nearest ,就是放大就一堆像素点的那种,如果要做像素风的游戏大概没什么问题,但是我不打算做像素风啊!在我看来现在像素泛滥已经超过怀旧到了烂俗的地步了。
  3. 不支持 Retina 屏幕,画面颗粒感很严重。

于是只能盯上了 OpenGL,在跟着教程用 C 经过简单的学习 OpenGL 之后我觉得自己大概知道 2D 游戏应该怎么做了,于是开始在 Rust 里面写游戏啦。

Rust 里面有很多基于 OpenGL 的图形库,我最后选中了 glium,这是一个 so suck 的 OpenGL 绑定,OpenGL 本身麻烦的 API 被封装的非常现代简洁,作者也极其活跃的在更新。

于是做了个玩具 2D 引擎的雏形(sansa/engine/src · tioover/sansa),现在除了 UI 还刚开始做以外其它都能满足我的需求了。在这里稍微记录一下里面的设计(总共也才千来行代码囧)。

坐标轴

计算机中 2D 通常的坐标轴是左上角为原点,y 轴向下的。OpenGL 的坐标轴是屏幕中心为原点,x 轴向上 y 轴向右的常见坐标系(Z 轴比较反人类就是了),我比较喜欢 OpenGL 的坐标系,这样的话如果把一个东西放到屏幕中央就不用做位移了。而 Tile-base 的 2D 游戏正需要 Tile 从中央铺展开来。

唯一的问题是 OpenGL 的坐标轴是 [-1, 1] 的,而 2D 游戏是以像素为单位的,所以这里要叠加一个正交矩阵作为摄像机变换,值得注意的是矩阵应该把 Dpi 纳入计算,这样才能在各种 Dpi 下有统一的分辨率:

  \left(  \begin{array}{cccc}  \frac{f}{w} & 0 & 0 & 0\\  0 & \frac{f}{h} & 0 & 0\\  0 & 0 & -1 & 0\\  0 & 0 & 0 & 1 \\  \end{array}  \right)

这里的 f 就是 dpi 倍数。

精灵

对简单的 2D 游戏来说,Sprite 是重中之重,一切都是 Sprite 也不为过吧,这里 Sprite 的设计成这样:

其中 Image 是最简单的渲染单元,包含了顶点,定点索引和材质信息。Transform 是另一个单独的结构,这样分离开就不用为了实现 Transform 写大量 getter/setter 了。

pixel_factor 是个简单的颜色滤镜,在着色器里面乘上所有的像素,可以实现比如说淡入淡出之类的效果。

state 是一个动画状态姬,也是从 SDL 时代继承过来的设计。

动画

这是以前 SDL 时代上传的视频,动画系统说破了就是个状态姬,实际上很容易做,不过用有模式匹配的语言写起来就是爽

(其中 Vec 是动态数组,Box 是指针,Rc 是引用计数指针,i64 是 64 位有符号整型。)

这就是动画的基本状态,Static 就是相当于“0”,是每个类似系统里面都有的元素,Queue Paral Loop 都是控制元素。

Queue 中的动画会按照顺序播放,当前一个状态变成 Static 以后就会被删除,处理下一个状态,为空的时候 Queue 将变为 Static

Paral 中的动画将同时播放,每次都会迭代 Paral 中的所有状态,当 Paral 中所有状态为 Static 的时候,Paral 自身变为 Static

Loop 就是循环。第一个 i64 是计数器,看现在是第几次循环。最后一个 State 是实际进行迭代的状态。

当最后一个 State 变成 Static 的时候,复制一份第二个 Static 到自身重新开始,第二个 Static 相当于模板的作用。

还有个 Hold 就是一个定时停止播放,略过不谈。

这些都是控制结构,动画效果实际上是 Func 状态控制的:

其中的 StateFn (状态函数),是一个被引用计数指针管理的闭包函数,对每个函数传入 Sprite 指针,让其可以修改 Sprite 的状态,再传入 Timer 就能通过时间来控制动画效果了。

而返回值(是一个 Maybe Monad = =)如果是 None 的话就保持当前状态不变,如果是 Some (State) 的话就将自身变成其中的状态,比如说动画放完了,就返回 Some (Static) 来表明停止。

在这里贴一下贝塞尔曲线运动的代码作为示例:

下篇预告,文字渲染和 UI。

OpenGL 上面 PNG 图片边缘问题的解决

之前一直苦恼于 SDL 的材质采样算法,用的是最简单的 Nearest,而且不能变。

当缩放的时候会出现大块像素,这倒还好,但是旋转变形的时候怪异的锯齿就让人非常不爽了。

nearest sampler
比如这张,放大看

在尝试无果的情况下我开始用 OpenGL 代替 SDL2 了,OpenGL 默认的重采样算法是 Linear,比 Nearest 好,不会出现这些情况。然而我用 PNG 作为材质的时候,图案透明边缘出现了问题,有白线: 继续阅读OpenGL 上面 PNG 图片边缘问题的解决

用 Rust 来无痛并发

这是 Rust Blog 的一篇文章: Fearless Concurrency with Rust

稍微翻译下前面一点。

领略一下 Rust 的并发:

  • channel 会将所有权信息沿线转移,所以你可以把一个指针发送到另一个线程而不用担心别的线程会竞争访问这个指针,Rust 的 channels 强制确保线程隔离
  • 一个知道自己保护着哪些数据,Rust 确保数据只能在上锁的时候保存,状态永远不会意外的共享,Rust 强制确保“锁住数据,而非代码”。
  • 每个数据类型都知道是否可以在两个线程间发送或多个线程间访问,Rust 强制确保能够安全的使用,没有数据竞争,即使是无锁数据结构也是这样。线程安全不仅仅是文档,而是一个规则。
  • 你甚至可以在线程间共享栈帧,Rust 会静态的确保当有线程使用它的时候帧有效。即使最大胆的分享形式,Rust 仍然保证安全。

腾讯实习笔试面试小记

四月过了快一半了我却一篇文章都没写,但是我四月要写四篇!包括一篇 Trait 和 Monad。

稍微讲一下最近的事情,起因是有人觉得我蛮不错的推荐我去参加鹅厂的实习。真是谢谢

人家貌似不知道我是专科生,然后我看着每个岗位都写着本科学历心里有点忐忑,本来想不去的,但是想一想自己被刷下来了也是个经验呀。

然后去笔试了。笔试的不怎么样,人家还是 Javascript ObjC Java C++ C 混合起来考的。

很多数学题我都半蒙半做的,比如说最后有一道猴子摘香蕉,以为是自己一直搞不清楚的排列组合题,没仔细看,蒙了个 C_{50}^{2} 结果是这是个 fib 函数……

没想到通过了,让我去面试。

第一个面试官让我选个项目来说,我就说 ika 了,毕竟是料蛮足的。

然后就谈到编译这块去了,编译器,编译优化以及Gradual typing。反正挺顺利的。

然后出了个算法题,两个数集合并,我说了两个方法:

第一个是以一个数集建立二叉查找树,然后第二个数集查找。实际上随后想了想排序然后二分查找就行的,主要是原地。

第二个方法,我想到编程珠玑上面的 bitmap,所以说把数集作为位向量保存,他让我算算大小如何,我算了一下反正蛮大。后来算了一下 int 的话两个数集需要正好 1GB,这方法真臭……问我内存受限的时候怎么办,我就说 hash……嘛,一开始就说 hash 才好吧,半生不熟想要一个时髦的方法来卖弄 Orz
继续阅读腾讯实习笔试面试小记

技术杂记:Trait,2D 游戏,Monad 学习初步

这个月又差点整个博客空窗,以前写博客的勤勉到哪里去了!以后一定要一定要一定要每周写一点东西!!

于是我临时起意憋一点东西出来,那就这样啦。

2D 游戏开发

我在做的游戏,其实,严格来说还没有开始做……因为时间都花在造轮子上面了,首先我觉得只需要一些最基本的绘图功能就好了,于是用了功能很基础的 SDL,而不是游戏引擎,然后又觉得想要搞一些效果,所以尝试在 SDL 上面建立点点抽象,然后就一发不可收拾……现在我又嫌 SDL 在进行变幻的时候会出现锯齿,把目光投向功能更多更好开发更活跃的 SFML 上了。SFML 这个库的设计很不错,但是问题是这个库的 Rust 绑定有点糟糕,代码风格什么的就不说了,该有的抽象都没有做,很多对象都实现了诸如 set_rotate set_postition 这样的函数,但是没有抽离出来成为一个 Trait。现在我 folk 了,打算改进。

Trait

上面说到了 Trait,Trait 可以看作 Haskell 里面的 Type Class,Java 和 Go 里面的借口,只不过比接口要强大一点。

Trait 常常被译为特质,简单来说就是一个抽象的东西,要求你对特定的数据结构实现一些方法,如果满足了这个 Trait 你就可以把 Trait 应用到上面了。

具体可以看这里,我认为 Trait 是比继承更好的方式,尽管最初用 Trait 的时候可能会因为不能直接访问一个结构体里面的元素,也不能继承,会感觉很不方便,但是用久了会发现这一切是值得的。

(下文面向对象的语境是直觉的,传统的,大众的,不要给我说 Java C# 都不是面向对象语言,真正的面向对象是……)

继承是面向对象语言最基本的特性,但是继承也会带来许多的问题,比如说多重继承在所有语言里面都是问题重重,这不是设计问题,而是继承这种思想在面对这些情景的时候力不从心。而且出现了很多不必要的复杂度。而且加大了抽象的代价,这是万恶的,面向对象其实本质上就是一种简单的,傻瓜式的抽象准则,正因如此,其实抽象能力是被限制的。

时间所限,三月还有一个小时过去,我就不展开了,之后另开一篇文章。

Monad

Monad 这个东西非常神秘,让人心向往之,你想想“单子不就是自函子范畴上的幺半群”多么霸气!之前我看过各种科普,然后去看了点范畴论的 Wiki,感觉自己有点明白了自函子范畴上幺半群的意思,然后现在都忘了,昨天晚上看书《Haskell 函数式编程λ门》,里面举的例子就很好,让人一下子就懂了。

实际上 Monad 就是一个 Trait,对于实现了这个 Trait 的类型,类型里面可以“装”一些东西,又可以把一些东西装回去,比如说指针 Ptr<int> 就是一个 monad,你可以把一个数字装进去取出来再装回去……实际上 monad 就是那么简单的东西——箱子。

所以不用听别人讲什么什么本质上实际上就是个 Monad 就觉得难以企及,其实就是因为简单所以容易抽象,有些人经常会犯一个错误,A比B更抽象,所以A比B更本质,实际上真不一定是如此……不说了,再说就不是技术上的话题了。

言归正传,就我目前看到的内容,它常常用在“隔离”某些计算过程,这里我用 Python 来举例。假设有一些人比另一些人高贵,也就是贵族,这种人是不允许和平民通婚的,这时候我们就可以用 Monad 把两者隔离起来: 继续阅读技术杂记:Trait,2D 游戏,Monad 学习初步

Rust 之坑:啰嗦的浮点数排序

最近,一篇比较 Rust 和新出的 Nim 的语言的文章出现了,作者列举了 Rust 总总繁琐啰嗦的地方,然后在 Hacker News 中提供了新的弹药

如果要对一个浮点数数组进行排序,在 Python 中非常简单:

在 Haskell 中也非常简洁:

而在 Rust 中你得写这么一长串怪物:

继续阅读Rust 之坑:啰嗦的浮点数排序

传教文:Rust 大法好

Rust 是一门设计得非常不错的语言。我在 Twitter 上经常提起它。现在发布了 1.0 Alpha 测试版,是时候开始安利了!

rust game

不好意思图贴错了,

rust-lang

简介

Rust is a systems programming language that runs blazingly fast, prevents almost all crashes, and eliminates data races.

这是网站上的宣传语。作为一个系统级编程语言 Rust 并没有 .NET 或者 JVM 那样厚厚的 Runtime,并且有和 C 一样底层编程的能力。

并且非常快,速度和 C++ 差距不大,并且把 JVM .NET 甩在后面。它通过编译时检查来保证整个程序的正确和安全性,所有资源都会被回收,并且没有 GC 开销。在 Rust 中,一个变量的生存期(lifetime)是类型系统的一部分,内存何时回收会在编译时自动推算出来。

对比 C++ 它有更加干净的类型系统和语法,简洁的范型,在编译时被验证的 RAII,还有模式匹配之类独特的的函数式特性,以及强大的宏系统以及现代的模块管理。这里有一篇简单的比较

对比 Python、Ruby 等动态语言,可能没有那么灵活,但是先进技术下的静态类型语言别有一番风味,编译器会严谨地检查你的代码,杜绝一切低级错误发生。只要你心里装着:这个变量是什么类型,这个表达式是什么类型……你就会愉快地写程序,很多时候只要程序能编译出来,那么就能良好的运行了。

这一篇文章讲了语言本身的目标。和 C++ 一样,Rust 反对一个语言遵循一种教条的范式,你可以用它进行基本无副作用的函数式编程,也可以 OOP 或者过程式编程,利用宏,更多的范式也可以支持。没有多少的语法糖扰乱视线,比起一门炫酷的语言,Rust 更倾向于成为更现代化的工业级编程语言。

P.S. Rust 以前曾用过一个宣传语:“像 Haskell 一样类型安全,像 Erlang 一样并发,像 C++ 一样的性能。”。

特性概览

语言网站上的例子很好,而且能在网页上编译运行,只是用到的特性比较少。

继续阅读传教文:Rust 大法好

游戏开发小记 01

半,年,没,写,Blog,了!半年来发生了不少的事情,主要是实习和比赛这两件大事。之后生活恢复常态,但是却没恢复到以前的状态,比如——Blog 就长草了。

之前觉得 WordPress 逼格有点低下,所以想用 GitHub Page 取而代之,然后又想学 Belleve 巨巨Yuki 一样自己写一个生成器,最后坑了。然后托 GitHub 的福,得到了一个免费用两年的 VPS

总而言之,在比赛完不知道干什么的那段日子,我开始了这个游戏项目,名叫 Sansa,最后完成的游戏是不是叫这名我不确定,反正这个项目正好创建于一个月前的明天,也就是说我已经差不多写了一个月了!

所以……进度呢?

屏幕快照 2014-12-18 下午8.08.51

……就是这点内容,你所看到的就是全部了。 继续阅读游戏开发小记 01

只有咸鱼看不懂的解释器科普 第一步:解析

嗯,这篇文章是我用来介绍自己的解释器 ika 的,不是宜家是乌贼娘!

ika

ika 其实没有什么独创的设计思想都是抄袭来的,所以我觉得要介绍还不如写一篇科普文。

当然这篇科普文会比较简略,毕竟我也扯不出那么多嘛,不过看完了,虽然不能让你闭着眼睛写一门语言,不过该给你的都会给你……吧。

继续阅读只有咸鱼看不懂的解释器科普 第一步:解析

pyPEG 一个很不错的 PEG 文法 Parser 生成器

所谓 Parser(维基百科称作语法分析器,但是我还没见什么人这样说。) ,就是把字符串转化成程序内部的数据结构,所有编程语言,或者 JSON,XML 这种都需要 Parser。一开始人们人肉写 Parser,然后人们崩溃了,尝试提取 Parser 的模式出来,创造了 Parser 生成器,Parser 生成器通过某些规则来生成 Parser,这种规则就是描述语言文法规则的形式文法,常用的是 BNF 以及其扩展。

因为第四次(还是第五次?)重写自己的 Scheme 解析器,看了自己人肉手写的 Parser,虽然经过多次重构,逻辑更清晰一致,但是还是十分冗杂,本来一直在犹豫要不要用 Parser 生成器,最后 Belleve 大神的文章让我下定决心(已成为脑残粉!本来对 Node.js 不屑一顾,现在打算试试了),用,找不到合适的就写。

我之所以那么纠结用不用 Parser 生成器的原因,一是我想让自己这个东西变得纯净,不是依赖别人的轮子,而是从头发明轮子。二,也是最重要的是 Python 最知名的 Parser 生成器 PLY,并不符合我的口味,先不提很久没更新了,更重要的是,PLY 大量使用了反射,破坏了 Python 原本的模式,以前缀为约定,并不美。

中间还在 GitHub 上找到一个同样是 PEG 文法的 Parser 生成器 但是很遗憾,Python 2 Only。最终还是选择了 pyPEG,虽然感觉知名度不太高,但是文档完备,支持 Python 3 ,而且用法也很清新。

因为这个是我用的第一个 Parser 生成器,所以我不能给你讲 PEG 文法好在哪里,不过和 (E)BNF 最大的差别就是,表达式的析取 (expr | expr) 是有顺序的,如果匹配了一个,就会终止匹配,所以 | 在 PEG 文法里面会写作 /。

虽然说是 PEG 文法,其实并不是像别的工具一样,程序员通过 PEG 文法来写,而是用 Python Class,根据规则来进行,这样虽然有一点麻烦和不直观(嗯,主要是写递归规则的时候有点麻烦。),但是因为不像别的库,没有形式化语言和程序语言的连接问题(比如说 Yacc,里面既有 BNF 也有 ),感觉有点清爽。

于是我用了五行就写了一个 S 表达式解释器,但是现在不这样了,因为 Python 有递归深度限制,还有一些特殊情况比如说 Quote。

具体的用法就看文档吧。

函数式编程简介

这是我为了学校的一个活动准备的讲稿,这几天会不断编辑。

伪代码

为了便于理解,这里用类似 JavaScript 的代码,在文中可能不会给出函数的具体实现,但都是容易实现的。

在这里,我尽量使用比较通用的名词,但是因为语言不同也会有差异。

另外,JavaScript 也算是函数式编程语言,所以文中的伪代码在简单的修改以后应该可以运行。

什么是函数式编程?

广义上很多编程语言都是函数式编程语言,比如说 Python、Ruby,而在最近 Java 8 和 C++ 11 都引入了很多函数式特性。

概括说,函数式编程往往有这些特点,而且这些特点是有关联的:

  • “第一级”(first class)的函数,常常使用高阶函数来抽象。
  • 利用递归进行循环。
  • 将程序看作表达式的组合,尽量避免“副作用”——很少使用变量!
  • 惰性求值。

下面就稍微说一说。 继续阅读函数式编程简介

作为初学者给编程初学者的建议

同为编程初学者,特别建议初学者把自己的代码发到 GitHub。

首先不管是不是有人看,代码总是在大庭广众之下的,你也有动力去反复改反复注意如何编码更好,总之就是代码写得丑了不好出门见人的感觉。

其次是版本控制的天然优势,你可以翻自己以前的代码,看到自己是怎么进步的,代码是如何从少变多从简单变复杂的。Commits tioover/cbase GitHub (别学我,我原地踏步)

再次是如果有问题,你可以直接贴地址给别人,有代码高亮也有评论功能,实在不行还能把代码下载下来自己调试。这个就是昨天我遇到了问题,@csslayer 和 雷喵 两位好人大大帮助了我解决这个弱智低级错误:

同时 GitHub 上也有很多项目,不乏同是新手的联系项目和帮助新手的手册等等,你看我随便一搜“中文”二字就出来一堆很赞的教程: Unknwon/the-way-to-go_ZH_CN · GitHub youyudehexie/node123 · GitHub justjavac/free-programming-books-zh_CN · GitHub

然后然后你可以参与开源项目,就算只是提交几个 Issue。

最后,你还可以看个人页面的格子图,一年里哪天荒废了,哪天代码写得很多一目了然,既激励又敦促。

GitHub_grid
荒废了那么多时光……

你们看,那么好的方法,对初学者来说简直就是量身打造啊。

诡秘深奥的现代魔法 1.3 下

虽然是下,但是因为只剩一个小节了所以没什么好说

1.3.4 过程作为返回值

过程作为返回值,意思是在函数里面用 lambda 动态的生成一个函数作为返回值,作为一种抽象工具来说是十分强大的,在后面的例子里也能看到。

这一小节的实例是牛顿法,可以逼近方程的解,我猜计算器解方程就用得是这种方法。

在这个例子里面,“高阶函数做抽象”这一节里面学到的方法基本上都被用到。

后面的习题看着虽然吓人,之前还吓退了我,不过硬着头皮去做会发现不难。

练习 1.45

这一题要写代码不断试做实验,但是因为用了前面的习题的代码所以要保证前面的习题的正确。

实验以后可以看到:(平均阻尼次数 -> 开次方数)

  • 2 -> 4
  • 3 -> 8
  • 4 -> 16
  • 5 -> 32
  • ……

显然是对数的规律,k次开方最少需要 \lfloor lg(k) \rfloor 次平均阻尼,lg 代码懒得写,是从这里复制的。

诡秘深奥的现代魔法 1.3 上

用高阶函数做抽象

终于来到这里了,前面的大都是开胃菜,我们常说的函数式编程最大的特点就是,函数也像一个数据一样可以被放进数据结构里面,也可以作为参数传入,作为返回值,在程序中动态生成,一个常用的行话叫做:把函数作为一等公民。

这个特性能让程序的表现力大大提高,以至于很多新旧语言都吸纳了这个特性。我们从现在开始真正学习抽象这个极其有力的魔法,到了这本书后面你就会觉得,自己动手让没有 OO (面向对象)特性的 Scheme 语言支持 OO 实在是一件简单的事情。有人想对 C 这样做,最后出来的是 C++!玩笑玩笑。

言归正传,书中也讲了,高阶过程就是将过程作为参数或者返回值的过程,在数学里面很高端地叫做“泛函”,还有一个高大上的数学分支叫做“泛函分析”,我是完全搞不懂啦。

继续阅读诡秘深奥的现代魔法 1.3 上

微世纪

我觉得可以有一个信仰微生物的宗教啊。

  • 起初没有世界也没有神,神在混沌中被孕育。祂无比的微小,但是又无比浩瀚,因为祂可以复制自身,神复制了以后依旧是神,依旧只有一个神,所有微小的亿万分之一的整体才是祂。
  • 经历了漫长的岁月以后,神想要创造世界。神必须审判自己,让自己的一部分褪去神性。
  • 神化作蓝藻,从混沌中采集负熵,降下了审判。神的审判遮蔽了这个世界,现在的凡人唤作氧气。
  • 失去神性的神难以对抗外界,他们聚在一起成为了多细胞生物。
  • 神是遍在的,神调和着自然的规律。神将死去的生物分解,轮回于自然。神将创生无穷力量的权柄化作叶绿体分享给了一脉生物,将使用这些力量的权柄化作线粒体分享给了所有生物,权柄都含有神性。
  • 多细胞生物不断繁衍壮大,存在于海中和陆地。神帮助它们,也用死亡选择他们。神是仁慈的,也是残酷的。
  • 最后,灵长类的裸猿诞生了,与此同时世界也诞生了。
  • 神安息了。
  • 神被惊醒了,因为裸猿窃取了专属于祂的权柄——青霉素——对抗祂自身。神愤怒的降下审判,专属于裸猿的审判,裸猿唤作 HIV。

诡秘深奥的现代魔法 1.2 下

这个系列好久没写了,刚刚依靠光速浏览看到了第三章的结尾,于是回顾以前的章节开始认认真真读第二遍了。看以前的写的内容感觉就像习题解答一样无趣,于是多一点理解少一点习题,有趣的习题当然还是要写的,没写出来的习题也应该在这个仓库里面,如果没有的话大概是我不会做。

1.2 过程与它们所产生的计算

1.2.4  求幂

这里介绍了求幂的一种\Theta(\log(n))时间界。特别舒爽。下面的习题里面的迭代计算过程的求幂比较简单,后面的练习 1.17 也没什么难点。

对数步骤的求幂已经很让人奇异了,下面还有对数步骤的斐波那契数。

练习 1.19

这一题别看说什么变换族,什么让你证明,实际上挺容易的。

a\leftarrow bq+aq+ap
b\leftarrow bp+aq
.
继续阅读诡秘深奥的现代魔法 1.2 下