阴阳师爬塔与迷宫生成算法

最近的阴阳师缘结神活动新增了走迷宫的要素。几百层的迷宫不可能手动绘制吧?于是想到了是不是有迷宫生成算法

能查到的迷宫生成算法有三种:递归回溯、 随机prim算法、 递归分割。前两种属于“拆墙法”,而递归分割则是“造墙法”。先放一下结论:

这三种算法分别适合不同的迷宫情况,递归回溯适合于那种主线支线明显的游戏(如RPG),而递归分割则适合转角较少的游戏(如FPS和ACT),至于Prim,似乎适合最标准的迷宫游戏(随机Prim算法生成的迷宫分支较多,整体上更复杂也更自然)。

阴阳师这个迷宫给我感觉是用递归回溯生成的,因为有一条指向终点的非常明显的通路。

递归回溯本质上是深度优先搜算方法,其迷宫生成步骤为(引自 https://www.jianshu.com/p/f643b0a0b887 ):

  1. 初始化,建立一个所有单元格都被墙隔开的迷宫。
  2. 随机选择一个单元格作为起始点,以此单元格开始打通墙壁。
  3. 以当前单元格为基准,随机选择一个方向,若此方向的邻接单元格没有被访问过,则打通这两个单元格之间的墙壁,并将此邻接单元格作为当前单元格,重复步骤3。
  4. 若当前单元格的四个邻接单元格都已经被访问过,则退回到进入当前单元格的邻接单元格,且以此单元格为当前单元格,重复步骤3,4。
  5. 直到起始点单元格被退回,则算法结束。

为了记录已经访问过的单元格,迷宫生成程序会维护一个,每次进入一个新的单元格,就将这个单元格的坐标放入栈顶。这样回退操作所需要的坐标从栈顶弹出就可以了。

又看了一下维基百科,自己摸索着写出了演示代码(github)。写完后发现,其实用这个算法的话,生成起点和生成终点未必就是玩家走的起点和终点。因为这个算法生成的图中,通路上的任意两点必然是可达的,因此起点和终点可以任意设置。

使用Radicale建立你的私有日历和联系人同步服务器

换手机了,发现新手机完全不能兼容google play,看log是少一个权限无法申请。不知道是不是google单方面ban了华为,或者华为单方面ban了google。不管怎么样我想要同步我的google账号上的日历和联系人是不可能了。

就在我导出google日历和联系人的时候,我又开始在想那个问题了:数据不在自己的手上,有一天可能就找不回来了。能不能自己搭建一个私有云呢?说到私有云我立刻想到了Nextcloud,但是看到Nextcloud的各种php、数据库还有http服务器依赖之后我觉得太麻烦了——我的需求是日历同步,Nextcloud一套上来过于复杂了,而且不够轻量。

于是我找到了Radicale这个开始于学校作业的项目。这个项目基本上可以在任何能运行Python的地方运行。它支持的CalDAV协议。这种协议的客户端的话,PC上的邮件和日历app基本都支持这个协议,我用的是thunderbird。手机上的话,貌似华为不能直接支持这种协议,得装个DAVx5

继续阅读“使用Radicale建立你的私有日历和联系人同步服务器”

解决Linux关机时音响会发出巨响的问题

如果你上网搜“linux pop sound on shutdown”会发现许多发行版都存在这个问题。我这边的发行版是Fedora,机器是惠普的暗影精灵第一代。

我试了一下,关机或者重启前用将系统静音并不能解决问题,仍然会听到“砰”一声响。

Arch wiki给出的建议是新建这样一个modprobe配置(比如文件名是 /etc/modprobe.d/modprobe.conf ),里面写上

options snd_hda_intel power_save=0

试了一下居然奏效了。虽然不太明白为什么要这么做(Arch wiki上给的https://www.kernel.org/doc/Documentation/sound/alsa/powersave.txt直接404了) ,但是确实重启时听不到那吓人的“砰”声了。

Installing nvidia driver on Fedora 29

Forewords

Installing the nvidia driver on Fedora has been a painful experience for me. If I don’t get it wrong, I have been trying since F26!

I will not touch on bumblebee. I will instead use nvidia-xrun to utilize the driver.

This article serves as a reminder for myself on what did I do to make things work for my Intel/nvidia hybrid laptop. It might hopefully help other people as well.

继续阅读“Installing nvidia driver on Fedora 29”