使用WebAssembly实现前端运行Kociemba算法自动解魔方

© Young 2018-08-31 16:49
Welcome to My GitHub

Kociemba算法,又称为Two-Phase算法或者二阶段算法;本质上是利用搜索算法来还原魔方;

当然这里并不准备仔细聊这个算法的实现,毕竟我也不是很清楚!

接下来的内容是怎么使用WebAssembly技术C语言实现的Kociemba算法在浏览器环境中也能运行起来。

如果不是很清楚什么是WebAssembly,可以去看这篇文章https://www.zhihu.com/question/31415286/answer/58022648

另外还需要一个工具Emscripten,如果对这个也不是很清楚可以去看这篇文章http://www.ruanyifeng.com/blog/2017/09/asmjs_emscripten.html

接下需要一个Kociemba算法的实现,在GITHUB上边有很多,比如这个https://github.com/muodov/kociemba

这个库有Python的实现版本,同时也有C的实现版本:

READMEPython实现版本的介绍很详细;我们来看看C的实现版本:

进入源代码目录即可看到Makefile文件已经有了,那么接下来只需要直接编译就好了:

编译时会创建bin目录,并把编译好的文件放入其中;

编译完成之后我们就可以直接执行了:

传入特定的魔方序列即可得到解法了。

至于魔方序列是怎么回事?README里边解释的很清楚:

简单来说就是不同面用不同字母表示,比如U表示顶面、F表示正面等;正面的意思是你用手拿着魔方时正对着你的那个面;然后按照固定的规律依次排列得到的字符串序列。

比如初始魔方序列为:UUUUUUUUURRRRRRRRRFFFFFFFFFDDDDDDDDDLLLLLLLLLBBBBBBBBB

其实我们要使用这个算法有很多种方式,比如:用Python或者Node搭建后台,然后封装接口给前台调用即可;

但是秉着折腾的原则偏要浏览器里边运行算法,那这时候就需要用到Emscripten了,安装完成之后,在C的实现版本源代码目录执行以下命令:

    emcc coordcube.c cubiecube.c facecube.c prunetable_helpers.c search.c solve.c -s WASM=1 -s EXTRA_EXPORTED_RUNTIME_METHODS='["UTF8ToString"]' -s ALLOW_MEMORY_GROWTH=1 -s EXPORTED_FUNCTIONS="['_solve']" -o kociemba.js

首先如果需要编译多个文件需要把它们依次列出coordcube.c cubiecube.c facecube.c prunetable_helpers.c search.c solve.c

然后需要设置ALLOW_MEMORY_GROWTH=1表示运行内存自动增长,如果不设置运行时会因为内存不够报错;

EXTRA_EXPORTED_RUNTIME_METHODS='["UTF8ToString"]'EXPORTED_FUNCTIONS="['_solve']"这两点也很重要,后边再说!

最后需要设置编译得到文件的文件名,WebAssembly文件的后缀名为.wasm,这里之所以设置为.js,主要是因为如果设置为.wasm,那么仅仅只能得到WebAssembly文件,之后你还需要自己实现加载WebAssembly文件,内存设置等一系列工作;

这里边坑很多,比如如果WebAssembly文件超过4K就不能使用WebAssembly.Instance来初始化了,而应该使用WebAssembly.instantiate等等…

这也是为什么现在的一些教程都只是拿单个C文件来举例的原因所在了!

但是设置为.js文件,则不光会生成WebAssembly文件,还会顺便帮你生成一份JS文件,里边会做一些默认的基本操作,比如加载WebAssembly文件,内存设置等。

执行命令之前,如果你不对源代码做任何改动,你就会发现如下错误:

大致意思是找不到头文件,解决办法是把源代码include目录里边头文件移出来和源文件同级即可。

如果不报任何错,同时会得到一份.js文件以及一份.wasm文件,那么编译过程基本就成功了。

接下来的问题,我们怎么使用呢?

首先只需要加载编译得到的JS文件即可:

接着需要对算法源代码进行一定的修改,新增一个solve方法,让其暴漏出来供JS调用:

因此需要设置EXPORTED_FUNCTIONS="['_solve'],方法名默认需要加上横杆才能正确匹配。

因为传入的是魔方序列字符串因此方法参数为char * rubik表示char类型的指针,同时返回的解法也是字符串,因此返回值类型为char *

至于solve函数的内容则是来自源代码中的main函数,int argc默认表示参数个数,char **argv则表示参数数组,当我们执行./kociemba DRLUUBFBRBLURRLRUBLRDDFDLFUFUFFDBRDUBRUFLLFDDBFLUBLRBD时,参数只有一个,因此可以推测出main函数中的执行语句,复制到solve函数中即可。

修改完成之后别忘了重新编译。

具体执行过程如下:

Module['onRuntimeInitialized']表示初始化完成,_solve方法已经被挂载到Module对象上了,直接执行即可;

但是在传递以及接收字符串时,需要额外处理;

比如传递字符串需要用allocate(intArrayFromString(rubik), 'i8', ALLOC_NORMAL)转换成内存地址;

接收时直接得到也是内存地址,要取得真正的字符串需要调用UTF8ToString方法,为了能直接调用该方法,需要在执行编译命令时设置EXTRA_EXPORTED_RUNTIME_METHODS='["UTF8ToString"]'

各内置方法详情可以去Emscripten官网http://kripken.github.io/emscripten-site/index.html查看。


在浏览器中运行结果如下:

示例代码在https://newbieyoung.github.io/Html_learn/webassembly/demo3.html

至此折腾结束!

最后剩下的工作就是把已有的魔方模型转换成Kociemba算法所需要的魔方序列即可。

发表评论

电子邮件地址不会被公开。 必填项已用*标注