"Snake"--H5 미니 게임 개발

php中世界最好的语言원래의: 2017-11-18 17:27:122026검색

오늘은 모두가 토론하고 공부할 수 있도록 H5로 만든 작은 게임을 공유하겠습니다. 아주 고전적인 게임인 Snake입니다. Snake를 플레이하는 방법에는 두 가지가 있습니다. 하나는 점수를 획득하여 레벨을 클리어하는 것이고, 다른 하나는 끝까지 먹는 것입니다.

첫 번째 구체적인 플레이 방법은 뱀이 일정량의 음식을 먹은 후 레벨을 클리어하고, 레벨을 통과한 후 속도가 빨라지는 것입니다. 두 번째 플레이 방법은 더 이상 음식이 없을 때까지 먹는 것입니다. 오늘 우리가 구현해 볼 것은 두 번째 플레이 방법입니다.

MVCDesign Pattern

클래식 Snake를 기반으로 구현 시에도 클래식 디자인 모델인 MVC(예: Model – View – Control)를 사용합니다. 게임의 다양한 상태와 데이터 구조는 Model에 의해 관리됩니다. View는 Model의 변경 사항을 표시하는 데 사용됩니다. Control은 다양한 게임 API 인터페이스를 제공합니다.

모델은 게임의 핵심이며 이 기사의 주요 내용에는 일부 성능 문제가 포함됩니다. 제어는 비즈니스 로직을 담당합니다. 이 디자인의 장점은 모델이 완전히 독립적이고, 뷰가 모델의 상태 머신이며, 모델과 뷰가 모두 제어에 의해 구동된다는 것입니다.

모델

욕심 많은 뱀의 고전적인 사진을 보세요.

Snake에는 4개의 주요 참여자가 있습니다:

snake

food

walls

zone

단계는 m * n 행렬(2차원 배열)이며, 행렬의 인덱스 경계는 다음과 같습니다. 무대 벽면과 매트릭스 위의 멤버들을 이용해 음식과 뱀의 위치를 표시한다.

빈 무대는 다음과 같습니다.

[
[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],
]

2차원 배열을 조작하는 것이 1차원 배열만큼 편리하지 않기 때문에 저는 다음과 같이 1차원 배열을 사용합니다.

[
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,
]

스테이지 매트릭스의 뱀과 음식은 둘에 대한 매핑일 뿐입니다. 그들은 독립적인 데이터 구조를 가지고 있습니다.

스네이크는 좌표 인덱스의 연결된 목록입니다. food는 무대 좌표를 가리키는 인덱스 값입니다.

뱀의 활동

뱀의 세 가지 활동은 다음과 같습니다.

Move

Eat

Collision

Move

뱀이 움직일 때 내부에서는 무슨 일이 일어날까요?

스네이크 연결 목록은 한 번의 이동 중에 두 가지 작업을 수행합니다. 즉, 테이블 헤드에 새 노드를 삽입하고 테이블 끝에 있는 이전 노드를 삭제하는 것입니다. 스네이크 연결 리스트를 배열로 표현하면 스네이크의 움직임은 다음과 같은 의사 코드가 됩니다.

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

배열이 스네이크 연결 리스트로 적합한가요?

이것이 제가 생각한 첫 번째 질문입니다. 결국 배열의 unshift & pop은 뱀의 움직임을 완벽하게 표현할 수 있습니다. 그러나 편리하다고 해서 배열에 요소를 삽입하는 unshift의 시간 복잡도는 O(n)이고, 배열의 꼬리 요소를 제거하는 pop의 시간 복잡도는 O(1)입니다.

뱀의 움직임은 빈도가 높은 동작입니다. 동작의 알고리즘 복잡도가 O(n)이고 뱀의 길이가 상대적으로 길면 게임 성능에 문제가 발생합니다. 제가 실현하고 싶은 탐욕스러운 뱀은 이론적으로 긴 뱀입니다. 따라서 이 기사에 대한 나의 답변은 - 배열은 뱀 연결 목록으로 적합하지 않습니다.

스네이크 연결리스트는 실제 연결리스트 구조여야 합니다.

