2015-05-24

变色龙代码

最近的新玩具: https://github.com/coolwanglu/quine-chameleon

受mame的100个语言的quine-relay的启发,我想可否做一个完全图,即多个语言互相转换。
这样的程序英文叫multiquines,Wikipedia上有介绍,程序运行时需要指定一个参数,比如输出语言,然后程序会输出自身代码的对应那种语言的版本。如果指定参数就是这个程序源代码所使用的语言,那就是quine了。

网上有一个5种语言的multiquines,我看了看,不是太优美。我一开始就是朝着multiquines的方向写。然而后来注意到,不指定任何参数的时候对multiquines来说是没定义的(或者什么都不应该输出),这个有点浪费,于是我做了ouroboros(就像quine-relay那样)和随机转换两种模式。

再后来我注意到反而是不指定参数这部分更有趣,而且为了同时支持带参数和不带参数,需要各种判断,造成代码臃肿。于是我就把这两部分拆开,目前在源码中分别叫chameleon.*和multiquines.*。分别进行优化。

写这个东西最大的乐趣当然是不断加入新的语言。我开始不久就把自己熟悉的语言放进去了,然后慢慢添加新语言,不会的就现学现卖。基本上需要的语言特性和函数有如下几个

- 支持双引号定义的字符串,支持反斜杠转义
- 将字符串按分隔符切成数组
- 生成随机数
- 支持命令行参数
- 数组查找
- 字符串转义,或者json输出,或者字符串/正则式替换
- 输出(不带换行)

按目前的设计,第一条决定了一个语言是否能很容易的加入。这里比quine-relay难的地方在于,任何两个语言都要互相输出,所以最好能有一个公共的转义和还原的标准。而quine-relay中每个语言只需要考虑下一个语言的转义就好了,更方便预处理,支持新语言(比如whitespace,brainfuck)以及其他特性(比如字符串压缩)

我在写这个玩具的过程中也很自然的学习了一些新语言。之前为了写dunnet.js而研究了emacs lisp,这里还加入了其他lisp系列比如clojure,racket,发现写写脚本也还挺顺手的。只可惜scheme由于标准库太小以及srfi实现不统一没能加入。另外就是接触了之前完全不想接触的perl和awk,发现不但没有想像中的可怕,反而挺好用的。

ruby出乎我的意料,一直是各个语言中最短的,尤其multiquines的原始代码(不包含数据)只有80个字节!然而一般python就够我用了,也没有太大动力学新的。coffeescirpt和javascript经过不断优化也冲到了前面,不错!

其他值得一提的是,即使是之前比较陌生的go,lua,vala,我都能很快上手,一方面说明了文档齐全,互联网时代获取知识非常容易,另一方面我也觉得现代编程语言比较类似,语言本身已经成为了工具,脑子里有一些大概念就可以畅行无阻了。当然具体细节还是要慢慢学习和熟悉。

至于C家族,你们就乖乖在最后好好歇着吧。。。

2015-04-12

NetHack 网页移植

最近在试图把NetHack移植到网页上,名曰BrowserHack。目前功能上基本完成了,还剩下界面调整和修复bug。

NetHack我很早就有耳闻,简单尝试一下不太喜欢它的字符界面。其实我小时候很喜欢玩SuperZZT,现在也还行,不过比较来看SuperZZT还是象形,而NetHack的字符界面就是会意了,还是蛮需要想像力的。

NetHack自然也有各种图形界面移植。以前也是没有深入尝试过。这次移植正好也研究了一番,没想到很快就入迷了,令我之前玩过的RPG游戏顿时黯然失色。

这游戏有两个特点,其一是系统和操作非常复杂,各种奇怪的命令,让我不禁想起了文字冒险类游戏。不过配合地图和帮助,这不是问题。里面物体和各种交互也非常复杂,武器放水里会生锈,地面上各种暗门陷阱,怪物的AI,无不体现出设计者的用心。另一个特点是,按Wiki的说法是这个游戏最难在于初期,这在现代游戏里也是不多见,这可能让我一开始有点望而却步,但是熟悉了几本操作以后,每次重玩都能很快上手进入状态,开始刺激的冒险。专门有一片文章讲“为什么我死了又死还是死?”,按现代游戏的玩法,一上来就横冲直撞,很快就死了。如果考虑现实生活中的探险,每一步前进必定是小心翼翼。

