QuadTree四叉树顾名思义就是树状的数据结构,其每个节点有四个孩子节点,可将二维平面递归分割子区域。QuadTree常用于空间数据库索引,3D的椎体可见区域裁剪,甚至图片分析处理,我们今天介绍的是QuadTree最常被游戏领域使用到的碰撞检测。采用QuadTree算法将大大减少需要测试碰撞的次数,从而提高游戏刷新性能,本文例子基于HT for Web的图形引擎,通过GraphView和Graph3dView共享同一数据模型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)获取指定矩形区域下,与其可能相交需要检测的矩形对象数组。
我构建了HT的GraphView和Graph3dView两个组件,通过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)的量:
除了碰撞检测外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 }); }
相关推荐
这个代码是一个四叉树的C#实现,使用四叉树文成一个可视项目。四叉树是一种树结构可以用于编码和2D碰撞检测。多用在2D碰撞检测中,在大量的碰撞检测中可以提高效率,但结构略复杂。
creator 四叉树 Quadtree.ts 用于优化碰撞检测
matlab 图像分析 包括(边缘检测 ;微分算子 ;Log算子 ;Canny 算子 ;四叉树分解 ;四叉树分解 ;四叉树及相应的MATLAB 函数
使用四叉树进行粒子碰撞检测。 四叉树是一种树数据结构,其中每个内部节点恰好具有四个子节点。 四叉树是八叉树的二维模拟,最常用于通过将二维空间递归细分为四个象限或区域来划分二维空间。 演示版 在GitHub页面...
使用c++实现一棵四叉树,每个叶节点最多只包含一个二维平面的点。四叉树可以进行遍历,删除,添加,查询操作。
四叉树分割图像中的点,左键点击 右键分割
四叉树这是Quadtree的Java实现,Quadtree是一种树数据结构,可用于存储2D位置数据。用法创建新的四叉树从点(0,0)开始以400 x 400尺寸初始化世界// init.Dimension dimension = new Dimension ( 400 , 400 ); ...
图像的Matlab用四叉树分解程序 可以自定义detfun函数以确定基于什么规则判断目标block需要继续分解或者不用继续分解 编辑encode函数可以改变分块的编码方式 test_codec函数为源码本身自带的编解码 test_split函数为...
四叉树 这是一个基于JavaScript方法JavaScript Quadtree实现,该实现基于在上描述的Java方法: 许多游戏需要使用碰撞检测算法来确定两个对象何时发生碰撞,但是这些算法通常是昂贵的操作,并且会大大降低游戏的速度...
一种基本的四叉树类型,用于检索潜在的碰撞 方法 用于插入和检索“对象”的数据类型定义为: object = {} object. left = _ object. top = _ object. width = _ object. height = _ Quadtree.create(left,top,...
quadtree-js, 另一个用于javascript的四叉树实现 四叉树 js这是本教程中介绍的Java方法的JavaScript四叉树实现: http://gamedev.tutsplus.com/tutorials/implementation/quick-tip-use-quadtrees-to-
四叉树 Lua 模块 版权 版权所有 (C) 2008 Samuel Stauffer < > 执照 GPLv2 - 有关许可证详细信息,请参阅许可证和复制。 API 文档 QuadTree.new(左、上、宽、高) 创建并返回具有给定位置和大小的 QuadTree 类的...
最近在看canvas动画方面教程,里面提到了采用四叉树检测碰撞。之前也看到过四叉树这个名词,但是一直不是很懂。于是就又找了一些四叉树方面的资料看了看,做个笔记,就算日后忘了,也可以回来看看。 QuadTree四叉树...
Unity下的 四叉树Demo, 参考 https://github.com/CodingTrain/QuadTree
四叉树Python 在Python3中实现四叉树算法。
QuadTree(VC#2005) 四叉树算法C#实现 GDI+示例
四叉树分割 opencv 编写 读入灰度图 进行递归分割(Quadtree segmentation opencv read into grayscale prepared for recursive partitioning)
四叉树是用于二维空间对象查找的一个数据结构,本实现包括了三个类:QuadTree,QuadTreeNode, QuadNodeItem。
四叉树上的A * 四叉树上的A *算法
来自维基百科 - 有关更多信息,请访问 项目包括几个演示场景来清楚地展示 QuadTree 的可用性: Only balls(飞球) - QuadTree 中二维对象的简单可视化Collisions - 检测两个球之间的碰撞(大约 150 个球) 简单...