碰撞检测优化-四叉树
程序员文章站
2024-03-16 16:48:34
...
经过测试得出的结论：
检索的对象比较多时，四叉树检索效率明显优于暴力检索。
演示代码 index.html
<body style="margin: 0px;">
<button style="position: fixed; margin-top: 70px; margin-left: 30px;">当前算法：四叉树检索</button>
<canvas></canvas>
</body>
<script>
const COLOR_WHITE = "rgb(255,255,255)";
const COLOR_GRAY = "rgb(155,155,155)";
const COLOR_RED = "rgb(255,0,0)";
const COLOR_BLUE = "rgb(0,0,255)";
const canvas = document.querySelector("canvas");
const ctx = canvas.getContext("2d");
/**定义矩形类 */
const Rect = (function() {
function Rect() {
this.x = Math.random() * innerWidth;
this.y = Math.random() * innerHeight;
this.width = 10;
this.height = 10;
this.speedX = Math.random() * 10 - 5;
this.speedY = Math.random() * 10 - 5;
this.color = COLOR_GRAY;
}
/**判断是否与指定矩形相交 */
Rect.prototype.intersects = function(rect) {
let maxax = this.x + this.width,
maxay = this.y + this.height,
maxbx = rect.x + rect.width,
maxby = rect.y + rect.height;
return !(maxax < rect.x || maxbx < this.x || maxay < rect.y || maxby < this.y);
}
Rect.pool = [];
Rect.initPool = function() {
for (let i = 0; i < 3000; i++) {
this.pool.push(new Rect());
}
}
Rect.updatePool = function(canvas) {
for (let rect of this.pool) {
ctx.fillStyle = rect.color;
ctx.fillRect(rect.x, rect.y, rect.width, rect.height);
rect.x += rect.speedX;
rect.y += rect.speedY;
rect.x < 0 && (rect.speedX = Math.abs(rect.speedX));
rect.y < 0 && (rect.speedY = Math.abs(rect.speedY));
rect.x > (innerWidth - rect.width) && (rect.speedX = -Math.abs(rect.speedX));
rect.y > (innerHeight - rect.height) && (rect.speedY = -Math.abs(rect.speedY));
}
}
return Rect;
}());
Rect.initPool();
/**四叉树 */
const QuadTree = (function() {
function QuadTree(bounds, max_objects, max_levels, level) {
this.max_objects = max_objects || 10; //最大对象存储数
this.max_levels = max_levels || 5; //树的最大深度，从0开始
this.level = level || 0; //树的当前深度
this.bounds = bounds; //界限信息{x: number, y: number, width: number, height: number},锚点是左上角
this.objects = []; //存储对象
this.nodes = []; //子节点
}
/**使当前节点分裂出四个子节点 */
QuadTree.prototype.split = function() {
let nextLevel = this.level + 1;
let subWidth = this.bounds.width / 2;
let subHeight = this.bounds.height / 2;
let x = this.bounds.x;
let y = this.bounds.y;
this.nodes[0] = new QuadTree({
x: x + subWidth,
y: y,
width: subWidth,
height: subHeight
}, this.max_objects, this.max_levels, nextLevel);
this.nodes[1] = new QuadTree({
x: x,
y: y,
width: subWidth,
height: subHeight
}, this.max_objects, this.max_levels, nextLevel);
this.nodes[2] = new QuadTree({
x: x,
y: y + subHeight,
width: subWidth,
height: subHeight
}, this.max_objects, this.max_levels, nextLevel);
this.nodes[3] = new QuadTree({
x: x + subWidth,
y: y + subHeight,
width: subWidth,
height: subHeight
}, this.max_objects, this.max_levels, nextLevel);
};
/**检索目标对象在当前节点的哪个子节点 */
QuadTree.prototype.getIndexes = function(object) {
let indexes = [];
let centerX = this.bounds.x + (this.bounds.width / 2);
let centerY = this.bounds.y + (this.bounds.height / 2);
let top = object.y < centerY;
let left = object.x < centerX;
let right = object.x + object.width > centerX;
let bottom = object.y + object.height > centerY;
top && right && indexes.push(0);
top && left && indexes.push(1);
bottom && left && indexes.push(2);
bottom && right && indexes.push(3);
return indexes;
};
/**向四叉树插入待检索对象 */
QuadTree.prototype.insert = function(object) {
if (this.nodes.length) {
let indexes = this.getIndexes(object);
for (let index of indexes) {
this.nodes[index].insert(object);
}
return;
}
this.objects.push(object);
if (this.objects.length > this.max_objects && this.level < this.max_levels) {
!this.nodes.length && this.split();
for (let object of this.objects) {
let indexes = this.getIndexes(object);
for (let index of indexes) {
this.nodes[index].insert(object);
}
}
this.objects = [];
}
};
/**检索出可能与该对象发生碰撞的对象集合 */
QuadTree.prototype.retrieve = function(object) {
let returnObjects = this.objects;
if (this.nodes.length) {
let indexes = this.getIndexes(object);
for (let index of indexes) {
returnObjects = returnObjects.concat(this.nodes[index].retrieve(object));
}
}
returnObjects = returnObjects.filter((item, index) => {
return returnObjects.indexOf(item) == index;
});
return returnObjects;
};
/**清空四叉树的内容 */
QuadTree.prototype.clear = function() {
this.objects = [];
for (let node of this.nodes) {
node.clear();
}
this.nodes = [];
};
return QuadTree;
}());
let useQuadTree = true;
let tapBtn = document.querySelector("button");
tapBtn.addEventListener("click", () => {
useQuadTree = !useQuadTree;
tapBtn.innerText = "当前算法：" + (useQuadTree ? "四叉树" : "暴力") + "检索";
});
/**主循环 */
function loop() {
requestAnimationFrame(loop);
canvas.width = window.innerWidth;
canvas.height = window.innerHeight;
ctx.clearRect(0, 0, canvas.width, canvas.height);
Rect.updatePool();
let retrieveStartTime = Date.now();
if (useQuadTree) { //四叉树检索
let tree = new QuadTree({x: 0, y: 0, width: canvas.width, height: canvas.height});
for (let rect of Rect.pool) {
rect.color = COLOR_GRAY;
tree.insert(rect);
}
for (let rect of Rect.pool) {
let targets = tree.retrieve(rect);
for (let target of targets) {
if (rect == target) continue;
if (rect.intersects(target)) {
rect.color = COLOR_RED;
target.color = COLOR_RED;
}
}
}
tree.clear();
} else { //暴力检索
for (let rect of Rect.pool) {
rect.color = COLOR_GRAY;
}
for (let i = 0; i < Rect.pool.length; i++) {
for (let j = i + 1; j < Rect.pool.length; j++) {
let rectA = Rect.pool[i];
let rectB = Rect.pool[j];
if (rectA.intersects(rectB)) {
rectA.color = COLOR_RED;
rectB.color = COLOR_RED;
}
}
}
}
let retrieveTime = Date.now() - retrieveStartTime;
ctx.fillStyle = COLOR_BLUE;
ctx.font = "24px Arial";
ctx.textAlign = "left";
ctx.textBaseline = "top";
ctx.fillText("检索耗时：" + parseInt(retrieveTime) + " ms", 30, 30);
}
requestAnimationFrame(loop);
</script>