快速判断塔防迷宫中的割点(Tarjan算法)

凡是允许玩家自行建造迷宫的塔防游戏都有一个规则,那就是不允许玩家封死迷宫。目前我观察到的塔防游戏大概有三种处理方法:

  1. 基于魔兽RPG地图的塔防大多有这种设定,当玩家封死迷宫后,怪物会变成主动攻击玩家的炮塔。
  2. 另外有一些作品,比如《防御阵型:觉醒》,当玩家封死迷宫后,怪物可以从炮塔建筑的间隙中穿过。
  3. 还有一些作品,比如《兽人必须死》,游戏根本就不允许你在可以封死迷宫的位置建造炮塔。

第一处理方法是比较简单讨巧的。当玩家建造或拆除炮塔后,游戏必然会重新触发一次怪物的寻路。如果此时发现无法到达终点,那么久开启怪物的攻击性。

第二种方法更加简单,建造炮塔的位置并不是完全封死的,而是给一个极大的障碍权重值。这样,寻路算法自然会在路被堵死的时候穿越炮塔了。

难就难在第三种处理方法:我要怎么知道建造了哪些炮塔后路会被堵死?

继续阅读

基于Flash3D的粒子系统实现

因为项目需要,自己动手实现了一个粒子系统,同时为其编写了配套的粒子编辑器。由于自己对这一块并不是很熟悉,于是前前后后推翻重做了好多版,花费了大量的时间。所谓折腾使人进步,随着对粒子系统的编写、重构、优化,我自己对3D渲染的各方面也有了更深入的理解。随着时间的推进,粒子系统的设计也已经慢慢稳定下来,并经受了实际项目的考验。我想是时候记录一下自己在粒子系统这块探索的过程。

f

继续阅读

AutoWrapLuaApi v0.3

今天顺手把自动为lua包装C++的脚本给完善了下,总体来说v0.3版本有以下改进:

  1. 仅导出public区域的api
  2. 支持成员函数重载
  3. 支持运算符重载

还存在许多问题:

其一是依旧未实现导出类的static函数。

其二是成员函数重载有一些问题,但我觉得是luabind的问题。我的导出格式是没有问题的,但有一些重载函数无法通过C++的编译。例如以下这两条函数:

.def("ToAngleAxis", (void (Matrix3::*)(Ogre::Vector3 &,  Ogre::Radian &))&Matrix3::ToAngleAxis)
.def("ToAngleAxis", (void (Matrix3::*)(Ogre::Vector3 &,  Ogre::Degree &))&Matrix3::ToAngleAxis)

貌似luabind无法区分Radian和Degree两个类型,再比如下面两条函数

.def("ToAxes", (void (Quaternion::*)(Ogre::Vector3 *))&Quaternion::ToAxes)
.def("ToAxes", (void (Quaternion::*)(Ogre::Vector3 &,  Ogre::Vector3 &,  Ogre::Vector3 &))&Quaternion::ToAxes)

貌似在luabind眼中,一个Vector3 * 和三个Vector3 &是同一种东西?但下面这条加了const的又可以通过编译

.def("FromAxes", (void (Quaternion::*)(const Ogre::Vector3 *))&Quaternion::FromAxes)
.def("FromAxes", (void (Quaternion::*)(const Ogre::Vector3 &,  const Ogre::Vector3 &,  const Ogre::Vector3 &))&Quaternion::FromAxes)

这些依旧需要在C++中手工编辑一下

其三是luabind仅支持有限的几个运算符重载,分别是:
+   –   *   /   ==   <   <=
其余的运算符重载均无法导出。注意,以上的运算符均为二元运算符。

工具github地址:https://github.com/kidsang/LuabindAutoWrap

自动为C++类生成luabind api

在我的上一篇日志中提到使用luabind来导出C++类会很方便,但是通常来说,一个类中都会有几十个函数需要被导出,而我们手头上往往有几十个这样的类。如果要人工去一个一个为它们写导出API,那将会是一件十分令人崩溃的事情!对于boost::python来说,有一个现成的工具(具体叫什么名字请询问亮哥…)。但luabind就没有这般幸运了~所以我决定自己写一个。

