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

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

http://www.hightopo.com/demo/QuadTree/ht-quadtree.html

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

我构建了HT(http://www.hightopo.com/)的GraphViewGraph3dView两个组件,通过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

http://www.hightopo.com/demo/QuadTree/ht-quadtree.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 条评论
登录 后参与评论

相关文章

来自专栏技术博客

Win8 连连看 第二季(1)

思路如下:暂定游戏中图标有100个(10行10列),对每个小图标用用户控件进行展示(好处很多方便绑定数据,链接事件,实现动画效果等)。

562
来自专栏HT

玩转 HTML5 下 WebGL 的 3D 模型交并补

建设性的立体几何具有许多实际用途,它用于需要简单几何对象的情况下,或者数学精度很重要的地方,几乎所有的工程 CAD 软件包都使用 CSG(可以用于表示刀具切削,...

18110
来自专栏hightopo

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

1156
来自专栏落影的专栏

iOS开发-OpenGLES进阶教程4

教程 OpenGLES入门教程1-Tutorial01-GLKit OpenGLES入门教程2-Tutorial02-shader入门 OpenGLES入门...

2534
来自专栏数据小魔方

多条件排序

今天跟大家分享多条件排序的技巧! 之前分享过关于excel中的排序菜单及所有的排序函数,但是这些菜单和函数的排序功能仅限于单列排序,无法完成多列的多条件排序功...

2576
来自专栏逍遥剑客的游戏开发

WoWModelViewer分析

1625
来自专栏我和未来有约会

Silverlight 3.0 中的 WriteableBitmap

Silverlight 3.0 中的 WriteableBitmap 尽管矢量图形非常的强大但是在有些情况下还是需要用到位图,因为他们在运行时能得到更高的执行效...

1858
来自专栏hightopo

基于HTML5 Canvas的CSG构造实体几何书架

643
来自专栏Code_iOS

OpenGL ES 2.0 (iOS)[03]:熟练图元绘制,玩转二维图形

文章的大前提是,你得有《OpenGL ES 2.0 (iOS): 一步从一个小三角开始》的基础知识。

1091
来自专栏流媒体

Android平台下使用FFmpeg进行RTMP推流(摄像头推流)

前面讲到了在Android平台下使用FFmpeg进行RTMP推流(视频文件推流),里面主要是介绍如何解析视频文件并进行推流,今天要给大家介绍如何在Android...

1074

扫码关注云+社区