HTML5 implements 3D and 2D visualization QuadTree quadtree collision detection_PHP tutorial

HTML5 implements 3D and 2D visualization QuadTree quadtree collision detection

QuadTree quadtree, as the name suggests, is a tree-like data structure. Each node has four child nodes, which can Recursively divide a two-dimensional plane into subregions. QuadTree is often used for spatial database indexing, 3D vertebral visible area cropping, and even image analysis and processing. What we introduce today is QuadTree’s collision detection, which is most commonly used in the game field. Using the QuadTree algorithm will greatly reduce the number of collisions that need to be tested, thereby improving the game refresh performance. The example in this article is based on the Canvas topology map of HT for Web and the 3D engine component of WebGL, sharing the same data model DataModel through GraphView and Graph3dView, and simultaneously presenting the QuadTree algorithm. 2D and 3D collision view effects: http://v.youku.com/v_show/id_XODQyNTA1NjY0.html

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

There are many mature versions of QuadTree implementation. The one I chose is https://github.com/timohausmann/quadtree-js/ The algorithm of quadtree is very simple, so this The open source library only has about 200 lines of code. It is also very simple to use. Construct a Quadtree object. The first parameter is passed in rect information to set the game space range. Every time requestAnimationFrame refreshes the frame, the old data is first cleared through quadtree.clear() and inserted through quadtree.insert(rect). The new node rectangular area, so that quadtree is initialized. All that remains is to call quadtree.retrieve(rect) as needed to obtain an array of rectangular objects that may intersect with the specified rectangular area and need to be detected.

I built two components of HT (http://www.hightopo.com/) GraphView and Graph3dView, which are split left and right through ht.widget.SplitView. Since both views share the same DataModel, we The remaining focus is only on the data operation of the DataModel. 200 ht.Node objects are constructed. The attr attribute of each object saves the random movement directions vx and vy, and also saves the rectangular object that will be repeatedly inserted into the quadtree. This avoids repeatedly creating objects when updating each frame. At the same time, the rectangular object also references the ht.Node object. When obtaining the rectangular object that needs to be detected through quadtree.retrieve(rect), we can specify its associated ht.Node object. , because we need to set a red color effect on the primitives that are finally detected as collisions, that is, ht.Node usually displays the default blue color, and will change to red when it collides with each other.

It should be noted that the array of rectangular objects that need to be detected obtained from quadtree.retrieve(rect) will contain its own primitives. At the same time, these are only primitives that may collide. It does not mean that they have already collided. Since we The example is a rectangle, so ht.Default.intersectsRect(r1, r2) is used to finally determine whether it intersects. If your example is a circle, you can calculate whether the distance between the two circle centers is less than two radii to determine whether it intersects, so the final judgment is Criteria vary based on game type.

The use of QuadTree has greatly improved the computing performance. Otherwise, 100 graphics elements would require 100*100 times of monitoring. In my example scenario, the amount is generally 100*(10~30): http://v.youku.com/v_show/id_XODQyNTA1NjY0.html

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

In addition to collision detection, the QuadTree algorithm has many interesting application areas. If you are interested, you can play with this https://github.com/fogleman/Quads

All The code is as follows for reference:

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 d){                data.a('vx', -vx);                x = d - w;            }            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 continue data2.a setcolor requestanimationframe function randminmax max return min createshape shape="new" ht.shape shape.setpoints shape.setthickness shape.settall shape.s null datamodel.add color data.s><p style="margin:10px auto;font-family:verdana, Arial, Helvetica, sans-serif;font-size:14px;line-height:21px;white-space:normal;"></p>
<p align="left"></p>
<div style="display:none;">
<span id="url" itemprop="url">http://www.bkjia.com/PHPjc/1080259.html</span><span id="indexUrl" itemprop="indexUrl">www.bkjia.com</span><span id="isOriginal" itemprop="isOriginal">true</span><span id="isBasedOnUrl" itemprop="isBasedOnUrl">http: //www.bkjia.com/PHPjc/1080259.html</span><span id="genre" itemprop="genre">TechArticle</span><span id="description" itemprop="description">HTML5 realizes 3D and 2D visualization QuadTree quadtree collision detection QuadTree quadtree, as the name suggests, is a tree-like data structure. Each node has four child nodes, which can recursively divide the two-dimensional plane...</span>
</div>
<div class="art_confoot"></div></objs.length>