H5游戏开发:贪吃蛇

  • 时间:2018-06-06 01:02 作者:广东IT优就业 来源:广东IT优就业 阅读:377
  • 扫一扫,手机访问
摘要:广东IT优就业贪吃蛇的经典玩法有两种:积分闯关一吃究竟第一种是小编小时候在掌上游戏机最先体验到的(不小心暴露了年龄),具体玩法是蛇吃完肯定数量的食物后就通关,通关后速度会加快;第二种是诺基亚在1997年在其自家手机上安装的游戏,它的玩法是吃到没食物为止。笔者要实现的就是第二种玩法。MVC设计模式基于

H5游戏开发:贪吃蛇

广东IT优就业

贪吃蛇的经典玩法有两种:

  1. 积分闯关

  2. 一吃究竟

第一种是小编小时候在掌上游戏机最先体验到的(不小心暴露了年龄),具体玩法是蛇吃完肯定数量的食物后就通关,通关后速度会加快;第二种是诺基亚在1997年在其自家手机上安装的游戏,它的玩法是吃到没食物为止。笔者要实现的就是第二种玩法。

MVC设计模式

基于贪吃蛇的经典,笔者在实现它时也用一种经典的设计模型:MVC(即:Model - View - Control)。游戏的各种状态与数据结构由 Model 来管理;View 使用于显示 Model 的变化;使用户与游戏的交互由 Control 完成(Control 提供各种游戏API接口)。

Model 是游戏的核心也是本文的主要内容;View 会涉及到部分性可以问题;Control 负责业务逻辑。 这样设计的好处是: Model完全独立,View 是 Model 的状态机,Model 与 View 都由 Control 来驱动。

Model

看一张贪吃蛇的经典图片。

H5游戏开发:贪吃蛇

广东IT优就业

web前台/H5/javascript学习群:250777811

欢迎关注此公众号→【web前台EDU】跟大佬一起学前台!欢迎大家留言探讨一起转发

贪吃蛇有四个关键的参加对象:

  1. 蛇(snake)

  2. 食物(food)

  3. 墙(bounds)

  4. 舞台(zone)

舞台是一个

m * n

的矩阵(二维数组),矩阵的索引边界是舞台的墙,矩阵上的成员使用于标记食物和蛇的位置。

空舞台如下:

[[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],]

食物(F)和蛇(S)出现在舞台上:

[[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,F,0,0,0,0,0,0,0],[0,0,0,S,S,S,S,0,0,0],[0,0,0,0,0,0,S,0,0,0],[0,0,0,0,S,S,S,0,0,0],[0,0,0,0,S,0,0,0,0,0],[0,0,0,0,S,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],]

因为操作二维数组不如一维数组方便,所以笔者用的是一维数组, 如下:

[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,F,0,0,0,0,0,0,0,0,0,0,S,S,S,S,0,0,0,0,0,0,0,0,0,S,0,0,0,0,0,0,0,S,S,S,0,0,0,0,0,0,0,S,0,0,0,0,0,0,0,0,0,S,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,]

舞台矩阵上蛇与食物只是舞台对二者的映射,它们彼此都有独立的数据结构:

  • 蛇是一串坐标索引链表;

  • 食物是一个指向舞台坐标的索引值。

蛇的活动

蛇的活动有三种,如下:

  • 移动(move)

  • 吃食(eat)

  • 碰撞(collision)

移动

蛇在移动时,内部发生了什么变化?

H5游戏开发:贪吃蛇

广东IT优就业

蛇链表在一次移动过程中做了两件事:向表头插入一个新节点,同时剔除表尾一个旧节点。使用一个数组来代表蛇链表,那么蛇的移动就是以下的伪代码:

function move(next) {snake.pop() & snake.unshift(next);}

数组作为蛇链表合适吗? 这是笔者最开始思考的问题,毕竟数组的

unshift & pop

能无缝表示蛇的移动。不过,方便不代表性可以好,

unshift

向数组插入元素的时间复杂度是 O(n),

pop

剔除数组尾元素的时间复杂度是 O(1)。

蛇的移动是一个高频率的动作,假如一次动作的算法复杂度为 O(n) 并且蛇的长度比较大,那么游戏的性可以会有问题。笔者想实现的贪吃蛇理论上讲是一条长蛇,所以笔者在本文章的回复是 ------ 数组不适合作为蛇链表。

