改进版迷宫

以前曾经写过一个JavaScript版迷宫,生成迷宫的算法很简单,就是在一个空白迷宫中,让一个小人随机地行走,并记录下每个格子所通过的方向,直到地图上每个格子都到达过为止。

由这个算法生成的一个典型的迷宫如下:

最近重新玩这个迷宫游戏,总觉得有一些问题,简单来说就是岔路太少,即使有一些小岔路也经常能一眼看到头,于是经常很容易就能一次走到终点。仔细想一想,也不难理解,因为生成迷宫的方式是模拟一个小人随机行走,虽然这个小人会不断转弯,但很多时候他会走出一条很长的连续的道路。

找到了原因,改进也就简单了。我改进了一下生成算法,基本操作和原来一致,但不再是一个小人随机行走,而是每隔一段时间再随机地添加一个小人到地图中,这样便很容易产生比较长的岔路了。

一个典型的改进后的迷宫如下:

可以看到,新迷宫的岔路更多了,有几条岔路都比较长,并不能一眼看到终点,走这样的新迷宫,至少有一半的机率在第一个岔路就走错路。

当然,20*20 的地图还是稍小了一点,如果增大地图,对应的岔路也会更多,难度也会更大。

最后,放一下改进版迷宫的链接: https://oldj.net/static/maze2/

Advertisements

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

You are commenting using your WordPress.com account. Log Out /  更改 )

Google+ photo

You are commenting using your Google+ account. Log Out /  更改 )

Twitter picture

You are commenting using your Twitter account. Log Out /  更改 )

Facebook photo

You are commenting using your Facebook account. Log Out /  更改 )

Connecting to %s