Jump to content
  • Advertisement
Sign in to follow this  
Dizzy1

seg fault while traversing a rendering tree

This topic is 3980 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm experiencing some difficulty while testing my 2d game engine. [help] My system manages rendering the scene through a global class called RenderManager. when an object needs to get rendered it's passed to RenderManager::insertEntity(Entity& e1, int z = 0), then a EntityQueueItem object gets built which contains the entity, and its z-value, that are passed to the function. this EntityQueueItem gets pushed into the entityQueue, which contains all the enitities that need to get rendered. when RenderManager::Run gets called each frame, all the entities in the queue get sorted in two binary trees, one - yValueTree sorts the entities that have a 0 z-value by their y position, and the other - zValueTree (as you probably guessed [smile] ) sorts the remaining entities by their z-value. the trees are traversed inorder obviously, and it appears as it crashes there. when there is a relatively small amount of entities on screen everything is fine, but going higher than 10-12 is dangerous. i can't figure out where the problem is, so i need you for that... the TNode class:
#ifndef TNODE_H_
#define TNODE_H_

namespace Ginge
{

template <class T>
class TNode
{
	void ClearNodes();
public:
	TNode<T> * Left;
	TNode<T> * Right;
	TNode<T> * Thread;
	T Value;
	TNode(const T& t) { Value = t; Left = 0; Right = 0; }
	TNode() { Left = 0; Right = 0; }
	virtual ~TNode() { 
		ClearNodes();
	}
	const T& operator()() const { return Value; }
	T& operator()() { return Value; }
	void operator()(const T& t) { Value = t; }
	bool operator==(const TNode& t) { return ((Value == t.Value)&&(Left == t.Left)&&(Right == t.Right)); }
};

template<class T>
void TNode<T>::ClearNodes()	
{
	if (Left) {
		delete Left;
                Left = 0;
	}
	if (Right) {
		delete Right;
                Right = 0;
	}
}

}

#endif /*TNODE_H_*/




RenderManager header:
typedef std::queue<EntityQueueItem> EntityQueue;

class RenderManager
{
	static EntityQueue entityQueue;
	static BinaryTree<EntityQueueItem *> zValueTree;
	static BinaryTree<EntityQueueItem *> yValueTree;
	static Display * display;
	static void inOrder(TNode<EntityQueueItem *> * T);
	static void addNode(EntityQueueItem& item, TNode<EntityQueueItem *> *& T);
public:
	static void insertEntity(Entity& e1, int z = 0);
	static void removeEntity(Entity& e1);
	static void Init();
	static void Init(int width, int height, int bpp, Uint32 flags);
	static void Run();
	static Display& getDisplay();
	static void Clean();
};




RenderManager implementation:
EntityQueue RenderManager::entityQueue;
BinaryTree<EntityQueueItem *> RenderManager::zValueTree;
BinaryTree<EntityQueueItem *> RenderManager::yValueTree;
Display * RenderManager::display;

void RenderManager::inOrder(TNode<EntityQueueItem *> * T)
{
	if (T) {
		inOrder(T->Left);
		T->Value->entity->Render(*display);
		inOrder(T->Right);
	}
}

void RenderManager::addNode(EntityQueueItem& item, TNode<EntityQueueItem *> *& T)
{
	if (item.z) {
		if (T) {
			if (T->Value->z > item.z) {
				addNode(item, T->Left);
			} else {
				addNode(item, T->Right);
			}
		} else {
			T = new TNode<EntityQueueItem *>(&item);
		}
	} else {
		if (T) {
			if (T->Value->entity->getPosition().getY() > item.entity->getPosition().getY()) {
				addNode(item, T->Left);
			} else {
				addNode(item, T->Right);
			}
		} else {
			T = new TNode<EntityQueueItem *>(&item); 
		}
	}
}

void RenderManager::insertEntity(Entity& e1, int z)
{
	entityQueue.push(EntityQueueItem(&e1, z));
}

void RenderManager::removeEntity(Entity& e1)
{
	EntityQueue temp;
	for (unsigned int i=0; i<entityQueue.size(); i++) {
		if (entityQueue.front().entity == &e1) {
			entityQueue.pop();
		} else {
			temp.push(entityQueue.front());
			entityQueue.pop();
		}
	}
	for (unsigned int i=0; i<temp.size(); i++) {
		entityQueue.push(temp.front());
		temp.pop();
	}
}

void RenderManager::Init()
{
	display = new Display();
}

void RenderManager::Init(int width, int height, int bpp, Uint32 flags)
{
	display = new Display(width, height, bpp, flags);
}

void RenderManager::Run()
{
	yValueTree.Clear();
	zValueTree.Clear();
	for (unsigned int i=0; i<entityQueue.size(); i++) {
		Rectangle rectCamera(MapManager::getTileMap().getCameraOffset(), MapManager::getTileMap().getCameraHeight(), MapManager::getTileMap().getCameraWidth());
		Rectangle rectEntity(entityQueue.front().entity->getPosition(), entityQueue.front().entity->getActiveSprite().getHeight(), entityQueue.front().entity->getActiveSprite().getWidth());
		if (rectCamera.Intersect(rectEntity))
		{
			if (entityQueue.front().z) {
				addNode(entityQueue.front(),zValueTree.Root);
			} else {
				addNode(entityQueue.front(),yValueTree.Root);
			}
		}
		entityQueue.push(entityQueue.front());
		entityQueue.pop();
	}
	
	display->Fill(0x00);
	MapManager::getTileMap().Render(*display);
	inOrder(yValueTree.Root); 
	inOrder(zValueTree.Root);
	display->Flip();
}

Display& RenderManager::getDisplay()
{
	return * display;
}

void RenderManager::Clean()
{
	delete display;
	yValueTree.Clear();
	zValueTree.Clear();
}




sorry for this load of code... [oh] [Edited by - Dizzy1 on July 27, 2007 4:29:46 AM]

Share this post


Link to post
Share on other sites
Advertisement
This is rather convoluted.
I'd use a std::vector<EntityQueueItem*> and when rendering just make two copies of it, then sort one of them by y and the other by z. No need for custom queue or tree classes here.
Also make sure that you don't delete any entities before you render an EntityQueueItem that references them.
Also, binary tree node insertion either belongs in the tree or node class, not in RenderManager.

Share this post


Link to post
Share on other sites
Quote:
Original post by Barius
This is rather convoluted.
I'd use a std::vector<EntityQueueItem*> and when rendering just make two copies of it, then sort one of them by y and the other by z. No need for custom queue or tree classes here.
Also make sure that you don't delete any entities before you render an EntityQueueItem that references them.
Also, binary tree node insertion either belongs in the tree or node class, not in RenderManager.


creating and sorting a vector 2 times in a frame is a pretty inefficient... i can do both together by using a tree.

as for deleting entities, it's not the case, because it works fine when rendering the queue directly without using a tree, with any number of entities.

the problem lies in one of the tree algorithms.

Share this post


Link to post
Share on other sites
FIXED...

in my infinite stupidity i was saving
EntityQueueItem
in the queue, instead of
EntityQueueItem*
, and by passing it's address to the tree i was just passing random addresses.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!