蛇链表必需是真正的链表结构。 链表删除或者插入一个节点的时间复杂度为O(1),使用链表作为蛇链表的数据结构可以提高游戏的性可以。javascript 没有现成的链表结构,笔者写了一个叫 Chain 的链表类,

Chain

提供了

unshfit & pop

。以下伪代码是创立一条蛇链表:
let snake = new Chain();

吃食 & 碰撞

「吃食」与「碰撞」区别在于吃食撞上了「食物」,碰撞撞上了「墙」。笔者认为「吃食」与「碰撞」属于蛇一次「移动」的三个可可以结果的两个分支。蛇移动的三个可可以结果是:「前进」、「吃食」和「碰撞」。

回头看一下蛇移动的伪代码:

function move(next) {snake.pop() & snake.unshift(next);}

代码中的

next

表示蛇头即将进入的格子的索引值,只有当这个格子是

0

时蛇才可以「前进」,当这个格子是

S

表示「碰撞」自己,当这个格子是

F

表示吃食。

如同少了撞墙? 笔者在设计过程中,并没有把墙设计在舞台的矩阵中,而是通过索引出界的方式来表示撞墙。简单地说就是

next === -1

时表示出界和撞墙。

以下伪代码表示蛇的整上活动过程:

H5游戏开发:贪吃蛇

广东IT优就业

// B 表示撞墙let cell = -1 === next ? B : zone[next];switch(cell) { // 吃食case F: eat(); break; // 撞到自己case S: collision(S); break; // 撞墙case B: collision(B): break; // 前进default: move;}

随机投食

随机投食是指随机筛选舞台的一个索引值使用于映射食物的位置。这似乎很简单,能直接这样写:

// 伪代码food = Math.random(zone.length) >> 0;

假如考虑到投食的前提 ------ 不与蛇身重叠,你会发现上面的随机代码并不可以保证投食位置不与蛇身重叠。因为这个算法的安全性带有赌博性质,且把它称作「赌博算法」。为了保证投食的安全性,笔者把算法扩展了一下:

// 伪代码function feed() { let index = Math.random(zone.length) >> 0; // 当前位置能否被占使用return zone[index] === S ? feed() : index;}food = feed();

上面的代码尽管在理论上能保证投食的绝对安全,不过笔者把这个算法称作「不要命的赌徒算法」,由于上面的算法有致命的BUG ------ 超长递归 or 死循环。

为理解决上面的致命问题,笔者设计了下面的算法来做随机投食:

// 伪代码function feed() { // 未被占使用的空格数let len = zone.length - snake.length; // 无法投食if(len === 0) return ; // zone的索引let index = 0, // 空格计数器count = 0, // 第 rnd 个空格子是最终要投食的位置rnd = Math.random() * count >> 0 + 1; // 累计空格数while(count !== rnd) { // 当前格子为空,count总数增一zone[index++] === 0 && ++count; } return index - 1;}food = feed();

这个算法的平均复杂度为 O(n/2)。因为投食是一个低频操作,所以 O(n/2)的复杂度并不会带来任何性可以问题。不过,笔者觉得这个算法的复杂度还是有点高了。回头看一下最开始的「赌博算法」,尽管「赌博算法」很不靠谱,但是它有一个优势 ------ 时间复杂度为 O(1)。

「赌博算法」的靠谱概率 = (zone.length - snake.length) / zone.length。

snake.length

是一个动态值,它的变化范围是:

0 ~ zone.length

。推导出「赌博算法」的平均靠谱概率是:

「赌博算法」平均靠谱概率 = 50%

看来「赌博算法」还是能利使用一下的。于是笔者重新设计了一个算法:

// 伪代码function bet() { let rnd = Math.random() * zone.length >> 0; return zone[rnd] === 0 ? rnd : -1;}function feed() { ...}food = bet();if(food === -1) food = feed();

新算法的平均复杂度能有效地降低到 O(n/4),人生有时候需要点运气 : )。

View

在 View 能根据喜好选择一款游戏渲染引擎,笔者在 View 层选择了

PIXI

作为游戏游戏渲染引擎。

View 的任务主要有两个:

  1. 绘制游戏的界面;

  2. 渲染 Model 里的各种数据结构

也就是说 View 是用渲染引擎复原设计稿的过程。本文的目的是详情「贪吃蛇」的实现思路,如何用一个渲染引擎不是本文探讨的范畴,笔者想详情的是:「如何提高渲染的效率」。