링크드 리스트에서 노드를 삭제하거나 삽입하는 시간 복잡도는 O(1)입니다. 링크드 리스트를 스네이크 링크드 리스트의 데이터 구조로 사용하면 게임 성능을 향상시킬 수 있습니다.

javascript

미리 만들어진 연결 목록 구조가 없습니다. 체인이 unshfit & pop을 제공하는 연결 목록 클래스를 작성했습니다. 다음 의사 코드는 스네이크 연결 목록을 생성합니다.

let snake = new Chain();

공간 문제로 인해 여기에서는 체인 구현 방법을 소개하지 않습니다. 관심 있는 학생들은 https://github.com/leeenx/es6-utils#chain

을 방문하세요.

Eating & Collision

"먹는 것"과 "충돌"의 차이점은 먹는 것이 "음식"에 부딪히고 충돌이 "벽"에 부딪힌다는 것입니다. 나는 "먹는 것"과 "충돌하는 것"이 뱀의 "움직임"의 세 가지 가능한 결과 중 두 가지라고 생각합니다. 뱀이 움직일 때 가능한 세 가지 결과는 "전진", "먹기", "충돌"입니다.

뱀 이동에 대한 의사코드를 다시 살펴보세요.

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

코드의 다음은 뱀의 머리가 들어가려는 그리드의 인덱스 값을 나타냅니다. 이 그리드가 0일 때만 뱀이 "앞으로" 갈 수 있습니다. 그리드가 S이면 '충돌'을 의미합니다. 여러분 스스로 이 그리드가 F이면 먹는 것을 의미합니다.

벽에 부딪히는 일이 덜한 것 같나요?

디자인 과정에서는 무대의 매트릭스에 벽을 디자인하지 않고 대신 경계를 벗어나서 벽에 부딪히는 모습을 표현했습니다. 간단히 말해서 next === -1은 경계를 벗어나 벽에 부딪히는 것을 의미합니다.

다음 의사 코드는 뱀의 전체 활동 과정을 나타냅니다.

// 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;
}

Random Feeding

Random Feeding은 스테이지의 인덱스 값을 무작위로 선택하여 먹이의 위치를 매핑하는 것을 의미합니다. 다음과 같이 작성하면 충분히 간단해 보입니다.

// 伪代码
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%

看来「赌博算法」还是可以利用一下的。于是我重新设计了一个算法：

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

View

在 View 可以根据喜好选择一款游戏渲染引擎，我在 View 层选择了 PIXI 作为游戏游戏渲染引擎。

View 的任务主要有两个：

绘制游戏的界面；

渲染 Model 里的各种数据结构

也就是说 View 是使用渲染引擎还原设计稿的过程。本文的目的是介绍「贪吃蛇」的实现思路，如何使用一个渲染引擎不是本文讨论的范畴，我想介绍的是：「如何提高渲染的效率」。

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

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

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

Model 中的蛇（链表）在一次「移动」过程中做了两件事：向表头插入一个新节点，同时剔除表尾一个旧节点；蛇（链表）在一次「吃食」过程中只做一件事：向表头插入一个新节点。

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

Control

Control 主要做 3 件事：

游戏与用户的互动

驱动 Model

同步 View 与 Model

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

name

type

deltail

init method 初始化游戏

start method 开始游戏

restart method 重新开始游戏

pause method 暂停

resume method 恢复

turn method 控制蛇的转向。如：turn(“left”)

destroy method 销毁游戏

speed property 蛇的移动速度

事件如下：

name

detail

countdown 倒时计

eat 吃到食物

before-eat 吃到食物前触发

gameover 游戏结束

事件统一挂载在游戏实例下的 event 对象下。

「驱动 Model 」只做一件事 —— 将 Model 的蛇的方向更新为用户指定的方向。

「同步 View 与 Model 」也比较简单，检查 Model 是否有更新，如果有更新通知 View 更新游戏界面。

以上就是用H5做贪吃蛇小游戏的全部步奏，有兴趣的朋友可以深度研究一下。

"Snake"--H5 미니 게임 개발

관련 기사