反观现代游戏,显示技术不断提高,似乎大多数游戏都把精力放到显示效果去了。虽然显示技术能极大提高游戏吸引力,NetHack换了几个主题我也是非常兴奋,但是玩家不是傻子,游戏本质如果弱智还是没法玩。此外,现在游戏的难度与老游戏也是没有可比性。大多数游戏难度都是循序渐进的,各种教学关卡。当然这是改进了,可是很多游戏设置了各种弱智的成就,欺骗大脑的奖励系统,感觉是把玩家训练成傀儡。

NetHack也有各种不错的移植,比如Steam上的Vulture for NetHack。有如此强大的游戏核心,再辅以美观的画面和易用的操作,真是绝了!

2014-04-01

Studying Metal Slug's Engine

There's a Debug Menu in many titles from the Metal Slug series. Today I played around with that debug menu in Metal Slug X, especially I turned on 'body rect' and 'attack rect', which revealed how the game works. Now not only did I have tons of hours of fun, I also studied a lot from this amazing game!




Of course the following are only my observations, or my best guess on how they have been implemented the game. Although I think my interpretation should work, but it's definitely not the only way, and it's quite possible that the developers have achieved the same effect with another (maybe better) method.


First Impression


At the first glance, the debug drawing is far cleaner than I had expected, it seems that it's not tiled based physics at all. But note the thin shadowed area below the line, which may imply that it's still using tiled based calculation somehow.



Edges


The ground is described as line segments, from the way the shadow is drawn I think that those are directed edges, so we know that on which side shall we keep things. Actually I think that all the edges are half-platforms, will talk about that below.

 In this picture, an obstacle is mark with 3 line segments, clever & cute! 


Rectangles


Besides the edges, there are two types of rectangles, 'body rects' (marked with a pair of right angles) and 'attack rects' (marked with a pair of arrows).

All the rectangles are axis aligned, even if they disagree with the visual. The missiles in the above pictures are heading toward different directions, but their body rects are still AA.  Sometimes we need to approximate the shape with multiple rectangles, for example in the pictures below.

Two body rects for the truck

Note the attack rects of the missles
Note the attack rects on the boss, marking the effective area of the spikes.


My interpretation of the rectangles is that they are using for hitting detection. Attack rects mark the effective area of attacking, and body rects mark the effective area of receiving damages.
About the attack rect of the player, I think it marks the melee range.


Colliding

Objects in Metal Slug can be roughly categorized into the following groups:

- Terrain: ground, slopes, platforms
- Mobs: infantry, vehicles, bullet, projectiles
- Attack areas: logical areas that may cause damage

So let's try to talk about all possible ways of collidings.

Terrain vs Mobs

Terrain collide with mobs only.  Since terrain is mostly marked as line segments, for each mob it is easy to find out which point on the ground is supporting it. One way of doing this is by casting a gravity direction ray right below the mob and find the first intersection point with the terrain.

How to find the intersection then? I guess the game is using the line sweep algorithm from left to right. A clue is that there are never vertical edges, which do not have upper side and lower side. Whenever the game wants to setup vertical obstacles, unit squires are used, as in below: 


The stacked squares are used to block the player. I think that it may be easier to implement this way than vertical line segments. Also I think the squares are not static body rects, why? see below.