在 View 中显示 Model 的蛇能简单地如以下伪代码:

// 清空 View 上的蛇view.snake.clean();model.snake.forEach( (node) => { // 创立 View 上的蛇节点let viewNode = createViewNode(node); // 并合一条新蛇 view.snake.push(viewNode); });

上面代码的时间复杂度是 O(n)。上面详情过蛇的移动是一个高频的活动,我们要尽量避免高频率地运行 O(n) 的代码。来分析蛇的三种活动:「移动」,「吃食」,「碰撞」。

首先,Model 发生了「碰撞」,View 应该是直接暂停渲染 Model 里的状态,游戏处在死亡状态,接下来的事由 Control 解决。

Model 中的蛇(链表)在一次「移动」过程中做了两件事:向表头插入一个新节点,同时剔除表尾一个旧节点;蛇(链表)在一次「吃食」过程中只做一件事:向表头插入一个新节点。

H5游戏开发:贪吃蛇

假如在 View 中对 Model 的蛇链表做差异化检查,View 只增量升级差异部分的话,算法的时间复杂度就可降低至 O(1) ~ O(2) 。以下是优化后的伪代码:

let snakeA = model.snake, snakeB = view.snake;// 增量升级尾部while(snakeB.length <= snakeA.length) { headA = snakeA.next(); // 头节点匹配if(headA.data === headB.data) break; // 不匹配else { // 向snakeB插入头节点if(snakeA.HEAD === headA.index) { snakeB.unshift(headA.data); } // 向snakeB插入第二个节点else snakeB.insertAfter(0, headA.data); }}// 增量升级头部 let tailA = snakeA.last(), tailB;while(snakeB.length !== 0) { tailB = snakeB.last(); // 尾节点匹配if(tailA.data === tailB.data) break; // 不匹配else snakeB.pop();}

Control

Control 主要做 3 件事:

  1. 游戏与使用户的互动

  2. 驱动 Model

  3. 同步 View 与 Model

「游戏与使用户的互动」是指向外提供游戏过程需要用到的 APIs 与 各类事件。笔者规划的 APIs 如下:

nametypedeltail
initmethod初始化游戏
startmethod开始游戏
restartmethod重新开始游戏
pausemethod暂停
resumemethod恢复
turnmethod控制蛇的转向。如:turn("left")
destroymethod销毁游戏
speedproperty蛇的移动速度

事件如下:

namedetail
countdown倒时计
eat吃到食物
before-eat吃到食物前触发
gameover游戏结束

事件统一挂载在游戏实例下的

event

对象下。

snake.event.on("countdown", (time) => console.log("剩余时间:", time));

「驱动 Model 」只做一件事 ------ 将 Model 的蛇的方向升级为使用户指定的方向。 「同步 View 与 Model 」也比较简单,检查 Model 能否有升级,假如有升级通知 View 升级游戏界面。

H5游戏开发:贪吃蛇

广东IT优就业

更多IT精彩推荐:

人人都要学的IT小技巧:http://xue.ujiuye.com/zt/renrenxue/

  • 全部评论(0)
最新发布的资讯信息
【系统环境|】淘码库,据消息称已被调查。淘码库源码网,已经无法访问!(2020-01-14 04:13)
【系统环境|服务器应用】Discuz隐藏后台admin.php网址修改路径(2019-12-16 16:48)
【系统环境|服务器应用】2020新网站如何让百度快速收录网站首页最新方法,亲测有用!免费(2019-12-16 16:46)
【系统环境|服务器应用】Discuz发布帖子时默认显示第一个主题分类的修改方法(2019-12-09 00:13)
【系统环境|软件环境】Android | App内存优化 之 内存泄漏 要点概述 以及 处理实战(2019-12-04 14:27)
【系统环境|软件环境】MySQL InnoDB 事务(2019-12-04 14:26)
【系统环境|软件环境】vue-router(单页面应用控制中心)常见用法(2019-12-04 14:26)
【系统环境|软件环境】Linux中的Kill命令(2019-12-04 14:26)
【系统环境|软件环境】Linux 入门时必学60个文件解决命令(2019-12-04 14:26)
【系统环境|软件环境】更新版ThreeJS 3D粒子波浪动画(2019-12-04 14:26)
手机二维码手机访问领取大礼包
返回顶部