千嶂夹城
发布于 2025-10-03 / 14 阅读
0
0

一个 brainfuck 小游戏,以及通解

小游戏地址:https://game.uqzjc.cn/bfmaze

前几天有了一个小游戏的点子,然后 vibe coding 把它做了出来。

游戏规则

游戏的规则是这样的:你需要在左侧写下一个 brainfuck 代码,操控一个小机器人走迷宫。brainfuck 的输入是小机器人前面的方块是什么,输出控制小机器人转向与前进。

具体而言:

  • brainfuck 输入 0 表示前面是空的,输入 1 表示前面有墙,输入 2 表示前面是终点。

  • brainfuck 输出 1 表示左转,输出 2 表示前进,输出 3 表示右转。

小游戏采用前后端分离的开发模式,前端使用纯 web 三件套,使用 XMLHttpRequest(main.js) 或 fetchAPI(scoreboard.js) 与后端(使用 node.js)通信,由于前后端三级域名不一样,踩了一些 CORS 的坑,最后后端用 node 的 cors 组件解决了。

brainfuck 规则

  • -/+ :将指针指向的内存位置上的数减一或加一

  • </> :将指针左移或右移一位

  • ,/. :输入或输出一个内容(输入和输出规则见上)


关于通关代码的思路:

朴素方法

一个朴素的方法是针对每一关写一个特解,得到一串操作序列,然后针对一块内存加加减减再输出。第零关的通关代码(默认给出的代码)就是这样解决的。

但是这种玩法的最大问题是,针对每一关,需要不一样的代码。而排行榜上记录的只有能通关所有关卡的代码。所以这种朴素方法上不了排行榜。

超级随机化

这种方法是通过一长串足够长的代码让机器人随机地走来走去,当机器人前面看到终点时,离开随机化过程,一步到达终点。

这种方法在随机程度足够高时是最万能的方法。

但相对应的代价是代码长度可能会长,一个记录中使用该方法通关的代码长度 15613 ,关卡执行指令数总和为 68445。

迷宫巡线法

这种方法的思路是,走迷宫的时候,扶着某一侧的墙,最终总会走出迷宫,这是一个我从智能车竞赛中学到的这种算法,参考资料:

https://zhuanlan.zhihu.com/p/391392970

对应的代码,我没有刻意优化的前提下,长度可达 47 字符,可以通过大多数关卡。后来有大佬优化至 22 字符,使用的思路类似,但去掉了一些检测,导致一些迷宫法理论能过的关卡过不去。

但这种方法必须开始时在墙旁边,或者开始先走到墙旁边,而且如果遇到终点不在墙旁边的环路上,也会使算法失效(无限循环)。

为了针对题目中的 hack,只需要做一些判断,提前走到沿环路能到终点的位置就好了,目前的 33 最优解使用的是这种方法。

总之大抵如此,欢迎来玩,欢迎挑战记录。(但别恶意 hack 我的网站就好啦)


评论