您的位置:奥门新浦京网址 > Wed前段 > 常见的2D碰撞检测,一起理解

常见的2D碰撞检测,一起理解

发布时间:2019-10-24 03:06编辑:Wed前段浏览(167)

    “等一下,我碰!”——常见的2D碰撞检测

    2017/02/22 · HTML5 · 1 评论 · 碰撞检测

    原文出处: 凹凸实验室   

    图片 1

    “碰乜鬼嘢啊,碰走晒我滴靓牌”。想到“碰”就自然联想到了“麻将”这一伟大发明。当然除了“碰”,洗牌的时候也充满了各种『碰撞』。

    好了,不废话。直入主题——碰撞检测。

    在 2D 环境下,常见的碰撞检测方法如下:

    • 外接图形判别法
      • 轴对称包围盒(Axis-Aligned Bounding Box),即无旋转矩形。
      • 圆形碰撞
    • 光线投射法
    • 分离轴定理
    • 其他
      • 地图格子划分
      • 像素检测

    下文将由易到难的顺序介绍上述各种碰撞检测方法:外接图形判别法 > 其他 > 光线投射法 > 分离轴定理。

    另外,有一些场景只要我们约定好限定条件,也能实现我们想要的碰撞,如下面的碰壁反弹:

    当球碰到边框就反弹(如x/y轴方向速度取反)。

    JavaScript

    if(ball.left < 0 || ball.right > rect.width) ball.velocityX = -ball.velocityX if(ball.top < 0 || ball.bottom > rect.height) ball.velocityY = -ball.velocityY

    1
    2
    if(ball.left < 0 || ball.right > rect.width) ball.velocityX = -ball.velocityX
    if(ball.top < 0 || ball.bottom > rect.height) ball.velocityY = -ball.velocityY

    再例如当一个人走到 100px 位置时不进行跳跃,就会碰到石头等等。

    因此,某些场景只需通过设定到适当的参数即可。

    一起理解 Virtual DOM

    2016/11/14 · JavaScript · DOM

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

    理解JavaScript的原型属性

    2016/06/21 · JavaScript · 2 评论 · 原型

    本文由 伯乐在线 - alvendarthy 翻译,sunshinebuel 校稿。未经许可,禁止转载!
    英文出处:bytearcher。欢迎加入翻译组。

    理解 JavaScript 的prototype属性不太容易。你也许知道它同面向对象编程(OOP)和对象继承有关,但未必对其技术原理非常清楚。

    外接图形判别法

    前言

    React 好像已经火了很久很久,以致于我们对于 Virtual DOM 这个词都已经很熟悉了,网上也有非常多的介绍 React、Virtual DOM 的文章。但是直到前不久我专门花时间去学习 Virtual DOM,才让我对 Virtual DOM 有了一定的理解,以致于要怀疑起很久之前看过的那些文章来。倒不是这些文章讲得不对,而是现在在我看来角度不太好,说得越多,越说不清。

    让我能够有所开窍(自认为)的,是这篇文章:


    Change And Its Detection In JavaScript Frameworks
    Monday Mar 2, 2015 by Tero Parviainen


    作者看问题的角度很棒,从数据变更与UI同步的角度来介绍各个典型框架,特别是对于 React 的 Virtual DOM,从这个角度理解起来更容易些。

    感兴趣的同学,如果没有读过这篇文章,推荐去看一看,不感兴趣就算了。不过接下来我要讲的东西,部分整理自这篇文章,特别是从这篇文章中引用的图片,非常棒。当然还有我自己的一些思考,以及一些对于目前 Virtual DOM 实现的开源库的分析。

    如果读了上面推荐的这篇文章,我倒是不介意你不再继续把本文读下去,因为有些东西你已经领会到了。当然,也不反对。

    原型继承

    面向对象编程可以通过很多途径实现。其他的语言,比如 Java,使用基于类的模型实现: 类及对象实例区别对待。但在 JavaScript 中没有类的概念,取而代之的是一切皆对象。JavaScript 中的继承通过原型继承实现:一个对象直接从另一对象继承。对象中包含其继承体系中祖先的引用——对象的 prototype 属性。

    class 关键字是在 ES6 中首次引入 JavaScript 的。其实,它并没有为面向对象继承引入新模型, class 关键字通过语法糖,实现了本文介绍的原型特性和构造函数。

    轴对称包围盒(Axis-Aligned Bounding Box)

    概念:判断任意两个(无旋转)矩形的任意一边是否无间距,从而判断是否碰撞。

    算法:

    JavaScript

    rect1.x < rect2.x + rect2.width && rect1.x + rect1.width > rect2.x && rect1.y < rect2.y + rect2.height && rect1.height + rect1.y > rect2.y

    1
    2
    3
    4
    rect1.x < rect2.x + rect2.width &&
    rect1.x + rect1.width > rect2.x &&
    rect1.y < rect2.y + rect2.height &&
    rect1.height + rect1.y > rect2.y

    两矩形间碰撞的各种情况:
    图片 2

    在线运行示例(先点击运行示例以获取焦点,下同):

    缺点:

    • 相对局限:两物体必须是矩形,且均不允许旋转(即关于水平和垂直方向上对称)。
    • 对于包含着图案(非填满整个矩形)的矩形进行碰撞检测,可能存在精度不足的问题。
    • 物体运动速度过快时,可能会在相邻两动画帧之间快速穿越,导致忽略了本应碰撞的事件发生。

    适用案例:

    • (类)矩形物体间的碰撞。

    变化这件事

    谈论页面的变化之前,咱们先看下数据和页面(视觉层面的页面)的关系。数据是隐藏在页面底下,通过渲染展示给用户。同样的数据,按照不同的页面设计和实现,会以不同形式、样式的页面呈现出来。有时候在一个页面内的不同位置,也会有相同数据的不同表现。

    图片 3

    Paste_Image.png

    Web 的早期,这些页面通常是静态的,页面内容不会变化。而如果数据发生了变化,通常需要重新请求页面,得到基于新的数据渲染出的新的页面。

    图片 4

    Paste_Image.png

    至少,这个模式理解起来挺简单不是吗。

    直到 Web 应用复杂起来,开发者们开始关注用户体验,开始将大量的处理向前端迁移,页面变得动态、灵活起来。一个显著的特征是,数据发生变化之后,不再需要刷新页面就能看到页面上的内容随之更新了。

    前端需要做的事情变得多了起来,前端工程师们也就修炼了起来,各种前端技术也就出现了。

    首先,聪明的工程师们发现既然是在前端渲染页面,如果只是部分数据发生了变化,就要把页面整体或一大块区域重新渲染就有点笨了。为什么不把事情做得更极致些,只更新变化的数据对应的页面的内容呢?

    怎么做呢?操作 DOM 呗。DOM 就是浏览器提供给开发者用于操作页面的模型嘛,直接通过脚本来调用 DOM 的各种接口就 OK 了。而且我们还有了像 jQuery 这样的棒棒的工具,操作 DOM 变得 so easy。

    然而,页面越来越复杂,聪明的工程师们发现数据变化之后,老是需要手动编码去操作对应的 DOM 节点执行更新,有点烦,不够懒啊。于是各种框架如雨后春笋般出现了,纷纷表示可以简化这个过程。

    稍微早期的框架有这样的:

    图片 5

    Paste_Image.png

    开发者借助框架,监听数据的变更,在数据变更后更新对应的 DOM 节点。虽然还是要写一些代码,但是写出来的代码好像很有条理的样子,至少更容易理解和维护了,也不错嘛。

    更进一步,MVVM 框架出现了,以 AngularJS 为代表:

    图片 6

    Paste_Image.png

    仍然是数据变化后更新对应 DOM 节点的方式,但是建立这种绑定关系的过程被框架所处理,开发者要写的代码变少了,而且代码更易读和维护了。

    再然后呢,大家就在这个棒棒的模式上继续深耕,纷纷表示还可以在性能上做得更好,前端领域一片繁荣。

    再后来 React 出现了,它不仅不是 MVVM 框架,甚至连 MV 框架都不是。这年头,不是个 MV 框架还好意思出门?可 React 还真的带来了新的思路!

    什么思路呢?

    就是回到过去,回到那个简单而美好的时候。具体而言,就是每次数据发生变化,就重新执行一次整体渲染。的确这样更简单,不用去琢磨到底是数据的哪一部分变化了,需要更新页面的哪一部分。但是坏处太明显,体验不好啊。而 React 给出了解决方案,就是 Virtual DOM。

    Virtual DOM 概况来讲,就是在数据和真实 DOM 之间建立了一层缓冲。对于开发者而言,数据变化了就调用 React 的渲染方法,而 React 并不是直接得到新的 DOM 进行替换,而是先生成 Virtual DOM,与上一次渲染得到的 Virtual DOM 进行比对,在渲染得到的 Virtual DOM 上发现变化,然后将变化的地方更新到真实 DOM 上。

    简单来说,React 在提供给开发者简单的开发模式的情况下,借助 Virtual DOM 实现了性能上的优化,以致于敢说自己“不慢”。

    JavaScript 实现继承的语言特性

    以下语言特性共同实现了 JavaScript 继承。

    • 当尝试访问 JavaScript 对象中不存在的属性时,解析器会查找匹配的对象原型。例如调用 car.toString(),如果 car 没有 toString 方法,就会调用 car 对象的原型。 这个查找过程会一直递归, 直到查找到匹配的原型或者继承链尽头。
    • 调用  new Car() 会创建一个新的对象,并初始化为 Car.prototype。 这样就允许为新对象设置原型链。需要注意的是,new Car() 只有当  Car 是函数时才有意义。 此类函数即所谓构造函数。
    • 调用对象的一个成员函数时, this 的值被绑定为当前对象。例如调用 "abc".toString()this 的值被设置为 "abc",然后调用 toString 函数。该技术支持代码重用:同样的代码,可在 this 为各种不同的值时调用。对象的成员函数,也被称为对象的方法。

    圆形碰撞(Circle Collision)

    概念:通过判断任意两个圆形的圆心距离是否小于两圆半径之和,若小于则为碰撞。

    两点之间的距离由以下公式可得:
    图片 7

    判断两圆心距离是否小于两半径之和:

    JavaScript

    Math.sqrt(Math.pow(circleA.x - circleB.x, 2) + Math.pow(circleA.y - circleB.y, 2)) < circleA.radius + circleB.radius

    1
    2
    3
    Math.sqrt(Math.pow(circleA.x - circleB.x, 2) +
    Math.pow(circleA.y - circleB.y, 2))
    < circleA.radius + circleB.radius

    图例:
    图片 8

    在线运行示例:

    缺点:

    • 与『轴对称包围盒』类似

    适用案例:

    • (类)圆形的物体,如各种球类碰撞。

    Virtual DOM

    React 基于 Virtual DOM 的数据更新与UI同步机制:

    图片 9

    React – 初始渲染

    初始渲染时,首先将数据渲染为 Virtual DOM,然后由 Virtual DOM 生成 DOM。

    图片 10

    React – 数据更新

    数据更新时,渲染得到新的 Virtual DOM,与上一次得到的 Virtual DOM 进行 diff,得到所有需要在 DOM 上进行的变更,然后在 patch 过程中应用到 DOM 上实现UI的同步更新。

    Virtual DOM 作为数据结构,需要能准确地转换为真实 DOM,并且方便进行对比。除了 Virtual DOM 外,React 还实现了其他的特性,为了专注于 Virtual DOM,我另外找了两个比较 Virtual DOM 来学习:

    • virtual-dom
    • Snabbdom

    这里也推荐给感兴趣且还没有读过两个库源码的同学。

    由于只关注 Virtual DOM,通过阅读两个库的源码,对于 Virtual DOM 的定位有了更深一步的理解。

    首先看数据结构。

    Virtual DOM 数据结构

    DOM 通常被视为一棵树,元素则是这棵树上的节点(node),而 Virtual DOM 的基础,就是 Virtual Node 了。

    在 virtual-dom 中,给 Virtual Node 声明了对应的类 VirtualNode,基本是用于存储数据,包括:

    • tagName
    • properties
    • children
    • key
    • namespace
    • count
    • hasWidgets
    • hasThunks
    • hooks
    • descendantHooks

    Snabbdom 的 Virtual Node 则是纯数据对象,通过 vnode 模块来创建,对象属性包括:

    • sel
    • data
    • children
    • text
    • elm
    • key

    虽然有所差别,除去实现上的差别和库本身的额外特性,可以看到 Virtual Node 用于创建真实节点的数据包括:

    • 元素类型
    • 元素属性
    • 元素的子节点

    有了这些其实就可以创建对应的真实节点了。

    创建 Virtual DOM

    嵌套 Virtual Node 就可以得到一棵树了。virtual-dom 和 Snabbdom 都提供了函数调用的方式来创建 Virtual Tree,这个过程就是渲染了:

    JavaScript

    var vTree = h('div', [ h('span', 'hello'), h('span', 'world') ])

    1
    2
    3
    4
    var vTree = h('div', [
      h('span', 'hello'),
      h('span', 'world')
    ])

    React 提供 JSX 这颗糖,使得我们可以用类似 HTML 的语法来编写,不过编译后实质还是通过函数调用来得到一棵嵌套的 Virtual Tree。而且这对于理解 Virtual DOM 机制来说不是特别重要,先不管这个。

    使用 Virtual DOM

    首先来看初始化,virtual-dom 提供了 createElement 函数:

    JavaScript

    var rootNode = createElement(tree) document.body.appendChild(rootNode)

    1
    2
    var rootNode = createElement(tree)
    document.body.appendChild(rootNode)

    根据 Virtual Node 创建真实 DOM 元素,然后再追加到页面上。

    再来看更新。virtual-dom 有明确的两步操作,首先 diff,然后 patch:

    JavaScript

    var newTree = render(count) var patches = diff(tree, newTree) rootNode = patch(rootNode, patches)

    1
    2
    3
    var newTree = render(count)
    var patches = diff(tree, newTree)
    rootNode = patch(rootNode, patches)

    而 Snabbdom 则简单些,只有一个 patch 函数,内部在进行比对的同时将更新应用到了真实 DOM 上,而且初始化也是用的 patch 函数:

    JavaScript

    var vnode = render(data) var container = document.getElementById('container') patch(container, vnode) // after data changed var newVnode = render(data) patch(vnode, newVnode)

    1
    2
    3
    4
    5
    6
    7
    var vnode = render(data)
    var container = document.getElementById('container')
    patch(container, vnode)
     
    // after data changed
    var newVnode = render(data)
    patch(vnode, newVnode)

    性能优化

    关于性能优化,除了 Virtual DOM 机制本身提供的特性以外,再就是不同的 Virtual DOM 库自身的优化方案了,这个可以看上面两个库的文档,不再赘述。

    其实提到 Virtual DOM 的差异比对,有人会对其内部如何处理数组感兴趣。的确,如果数组元素的位置发生了改变,这个要识别起来是有点麻烦。为此,上面两个库和 React 其实都在 Virtual Node 上额外记录了一个属性“key”,就是用来辅助进行 Virtual Node 的比对的。

    简单来说,如果两个 Virtual Node 的位置不同,但是 key 属性相同,那么会将这两个节点视为由相同数据渲染得到的,然后进一步进行差异分析。所以,并不是仅仅按照位置进行比对,具体的实现可以查看各个库的源码。

    举个栗子

    我们用面向对象编程,实现一个计算矩形周长的例子。

    JavaScript

    function Rectangle(x, y) { this.x = x; this.y = y; } Rectangle.prototype.perimeter = function() { return 2 * (this.x + this.y); } var rect = new Rectangle(1, 2); console.log(rect.perimeter()); // outputs '6'

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    function Rectangle(x, y) {
        this.x = x;
        this.y = y;
    }
     
    Rectangle.prototype.perimeter = function() {
        return 2 * (this.x + this.y);
    }
     
    var rect = new Rectangle(1, 2);
    console.log(rect.perimeter()); // outputs '6'

    首先,我们定义构造函数 Rectangle。 按照规范,我们大写构造函数名首字母,表明它可以用 new 调用,以示与其他常规函数的区别。构造函数自动将 this 赋值为一空对象,然后代码中用 xy 属性填充它,以备后用。

    然后, Rectangle.prototype 新增一个通过 xy 属性计算周长成员函数。 注意 this 的使用,在不同的对象中,this 会有不同的值,这些代码都可以正常工作。

    最后, 一个名为 rect 的对象创建出来了。 它继承了 Rectangle.prototype, 我们可以调用 rect.perimeter(), 然后将结果打印到控制台。

    其他

    小结

    OK,以上就是我要讲的全部所有内容了。

    相信很多同学之前对 Virtual DOM 已经很熟悉了,比我理解得更深入的同学相信也不会少。不过从“数据变化与UI同步更新”这个角度来理解 Virtual DOM,在我看来是比较好的,所以整理在这里了。

    有个问题挺常见,AngularJS 和 React 哪个更好?

    如果说各有千秋的话,估计大家就“呵呵”了。但是这两个框架/库从“数据变化与UI同步更新”的角度来看,的确都解决了问题,而且解决问题的方式大家都挺认可(至少在喜欢它们的同学眼里是这样的)。

    而且,如果大家关注 Vue 的话,可以看到,这个 MVVM 框架已经发布了 2.0,其中就采用了 Virtual DOM 实现其UI同步更新!所以,这的确不矛盾啊。

    第二个而且,技术本身不是目的,能够更好地解决问题才是王道嘛。

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

    打赏作者

    prototype 属性名称带来的误解

    有一些关于 JavaScript 的原型的误解。 一个对象的原型与对象的 prototype 属性并非一回事。 前者用于在原型链中匹配不存在的属性。后者用于通过 new 关键字创建对象,它将作为新创建对象的原型。 理解二者的差异,将帮助你彻底理解 JavaScript 中的原型特性。

    在我们的例子中, Rectangle.prototype 是用 new Rectangle() 创建出来对象的原型, 而 Rectangle 的原型实际上是 JavaScript 的 Function.prototype。(子对象的原型是父对象的 prototype 属性)

    对象中保存原型的变量,也被称之为内部原型引用(the internal prototype link),历史上也曾称之为 __proto__ ,对这个称谓始终存在一些争议。 更精确的,它可以被称为 Object.getPrototypeOf(...) 的返回值。

    2 赞 5 收藏 2 评论

    地图格子划分

    概念:将地图(场景)划分为一个个格子。地图中参与检测的对象都存储着自身所在格子的坐标,那么你即可以认为两个物体在相邻格子时为碰撞,又或者两个物体在同一格才为碰撞。另外,采用此方式的前提是:地图中所有可能参与碰撞的物体都要是格子单元的大小或者是其整数倍。

    蓝色X 为障碍物:
    图片 11

    实现方法:

    JavaScript

    // 通过特定标识指定(非)可行区域 map = [ [0, 0, 1, 1, 1, 0, 0, 0, 0], [0, 1, 1, 0, 0, 1, 0, 0, 0], [0, 1, 0, 0, 0, 0, 1, 0, 0], [0, 1, 0, 0, 0, 0, 1, 0, 0], [0, 1, 1, 1, 1, 1, 1, 0, 0] ], // 设定角色的初始位置 player = {left: 2, top: 2}   // 移动前(后)判断角色的下一步的动作(如不能前行) ...

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    // 通过特定标识指定(非)可行区域
    map = [
    [0, 0, 1, 1, 1, 0, 0, 0, 0],
    [0, 1, 1, 0, 0, 1, 0, 0, 0],
    [0, 1, 0, 0, 0, 0, 1, 0, 0],
    [0, 1, 0, 0, 0, 0, 1, 0, 0],
    [0, 1, 1, 1, 1, 1, 1, 0, 0]
    ],
    // 设定角色的初始位置
    player = {left: 2, top: 2}
     
    // 移动前(后)判断角色的下一步的动作(如不能前行)
    ...

    在线运行示例:

    缺点:

    • 适用场景局限。

    适用案例:

    • 推箱子、踩地雷等

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

    任选一种支付方式

    图片 12 图片 13

    1 赞 3 收藏 评论

    关于作者:alvendarthy

    图片 14

    一个热爱生活的家伙! 个人主页 · 我的文章 · 16

    图片 15

    本文由奥门新浦京网址发布于Wed前段,转载请注明出处:常见的2D碰撞检测,一起理解

    关键词: