金沙国际官网_金沙国际平台登录

因为这个金沙国际官网_金沙国际平台登录网站与很多的大型澳门赌场都有合作,金沙国际官网_金沙国际平台登录尽职尽责,高效执行,保持好奇心,不断学习,追求卓越,点击进入金沙国际官网_金沙国际平台登录马上体验吧,所以现在也正式地开始了营业。

您的位置:金沙国际官网 > web前端 > H5游戏开发,移动端H5音频与视频问题及解决方案

H5游戏开发,移动端H5音频与视频问题及解决方案

发布时间:2019-10-25 15:34编辑:web前端浏览(115)

    十大经典排序算法

    2016/09/19 · 基础技术 · 7 评论 · 排序算法, 算法

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

    H5游戏开发:一笔画

    2017/11/07 · HTML5 · 游戏

    原文出处: 凹凸实验室   

    图片 1

    移动端H5音频与视频问题及解决方案

    2015/09/16 · HTML5 · 1 评论 · 视频, 音频

    原文出处: Aaron的博客   

    最近在研究用视频代替动画,已经初步有成果了,顺便总结下几年开发中遇到的实际问题及给出自己的解决方案

    看下最后实际效果:兼容PC,iphone, 安卓5.0

    解决了,手动,自动,不全屏的问题

    左边视频代替了动画,然后支持背景蒙板效果,能够透出底图

    右边是原视频文件

    图片 2

    H5 audio音频

    • 每次通过 new Audio 一个音频对象,在IOS上可以看到会产生一个新的线程,这个很恶心

    解决方案:

    new Audio一个对象,通过替换不同的音频地址,达到不多开线程的目的

    • 在安卓上支持不给力

    解决方案:

    低版本安卓上的问题没解,一般是混合开发都是可以调底层接口处理的,比如 phonegap

    • iphone上不能自动播放

    解决方案:

    iphone上自动播放,是IOS设计的的时候做的一个处理,貌似是为了防止自动盗用流量吧

    简单来说,需要模拟用户手动去触发才可以

    所以我们需要在最开始调用这样一段代码:

    这是我项目上的,我就直接扣过来了

    JavaScript

    //修复ios 浏览器不能自动播放音频的问题 在加载时创建新的audio 用的时候更换src即可 Xut.fix = Xut.fix||{}; if (Xut.plat.isBrowser && Xut.plat.isIOS) { var isAudio = false var fixaudio = function() { if (!isAudio) { isAudio = true; Xut.fix.audio = new Audio(); document.removeEventListener('touchstart', fixaudio, false); } }; document.addEventListener('touchstart', fixaudio, false); }

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    //修复ios 浏览器不能自动播放音频的问题 在加载时创建新的audio 用的时候更换src即可
    Xut.fix = Xut.fix||{};
    if (Xut.plat.isBrowser && Xut.plat.isIOS) {
        var isAudio = false
        var fixaudio = function() {
            if (!isAudio) {
                isAudio = true;
                Xut.fix.audio = new Audio();
                document.removeEventListener('touchstart', fixaudio, false);
            }
        };
        document.addEventListener('touchstart', fixaudio, false);
    }

    假如在body上绑定这样一个代码:通过手动触发创建一个audio对象,然后保存在全局中

    在使用的时候如下

    JavaScript

    //如果为ios browser 用Xut.fix.audio 指定src 初始化见app.js if (Xut.fix.audio) { audio = Xut.fix.audio; audio.src = url; } else { audio = new Audio(url); } audio.autoplay = true; audio.play();

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    //如果为ios browser 用Xut.fix.audio 指定src 初始化见app.js
    if (Xut.fix.audio) {
        audio
    =
    Xut.fix.audio;
        audio.src = url;
    } else {
        audio = new Audio(url);
    }
    audio.autoplay = true;
    audio.play();

    直接替换音频对象即可,简单来说,就是要自动就必须是用户触发创建的对象才能播

    H5 video音频

    视频标签可能在移动端用的很少,安卓支持太烂了,目测5.0才好转

    iphone上老问题,不能自动播放(省流量啊,省你妹!!!),并且默认就是全屏控件播放

    很长一段时间里,我都没理会这个视频处理,安卓用底层,iphone直接用VideoJS,内置flash与h5切换的,flash也有支持问题

    前阵子老板有个需求,我们应用动画太多了,都是精灵路线的组合动画,一个app下来上百M 到几百M不等

    所以急需有一个方案可以压缩图片

    最后的方案是采用视频代替动画,因为视频压缩技术发展了很多年,已经十分成熟了。现在视频压缩技术,能够很轻松地将720P的

    高清电影,压缩到10M/分钟,或者160K/秒。比图像序列的文件尺寸,至少小了几十倍。同时,在于大部分设备,都支持对视频的

    硬件解压缩,这样呢,视频播放的CPU消耗很低,电池消耗也很低,同时播放速度还快。即使25帧的全屏幕播放,也能轻易地实

    现。

    方案定下来,需要解决的几个问题就来了

    1. 整个视频,包括视频中的某些物体,能够响应用户的点击、滑动之类的操作
    2. 在iPhone下面,可以在一个窗口中播放
    3. 能够过滤掉背景,从而能像PNG图像一样运用

    最后的实际效果也是开始gif动画所示:

    视频代替了动画,然后支持背景蒙板效果,能够透出底图

    同时也解决了,手动,自动,不全屏的问题

    iphone窗口化

    解决方案:

    通过canvas + video标签结合处理

    原理: 获取video的原图帧,通过canavs绘制到页面

    这里我直接附上源码把,代码写的一般,但是突出了几个重点

    1 赞 2 收藏 1 评论

    图片 3

    前言

    读者自行尝试可以想看源码戳这,博主在github建了个库,读者可以Clone下来本地尝试。此博文配合源码体验更棒哦

    • 这世界上总存在着那么一些看似相似但有完全不同的东西,比如雷锋和雷峰塔,小平和小平头,玛丽和马里奥,Java和javascript….当年javascript为了抱Java大腿恬不知耻的让自己变成了Java的干儿子,哦,不是应该是跪舔,毕竟都跟了Java的姓了。可如今,javascript来了个咸鱼翻身,几乎要统治web领域,Nodejs,React Native的出现使得javascript在后端和移动端都开始占有了一席之地。可以这么说,在Web的江湖,JavaScript可谓风头无两,已经坐上了头把交椅。
    • 在传统的计算机算法和数据结构领域,大多数专业教材和书籍的默认语言都是Java或者C/C+ +,O’REILLY家倒是出了一本叫做《数据结构与算法javascript描述》的书,但不得不说,不知道是作者吃了shit还是译者根本就没校对,满书的小错误,这就像那种无穷无尽的小bug一样,简直就是让人有种嘴里塞满了shit的感觉,吐也不是咽下去也不是。对于一个前端来说,尤其是笔试面试的时候,算法方面考的其实不难(十大排序算法或是和十大排序算法同等难度的),但就是之前没用javascript实现过或是没仔细看过相关算法的原理,导致写起来浪费很多时间。所以撸一撸袖子决定自己查资料自己总结一篇博客等用到了直接看自己的博客就OK了,正所谓靠天靠地靠大牛不如靠自己(ˉ(∞)ˉ)。
    • 算法的由来:9世纪波斯数学家提出的:“al-Khowarizmi”就是下图这货(感觉重要数学元素提出者貌似都戴了顶白帽子),开个玩笑,阿拉伯人对于数学史的贡献还是值得人敬佩的。
      图片 4

    H5游戏开发:一笔画

    by leeenx on 2017-11-02

    一笔画是图论[科普](https://zh.wikipedia.org/wiki/%E5%9B%BE%E8%AE%BA)中一个著名的问题,它起源于柯尼斯堡七桥问题[科普](https://zh.wikipedia.org/wiki/%E6%9F%AF%E5%B0%BC%E6%96%AF%E5%A0%A1%E4%B8%83%E6%A1%A5%E9%97%AE%E9%A2%98)。数学家欧拉在他1736年发表的论文《柯尼斯堡的七桥》中不仅解决了七桥问题,也提出了一笔画定理,顺带解决了一笔画问题。用图论的术语来说,对于一个给定的连通图[科普](https://zh.wikipedia.org/wiki/%E8%BF%9E%E9%80%9A%E5%9B%BE)存在一条恰好包含所有线段并且没有重复的路径,这条路径就是「一笔画」。

    寻找连通图这条路径的过程就是「一笔画」的游戏过程,如下:

    图片 5

    正文

    游戏的实现

    「一笔画」的实现不复杂,笔者把实现过程分成两步:

    1. 底图绘制
    2. 交互绘制

    「底图绘制」把连通图以「点线」的形式显示在画布上,是游戏最容易实现的部分;「交互绘制」是用户绘制解题路径的过程,这个过程会主要是处理点与点动态成线的逻辑。

    排序算法说明

    (1)排序的定义:对一序列对象根据某个关键字进行排序;

    输入:n个数:a1,a2,a3,…,an
    输出:n个数的排列:a1’,a2’,a3’,…,an’,使得a1’

    再讲的形象点就是排排坐,调座位,高的站在后面,矮的站在前面咯。

    (3)对于评述算法优劣术语的说明

    稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面;
    不稳定:如果a原本在b的前面,而a=b,排序之后a可能会出现在b的后面;

    内排序:所有排序操作都在内存中完成;
    外排序:由于数据太大,因此把数据放在磁盘中,而排序通过磁盘和内存的数据传输才能进行;

    时间复杂度: 一个算法执行所耗费的时间。
    空间复杂度: 运行完一个程序所需内存的大小。

    关于时间空间复杂度的更多了解请戳这里,或是看书程杰大大编写的《大话数据结构》还是很赞的,通俗易懂。

    (4)排序算法图片总结(图片来源于网络):

    排序对比:

    图片 6

    图片名词解释:
    n: 数据规模
    k:“桶”的个数
    In-place: 占用常数内存,不占用额外内存
    Out-place: 占用额外内存

    排序分类:

    图片 7

    底图绘制

    「一笔画」是多关卡的游戏模式,笔者决定把关卡(连通图)的定制以一个配置接口的形式对外暴露。对外暴露关卡接口需要有一套描述连通图形状的规范,而在笔者面前有两个选项:

    • 点记法
    • 线记法

    举个连通图 —— 五角星为例来说一下这两个选项。

    图片 8

    点记法如下:

    JavaScript

    levels: [ // 当前关卡 { name: "五角星", coords: [ {x: Ax, y: Ay}, {x: Bx, y: By}, {x: Cx, y: Cy}, {x: Dx, y: Dy}, {x: Ex, y: Ey}, {x: Ax, y: Ay} ] } ... ]

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    levels: [
    // 当前关卡
    {
    name: "五角星",
    coords: [
    {x: Ax, y: Ay},
    {x: Bx, y: By},
    {x: Cx, y: Cy},
    {x: Dx, y: Dy},
    {x: Ex, y: Ey},
    {x: Ax, y: Ay}
    ]
    }
    ...
    ]

    线记法如下:

    JavaScript

    levels: [ // 当前关卡 { name: "五角星", lines: [ {x1: Ax, y1: Ay, x2: Bx, y2: By}, {x1: Bx, y1: By, x2: Cx, y2: Cy}, {x1: Cx, y1: Cy, x2: Dx, y2: Dy}, {x1: Dx, y1: Dy, x2: Ex, y2: Ey}, {x1: Ex, y1: Ey, x2: Ax, y2: Ay} ] } ]

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    levels: [
    // 当前关卡
    {
    name: "五角星",
    lines: [
    {x1: Ax, y1: Ay, x2: Bx, y2: By},
    {x1: Bx, y1: By, x2: Cx, y2: Cy},
    {x1: Cx, y1: Cy, x2: Dx, y2: Dy},
    {x1: Dx, y1: Dy, x2: Ex, y2: Ey},
    {x1: Ex, y1: Ey, x2: Ax, y2: Ay}
    ]
    }
    ]

    「点记法」记录关卡通关的一个答案,即端点要按一定的顺序存放到数组 coords中,它是有序性的记录。「线记法」通过两点描述连通图的线段,它是无序的记录。「点记法」最大的优势是表现更简洁,但它必须记录一个通关答案,笔者只是关卡的搬运工不是关卡创造者,所以笔者最终选择了「线记法」。:)

    1.冒泡排序(Bubble Sort)

    好的,开始总结第一个排序算法,冒泡排序。我想对于它每个学过C语言的都会了解的吧,这可能是很多人接触的第一个排序算法。

    交互绘制

    在画布上绘制路径,从视觉上说是「选择或连接连通图端点」的过程,这个过程需要解决2个问题:

    • 手指下是否有端点
    • 选中点到待选中点之间能否成线

    收集连通图端点的坐标,再监听手指滑过的坐标可以知道「手指下是否有点」。以下伪代码是收集端点坐标:

    JavaScript

    // 端点坐标信息 let coords = []; lines.forEach(({x1, y1, x2, y2}) => { // (x1, y1) 在 coords 数组不存在 if(!isExist(x1, y1)) coords.push([x1, y1]); // (x2, y2) 在 coords 数组不存在 if(!isExist(x2, y2)) coords.push([x2, y2]); });

    1
    2
    3
    4
    5
    6
    7
    8
    // 端点坐标信息
    let coords = [];
    lines.forEach(({x1, y1, x2, y2}) => {
    // (x1, y1) 在 coords 数组不存在
    if(!isExist(x1, y1)) coords.push([x1, y1]);
    // (x2, y2) 在 coords 数组不存在
    if(!isExist(x2, y2)) coords.push([x2, y2]);
    });

    以下伪代码是监听手指滑动:

    JavaScript

    easel.addEventListener("touchmove", e => { let x0 = e.targetTouches[0].pageX, y0 = e.targetTouches[0].pageY; // 端点半径 ------ 取连通图端点半径的2倍,提升移动端体验 let r = radius * 2; for(let [x, y] of coords){ if(Math.sqrt(Math.pow(x - x0, 2) + Math.pow(y - y0), 2) <= r){ // 手指下有端点,判断能否连线 if(canConnect(x, y)) { // todo } break; } } })

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    easel.addEventListener("touchmove", e => {
    let x0 = e.targetTouches[0].pageX, y0 = e.targetTouches[0].pageY;
    // 端点半径 ------ 取连通图端点半径的2倍,提升移动端体验
    let r = radius * 2;
    for(let [x, y] of coords){
    if(Math.sqrt(Math.pow(x - x0, 2) + Math.pow(y - y0), 2) <= r){
    // 手指下有端点,判断能否连线
    if(canConnect(x, y)) {
    // todo
    }
    break;
    }
    }
    })

    在未绘制任何线段或端点之前,手指滑过的任意端点都会被视作「一笔画」的起始点;在绘制了线段(或有选中点)后,手指滑过的端点能否与选中点串连成线段需要依据现有条件进行判断。

    图片 9

    上图,点A与点B可连接成线段,而点A与点C不能连接。笔者把「可以与指定端点连接成线段的端点称作有效连接点」。连通图端点的有效连接点从连通图的线段中提取:

    JavaScript

    coords.forEach(coord => { // 有效连接点(坐标)挂载在端点坐标下 coord.validCoords = []; lines.forEach(({x1, y1, x2, y2}) => { // 坐标是当前线段的起点 if(coord.x === x1 && coord.y === y1) { coord.validCoords.push([x2, y2]); } // 坐标是当前线段的终点 else if(coord.x === x2 && coord.y === y2) { coord.validCoords.push([x1, y1]); } }) })

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    coords.forEach(coord => {
    // 有效连接点(坐标)挂载在端点坐标下
    coord.validCoords = [];
    lines.forEach(({x1, y1, x2, y2}) => {
    // 坐标是当前线段的起点
    if(coord.x === x1 && coord.y === y1) {
    coord.validCoords.push([x2, y2]);
    }
    // 坐标是当前线段的终点
    else if(coord.x === x2 && coord.y === y2) {
    coord.validCoords.push([x1, y1]);
    }
    })
    })

    But…有效连接点只能判断两个点是否为底图的线段,这只是一个静态的参考,在实际的「交互绘制」中,会遇到以下情况:

    图片 10
    如上图,AB已串连成线段,当前选中点B的有效连接点是 A 与 C。AB 已经连接成线,如果 BA 也串连成线段,那么线段就重复了,所以此时 BA 不能成线,只有 AC 才能成线。

    对选中点而言,它的有效连接点有两种:

    • 与选中点「成线的有效连接点」
    • 与选中点「未成线的有效连接点」

    其中「未成线的有效连接点」才能参与「交互绘制」,并且它是动态的。

    图片 11

    回头本节内容开头提的两个问题「手指下是否有端点」 与 「选中点到待选中点之间能否成线」,其实可合并为一个问题:手指下是否存在「未成线的有效连接点」。只须把监听手指滑动遍历的数组由连通图所有的端点坐标 coords 替换为当前选中点的「未成线的有效连接点」即可。

    至此「一笔画」的主要功能已经实现。可以抢先体验一下:

    图片 12

    (1)算法描述

    冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

    自动识图

    笔者在录入关卡配置时,发现一个7条边以上的连通图很容易录错或录重线段。笔者在思考能否开发一个自动识别图形的插件,毕竟「一笔画」的图形是有规则的几何图形。

    图片 13

    上面的关卡「底图」,一眼就可以识出三个颜色:

    • 白底
    • 端点颜色
    • 线段颜色

    并且这三种颜色在「底图」的面积大小顺序是:白底 > 线段颜色 > 端点颜色。底图的「采集色值表算法」很简单,如下伪代码:

    JavaScript

    let imageData = ctx.getImageData(); let data = imageData.data; // 色值表 let clrs = new Map(); for(let i = 0, len = data.length; i < len; i += 4) { let [r, g, b, a] = [data[i], data[i + 1], data[i + 2], data[i + 3]]; let key = `rgba(${r}, ${g}, ${b}, ${a})`; let value = clrs.get(key) || {r, g, b, a, count: 0}; clrs.has(key) ? ++value.count : clrs.set(rgba, {r, g, b, a, count}); }

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    let imageData = ctx.getImageData();
    let data = imageData.data;
    // 色值表
    let clrs = new Map();
    for(let i = 0, len = data.length; i < len; i += 4) {
    let [r, g, b, a] = [data[i], data[i + 1], data[i + 2], data[i + 3]];
    let key = `rgba(${r}, ${g}, ${b}, ${a})`;
    let value = clrs.get(key) || {r, g, b, a, count: 0};
    clrs.has(key) ? ++value.count : clrs.set(rgba, {r, g, b, a, count});
    }

    对于连通图来说,只要把端点识别出来,连通图的轮廓也就出来了。

    (2)算法描述和实现

    具体算法描述如下:

    • <1>.比较相邻的元素。如果第一个比第二个大,就交换它们两个;
    • <2>.对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大的数;
    • <3>.针对所有的元素重复以上的步骤,除了最后一个;
    • <4>.重复步骤1~3,直到排序完成。

    JavaScript代码实现:

    JavaScript

    function bubbleSort(arr) { var len = arr.length; for (var i = 0; i < len; i++) { for (var j = 0; j < len - 1 - i; j++) { if (arr[j] > arr[j+1]) { //相邻元素两两对比 var temp = arr[j+1]; //元素交换 arr[j+1] = arr[j]; arr[j] = temp; } } } return arr; } var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]; console.log(bubbleSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    function bubbleSort(arr) {
        var len = arr.length;
        for (var i = 0; i < len; i++) {
            for (var j = 0; j < len - 1 - i; j++) {
                if (arr[j] > arr[j+1]) {        //相邻元素两两对比
                    var temp = arr[j+1];        //元素交换
                    arr[j+1] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        return arr;
    }
    var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
    console.log(bubbleSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

     

    改进冒泡排序: 设置一标志性变量pos,用于记录每趟排序中最后一次进行交换的位置。由于pos位置之后的记录均已交换到位,故在进行下一趟排序时只要扫描到pos位置即可。

    改进后算法如下:

    JavaScript

    function bubbleSort2(arr) { console.time('改进后冒泡排序耗时'); var i = arr.length-1; //初始时,最后位置保持不变 while ( i> 0) { var pos= 0; //每趟开始时,无记录交换 for (var j= 0; j< i; j++) if (arr[j]> arr[j+1]) { pos= j; //记录交换的位置 var tmp = arr[j]; arr[j]=arr[j+1];arr[j+1]=tmp; } i= pos; //为下一趟排序作准备 } console.timeEnd('改进后冒泡排序耗时'); return arr; } var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]; console.log(bubbleSort2(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    function bubbleSort2(arr) {
        console.time('改进后冒泡排序耗时');
        var i = arr.length-1;  //初始时,最后位置保持不变
        while ( i> 0) {
            var pos= 0; //每趟开始时,无记录交换
            for (var j= 0; j< i; j++)
                if (arr[j]> arr[j+1]) {
                    pos= j; //记录交换的位置
                    var tmp = arr[j]; arr[j]=arr[j+1];arr[j+1]=tmp;
                }
            i= pos; //为下一趟排序作准备
         }
         console.timeEnd('改进后冒泡排序耗时');
         return arr;
    }
    var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
    console.log(bubbleSort2(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

     

    传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值,我们考虑利用在每趟排序中进行正向和反向两遍冒泡的方法一次可以得到两个最终值(最大者和最小者) , 从而使排序趟数几乎减少了一半。

    改进后的算法实现为:

    JavaScript

    function bubbleSort3(arr3) { var low = 0; var high= arr.length-1; //设置变量的初始值 var tmp,j; console.time('2.改进后冒泡排序耗时'); while (low < high) { for (j= low; j< high; ++j) //正向冒泡,找到最大者 if (arr[j]> arr[j+1]) { tmp = arr[j]; arr[j]=arr[j+1];arr[j+1]=tmp; } --high; //修改high值, 前移一位 for (j=high; j>low; --j) //反向冒泡,找到最小者 if (arr[j]<arr[j-1]) { tmp = arr[j]; arr[j]=arr[j-1];arr[j-1]=tmp; } ++low; //修改low值,后移一位 } console.timeEnd('2.改进后冒泡排序耗时'); return arr3; } var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]; console.log(bubbleSort3(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    function bubbleSort3(arr3) {
        var low = 0;
        var high= arr.length-1; //设置变量的初始值
        var tmp,j;
        console.time('2.改进后冒泡排序耗时');
        while (low < high) {
            for (j= low; j< high; ++j) //正向冒泡,找到最大者
                if (arr[j]> arr[j+1]) {
                    tmp = arr[j]; arr[j]=arr[j+1];arr[j+1]=tmp;
                }
            --high;                 //修改high值, 前移一位
            for (j=high; j>low; --j) //反向冒泡,找到最小者
                if (arr[j]<arr[j-1]) {
                    tmp = arr[j]; arr[j]=arr[j-1];arr[j-1]=tmp;
                }
            ++low;                  //修改low值,后移一位
        }
        console.timeEnd('2.改进后冒泡排序耗时');
        return arr3;
    }
    var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
    console.log(bubbleSort3(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

    三种方法耗时对比:

    图片 14

    由图可以看出改进后的冒泡排序明显的时间复杂度更低,耗时更短了。读者自行尝试可以戳这,博主在github建了个库,读者可以Clone下来本地尝试。此博文配合源码体验更棒哦~~~

    冒泡排序动图演示:

    图片 15

    (3)算法分析

    • 最佳情况:T(n) = O(n)

    当输入的数据已经是正序时(都已经是正序了,为毛何必还排序呢….)

    • 最差情况:T(n) = O(n2)

    当输入的数据是反序时(卧槽,我直接反序不就完了….)

    • 平均情况:T(n) = O(n2)

    端点识别

    理论上,通过采集的「色值表」可以直接把端点的坐标识别出来。笔者设计的「端点识别算法」分以下2步:

    1. 按像素扫描底图直到遇到「端点颜色」的像素,进入第二步
    2. 从底图上清除端点并记录它的坐标,返回继续第一步

    伪代码如下:

    JavaScript

    for(let i = 0, len = data.length; i < len; i += 4) { let [r, g, b, a] = [data[i], data[i + 1], data[i + 2], data[i + 3]]; // 当前像素颜色属于端点 if(isBelongVertex(r, g, b, a)) { // 在 data 中清空端点 vertex = clearVertex(i); // 记录端点信息 vertexes.push(vertext); } }

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    for(let i = 0, len = data.length; i < len; i += 4) {
    let [r, g, b, a] = [data[i], data[i + 1], data[i + 2], data[i + 3]];
    // 当前像素颜色属于端点
    if(isBelongVertex(r, g, b, a)) {
    // 在 data 中清空端点
    vertex = clearVertex(i);
    // 记录端点信息
    vertexes.push(vertext);
    }
    }

    But… 上面的算法只能跑无损图。笔者在使用了一张手机截屏做测试的时候发现,收集到的「色值表」长度为 5000+ !这直接导致端点和线段的色值无法直接获得。

    经过分析,可以发现「色值表」里绝大多数色值都是相近的,也就是在原来的「采集色值表算法」的基础上添加一个近似颜色过滤即可以找出端点和线段的主色。伪代码实现如下:

    JavaScript

    let lineColor = vertexColor = {count: 0}; for(let clr of clrs) { // 与底色相近,跳过 if(isBelongBackground(clr)) continue; // 线段是数量第二多的颜色,端点是第三多的颜色 if(clr.count > lineColor.count) { [vertexColor, lineColor] = [lineColor, clr] } }

    1
    2
    3
    4
    5
    6
    7
    8
    9
    let lineColor = vertexColor = {count: 0};
    for(let clr of clrs) {
    // 与底色相近,跳过
    if(isBelongBackground(clr)) continue;
    // 线段是数量第二多的颜色,端点是第三多的颜色
    if(clr.count > lineColor.count) {
    [vertexColor, lineColor] = [lineColor, clr]
    }
    }

    取到端点的主色后,再跑一次「端点识别算法」后居识别出 203 个端点!这是为什么呢?

    图片 16

    上图是放大5倍后的底图局部,蓝色端点的周围和内部充斥着大量噪点(杂色块)。事实上在「端点识别」过程中,由于噪点的存在,把原本的端点被分解成十几个或数十个小端点了,以下是跑过「端点识别算法」后的底图:

    图片 17

    通过上图,可以直观地得出一个结论:识别出来的小端点只在目标(大)端点上集中分布,并且大端点范围内的小端点叠加交错。

    如果把叠加交错的小端点归并成一个大端点,那么这个大端点将十分接近目标端点。小端点的归并伪代码如下:

    JavaScript

    for(let i = 0, len = vertexes.length; i < len - 1; ++i) { let vertexA = vertexes[i]; if(vertextA === undefined) continue; // 注意这里 j = 0 而不是 j = i +1 for(let j = 0; j < len; ++j) { let vertexB = vertexes[j]; if(vertextB === undefined) continue; // 点A与点B有叠加,点B合并到点A并删除点B if(isCross(vertexA, vertexB)) { vertexA = merge(vertexA, vertexB); delete vertexA; } } }

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    for(let i = 0, len = vertexes.length; i < len - 1; ++i) {
    let vertexA = vertexes[i];
    if(vertextA === undefined) continue;
    // 注意这里 j = 0 而不是 j = i +1
    for(let j = 0; j < len; ++j) {
    let vertexB = vertexes[j];
    if(vertextB === undefined) continue;
    // 点A与点B有叠加,点B合并到点A并删除点B
    if(isCross(vertexA, vertexB)) {
    vertexA = merge(vertexA, vertexB);
    delete vertexA;
    }
    }
    }

    加了小端点归并算法后,「端点识别」的准确度就上去了。经笔者本地测试已经可以 100% 识别有损的连通图了。

    2.选择排序(Selection Sort)

    表现最稳定的排序算法之一(这个稳定不是指算法层面上的稳定哈,相信聪明的你能明白我说的意思2333),因为无论什么数据进去都是O(n²)的时间复杂度…..所以用到它的时候,数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。理论上讲,选择排序可能也是平时排序一般人想到的最多的排序方法了吧。

    线段识别

    笔者分两个步骤完成「线段识别」:

    1. 给定的两个端点连接成线,并采集连线上N个「样本点」;
    2. 遍历样本点像素,如果像素色值不等于线段色值则表示这两个端点之间不存在线段

    如何采集「样式点」是个问题,太密集会影响性能;太疏松精准度不能保证。

    在笔者面前有两个选择:N 是常量;N 是变量。
    假设 N === 5。局部提取「样式点」如下:

    图片 18

    上图,会识别出三条线段:AB, BC 和 AC。而事实上,AC不能成线,它只是因为 AB 和 BC 视觉上共一线的结果。当然把 N 值向上提高可以解决这个问题,不过 N 作为常量的话,这个常量的取量需要靠经验来判断,果然放弃。

    为了避免 AB 与 BC 同处一直线时 AC 被识别成线段,其实很简单 —— 两个「样本点」的间隔小于或等于端点直径
    假设 N = S / (2 * R),S 表示两点的距离,R 表示端点半径。局部提取「样式点」如下:

    图片 19

    如上图,成功地绕过了 AC。「线段识别算法」的伪代码实现如下:

    JavaScript

    for(let i = 0, len = vertexes.length; i < len - 1; ++i) { let {x: x1, y: y1} = vertexes[i]; for(let j = i + 1; j < len; ++j) { let {x: x2, y: y2} = vertexes[j]; let S = Math.sqrt(Math.pow(x1 - x2, 2) + Math.pow(y1 - y2, 2)); let N = S / (R * 2); let stepX = (x1 - x2) / N, stepY = (y1 - y2) / n; while(--N) { // 样本点不是线段色 if(!isBelongLine(x1 + N * stepX, y1 + N * stepY)) break; } // 样本点都合格 ---- 表示两点成线,保存 if(0 === N) lines.push({x1, y1, x2, y2}) } }

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    for(let i = 0, len = vertexes.length; i < len - 1; ++i) {
    let {x: x1, y: y1} = vertexes[i];
    for(let j = i + 1; j < len; ++j) {
    let {x: x2, y: y2} = vertexes[j];
    let S = Math.sqrt(Math.pow(x1 - x2, 2) + Math.pow(y1 - y2, 2));
    let N = S / (R * 2);
    let stepX = (x1 - x2) / N, stepY = (y1 - y2) / n;
    while(--N) {
    // 样本点不是线段色
    if(!isBelongLine(x1 + N * stepX, y1 + N * stepY)) break;
    }
    // 样本点都合格 ---- 表示两点成线,保存
    if(0 === N) lines.push({x1, y1, x2, y2})
    }
    }

    (1)算法简介

    选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

    性能优化

    由于「自动识图」需要对图像的的像素点进行扫描,那么性能确实是个需要关注的问题。笔者设计的「自动识图算法」,在识别图像的过程中需要对图像的像素做两次扫描:「采集色值表」 与 「采集端点」。在扫描次数上其实很难降低了,但是对于一张 750 * 1334 的底图来说,「自动识图算法」需要遍历两次长度为 750 * 1334 * 4 = 4,002,000 的数组,压力还是会有的。笔者是从压缩被扫描数组的尺寸来提升性能的。

    被扫描数组的尺寸怎么压缩?
    笔者直接通过缩小画布的尺寸来达到缩小被扫描数组尺寸的。伪代码如下:

    JavaScript

    // 要压缩的倍数 let resolution = 4; let [width, height] = [img.width / resolution >> 0, img.height / resolution >> 0]; ctx.drawImage(img, 0, 0, width, height); let imageData = ctx.getImageData(), data = imageData;

    1
    2
    3
    4
    5
    // 要压缩的倍数
    let resolution = 4;
    let [width, height] = [img.width / resolution >> 0, img.height / resolution >> 0];
    ctx.drawImage(img, 0, 0, width, height);
    let imageData = ctx.getImageData(), data = imageData;

    把源图片缩小4倍后,得到的图片像素数组只有原来的 4^2 = 16倍。这在性能上是很大的提升。

    (2)算法描述和实现

    n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下:

    • <1>.初始状态:无序区为R[1..n],有序区为空;
    • <2>.第i趟排序(i=1,2,3…n-1)开始时,当前有序区和无序区分别为R[1..i-1]和R(i..n)。该趟排序从当前无序区中-选出关键字最小的记录 R[k],将它与无序区的第1个记录R交换,使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区;
    • <3>.n-1趟结束,数组有序化了。

    Javascript代码实现:

    JavaScript

    function selectionSort(arr) { var len = arr.length; var minIndex, temp; console.time('选择排序耗时'); for (var i = 0; i < len - 1; i++) { minIndex = i; for (var j = i + 1; j < len; j++) { if (arr[j] < arr[minIndex]) { //寻找最小的数 minIndex = j; //将最小数的索引保存 } } temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } console.timeEnd('选择排序耗时'); return arr; } var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]; console.log(selectionSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    function selectionSort(arr) {
        var len = arr.length;
        var minIndex, temp;
        console.time('选择排序耗时');
        for (var i = 0; i < len - 1; i++) {
            minIndex = i;
            for (var j = i + 1; j < len; j++) {
                if (arr[j] < arr[minIndex]) {     //寻找最小的数
                    minIndex = j;                 //将最小数的索引保存
                }
            }
            temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
        console.timeEnd('选择排序耗时');
        return arr;
    }
    var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
    console.log(selectionSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

    选择排序动图演示:

    图片 20

    使用「自动识图」的建议

    尽管笔者在本地测试的时候可以把所有的「底图」识别出来,但是并不能保证其它开发者上传的图片能否被很好的识别出来。笔者建议,可以把「自动识图」做为一个单独的工具使用。

    笔者写了一个「自动识图」的单独工具页面:
    可以在这个页面生成对应的关卡配置。

    (3)算法分析

    • 最佳情况:T(n) = O(n2)
    • 最差情况:T(n) = O(n2)
    • 平均情况:T(n) = O(n2)

    结语

    下面是本文介绍的「一笔画」的线上 DEMO 的二维码:

    图片 21

    游戏的源码托管在:
    其中游戏实现的主体代码在:
    自动识图的代码在:

    感谢耐心阅读完本文章的读者。本文仅代表笔者的个人观点,如有不妥之处请不吝赐教。

    感谢您的阅读,本文由 凹凸实验室 版权所有。如若转载,请注明出处:凹凸实验室()

    1 赞 1 收藏 评论

    图片 22

    3.插入排序(Insertion Sort)

    插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴,但它的原理应该是最容易理解的了,因为只要打过扑克牌的人都应该能够秒懂。当然,如果你说你打扑克牌摸牌的时候从来不按牌的大小整理牌,那估计这辈子你对插入排序的算法都不会产生任何兴趣了…..

    (1)算法简介

    插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

    (2)算法描述和实现

    一般来说,插入排序都采用in-place在数组上实现。具体算法描述如下:

    • <1>.从第一个元素开始,该元素可以认为已经被排序;
    • <2>.取出下一个元素,在已经排序的元素序列中从后向前扫描;
    • <3>.如果该元素(已排序)大于新元素,将该元素移到下一位置;
    • <4>.重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;
    • <5>.将新元素插入到该位置后;
    • <6>.重复步骤2~5。

    Javascript代码实现:

    JavaScript

    function insertionSort(array) { if (Object.prototype.toString.call(array).slice(8, -1) === 'Array') { console.time('插入排序耗时:'); for (var i = 1; i < array.length; i++) { var key = array[i]; var j = i - 1; while (j >= 0 && array[j] > key) { array[j + 1] = array[j]; j--; } array[j + 1] = key; } console.timeEnd('插入排序耗时:'); return array; } else { return 'array is not an Array!'; } }

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    function insertionSort(array) {
        if (Object.prototype.toString.call(array).slice(8, -1) === 'Array') {
            console.time('插入排序耗时:');
            for (var i = 1; i < array.length; i++) {
                var key = array[i];
                var j = i - 1;
                while (j >= 0 && array[j] > key) {
                    array[j + 1] = array[j];
                    j--;
                }
                array[j + 1] = key;
            }
            console.timeEnd('插入排序耗时:');
            return array;
        } else {
            return 'array is not an Array!';
        }
    }

    改进插入排序: 查找插入位置时使用二分查找的方式

    JavaScript

    function binaryInsertionSort(array) { if (Object.prototype.toString.call(array).slice(8, -1) === 'Array') { console.time('二分插入排序耗时:'); for (var i = 1; i < array.length; i++) { var key = array[i], left = 0, right = i - 1; while (left <= right) { var middle = parseInt((left + right) / 2); if (key < array[middle]) { right = middle - 1; } else { left = middle + 1; } } for (var j = i - 1; j >= left; j--) { array[j + 1] = array[j]; } array[left] = key; } console.timeEnd('二分插入排序耗时:'); return array; } else { return 'array is not an Array!'; } } var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]; console.log(binaryInsertionSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    function binaryInsertionSort(array) {
        if (Object.prototype.toString.call(array).slice(8, -1) === 'Array') {
            console.time('二分插入排序耗时:');
            for (var i = 1; i < array.length; i++) {
                var key = array[i], left = 0, right = i - 1;
                while (left <= right) {
                    var middle = parseInt((left + right) / 2);
                    if (key < array[middle]) {
                        right = middle - 1;
                    } else {
                        left = middle + 1;
                    }
                }
                for (var j = i - 1; j >= left; j--) {
                    array[j + 1] = array[j];
                }
                array[left] = key;
            }
            console.timeEnd('二分插入排序耗时:');
            return array;
        } else {
            return 'array is not an Array!';
        }
    }
    var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
    console.log(binaryInsertionSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

    改进前后对比:

    图片 23

    插入排序动图演示:

    图片 24

    (3)算法分析

    • 最佳情况:输入数组按升序排列。T(n) = O(n)
    • 最坏情况:输入数组按降序排列。T(n) = O(n2)
    • 平均情况:T(n) = O(n2)

    4.希尔排序(Shell Sort)

    1959年Shell发明;
    第一个突破O(n^2)的排序算法;是简单插入排序的改进版;它与插入排序的不同之处在于,它会优先比较距离较远的元素。希尔排序又叫缩小增量排序

    本文由金沙国际官网发布于web前端,转载请注明出处:H5游戏开发,移动端H5音频与视频问题及解决方案

    关键词:

上一篇:没有了

下一篇:没有了