游戏开发,一个整数是否是

2019-09-11 16:05栏目:人才招聘
TAG:

H5 游戏开发:游戏引擎入门推荐

2017/12/28 · HTML5 · 1 评论 · 游戏引擎

原文出处: 凹凸实验室   

图片 1

H5 游戏开发:推金币

2017/11/10 · HTML5 · 1 评论 · 游戏

原文出处: 凹凸实验室   

近期参与开发的一款「京东11.11推金币赢现金」(已下线)小游戏一经发布上线就在朋友圈引起大量传播。看到大家玩得不亦乐乎,同时也引发不少网友激烈讨论,有的说很带劲,有的大呼被套路被耍猴(无奈脸),这都与我的预期相去甚远。在相关业务数据呈呈上涨过程中,曾一度被微信「有关部门」盯上并要求做出调整,真是受宠若惊。接下来就跟大家分享下开发这款游戏的心路历程。

别人家的面试题:一个整数是否是“4”的N次幂

2016/05/30 · 基础技术 · 2 评论 · 算法

本文作者: 伯乐在线 - 十年踪迹 。未经作者许可,禁止转载!
欢迎加入伯乐在线 专栏作者。

这是 leetcode.com 的第二篇。与上一篇一样,我们讨论一道相对简单的问题,因为学习总讲究循序渐进。而且,就算是简单的问题,追求算法的极致的话,其中也是有大学问的。

前言

很多刚刚接触到游戏开发,准备大展拳脚的小鲜肉们,往往在技术选型这第一关就栽了跟头。毕竟网络上的游戏引擎良莠不齐,官网上相关资料也比较少,而选择一个适合的游戏引擎是一个项目最基础,也是很核心的一部分。
试想一下,在游戏开发进行到中后期的时候,才发现项目引入的游戏引擎与需求相悖,这时候不管是重新做一些修修补补的工作或者更换游戏引擎,这都是相当耗费人力物力的一件事。为了避免这种情况的出现,在前期选择适合项目需求的游戏引擎显得尤为重要。
接下来我们来聊一聊如何去选择适合项目的 JS 游戏引擎。

背景介绍

一年一度的双十一狂欢购物节即将拉开序幕,H5 互动类小游戏作为京东微信手Q营销特色玩法,在今年预热期的第一波造势中,势必要玩点新花样,主要肩负着社交传播和发券的目的。推金币以传统街机推币机为原型,结合手机强大的能力和生态衍生出可玩性很高的玩法。

“4”的整数次幂

给定一个32位有符号整数(32 bit signed integer),写一个函数,检查这个整数是否是“4”的N次幂,这里的N是非负整数。

例如:

  • 给定 num = 16,返回 true,因为 16 = 42
  • 给定 num = 5,返回 flase

附加条件: 你能够不用循环和递归吗?

游戏场景分类

在刚接到游戏需求时,我们可以从以下几个方面进行考量,分析出游戏需求场景所属,从而作为我们选择游戏引擎的依据。

  • 游戏效果呈现方式( 2D ? 3D ? VR ?)
    这与游戏引擎能够支持的渲染方式直接挂钩。现在的 H5 游戏渲染方式一般有 2D 渲染、3D 渲染、VR 渲染三种。
    而 2D 渲染一般也有三种:Dom 渲染、Canvas 渲染、WebGL 渲染。Dom 由于性能原因,一般只适合做一些动画效果较少,交互较少的小游戏,本文主要针对 Canvas 和 WebGL 展开介绍。
    一般来说,对于 2D 小游戏来说,Canvas 渲染已经足够。然而 Canvas 渲染由于底层封装层次多,不足以支撑起大型游戏的性能要求,因此大型游戏最好选择 WebGL 渲染或者浏览器内嵌 Runtime 。
  • 游戏复杂度
    这与游戏引擎能够支持的功能,提供的API,性能等方面关系比较大。

前期预研