我最初的做法是完全使用正则表达式来匹配各种类和函数,花了一整天时间做出来一个有着许多错误,但经过人手动修改修改也勉勉强强能用的版本。在这个过程中我深深地了解到了从“还不错”到“完美”之间存在着多大的鸿沟。这让我下定决心要用词法分析的做法重新写一个。但是C++的词法何其复杂,如果要自己手写一个那就实在是太浪费时间了!经过亮哥指点,我使用clang作为词法分析器,并使用其python包装,完成了为C++自动生成luabind api的第一个版本。

工具github地址:https://github.com/kidsang/LuabindAutoWrap
因为我已经把clang的dll也放在了仓库里,所以理论上来说,只要下载下来就可以用了。这是个使用python写成的工具,所以为了使用它你首先需要下载安装python2.7

源码主要有三个文件,其中parse.py负责调用clang的函数对文件进行分析,construct.py负责输出格式化后的api代码,autowrap.py是一个调用工具进行api包装的例子。

目前版本为0.1,主要的功能是为C++的类导出luabind api。其中包含了以下缺陷:

  1. 不支持静态成员函数,事实上,它会把它们当做非静态的函数导出,需要手动去删……
  2. 不支持运算符重载,并且不会进行导出。
  3. 不支持成员函数重载,会导出多个重复的api,需要手动去删……

这些缺陷我会慢慢地改进。之所以是“慢慢地”,主要原因是这个工具主要是我写给自己用,为了辅助SaberCore开发的。目前的程度已经可以为我节省大量的时间了,在向其中投入时间会使回报不成比例。不过我会抽空完善。

使用的注意事项:如果你想为一个文件file1.h生成api,而file1.h中有#include “file2.h”,那么你必须保证他们之间的路径正确,否则clang会因为找不到file2.h而解析失败。

下面是为OgreMatrix4生成api的例子。

导出结果的截图:

Clover 项目总结

很遗憾clover未能进入微软ImagineCup的中国区半决赛,这个项目也因此而结项了。虽然因为不能再继续前进而感到很可惜,但有一点值得高兴的是终于可以不用那么忙了~。~按照惯例,还是要总结一下自己做过的东西,免得以后忘记了。

Clover演示视频:http://v.youku.com/v_show/id_XMzc0MTAyMDg0.html

clover最初是在2012年1月6日开始的,到2012年3月29日结束。开发人员四人,分别是KidETNeil HsuFish。大部分的开发时间是在图书馆七楼的小黑屋度过的。

clover在开发过程中由于为了提高开发效率一共换了三套SDK,最初是C++/Ogre,然后是Python/Py-Ogre,到最后是C#/WPF。每当换一个SDK,我们都要为搭环境和学习新语言痛苦得死去活来。不过这个过程极大地提升了我们的学习能力和对新语言的适应能力。前两天为了弄chidongxi.me,又非常蛋疼地啃php和sql,结果就是我现在已经基本上忘记C++要怎么写了。接下来的时间要静下心来好好看书,把母语C++给重新捡起来。

说一下我觉得clover里面比较好的一些设计。

首先,受Ogre的影响,clover中大量使用了单例的设计模式(甚至我觉得已经过量了)。使用单例的好处就是实例不会被重复创建,在节省了空间开销的同时还方便了不同模块间的调用。如果是在C++中,我们肯定会专门写一个Singleton的模板类,然后再让需要使用单例的类派生自Singleton。然而在C#中并没有模板这个概念,虽然我们知道C#有种东西叫做泛型(Generics),但是我们谁也没打算深入研究C#,所以我们使用了一种非常愚蠢的做法,就是为每个需要使用单例的类都写了一次单例……

另外我们还使用了观察者模式。在C#中实现观察者倒是比在C++中轻松了许多,因为C#有种东西叫做Delegate(托管?)。C#在这方面已经帮我们做了许多东西。

clover中我们使用了分层的形式,各层之间的耦合还是比较松散的。其中我主要负责的部分是蓝色和红色,也就是UI层和渲染层。

渲染层的工作主要是根据上层传下来的数据对mesh中的一部分进行更新。我忘记我是从哪里看到的一句话,大意是越接近底层的东西就越要简单,因此我在设计的时候非常注意渲染层模块的复杂度。最后事实证明,渲染层在绝绝大多数情况都运行良好,非常可靠。

