preface

“Data structure – using JS to achieve quadtree” in the article briefly introduced some of the implementation and application scenarios of quadtree this article should comment area friends of the message based on the quadtree to achieve 2D collision detection.

So let’s get started.

Let’s start with the quadtree test renderings

Text Coding section

Implementation approach

  • The data structure is a quadtree
  • Collision node comparison and quadtree search

Sample is drawn in Canvas2D and implemented in JavaScript.

The implementation process

Define the Quadtree data structure

/ * * * * @ quadtree structure function quadtree 2 d class need quadtree collision boundary layer / * / node @ param {the Rect} the boundary of the node ({x, y, width, Height}) *@param{number}[Max \u objects=10] @param{number}[Max \u levels=4] @param{number}[level=0] @param{number}[level=0] Child node to the default: 0 * / initial depth function Quadtree (bounds, max_objects max_levels, level) {enclosing max_objects = max_objects | | 4. this.max_levels = max_levels || 4; this.level = level || 0; this.bounds = bounds; this.objects = []; this.nodes = []; };Copy the code

Add objects/ if it exceeds max_objects then dismantle the node

/* * Insert the object into the node. If a node * exceeds capacity, all * objects are split and added to their corresponding child nodes. *@param{Rect} pRect boundary ({x, y, width, Height}) * @ memberof Quadtree * / Quadtree in prototype. Insert = function (pRect) {var I = 0, the indexes; If (this.node.length) {indexes = this.getIndex(pRect); // If (this.node.length) {indexes = this.getIndex(pRect); for(i=0; i<indexes.length; i++) { this.nodes[indexes[i]].insert(pRect); } return; } // Add this.objects.push(pRect) to the objects if it does not exist in nodes; If (this.objects.length > this.max_objects && this.level < this.max_levels) {if(this.objects.length > this.max_objects && this.level < this.max_levels) { // The split method can be used to look at the code in the repository, very simple. I will not post it later. this.nodes.length) { this.split(); } // Add all objects to the corresponding nodes for(I =0; i<this.objects.length; i++) { indexes = this.getIndex(this.objects[i]); Nodes for(var k=0; k<indexes.length; k++) { this.nodes[indexes[k]].insert(this.objects[i]); Object.objects = []; // Max_objects exceeds the logical end}};Copy the code

To obtain

/** * determine which node the object belong to *@param{Rect} pRect boundary ({x, y, width, Height}) * @ return {number} [] phase of jiaozi, node index array (0-3 = upper right, upper left, lower left and lower right) * @ memberof Quadtree * / Quadtree in prototype. GetIndex = function (pRect) { var indexes = [], verticalMidpoint = this.bounds.x + (this.bounds.width/2), HorizontalMidpoint = this.bound. y + (this.bound. height/2); // horizontalMidpoint = this.bound. y + (this.bound. height/2); Y < horizontalMidpoint, startIsWest = prect.x < verticalMidpoint, startIsNorth = prect.x < verticalMidpoint, endIsEast = pRect.x + pRect.width > verticalMidpoint, endIsSouth = pRect.y + pRect.height > horizontalMidpoint; // quad if(startIsNorth && endIsEast) {indexes. Push (0); } // quad if(startIsWest && startIsNorth) {indexes. Push (1); } // quad if(startIsWest && endIsSouth) {indexes. Push (2); } // quad if(endIsEast && endIsSouth) {indexes. Push (3); } return indexes; };Copy the code

Given a RECT structure to collide

/** * return all objects that may be colliding with a given object *@param{Rect} pRect boundary ({x, y, width, height}) *@return{Rect[]} array, Contains all the detected object * @ memberof Quadtree * / Quadtree in prototype. Retrieve = function (pRect) {var indexes = this. GetIndex (pRect), returnObjects = this.objects; //if we have subnodes, retrieve their objects if(this.nodes.length) { for(var i=0; i<indexes.length; i++) { returnObjects = returnObjects.concat(this.nodes[indexes[i]].retrieve(pRect)); }} objects = returnObjects = returnObjects. Filter (function(item, index) { return returnObjects.indexOf(item) >= index; }); return returnObjects; };Copy the code

Clear the quadtree

@memberof Quadtree */ quadtree.prototype.clear = function() {this.objects = []; for(var i=0; i < this.nodes.length; i++) { if(this.nodes.length) { this.nodes[i].clear(); } } this.nodes = []; };Copy the code

Quadtree other related warehousesD3 Quadtree

Take D3 for a study, first of all to achieve a more comprehensive (you can see a specific structure module in the screenshot below) there are Add cover,data,find…. And the details are great, worth learning. Here’s a quick example

Take a module for example: Find the js is also looking for the corresponding nodes and then add the implementation of the same, the difference is understandable for access to the records/no access to repeat points, and have access to the nearest principle (this can do some other work) I = (y > = ym) < < 1 | (x > = xm), are interested can go to learn.

In general, there are some things within D3 that can help you change and improve your thinking, and learning is necessary. By the way, you can try to combine it with the D3-force module in practice for better results.

conclusion

Quadtree as a tree structure, the above example is a good demonstration of quadtree in 2D collision practice, any questions please feel free to leave a message.

Finally, I feel very sorry for the day!!

Other links

The sample code repository above

D3 Quadtree