在体验过 AppStore 上好几款推金币游戏 App 后,发现游戏核心模型还是挺简单的,不过 H5 版本的实现在网上很少见。由于团队一直在做 2D 类互动小游戏,在 3D 方向暂时没有实际的项目输出,然后结合此次游戏的特点,一开始想挑战用 3D 来实现,并以此项目为突破口,跟设计师进行深度合作,抹平开发过程的各种障碍。

图片 2

由于时间紧迫,需要在短时间内敲定方案可行性,否则项目延期人头不保。在快速尝试了 Three.js + Ammo.js 方案后,发现不尽人意,最终因为各方面原因放弃了 3D 方案,主要是不可控因素太多:时间上、设计及技术经验上、移动端 WebGL 性能表现上,主要还是业务上需要对游戏有绝对的控制,加上是第一次接手复杂的小游戏,担心项目无法正常上线,有点保守,此方案遂卒。

如果读者有兴趣的话可以尝试下 3D 实现,在建模方面,首推 Three.js ,入手非常简单,文档和案例也非常详实。当然入门的话必推这篇 Three.js入门指南,另外同事分享的这篇 Three.js 现学现卖 也可以看看,这里奉上粗糙的 推金币 3D 版 Demo

解题思路

如果忽略“附加条件”,这题还挺简单的对吧?简直是信手拈来:

版本1

JavaScript

function isPowerOfFour(num){ while(!(num % 4)){ num /= 4; } return num === 1; }

1
2
3
4
5
6
function isPowerOfFour(num){
    while(!(num % 4)){
        num /= 4;
    }
    return num === 1;
}

版本1 好像很简单、很强大的样子,它的时间复杂度是 log4N。有同学说,还可以做一些微小的改动:

版本1.1

JavaScript

function isPowerOfFour(num){ while(!(num % 4)){ num >>>= 2; } return num === 1; }

1
2
3
4
5
6
function isPowerOfFour(num){
    while(!(num % 4)){
      num >>>= 2;
    }
    return num === 1;
}

上面的代码用位移替代除法,在其他语言中更快,鉴于 JS 通常情况下非常坑的位运算操作,不一定速度能变快。

好了,最关键的是,不管是 版本1 还是 版本1.1 似乎都不满足我们前面提到的“附加条件”,即不使用循环和递归,或者说,我们需要寻找 O(1) 的解法。

按照惯例,大家先思考10秒钟,然后往下看 ——


游戏引擎推荐

笔者从业界较流行的一些框架,进行以下几个方面对比,希望能从客观数据上给大家的技术选型带来建议和参考。

  • 引擎支持的渲染方式
  • github上的 star 数
  • 更新时间
  • 文档详细度
  • 周边产品

2D,3D,VR 都支持的游戏引擎

name 2D渲染(Canvas) 2D渲染(WebGL) 3D渲染(WebGL) VR github star 数 文档详细程度 周边产品 备注
Egret YES YES YES YES 2k(最新更新2017.12)
▪ 有中文文档
▪ 例子充足
▪ 社区活跃
游戏开发过程中的每个环节基本都有工具支撑。 不仅仅提供了一个基于HTML5技术的游戏引擎,更是提供了原生打包工具和众多周边产品
LayaAir YES YES(优先) YES YES 0.7k(最新更新2017.12)
▪ 有中文文档
▪ 例子充足
▪ 社区活跃
提供开发工具和可视化编辑器 支持2D、3D、VR,能开发超大游戏,forgame的醉西游,腾讯的QQ农场,乐动卓越的浪漫h5这些大作就是用它开发

技术选型

放弃了 3D 方案,在 2D 技术选型上就很从容了,最终确定用 CreateJS + Matter.js 组合作为渲染引擎和物理引擎,理由如下:

  • CreateJS 在团队内用得比较多,有一定的沉淀,加上有老司机带路,一个字「稳」;
  • Matter.js 身材纤细、文档友好,也有同事试玩过,完成需求绰绰有余。

不用循环和递归

其实这道题真心有好多种思路,计算指数之类的对数学系学霸们完全不是问题嘛:

版本2

JavaScript

