HT for Web可视化QuadTree四叉树碰撞检测

QuadTree四叉树顾名思义就是树状的数据结构,其每个节点有四个孩子节点,可将二维平面递归分割子区域。QuadTree常用于空间数据库索引,3D的椎体可见区域裁剪,甚至图片分析处理,我们今天介绍的是QuadTree最常被游戏领域使用到的碰撞检测。采用QuadTree算法将大大减少需要测试碰撞的次数,从而提高游戏刷新性能,本文例子基于HT for Web的图形引擎,通过GraphViewGraph3dView共享同一数据模型DataModel,同时呈现QuadTree算法下的2D和3D碰撞视图效果:http://v.youku.com/v_show/id_XODQyNTA1NjY0.html

QuadTree的实现有很多成熟的版本,我选择的是 https://github.com/timohausmann/quadtree-js/ 四叉树的算法很简单,因此这个开源库也就两百来行代码。使用也非常简单,构建一个Quadtree对象,第一个参数传入rect信息制定游戏空间范围,在每次requestAnimationFrame刷新帧时,先通过quadtree.clear()清除老数据,通过quadtree.insert(rect)插入新的节点矩形区域,这样quadtree就初始化好了,剩下就是根据需要调用quadtree.retrieve(rect)获取指定矩形区域下,与其可能相交需要检测的矩形对象数组。

我构建了HTGraphViewGraph3dView两个组件,通过ht.widget.SplitView左右分割,由于两个视图都共享同一DataModel,因此我们剩下的关注点仅是对DataModel的数据操作,构建了200个ht.Node对象,每个对象的attr属性上保存了随机的运动方向vx和vy,同时保存了将要反复插入quadtree的矩形对象,这样避免每帧更新时反复创建对象,同时矩形对象也引用了ht.Node对象,用来当通过quadtree.retrieve(rect)获取需要检测的矩形对象时,我们能指定其所关联的ht.Node对象,因为我们需要对最终检测为碰撞的图元设置上红颜色的效果,也就是ht.Node平时显示默认的蓝色,当互相碰撞时将改变为红色。

需要注意从quadtree.retrieve(rect)获取需要检测的矩形对象数组中会包含自身图元,同时这些仅仅是可能会碰撞的图元,并不意味着已经碰撞了,由于我们例子是矩形,因此采用ht.Default.intersectsRect(r1, r2)最终判断是否相交,如果你的例子是圆形则可以采用计算两个圆心距离是否小于两个半径来决定是否相交,因此最终判断的标准根据游戏类型会有差异。

采用了QuadTree还是极大了提高了运算性能,否则100个图元就需要100*100次的监测,我这个例子场景下一般也就100*(10~30)的量:http://v.youku.com/v_show/id_XODQyNTA1NjY0.html

除了碰撞检测外QuadTree算法还有很多有趣的应用领域,有兴趣可以玩玩这个 https://github.com/fogleman/Quads

所有代码如下供参考:

