Weird behaviour

[vastrolorde]

Im trying to implement quadtree. I have mostofit done, it works to a degree, but then it crashes with nullptr error. After lots of debugging i have boiled it down to the problem i think it is.

The thing is as follows. I set the max level depth for quadtree to be 5. I start with a object on the field. Its location isnt good to fit into the 5th level, so it sits in the 4th level. Now it starts to move. For few ms before leaving the first quadrant of the 4th level it sits in the 5th level. Now the problem starts. Object keeps moving and object itself knows where it is in witch quadrant of witch level. But the quadtree itself doesent. Object is starting to near the first quadrant of the 1st level. Now it should switch to 0th level(root) for few moments and then be put back to another quadrant of 1st level. But inside quadtree the object is still located in the level 5 of the very first quadrant. Why wont it change it.

Here is my code that controls the changing quadrants, if more is needed tell me:

void Object::checkContainemnt() {
	if (!partition->containsAndResides(this)) {
		QuadTree* temp = partition->getParent();
		while (!temp->contains(this)) {
			temp = temp->getParent();
		}
		temp->insert(this);
		partition->remove(this);
	}
}

bool QuadTree::contains(Object* col) {
	if (*(col->x_p) < bounds.x || *(col->x_p) + *(col->w_p) > bounds.x + bounds.w) return false;
	if (*(col->y_p) < bounds.y || *(col->y_p) + *(col->h_p) > bounds.y + bounds.h) return false;

	return true;
}

bool QuadTree::containsAndResides(Object* col) {
	return contains(col) && std::find(objects.begin(), objects.end(), col) != objects.end();
}

void QuadTree::insert(Object *col) {
	if (col == NULL) return;
	if (nodes[0] != NULL) {
		int index = getIndex(col);

		if (index != -1) {
			(*nodes[index]).insert(col);
			return;
		}
	}

	objects.push_back(col);
	col->setPartition(this);

	if (objects.size() > MAX_OBJECTS && level < MAX_LEVELS) {
		divide();
	}
}

void QuadTree::divide() {
	if (nodes[0] == NULL) {
		split();
	}

	std::list<Object*>::const_iterator it = objects.begin();
	while (it != objects.end()) {
		int index = getIndex(*it);

		if (index != -1) {
			(*nodes[index]).insert(*it);
			it = objects.erase(it);
		}
		else {
			++it;
		}
	}
}

void QuadTree::remove(Object *col) {
	objects.erase(std::remove(objects.begin(), objects.end(), col), objects.end());
}

//This is called after object is moved and all the checks are done to determine //the quadrant


//If quadrant is empty and its parent is below min treshold merge children
//together.(Currently not working)
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;
			}
		}
	} else*/ if (objects.size() > MAX_OBJECTS && level < MAX_LEVELS) {
		divide();
	}
	else if(nodes[0] != NULL){
		for (int i = 0; i < 4; i++) {
			nodes[i]->merge();
		}
	}
}

[vastrolorde]

Fixed the weird behaviour. I did a silly mistake. I inserted object to new partioion, but it also set the partition of the object to the new partition and then i removed the object from the same partition.

Now the problem is "Exception thrown: read access violation.
this was 0xDDDDDDDD." and is cause by the first if in function merge.

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;
			}
		}
	} else if (objects.size() > MAX_OBJECTS && level < MAX_LEVELS) {
		divide();
	}
	else if(nodes[0] != NULL){
		for (int i = 0; i < 4; i++) {
			nodes[i]->merge();
		}
	}
}

[cire]

Now the problem is "Exception thrown: read access violation.
this was 0xDDDDDDDD." and is cause by the first if in function merge.

Where a problem manifests is often not the cause. Here, this has an invalid value and the if condition is the first place this is dereferenced. The problem is in the code that calls this function.

You might have a read here to discover what that value signifies (assuming you're using VC++ in a debug build):
http://www.nobugs.org/developer/win32/debug_crt_heap.html#table

[vastrolorde]

i found the mistake. Mistake was in the getObjectCount function. Instead of for i ->4{nodes[i]} i had for i -> 4 {nodes[0]} (This is pseudocode for those who dont know).
And since the nodes[0] is in the testing set always empty it just breaks the code and causes the merge to delete everything.