const log4 = Math.log(4); function isPowerOfFour(num){ var n = Math.log(num) / log4; return n === (0|n); }

1
2
3
4
5
const log4 = Math.log(4);
function isPowerOfFour(num){
    var n = Math.log(num) / log4;
    return n === (0|n);
}

嗯,通过对数公式 logm(n) = log(n) / log(m) 求出指数,然后判断指数是不是一个整数,这样就可以不用循环和递归解决问题。而且,还要注意细节,可以将 log4 当做常量抽取出来,这样不用每次都重复计算,果然是学霸范儿。

不过呢,利用 Math.log 方法也算是某种意义上的犯规吧,有没有不用数学函数,用原生方法来解决呢?

当然有了!而且还不止一种,大家可以继续想30秒,要至少想出一种哦 ——


Egret

图片 3

Egret 周边产品

白鹭引擎是企业级游戏引擎,有团队维护。Egret 在工作流的支持上做的是比较好的,从 Wing 的代码编写,到 ResDepot 和 TextureMerger 的资源整合,再到 Inspector 调试,最后到原生打包(支持 APP 打包),游戏开发过程中的每个环节基本都有工具支撑。官网上的示例,教程也是比较多。值得一提的是,今年5月白鹭引擎支持了 WebAssembly ,这对于性能的提升又是一大里程碑。

技术实现

因为是 2D 版本,所以不需要建各种模型和贴图,整个游戏场景通过 canvas 绘制,覆盖在背景图上,然后再做下机型适配问题,游戏主场景就处理得差不多了,其他跟 3D 思路差不多,核心元素包含障碍物、推板、金币、奖品和技能,接下来就分别介绍它们的实现思路。

不用内置函数

这个问题的关键思路和上一道题类似,先考虑“4”的幂的二进制表示:

  • 40 = 1B
  • 41 = 100B
  • 42 = 10000B
  • 43 = 1000000B
  • ……

也就是每个数比上一个数的二进制后面多两个零嘛。最重要的是,“4”的幂的二进制数只有 1 个“1”。如果仔细阅读过上一篇,你就会知道,判断一个二进制数只有 1 个“1”,只需要:

JavaScript

(num & num - 1) === 0

1
(num & num - 1) === 0

但是,二进制数只有 1 个“1”只是“4”的幂的必要非充分条件,因为“2”的奇数次幂也只有 1 个“1”。所以,我们还需要附加的判断:

JavaScript

(num & num - 1) === 0 && (num & 0xAAAAAAAA) === 0

1
(num & num - 1) === 0 && (num & 0xAAAAAAAA) === 0

为什么是 num & 0xAAAAAAAA === 0? 因为这个确保 num 的二进制的那个 “1” 出现在“奇数位”上,也就确保了这个数确实是“4”的幂,而不仅仅只是“2”的幂。

最后,我们得到完整的版本:

版本3

JavaScript

function isPowerOfFour(num) { return num > 0 && (num & (num-1)) === 0 && (num & 0xAAAAAAAA) === 0; };

1
2
3
4
function isPowerOfFour(num) {
    return num > 0 && (num & (num-1)) === 0
                   && (num & 0xAAAAAAAA) === 0;
};

上面的代码需要加上 num > 0,是因为 0 要排除在外,否则 (0 & -1) === 0 也是 true


LayaAir

在渲染模式上,LayaAir 支持 Canvas 和 WebGL 两种方式;在工具流的支持程度上,主要是提供了 LayaAir IDE。LayaAir IDE 包括代码模式与设计模式,支持代码开发与美术设计分离,内置了 SWF 转换、图集打包、JS 压缩与加密、APP 打包、Flash 发布等实用功能。

下图是主要支持2D游戏的游戏引擎