Sometimes multiple squares are used, not sure why, maybe to avoid bugs? Also note that the body rect of the player is colliding with the them, so this proves that body rects are not used for terrain colliding detection. Instead I think that the foot point (don't know the actual term, I just mean the mid-point between the feet) is used.

 

The entrance of a cave, the line segments with squares around them are reversed platforms, they prevent user going up but not going down. This picture also proves that the foot point is used.

More examples:

 

A door.

Steps.


There are still some questions left:
 - Are the line segments represented by two endpoints or tiles? Both might be possible, but tiles may be more consistent with the squares
 - Why using all those reversed platforms inside (the door and the cave) entrace? I think it's enough to use the lowest one only. One possible answer is for robust.



Finally, the joints:

When a slope intersects with horizontal edges, special care must be taken, as marked in the screenshot. Interesting.


Attack Areas vs Mobs

Attack areas only collide with mobs. It's pretty straightforward,  if a mob collides with an attack rect, it may receive damage - need more logic checking, e.g. friendly fire. There are also other cases like saving hostages. It's too intuitive to put more words here.



Mobs vs Mobs


In Metal Slug, usually the player doesn't collide with enemy infanty. But there are exceptions:

This is the rightmost position I can reach from the left side of mummies. Note that I can jump into them from above, but will get pushed away gently.


This is the leftmost position I can reach from the right side of zombie dogs. Note that in this case if I try to jump onto them, I will bounce up instead of fall through.



With tanks it seems to be more complicated, it behaves differently when I try to approach from left and right. I didn't figure out if it's using the foot point of the body rect. There could be another type of rectangle, or there's an offset on the x axis.



Summary

So these are what I've got so far. I don't know why I haven't though of this idea before.

The using of directed edges and foot point is quite effective, since it's point-line segment intersections, which is much faster than polygon intersectons, or even AABB. Tunneling effects can be detected this way. And jump platforms are natural to implement.

On the other hand, this design justifies for Metal Slug, but may not for other games. Because the body rects may collide with the terrain, which may look weird in pure tiled based games like Super Mario. In Metal Slug, however, it's ok, since the background is not tiled, and we can see 'side faces' of '3d objects'.

Metal Slug has always been one of my top favorite games. Now there's a new way to play with more fun! I'd like to play through the series again with all the rectangles turned on!

Rocket lawn-cher!
Enemeee chaser!
Mission Complete!

2014-02-19

Notes

surface pro stylus calibration



Search for 'UserLinearityData' in HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet and remove 'devicekind=pen'


 
merge tool: meld


 
linux虚拟机的硬盘大小不够,扩容以后又调整了分区,于是grub就不能进入了。启动说unknown filesystem然后进入grub rescue。

根据
http://askubuntu.com/questions/142300/fixing-grub-error-error-unknown-filesystem
在grub rescue输入

set prefix=(hd0,5)/boot/grub
insmod linux
linux (hd0,5)/boot/vmlinuz-3.11.0-15-generic
initrd (hd0,5)/boot/initrd.img-3.11.0-15-generic
boot

然后grub这步正常了,但是会卡到initramfs/busybox,说找不到init
于是在linux命令后面加上root=/dev/sda5就可以正常进入系统

进入系统以后赶紧用grub-install和update-initramfs再修正一下。

2013-12-02

Converting synced C/C++ into asynced JavaScript

Emscripten is a C/C++ -> LLVM -> JavaScript compiler. It's useful and interesting, but one of its biggest limitations is about the sync/async model: JavaScript is single-threaded event-driven languages, therefore you cannot do a sleep() in the hope of receiving and processing extra events.

Demo


First of all, please enjoy this demo, on which I really spent some time.

tl;dr

  • Motivation: to make `sleep` and other similar functions actually work in our Runtime, without lots of labor work porting the C/C++ code
  • I actually made it worked
  •  `sync->async` is doable and I think it's not too hard - there are already implementations for JS
  • I think this is a feature that cannot be supported by merely an external library
  • Does it fit emscripten? Or is it possible to write a plugin for emscripten?

Demo explained(?)


The demo is basically a stop-time animation:

//draw something
//wait for some while
//draw something else
//wait...


You can verify this in the source code.

We all know that it is hard to convert it into the async model of JavaScript. Now would you please take a look at my ported code, it's almost identical to the original code, except for:
  • A few macros are introduced, which are defined in asyn2.h — actually the macros are pretty much just placeholders. 
  • A js function js_napms defined  — which is a wrapper of setTimeout

I fed emscripten with the code and blablabla — and the demo works. But wait! The code should be identical to the original code, which is synced!
Well, please let me explain a few more things before I reveal the secrets.

Another Demo

Here's another demo, which is... the same as above. So what's the deal?

We may imagine that, to really 'go to sleep', we need to store all the context and restore it when we come back again. Indeed, I did so in the source code, whenever you see a `ASYNC_` macro, it involves pushing and poping to maintain the async stack.

The actual functions behind those macros are defined in async.h.

Well, I'm NOT going to propose a set of API or a library, instead I'm proposing a way of pre-processing the code, and I did that myself manually. It's doable and there're patterns, you may see how a for-loop is broken down according to the comments. I'll put technical details in the end.

The porting experience may not be as smooth as it looks like, actually `xmas` is rather straightforward, where there are rarely recursive for-loops or branches. But if you take a look at other demos, it is a nightmare to define callbacks and maintain the stack manually, just imagine that there's no `call` and `ret ASM macros, and you have to do `push`, `pop` and `jump` manually.

My point is that: the sync->async process can, and should be done by the pre-processor/compiler


The Secrets of the 1st Demo

You didn't skip the previous section did you?

Actually I made the second demo at first, before I knew the the secret weapon — streamlinejs, and here is an intuitive demo.

It's not a library, but a parser/compiler instead. I didn't go too deep into its mechanism, but from the results it generated, the mechanism should be similar as what I'll mentioned below. You may read  this article for more details.

To build the first demo, all the placeholders are replace with underscores, which will be recognized by streamlinejs (as placeholders for calback), fortunately un-optimized JS generated by emscripten can be parsed without any problem — at lesat my demo.

Technical stuffs

Imagine that there a stack dedicated for async function calls, it is different from traditional stacks in that this stack is not cleared when a function exits.

Async function calls are different from (normal) sync funtion calls, an async call pushes the context into the async stack, including the callback (similar as the return address in the synced case) and returns. The central event dispatcher (the JS engine in our case) will call the callback eventually.

So the central idea is to identify all the async function calls, which are usually casuse by two reasons:

  • Calling an async function
  • `jump` over an async call

The first one should be easy: some functions are async natively, e.g. `SDL_Delay`. And if a function calls any other async funtions inside, it is async.

The second one is usually originated from loops and branches, which will be explained later.

I think that these can be identified by the compiler, in one of following stages:

- Pre-processing C/C++ — I did that manually myself
- LLVM bitcode — which I'm not so sure
- JavaScript — streamline itself is an example

There are advantages and disadvantages in different stages, for example it might be easier to optimize the code when parsing the C code; while it may be more light-weighted to store the local variables using JavaScript closures.


Identify and transfrom async functions


Here's an example:


// sync version
void work()
{
    int j = 99;
    SDL_Delay(1000);
    printf("result %d\n", j);
}


Since SDL_Delay is natively async, we have to transform `work` into its async counterpart, as follows:


// async version
// context: stack for async calls
int work(context_t * context)
{
    int j = 99;

    push_callback(context, work__cb1);  // set up callback
    put_variable(context, j); // save local variables

    SDL_Delay(1000, context); // async version of SDL_Delay
 
    return 0; // get out and wait for SDL_Delay
}
int work__cb1(context_t * context)
{
    get_variable(context, j);
    pop(context);  // prepare to return the previous chained callback
    printf("result %d\n", j);
    context->callback();
}
```

For-loops make the situation more complicated, which causes another type of async calls:


int f()
{
    for(int i = 0; i < 10; ++i)
    {
        printf("hi ");
        SDL_Delay(10);
        printf("%d\n", i);
    }
}



f() can be flattened as


int f()
{
   int i = 0;
start:
   if(i >= 10) goto end;
   printf("hi");
   SDL_Delay(10);
   printf("%d\n", i);
   ++ i;
   goto start;
end:
   // nothing
}


Now it is clear that we can split the function and make async calls


int f(context)
{
  int i = 0;
  // save i to the stack
  // async call f_start();
}
int f_start(context)
{
  // restore i
  //pop stack

  if(i >= 10) // async call f_end();

  printf("hi ");

  // save i
  // push f_start2 into the stack
  SDL_Delay(10, context);
  return 0;
}
int f_start2(context)
{
   // restore i
   //pop stack

   printf("%d\n", i);

  // push i
  // async call f_start() to continue the loop
   return 0;
}
int f_end(context)
{
   // pop stack
   // async call callback of f()
}


Braches (if, switch etc)  are similar, as long as we consider them as `goto`'s.


local variables and return values

local variables may be stored and retrieved when we push/pop the async stack,
and so are return values.

Compiler/Preprocessor Integration: Step 1

It should be clear now that this feature is kind of transformation, which cannot be supported by linking to an external library. Of course the pre-condition is that the transformation should be (almost) transparent, it should not be necessary for developers to maintain the stack manually.

The first step, I'd imagine, is that the async functions are explicitly marked through some mechanism. In my example, a placeholder is used.

Developers may still write programs in the sync fashion, for two reasons: one for the convenience writing new program, and the other for porting existing ones.

The compiler should detect, split and setup async functions automatically, the async stack should be managed by standard library while some API might be exposed.

There are two ways  of managing the local variables, let me call them the C style and the JavaScript style:

The C style: Local variables of async functions are stored in dedicated area in the memory (HEAP or a special stack for async functions), instead of the normal stack. To avoid lots of memcpy's, the variables may be directly allocate there. Some push/pop operations may be optimized if the caller/callee is known (e.g. loops/branches)

The JavaScript style: streamlinejs is a good example. Async functions are broken into a series of resursive functions, and local variables are stored into the closures.

The JavaScript style is easy and intuitive, but the hidden overhead might not be negligible. It may be too late to optimize when the LLVM bitcode have been transformed into JavaScript.


Compiler/Preprocessor Integration: Step 2

It might be possible to further reduce the work of writing/porting, as even marking async functions and define the placeholders for every async function declaration and every async function call is boring and error-prone.

My (naive & wild) imagination is that by defining a few essential async functions (such as SDL_Delay), the compiler would automatically recognize async functions, and set up the hidden parameter. It's not perfect, especially when we need to link a number libraries, but at least I think a C/C++ transformer would be possible and nice, perhaps based on LLVM?

Limitations

  • It might not work for muti-threading. Indeed I've been only thinking about single-threaded programs, especially most ones for terminal — But this should not affect the importance of this issue I think.
  • Lots of overhead might be introduced in this way — But I guess the performance should not be affected much if well optimized
  • C++: ctr/copy/dectr  of objects might be a problem, or maybe not since they can be `flattened` into C-style?
  • C++: try-catch might not work, the control flow is already diverted
  • There a few limitations of streamlinejs, but I think many of them can be addressed if we process in the C phase.

Discussion

Please follow this thread on GitHub.

2013-10-23

杂记 2013.10.23

png优化工具:pngnq(有损)和 pngcrush(无损)

ubuntu gnome 13.10的input source里找不到输入法:手动修改dconf键值
org.gnome.desktop.input-sources.sources
,在数组里添加('ibus','sunpinyin')('ibus', 'anthy')但是mozc似乎不行,原因不明。观望。mozc在dconf里要打('ibus', 'mozc-jp')

2013-10-20

Ubuntu 下 mount windows 共享目录

一般来说遇到标题所述问题我马上会想到smbfs,不过好久不用,最近发现smbfs已经没有了,取而代之的是cifs,于是命令大约是

sudo mount -t cifs //hostname//folder /localfolder -o user=username

不过总是报 Input/ouput error

google了一阵,有的说加上sec=ntlm有的说加iocharset=utf8,不过都没用。其中加了后者还会出 Can not access a needed shared library 的错误。根据 http://wiki.openwrt.org/doc/howto/cifs.client   和 https://bugs.launchpad.net/ubuntu/+source/linux/+bug/1067681, 安装了linux-image-extra-***的包以后才可以,但是mount还是不行。(我的linux是在虚拟器,装的最小内核linux-virtual)

于是尝试了一下smbclient,也是报错:tree connect failed: NT_STATUS_INSUFF_SERVER_RESOURCES 根据 http://klebom.net/melazy/tricks/ 查到是IRPStackSize过小的问题, 我在windows也确实查到了事件:
Log Name:      System
Source:        srv
Date:          2013-10-20 14:08:29
Event ID:      2011
Task Category: None
Level:         Error
Keywords:      Classic
User:          N/A
Computer:      ***
Description:
The server's configuration parameter "irpstacksize" is too small for the server to use a local device.  Please increase the value of this parameter.

于是查到需要改注册表
HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\lanmanserver\parameters\IRPStackSize

这是个DWORD值,根据http://support.microsoft.com/kb/285089说其默认值是15,可取范围是11-50。之前那个链接说改成了17,18才可以,但我一直尝试到20都不行,于是一口气改成32才可以。

但愿没有后遗症。具体原因仍不明,不知道是否跟在跑linux虚拟机有关。