在UI层,wpf已经提供了非常强大的界面功能,基本上关于界面的所有东西都可以通过编写XAML来完成。然而,非界面的视觉效果还是需要自己来实现的。比如,当进入折叠模式的时候,会显示非常多的视觉提示信息。这些视觉效果相互独立,且每个都有动画效果。对于视觉效果,我写了个叫做Visual的基类,在该类中规定了视觉效果的基本行为。比如,所有视觉效果都会有淡出和淡入的动画。这样,在后期当我想要加某种特定的视觉效果,我只需要派生自Visual就可以了,要另外写得代码非常少。另外我还写了一个类叫做VisualManager,该类中通过一个List来管理各种视觉效果,保证它们能以正常的方式显示和销毁。

模块间如果出现循环调用,将会是非常悲剧的事情,它可能会导致死循环或无限递归。我们写了一个controller类来负责调用其他各类,形成了一个星形结构,避免了循环调用。

由于折纸算法涉及到了大量的数学计算,因此我们将一些常用的数学计算函数(如计算空间中两线段交点)写成静态函数放在Utility模块中。这极大地提高了我们的开发效率。

由于UI层处于2D空间,逻辑层和渲染层处于3D空间,因此少不了2D空间坐标和3D空间坐标的相互转换运算。如果每当需要进行3D-2D转换时都重新乘一遍所有的矩阵(模型到空间矩阵,空间到摄像机矩阵,摄像机投影矩阵,投影到屏幕矩阵)将会非常耗时。首先我通过固定摄像机在000点,仅移动模型的做法减少了矩阵的运算量。另外每当模型发生旋转或位置改变时,我都会预先运算好矩阵并储存在一个静态变量中。这样,当需要将一个点从3D变换到2D,仅需要用自己去乘这个矩阵就行了。

 

最后再做一下自我的总结吧。为了比赛而做项目是一件非常辛苦的事情,首先有个deadline压着你,另外你无法完全按照自己的意愿去做想做的事。在clover的开发中我学到了很多新知识,但也逐渐发现了自己的缺点。我是个喜欢通过项目来学习东西的家伙,这样导致了我所学的知识很杂而不精深,基础也很薄弱。

看书和做项目是个挺矛盾的事情,因为时间有限,一旦进行其中一项另一项就难以进行。我觉得学习的过程就像是软件开发,也是需要迭代的。也许看书多了,就需要写写代码来消化下知识;当发现写代码出现瓶颈以后,就要通过多读书来汲取更多的知识。我一直相信一句话:“问题不在于你懂得多少知识,而在于当你需要知识时,你应该知道在何处找到它们。”但如果不读书的话,我无法知道该在何处寻找答案。

接下来的时间会比较清闲,是时候好好静下心来看看书。

3月24日 Clover 阶段成果展示

突然发现有差不多一个月没有更新了,主要原因是随着Clover的开发走上正轨,每天都忙得要死,根本就没时间没心情更新。

所幸的事clover的开发终于到达了可以拿出来见见人的阶段~

Project Name:Clover

The goal of our design is to perform an easy way to simulate origami in computer.

Features — Basic Operations

Folding Up  (贴合对折)

Bending (打开)

Tucking In (向内翻折)

Fold with code (使用Python代码折叠)

Change Paper (更换纸张纹理)

Export Annotated Paper (输出带折线提示的纸张)

Other features:

›Magnetism (auto aligning)
›Auto camera
›Simulated paper elasticity
›Undo and redo
›Export folding script
›Export 3d model
 
Design And Architecture
 
Framework Overview

Data Structure — Abstract Layer

UI Layer — Tools And Visuals

关于这部分的更详细设计请参照:

http://www.cnblogs.com/kidshusang/archive/2012/02/07/2342007.html

由于对纸张的分组还存在一些问题,我们现在还不能折叠比较复杂的形状(暂时来说我们的目标是折出千纸鹤,但是在倒数第四步出错了……)。过两天解决了这个问题后要录视频,连上文档和ppt一同交给微软,希望我们的这个作品可以进入复赛吧!