name 2D渲染(Canvas) 2D渲染(WebGL) 3D渲染(WebGL) VR github star 数 文档详细程度 周边产品 备注
Pixi.js YES YES NO NO 16.8k(最新更新2017.12)
▪ 英文文档
▪ 例子充足
▪ 英文社区
依赖于canvas的WebGL渲染器
Phaser YES YES NO NO 16.9k(最新更2017.07)
▪ 英文文档
▪ 例子充足
▪ 英文社区
提供在线编辑器Phaser Sandbox
CreateJs YES YES NO NO 6.5k(最新更新2017.12)
▪ 英文文档
▪ 例子充足
▪ 有博客
官方推荐TweenJS,SoundJS,PreloadJS配合使用
Hilo YES YES YES(Hilo3D) NO 4.2k(最新更新2017.12)
▪ 有中文文档
▪ 例子充足
提供资源下载和管理工具 阿里巴巴集团推出,适合开发营销小游戏,以Chipmunk为2D物理引擎,与主流物理引擎兼容
Cocos2d-x YES YES NO NO 11.2k(最新更新2017.12)
▪ 有中文文档
▪ js例子不多,c++例子较多
▪ 社区活跃
Cocos Creator编辑器,打包工具等 提供的功能相当完整
lufylegend.js YES NO NO NO 0.4k(最新更新2016.03)
▪ 有中文文档
▪ 社区活跃
仿ActionScript3.0的语法,支持Google Chrome,Firefox,Opera,IE9,IOS,Android等多种热门环境,可以配合Box2dWeb制作物理游戏,内置了LTweenLite缓动类等

障碍物

通过审稿确定金币以及奖品的活动区域,然后把活动区域之外的区域都作为障碍物,用来限制金币的移动范围,防止金币碰撞时超出边界。这里可以用 Matter.js 的 Bodies.fromVertices 方法,通过传入边界各转角的顶点坐标一次性绘制出形状不规则的障碍物。 不过 Matter.js 在渲染不规则形状时存在问题,需要引入 poly-decomp 做兼容处理。

图片 4

JavaScript

World.add(this.world, [ Bodies.fromVertices(282, 332,[ // 顶点坐标 { x: 0, y: 0 }, { x: 0, y: 890 }, { x: 140, y: 815 }, { x: 208, y: 614 }, { x: 548, y: 614 }, { x: 612, y: 815 }, { x: 750, y: 890 }, { x: 750, y: 0 } ]) ]);

1
2
3
4
5
6
7
8
9
10
11
12
13
World.add(this.world, [
  Bodies.fromVertices(282, 332,[
    // 顶点坐标
    { x: 0, y: 0 },
    { x: 0, y: 890 },
    { x: 140, y: 815 },
    { x: 208, y: 614 },
    { x: 548, y: 614 },
    { x: 612, y: 815 },
    { x: 750, y: 890 },
    { x: 750, y: 0 }
  ])
]);

其他版本

上面的版本已经符合了我们的需求,时间复杂度是 O(1),不用循环和递归。

此外,我们还可以有其他的版本,它们严格来说有的还是“犯规”,但是我们还是可以学习一下这些思路:

版本4:用 Math.sqrt

JavaScript

function isPowerOfFour(num) { num = Math.sqrt(num); return num > 0 && num === (0|num) && (num & (num-1)) === 0; };

1
2
3
4
function isPowerOfFour(num) {
    num = Math.sqrt(num);
    return num > 0 && num === (0|num) && (num & (num-1)) === 0;
};

版本5:用正则表达式

JavaScript

function isPowerOfFour(num) { return /^1(00)*$/g.test(num.toString(2)); };

1
2
3
function isPowerOfFour(num) {
    return /^1(00)*$/g.test(num.toString(2));
};

以上就是所有的内容,这道题有非常多种思路,相当有趣,也比较考验基本功。如果你有自己的思路,可以留言参与讨论。

下一期我们讨论另外一道题,这道题比这两道题要难一些,但也更有趣:给定一个正整数 n,将它拆成至少两个正整数之和,对拆出的正整数求乘积,返回能够得到的乘积最大的结果

想一想你的解法是什么?你能够尽可能减少算法的时间复杂度吗?期待你的答案~~

打赏支持我写出更多好文章,谢谢!

打赏作者

版权声明:本文由ag真人发布于人才招聘,转载请注明出处:游戏开发,一个整数是否是