function init(){  
    d = 200;
    speed = 8;
    dataModel = new ht.DataModel();                                
    g3d = new ht.graph3d.Graph3dView(dataModel);                                                  
    g2d = new ht.graph.GraphView(dataModel);                   
    mainSplit = new ht.widget.SplitView(g3d, g2d);                   
    mainSplit.addToDOM();                                        
    g2d.translate(300, 220);      
    g2d.setZoom(0.8, true);
      
    for(var i=0; i<100; i++) {
        var node = new ht.Node();
        node.s3(randMinMax(5, 30), 10, randMinMax(5, 30));
        node.p3(randMinMax(-d/2, d/2), 0, randMinMax(-d/2, d/2));
        node.s({
            'batch': 'group',
            'shape': 'rect',
            'shape.border.width': 1,
            'shape.border.color': 'white',
            'wf.visible': true,
            'wf.color': 'white'
        });
        node.a({
            vx: randMinMax(-speed, speed),
            vy: randMinMax(-speed, speed),
            obj: {
                width: node.getWidth(),
                height: node.getHeight(),
                data: node
            }
        });                    
        dataModel.add(node);
    }                
    createShape([
        {x: -d, y: d},
        {x: d, y: d},
        {x: d, y: -d},
        {x: -d, y: -d},
        {x: -d, y: d}
    ]);                   
    quadtree = new Quadtree({ x: -d, y: -d, width: d, height: d });                                
    requestAnimationFrame(update);
}               
function update() {   
    quadtree.clear();                
    dataModel.each(function(data){
        if(!(data instanceof ht.Shape)){
            var position = data.getPosition();
            var vx = data.a('vx');
            var vy = data.a('vy');
            var w = data.getWidth()/2;
            var h = data.getHeight()/2;
            var x = position.x + vx;
            var y = position.y + vy;
            if(x - w < -d){
                data.a('vx', -vx);
                x = -d + w;
            }
            if(x + w > d){
                data.a('vx', -vx);
                x = d - w;
            }
            if(y - h < -d){
                data.a('vy', -vy);
                y = -d + h;
            }
            if(y + h > d){
                data.a('vy', -vy);
                y = d - h;
            }
            data.setPosition(x, y);                        
            var obj = data.a('obj');
            obj.x = x - w;
            obj.y = y - h;
            
            quadtree.insert(obj);
            setColor(data, undefined);
        }
    });                
    dataModel.each(function(data){
        if(!(data instanceof ht.Shape)){ 
            var obj = data.a('obj');
            var objs = quadtree.retrieve(obj);
            if(objs.length > 1){                            
                for(var i=0; i<objs.length; i++ ) {
                    var data2 = objs[i].data;
                    if(data === data2){
                        continue;
                    }
                    if(ht.Default.intersectsRect(obj, data2.a('obj'))){
                        setColor(data, 'red');
                        setColor(data2, 'red');
                    }                                
                }                             
            }
        }
    });
    requestAnimationFrame(update);                    
}                        
function randMinMax(min, max) {
    return min + (Math.random() * (max - min));
}                      
function createShape(points){
    shape = new ht.Shape();
    shape.setPoints(points);
    shape.setThickness(4);
    shape.setTall(10);                                
    shape.s({
        'all.color': 'red',
        'shape.background': null,
        'shape.border.width': 2,
        'shape.border.color': 'red'                    
    });                
    dataModel.add(shape); 
    return shape;
}
function setColor(data, color){
    data.s({
        'all.color': color,
        'shape.background': color
    });
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏游戏杂谈

as3绘制抛物线

一般做页游的过程中,特效的释放可能是不是固定位置的播放,是需要进行“运动的”(其实就是移动特效这个影响剪辑)。举个例子:步兵射箭,不确定箭发射的方向,事先也不...

912
来自专栏IMWeb前端团队

前端如何呼风唤雨

创世纪第一章 首卷原文 起初我创造了canvas 。 我说,要有雨,就有了雨; 我说,要有雪,就有了雪。 而对于前端来说,canvas即是天地 在canv...

2657
来自专栏菩提树下的杨过

Metaball(元球)效果学习

几年前就在网上曾看见过这种效果,但一直不知道叫什么名字 ? 前一阵无意在9ria(天地会)论坛上看到了一篇专门讲这个的文章:AS3 元球(Metaball),不...

21810
来自专栏码洞

人生苦短我用Python?No!学习Python的真正理由其实是

作者:gashero 链接:https://www.zhihu.com/question/282875062/answer/441546530

511
来自专栏互联网大杂烩

八皇后问题

八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例:在8X8格的国际象棋棋盘上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一...

692
来自专栏数据小魔方

一款脑洞大开的表格可视化神器

今天跟大家介绍一款任坤大神写的新包——formattable。 这个包的功能很简单,但是却很具创意性,它颠覆了R语言data.frame数据表的呈现方式,允许在...

4478
来自专栏阿凯的Excel

巧妙完成二维表的数据匹配

接下来我将每周分享一个广大网友向我提问的经典问题。 本周问题,如何对二维表进行匹配! 原表格! ? 备注:以上人名,均属虚构,如有雷同!说明有缘!!! 咳...

2743
来自专栏数据小魔方

excel数据排序的常用方式

今天跟大家分享几种常用的数据排序方式! ▼ 在excel中整理数据、作图或者其他数据汇总操作,常会遇到对某一列数据排序的需求。当然用肉眼观察手动排序肯定是不现实...

41611
来自专栏Flutter&Dart

Flutter之通过AnimationController源码分析学习使用Animation

他实际上就是一个抽象类,在dart里面抽象类可继承可实现,看源码知道,他主要的一个方法就是dispose,用于规定释放资源的方法

1692
来自专栏HT

HTML5实现3D和2D可视化QuadTree四叉树碰撞检测

QuadTree四叉树顾名思义就是树状的数据结构,其每个节点有四个孩子节点,可将二维平面递归分割子区域。QuadTree常用于空间数据库索引,3D的椎体可见区域...

2249

扫码关注云+社区