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

This is a discussion on My attempt at coding a quadtree for a 2d game! within the C++ Programming forums, part of the General Programming Boards category; Hello all I'm fairly new to games programming. I have a nice little 2d tile engine going. I have optimised ...

  1. #1
    Registered User
    Join Date
    Jun 2010
    Posts
    4

    Talking 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;
    		}
    	};
    Last edited by fabspro; 06-25-2010 at 03:12 PM.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,824
    > 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?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. RPG 2d Game Map Editor?
    By drdroid in forum Game Programming
    Replies: 1
    Last Post: 01-08-2003, 01:17 PM
  2. What would i need to make a game in 2d?
    By DarkViper in forum Game Programming
    Replies: 41
    Last Post: 12-25-2002, 06:28 PM
  3. 2D Graphics In Game
    By drdroid33 in forum Game Programming
    Replies: 16
    Last Post: 02-23-2002, 10:01 PM
  4. how to make a racing 2d game
    By juandy in forum Game Programming
    Replies: 3
    Last Post: 10-28-2001, 09:47 PM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21