Thread: My attempt at coding a quadtree for a 2d game!

Hello all

I'm fairly new to games programming. I have a nice little 2d tile engine going. I have optimised it with a quadtree. I'm just posting the code here in case people want to read it, or if people want to see one way to make a quadtree, or in case anyone finds a flaw in it (aside from my laziness in optimising the calculating of the quadtree). I have yet to implement a destructor because it's 5am and i need to sleep.

Anyway, this was fun to make.

If anyone's interested, the graphics library is called SFML - Simple and Fast Multimedia Library, and is pretty nifty.

Code:

	struct CQTree_Node
	{
	private:
		CQTree_Node* children[4];
		int tilecount;
		sf::Sprite** tiles;
		sf::FloatRect rect;

		static bool RectExclContains(sf::FloatRect rect, sf::Sprite sprite)
		{
			return (sprite.GetPosition().x >= rect.Left) && (sprite.GetPosition().x < rect.Right) && (sprite.GetPosition().y >= rect.Top) && (sprite.GetPosition().y < rect.Bottom);
		}

		static CQTree_Node* CreateChildTree(sf::FloatRect rect, sf::Sprite** sprites, int spritecount)
		{
			if (((rect.GetHeight() <= 32) && (rect.GetWidth() <= 32)) || (spritecount == 0))
				return 0;

			CQTree_Node* node = new CQTree_Node;
			node->tilecount = 0;
			node->rect = rect;

			// first we count the number of tiles we need to store
			for (int i = 0; i < spritecount; ++i)
			{
				#ifdef DEBUG_QUADTREE
					sf::Sprite* sprite = sprites[i]; // (so i can see the values easily in visual studio o.o)
				#endif
				if (RectExclContains(rect, *sprites[i]))
					++node->tilecount;
			}

			// then we allocate space for that many
			node->tiles = new sf::Sprite*[node->tilecount];

			// then we store them all in our tiles array
			int pos = node->tilecount;
			for (int i = 0; i < spritecount; ++i)
			{
				if (RectExclContains(rect, *sprites[i]))
				{
					++node->tiles[--pos] = sprites[i];
					if (pos == 0) break;
				}
			}

			// then we create the four children by:
			// first we work out divisions
			float td = floor(((rect.GetWidth() / 2) / 32)) * 32;
			float hd = floor(((rect.GetHeight() / 2) / 32)) * 32;

			// then we recurse through the four child rectangles
			int n = 0;
			float width = rect.Right - rect.Left;
			float height = rect.Bottom - rect.Top;
			#define MAKETREE(X, Y, W, H) node->children[n++] = CreateChildTree(sf::FloatRect((X), (Y), (W), (H)) , node->tiles, node->tilecount);
			MAKETREE(rect.Left,			rect.Top,		td,				hd)
			MAKETREE(rect.Left + td,	rect.Top,		width - td,		hd)
			MAKETREE(rect.Left,			rect.Top + hd,	td,				height - hd)
			MAKETREE(rect.Left + td,	rect.Top + hd,	width - td,		height - hd)

			return node;
		}

	public:
		void Draw(sf::RenderTarget* target, sf::FloatRect rect)
		{
			if ((this->rect.Top >= rect.Top) &&
				(this->rect.Left >= rect.Left) &&
				(this->rect.Right < rect.Right) &&
				(this->rect.Bottom < rect.Bottom))
			{
				// draw all tiles
				for (int i = 0; i < tilecount; ++i)
				{
					target->Draw(*tiles[i]);
				}
			}
			else
			{
				for (int i = 0; i < 4; ++i)
				{
					if (this->children[i] == 0) continue; // (in case the child had no tiles in it and was set to 0)
					this->children[i]->Draw(target, this->rect);
				}
			}
		}

		static CQTree_Node* CreateQuadTree(sf::Sprite* sprites, int count) // relies on at least 1 sprite being parsed, needs fixing >.>
		{
			if (count < 1) return 0;

			sf::FloatRect tree_bounding_box(sprites[0].GetPosition().x, sprites[0].GetPosition().y, sprites[0].GetSize().x, sprites[0].GetSize().y);

			// first we expand our tree_bounding_box to contain all tiles, so we have somewhere to start
			for (int i = 1; i < count; ++i)
			{
				#ifdef DEBUG_QUADTREE
					sf::Sprite sprite = sprites[i]; // (so i can see the values easily in visual studio o.o)
				#endif
				if (!RectExclContains(tree_bounding_box, sprites[i]))
				{
					// expand box
					tree_bounding_box.Left = std::min<float>(tree_bounding_box.Left, sprites[i].GetPosition().x);
					tree_bounding_box.Top = std::min<float>(tree_bounding_box.Top, sprites[i].GetPosition().y);
					tree_bounding_box.Right = std::max<float>(tree_bounding_box.Left + tree_bounding_box.Right, sprites[i].GetPosition().x + sprites[i].GetSize().x);
					tree_bounding_box.Bottom = std::max<float>(tree_bounding_box.Top + tree_bounding_box.Bottom, sprites[i].GetPosition().y + sprites[i].GetSize().y);
				}
			}

			// secondly we do this magic: we start the recursive tree creation process with this box as a starting point
			// make the array of sprite pointers needed:
			sf::Sprite** spritelist = new sf::Sprite*[count];
			for (int i = 0; i < count; ++i)
				spritelist[i] = &sprites[i];
			return CreateChildTree(tree_bounding_box, spritelist, count);
			delete[] spritelist;
		}
	};

> return CreateChildTree(tree_bounding_box, spritelist, count);
> delete[] spritelist;
When do you delete the memory?

> #define MAKETREE(X, Y, W, H) node->children[n++]..
Eww - macros with side effects.
Try an inline function.

> ++node->tiles[--pos] = sprites[i];
What is this supposed to do?

The ++ at the start in particular.

> // then we store them all in our tiles array
Except you have a conditional statement.
What happens to all the slots which DON'T get used - do they have sensible values?