C++

Forum

 
Merging quadtree nodes

vastrolorde (178)
Im trying to implement dynamic quadtree. It is bit overkill but its for learning.
I have set a minimum element count for nodes. If object count in a node falls under the minimum i check its parent node for total object count(node + its children + children children + ...) And if that too falls under minimum i want to merge the parent node. Merging means that the parent node children will disappear and all the objects that were in the children are now in the parent. I have not run this part yet but i get the feeling that this is terribly made and that it will just break. So could someone take a look at it and give me advice how to make it better.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
 
void QuadTree::remove(Collider *col) {
	objects.erase(std::remove(objects.begin(), objects.end(), col), objects.end());
	merge();
}

void QuadTree::merge() {
	if (getObjectCount() < MIN_OBJECTS) {
		if (nodes[0] != NULL) {
			for (int i = 0; i < 4; i++) {
				std::vector<Collider*>::iterator it = objects.end();
				std::vector<Collider*> temp = nodes[i]->getObjects();
				objects.insert(it, temp.begin(), temp.end());
				delete nodes[i];
				nodes[i] = 0;
			}
		}
		parent->merge();
	}
}

std::vector<Collider*> QuadTree::getObjects() {
	std::vector<Collider*> objs;
	if (nodes[0] != NULL) {
		for (int i = 0; i < 4; i++) {
			std::vector<Collider*>::iterator it = objs.end();
			std::vector<Collider*> temp = nodes[i]->getObjects();
			objs.insert(it, temp.begin(), temp.end());
		}
	}

	std::vector<Collider*>::iterator it = objs.end();
	objs.insert(it, objects.begin(), objects.end());

	return objs;
}

int QuadTree::getObjectCount() {
	int count = objects.size();
	if (nodes[0] != NULL) {
		for (int i = 0; i < 4; i++) {
			count += nodes[0]->getObjectCount();
		}
	}
	return count;
}
vastrolorde (178)
OK i have run it and it causes error: "Exception thrown at 0x00CC417B in PhysicsEngine.exe: 0xC0000005: Access violation reading location 0x0000000C". So my guess is that the Child object calls for parentobject that destroys the child object. That this is the problem. But it needs to go like this. I dont know how to fix it.
closed account (48bpfSEw)
don't delete the nodes[i] within the for-loop!

1
2
3
4
5
6
7
8
9
10
 
list<int> lst; // Index2Delete;

for (...) {

  lst.push_back(i); // remember what you want to delete
 }


for (lst::iterator it...) 
  delete[nodes[*it]);
vastrolorde (178)
Its better now. But the parent->merge() is now the problem. Since there is a chance that the parent will delete its child the execution of the childs merge function can be cut short. How could i do it so that the parent can delete its child even when child invoked the parents merge function.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
void QuadTree::merge() {
	if (getObjectCount() < MIN_OBJECTS) {
		if (nodes[0] != NULL) {
			for (int i = 0; i < 4; i++) {
				std::list<Object*>::iterator it = objects.end();
				std::vector<Object*> temp = nodes[i]->getObjects();
				objects.insert(it, temp.begin(), temp.end());
			}
			for (int i = 0; i < 4; i++) {
				delete nodes[i];
				nodes[i] = NULL;
			}
		}
		if(parent != NULL)
			parent->merge();
	}
}
vastrolorde (178)
Topic archived. No new replies allowed.