Для аналогичной задачи (2D) я создал простую конструкцию типа дерева квадрантов, в которой каждый узел может содержать либо другие дочерние узлы, либо список экранных объектов для обнаружения столкновений.Обратите внимание, что если объекты (блоки в вашем случае) много перемещаются, это не будет эффективно, так как вам нужно будет перемещать их в правый узел каждый раз при перемещении.
Простой пример класса будет:
public class WorldPartitionNode {
private var minX : Number;
private var minY : Number;
private var maxX : Number;
private var maxY : Number;
private var width : Number;
private var height : Number;
private var _children : Vector.<WorldPartitionNode>;
private var _objects : Vector.<GameObject>;
public function WorldPartitionNode(x : Number, y : Number,
w : Number, h : Number, childLevels : int)
{
minX = x;
minY = y;
maxX = x + w;
maxY = y + h;
width = h;
height = h;
if (childLevels == 0) {
// This node should have no children, so instead it should
// contain display objects
_objects = new Vector.<GameObject>;
}
else {
_children = new Vector.<WorldPartitionNode>(4,true);
_children[0] = new WorldPartitionTreeNode(minX, minY, width/2, height/2, childLevels-1);
_children[1] = new WorldPartitionTreeNode(minX+width/2, minY, width/2, height/2, childLevels-1);
_children[2] = new WorldPartitionTreeNode(minX, minY+height/2, width/2, height/2, childLevels-1);
_children[3] = new WorldPartitionTreeNode(minX+width/2, minY+height/2, width/2, height/2, childLevels-1);
}
}
public function addObject(obj : GameObject) : void
{
if (_children) {
// This is not a leaf node, so add it to that of the child
// nodes in which it belongs.
var i : uint;
for (i=0; i<4; i++) {
var c : WorldPartitionNode = _children[i];
if (obj.x > c.minX && obj.y > c.minY && obj.x < c.maxX && obj.y < c.maxY) {
c.addObject(obj);
return; // Found node, so bail
}
}
}
else {
// This is a leaf node, so just add to the internal objects vector
_objects.push(obj);
}
}
public function checkCollisions(x : Number, y : Number) : GameObject
{
if (_children) {
// This node has children, so delegate to the right child
var i : uint;
for (i=0; i<4; i++) {
var c : WorldPartitionNode = _children[i];
if (x > c.minX && y > c.minY && x < c.maxX && y < c.maxY) {
return c.checkCollisions(x, y);
}
}
}
else {
// This is a leaf node (with objects directly in it) so loop through
// them all and check collision
var obj : GameObject;
for each (obj in _objects) {
if (obj.collidesWith(x, y))
return obj;
}
return null; //None if reached
}
}
}
Экземпляры этого класса разделятся на четыре прямоугольные секции (две строки, два столбца), если childLevels > 0, и создадут экземпляры одного и того же класса для каждого из этих узлов.Эти узлы, в свою очередь, будут делить свое пространство одинаково до тех пор, пока не будет получено в общей сложности childLevels уровней.
Таким образом, вы можете создать четырехуровневое четырехугольное дерево (с 64 конечными узлами разбиения), где каждый узелвсего 1/64 размера исходного пространства.Когда вы добавляете объекты с addObject(), объект будет добавлен к узлу разбиения, который соответствует квадрату, в котором он расположен.
Когда вы выполните checkCollision(), он будет повторяться childLevels раз, пока не будетнаходит правильный раздел, а затем выполняет обычный цикл обнаружения столкновений только для объектов в этом разделе.
Чтобы создать трехуровневое дерево, занимающее пространство размером 1024x1024 пикселей:
var treeRoot : WorldPartitionNode = new WorldPartitionNode(0, 0, 1024, 1024, 3);
И для проверки столкновений между вашими ракетами и объектами в дереве:
var missile : GameObject;
for each (missile in _missiles) {
var obj : GameObject = treeRoot.checkCollisions(missile.x, missile.y);
if (obj != null)
obj.kill(); // Was hit by missile
}
Это, вероятно, значительно ускорит обнаружение столкновений, но полагается на то, что ящики статичны (или редко перемещаются),потому что, если они перемещаются, они больше не будут в правильном узле раздела, и если они не будут, дерево не сможет обнаружить коллизии между ними.
Нет никаких сомнений, что более разумные системы разделения существуют, но это работало оченьхорошо для меня в проекте, где мне нужно было разбрасывать пикапы (монеты и т. д.) в большом пространстве и там, гдеты бы полетел вокруг, чтобы собрать их.Затем каждый кадр я бы позволял дереву проверять наличие столкновений между статическими пикапами и игроком.