JavaScript写的网页迷宫游戏

曾经做过一个JavaScript版的网页迷宫游戏,从生成地图到操作全是用JavaScript在浏览器端完成的,有兴趣的同学可以右键查看网页源代码,最关键的代码为 mg.js ,近 400 行。

有不少朋友问我,这个迷宫是怎么实现的,考虑到自己去读源码是有点累,我就大概写一下这个迷宫游戏的实现思路。我的实现不是最高效的,仅供感兴趣的同学讨论研究。:-)

这一个迷宫是基于平面上的方格的,每一个格子有上、下、左、右四个方向,每个方向上可能有墙(不能通过),也可能没墙(可以通过)。这样,每个格子实际上就有 16 种可能的状态,我们用 0 ~ 15 来给每一种状态编一个号。如下图所示。

注意,上面的编号并不是随意的。由于每个格子有四条边,每个边有两种状态(可通过与不可通过),如果我们用 0 表示某一条边不可通过,1 表示可通过,这样,四条边的状态就能组成一个四位的二进制数。我们把四条边按从上方开始按顺时针方向的上、右、下、左四个方向的状态分别代表二进制数的个、十、百、千位的话,得到的二进制数的十进制值就作为这个格子的编号。如下图所示。

这样做有什么好处呢?首先,我们只要用一个 0 ~ 15 之间的数字就能表示某个格子的状态了,便于地图数据的存储。另外,更重要的是,对于任意一个格子,我们要判断它的某个方向是否可通过时,只需要做一个简单的按位与,看结果是否为 0 就可以了。

如上面所说,我们的上、右、下、左四个方向分别代表这个二进制数的个、十、百、千位,即:

  • 上:0001,即十进制 1
  • 右:0010,即十进制 2
  • 下:0100,即十进制 4
  • 左:1000,即十进制 8

我们要判断某个格子(比如它的状态是 6)的上方是否可通过时,只要计算:

6 & 1 = 0,可知上方不可通过,类似地,想知道它的右方是否可通过时,只要计算:6 & 2 = 2,可知右方可以通过。

这样,当确定了迷宫地图的宽与高时,我们只需要一个简单的一维数组,每一项的值为 0 ~ 15 之间的整数,就足以记录这个迷宫的地图信息,并且能很方便高效地判断每个格子某个方向的可通过性。

确定了地图的表示方法,接下来的问题就是怎么生成地图。在这个游戏中,生成地图的方法比较简单:从某个格子开始,随机地遍历周边的未到达过的格子,如周边没有没到达过的格子了则后退一步,如地图上所有点都已到达则遍历完成,地图也就生成了。见下面的流程图。

这个过程,实际上就相当于一个人先随机地在地图上走一遍,并且把他走过的地方标记为可通过。这样就保证了地图上每一个格子都是连通的(任意一个格子总有某一条路能到达),并且保证有且仅有一条路可以从起点连到终点(事实上,地图上任意两个格子之间都有且仅有一条路相连)。

最终生成的迷宫就类似于下图的样子。当然,地图每次都是随机生成的,你看到的迷宫和我看到的会不一样。地图上的格子全是用 div + css 堆出来的,呵呵。

另外,这个算法生成的迷宫属于单连通迷宫,这类迷宫都有一个通用的简单解法“扶墙法”,即从起点开始,伸出一只手(左手右手都可以,看个人喜好)扶住墙壁,接下来就一直沿着这一边的墙走,无论转弯还是直走,都要保证这只手不要离开墙,这样虽然走的路线很可能不是最短的,但是能保证让你到达终点。

只生成地图,显然趣味性还不够,于是我又添加了一个小头像,再用了一个 jQuery 的键盘事件插件(js-hotkeys)接收按键事件控制小头像的移动,这样就差不多可以玩了。

然后,为了让游戏更加生动,我又为小头像加了一些状态,比如如果你进入页面几秒钟后还没有按方向键,它会弹出一个提示框告诉你操作方法,当你走到三面环墙的死胡同时它会说“哎呀……”,当你好一会儿没有操作了,它会说“Hello?”提醒你,走到终点时它会变成一个开心的笑脸并且欢呼。

最后,再贴一下这个迷宫游戏的游玩地址:https://oldj.net/static/maze/maze.html 。:-)

后续:

分类:编程标签:算法网页游戏迷宫JavaScript

相关文章:

评论:

pf_miles

相当漂亮

Allen.M

很好很强大

山哥

牛淫...

怿飞

挺有趣的游戏,不过代码中的MG.prototype.init 有严重性能问题,不消失输入了200200,基本浏览器就挂了。看了代码,基本仅用来做占位用,可以直接 this.grids[this.wthis.y -1]

oldj

的确是这样,已经改进了,多谢。:-)
目前生成大地图时性能上最大的瓶颈在于有一个很费时的 while 循环(随机遍历地图上每一个格子),生成大地图时浏览器失去响应主要是这个循环造成的。貌似要优化的话得换一种高效的算法,或者把这个 while 循环切成多个小循环,每两个小循环之间休息一段时间,避免浏览器完全失去响应。

怿飞

_showByDOM方法中的循环同样可以简化,并用 fragement 来存储 DOM片段,防止DOM的 reflow 的开销:var fragement = document.createDocumentFragment(), len = this.w * this.h;for(var i = 0; i < len ; i++) { tmp_ob = document.createElement("div"); ... tmp_ob.style.left = this.grid_size * (i% this.w) + "px"; tmp_ob.style.top = this.grid_size * Math.floor(i/ this.w) + "px"; v = this.grids[i]; MG.border(tmp_ob, v); ... fragement.appendChild(tmp_ob);} this.ob.appendChild(fragement);

oldj

感谢怿飞,不但指出我代码中的性能问题,还给出了如何改进的代码片断!
之前我只想着如何实现,在性能优化上考虑得比较少,多谢指教,已经按你的方案改进了。:-)

怿飞

_showByDOM方法改进后,基本生成DOM的效率比原来提升了一倍多

oldj

身经百战果然不一样啊,对代码效率的追求简直要达到极致了。接下来要多多向你们学习。:-)

cuixiping

很久以前,就知道三思迷宫了,非常佩服,昨天竟然无意中走进这个blog,原来是迷宫的作者,原来那个塔防游戏也是你的作品!我对js game也颇有兴趣,希望以后多交流。

oldj

呵呵,你那个 RectWiper 游戏我之前好像也玩过。多交流!:-)

cuixiping

关于生成大地图,脚本运行容易超时的问题,可以每循环多少次之后就setTimeout回调并break出来(记录一些循环中的变量值快照,下次“断点续传”),我曾经在做扫雷的时候用过这方法,生成超大的地图都只是时间问题,而不会假死。

oldj

嗯,貌似这是最好的办法了,下次如果要在浏览器里写大循环时得考虑这样的方法。要是 js 里有 sleep 方法该多好!

ninstein

来来来,webworker

新号外

有意思,哈哈。。。

freerabit

生成地图的算法很不错,不仅可以用于迷宫,还可以用于更多种类的游戏

skip

游戏页面打不开了,

oldj

嗯,那个链接失效了,稍后我会更新一下。

skip

THK , 想看一下源码学习下。

oldj

链接更新了。:)

star

真棒!!!!!

Saintjohn

距离初版发布已经12年了啊

这些年每隔几年都会拿出来玩一下,真是太好玩了

希望博主能继续更新,上架steam或其他方式收费以激励开发,我愿意付费购买

发表评论: