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

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

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

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

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

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

继续阅读

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的例子。

导出结果的截图:

Python反转字符串的方法碉堡了

有个同学在网易面试时被问到:在python中如何反转一个字符串。我同学当时想都没想就说:“不是有个函数叫做reverse吗?”
事实上,对于str类型,python并没有reverse函数。然而,通过反向步进切片,我们可以高效地反转一串字符串。

>>> string = 'abcde'
>>> string[::-1]
'edcba'