A detailed explanation of Cocos Creator’s open-source technical solution: using a quadtree to optimize collision detection
Introduction
The Cocos technical support team will continue to organize and provide some practical technical solutions based on the open-source solutions shared by the official employees or developers and update and iterate with Cocos Creator to ensure that it can run in the new version of the engine and help you improve Development efficiency and make better game effects. Let’s start with the “Quadtree Collision Detection Optimization Solution.”
Scheme application effect
A quadtree, also known as a quaternion, is a tree-like data structure with four sub-blocks on each node. Quadtrees are often used to analyze and classify data in two-dimensional space. If it is in three-dimensional space, it is an octree.
A quadtree is an optimization method that can help us divide elements into regions and reduce the number of detections. It should be noted that the quadtree is only an algorithm for “reducing collision candidates.” After using the quadtree to obtain the collision candidate elements, it is also necessary to detect whether these candidate elements collide with the target element.
Use in a scene
Quadtrees are widely used in game development for in-game large map detection, bullet collision detection, etc.
Imagine that if we want to perform collision detection on 200 objects in the game, according to the conventional collision detection method, each object needs to perform physical collision detection on the other 199 objects in each frame. We need to perform 200*199=39800 times to complete one detection cycle. Such detection efficiency can easily have a certain impact on the performance of low-end mobile phones.
The use of quadtree can significantly reduce the number of detections, so how does it do it?
Principle inquiry
We think of the game screen as an area, and we keep placing dots in it. Suppose we set that each area can only accommodate four objects. As long as this number is exceeded, the area will be divided into fours. As shown in the figure below, when the number of dots in the area reaches 4, if you want to add the fifth one, you must first divide the current area into four regions and then put the fifth one into the upper left area:
By analogy, when we want to put the ninth dot, we find that the upper left area where the black dot is located is also full, so** we need to divide the upper left area again.** As shown below:
Finally, we can get a tree structure like the following figure, which is why it is called a quadtree.
Impact checking
GitHub user “xjz1994” provided an open-source solution for quadtree collision detection optimization, which the official technical team has upgraded to Cocos Creator 3.4.1. The core code used is as follows.
Import by code:
import { Quadtree } from "./QuadTree";
Create a quadtree, the area is the entire screen, and save the tree as a global variable:
private tree: Quadtree = null;
start() {
const bounds = {
x: 0,
y:0,
width: screen.width,
height: screen.height
}
this.tree = new Quadtree(bounds);
}
Insert the target element that needs to be checked for collision:
for (let i = 0; i < 250; i++) {
let newNode = instantiate(this.nodePrefab);
this.node.addChild(newNode);
this.nodes.push(newNode);
this.tree.insert(newNode);
}
}
Retrieve the collision object to be detected by the target element, and return the collision candidate element group:
// node is the target element, targetNodes is the group of collision candidate elements
let targetNodes = this.tree.retrieve(node)
//Perform collision detection This part can call your own collision detection, or call the engine's own detection, here choose to write your own
let isCollision: any = this.isCollision(targetNode,node)
Clear the elements in the quadtree to facilitate the next detection:
this.tree.clear();
Download
- Click at the end of the article [read the original text] to go to GitHub to download the program for free:
- Forum Feedback Post