另外我们今天无聊,想测试一下在电脑里面纸张是不是可以无限次对折,因为在现实中纸张是很难对折超过7次的。以下是在电脑中对折6次后的截图:

第7次折叠时,我的电脑整整花了半分钟才有响应。

到第8次程序崩溃了,好吧……

Clover有致命弱点,数据结构太复杂。简而言之,为了完整记录纸张折叠的信息,我们一共使用了一颗二叉树,一片二叉树森林,两个十字链表和一个栈来保存所有信息。并且,这些数据结构之间是相互引用的,构成了一个颇为复杂的网络。复杂的数据结构导致了极差的容错性,我们现在可谓是每前进一步都心惊胆战。然而,由于提交作品的时间紧迫,我们也无暇研究更优的解决方案。

我个人希望可以使用粒子系统来重构一遍Clover的纸张数据结构,我要先一个人慢慢研究研究。

本文链接

CubeTest 老项目

这个项目是在大二上学期完成的,为了拿来交数据结构与算法课程的大作业

大概花了大半个学期的时间,使用的语言是C++,使用了郝靖同学提供的一个2D贴图库

郝靖同学的2D贴图库名字叫做2dRender,基于dx9,并且用上了多线程(虽然现在看来毫无意义……)。这是他在大一时候完成的,感谢郝靖同学!

我的本意是想把CubeTest做成一个重力感应的游戏,通过改变屏幕方向来改变重力方向,让玩家操控小球走过陷阱重重的迷宫。

然而由于缺少在手机上编程的经验,只好改为在电脑上实现,通过鼠标操控。

一路上,小球要通过吃能量来维持自己的生命。如果能量归零,则游戏结束。

小球还有血量,如果触发机关则会掉血。血量归零游戏也结束。

为什么要做这个呢,主要是想自己写个2D的物理引擎。

后来发现这是一件非常困难的事情,虽然到最后我也或多或少的实现了一些物理引擎的功能(比如重力,比如反弹,比如摩擦)。

我现在依旧记得,当时我桌面上那满满一叠的物理和数学草稿纸。

这也是我第一次与他人合作的一个编程作品。

我们组三个人。我是组长,另外两人是廖南濠和李润超。

其中廖南豪负责迷宫生成算法,李润超负责屏幕坐标转换和贴图,我负责物理引擎以及一些乱七八糟的东西。

在团队合作这件事情上我犯了很大的错误,因为我已经习惯于一个人单打独斗,所以我包揽了大部分工作,并且喜欢一个人闷声编程。

这在后面引起了某位组员的不满情绪。

不过我也吸收了经验教训,在之后的项目中都有做到和组员良好互动。

本文链接

Snake贪吃蛇 老项目

这是我在大一的时候完成的,也是我的第一个编程作品。花了一个暑假的时间完成,使用的语言是C++,使用了第三方图像库CxImage

那时候我除了会在黑白框(控制台)里面cout一堆毫无意义的东西以外,什么都不懂。

首先我花了大量的时间了解了Windows窗口的创建和管理机制,以及它的消息传递机制

其后我又花了大量的时间纠结该如何贴图

由于是第一次一个人完成这么大一个程序(七千行代码量),明明规范注释什么的真的没有注意

而且全局变量随便乱用,代码冗余毫无可读性,完全没有面向对象的思想

并且直到最后,我的程序依然有严重的内存泄露……

不过,这个作品却是我大学生涯的转折点

正是由于这个作品,我发现我自己深深地迷恋上了编程,踏上了程序员的不归路……

有三种游戏模式选择

游戏中所有图片(背景除外)都是由我一手设计绘画的

也是从这个作品开始,同学们觉得我是个做界面的高手

以至于之后许多人都认为我是个“搞界面的”

虽然说在后来很多项目中,我也包揽了做界面的工作,实际上我是逼不得已

因为除了我之外没人能做界面

但其他人看不见你七千行代码的努力,其他人能看见的就是界面

所以我也悟出来一个道理,无论内在如何,界面一定要做的漂亮……在现在这个社会就是真理

贪吃蛇一期:http://antdiscovered.blog.163.com/blog/static/1143646512010621102331304/

贪吃蛇二期:http://antdiscovered.blog.163.com/blog/static/1143646512010717111726298/

本文链接