Jump to content
  • Advertisement
Sign in to follow this  
Mybowlcut

Unity Quadtree for 2D tiled-based level

This topic is 3546 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

Hey. I've made a Quadtree after advice from this thread.
class Renderer;

class Quadtree
{
public:
	Quadtree(const SDL_Rect& area);

	void Subdivide(unsigned int times);

	void Draw(Renderer& renderer);
private:
	Quad_Node root;
};
Quadtree::Quadtree(const SDL_Rect& area)
: root(area)
{
}

void Quadtree::Subdivide(unsigned int times)
{
	for(unsigned int i = 0; i < times; ++i)
	{
		root.Subdivide();
	}
}

void Quadtree::Draw(Renderer& renderer)
{
	root.Draw(renderer);
}
class Quad_Node
{
public:
	Quad_Node(const SDL_Rect& area);

	bool Subdivide();

	void Draw(Renderer& renderer);
private:
	typedef std::vector<Quad_Node>::iterator node_it;

	enum DRAW_REGION {T, B, L, R};
	SDL_Rect Compute_Draw_Rect(DRAW_REGION r);

	SDL_Rect area;
	std::vector<Quad_Node> children;
};
Quad_Node::Quad_Node(const SDL_Rect& area)
: area(area)
{
}

bool Quad_Node::Subdivide()
{
	bool done = true;
	if(children.empty())
	{ // Empty; subdivide.
		SDL_Rect r = {area.x, area.y, area.w / 2, area.h / 2};
		children.push_back(r);
		children.push_back(SDL_Tools::rect(r.x + r.w, r.y, r.w, r.h));
		children.push_back(SDL_Tools::rect(r.x, r.y + r.h, r.w, r.h));
		children.push_back(SDL_Tools::rect(r.x + r.w, r.y + r.h, r.w, r.h));
	}
	else
	{ // Full; pass down instruction to children.
		for(node_it it = children.begin(); it != children.end() && done; ++it)
		{
			done = it->Subdivide();
		}
	}

	return done;
}

void Quad_Node::Draw(Renderer& renderer)
{
	if(children.empty()) return;

	for(node_it it = children.begin(); it != children.end(); ++it)
	{
		// draw a line on each edge of this node's area
		renderer.Draw_Rect(it->Compute_Draw_Rect(T), SDL_Tools::Colours::WHITE);
		renderer.Draw_Rect(it->Compute_Draw_Rect(B), SDL_Tools::Colours::WHITE);
		renderer.Draw_Rect(it->Compute_Draw_Rect(L), SDL_Tools::Colours::WHITE);
		renderer.Draw_Rect(it->Compute_Draw_Rect(R), SDL_Tools::Colours::WHITE);

		// draw children of this node (if any).
		it->Draw(renderer);
	}
}

SDL_Rect Quad_Node::Compute_Draw_Rect(DRAW_REGION r)
{
	SDL_Rect rect;
	switch(r)
	{
	case T:
		rect = SDL_Tools::rect(area.x, area.y, area.w, 1);
		break;
	case B:
		rect = SDL_Tools::rect(area.x, area.y+area.h, area.w, 1);
		break;
	case L:
		rect = SDL_Tools::rect(area.x, area.y, 1, area.h);
		break;
	case R:
		rect = SDL_Tools::rect(area.x+area.w, area.y, 1, area.h);
		break;
	}
	return rect;
}
I got it working in terms of creating child nodes and added a Draw function so I could see that it was working... My issue now is that I want to implement this in my game. I've got a Level class which at the moment is just a vector of tiles (as discussed in the thread linked above) and I want to instead use the Quadtree. What functions should I be adding to my Quadtree class? How do I store the tiles? I have no clue what to do next haha... Cheers.

Share this post


Link to post
Share on other sites
Advertisement
To answer your question, each node in the tree would contain a list of tiles. You then insert each tile to the correct node in the tree. For example, a tile that is located at 0,0 will be inserted to a node that is on the top-left corner of the map. Then when you draw, you simply iterate through all nodes and tiles in them.

Now, here's my suggestion. Quadtrees are a bit of an overkill for something as simple as tiles. Typically, tiles are stored sorted in the array. Element #0 in the array corresponds to tile at 0,0. Element #1 corresponds to tile at 1,0 or 0,1, depending on how you order your tiles, column-first or row-first. Or if you'd like, you can store them in a two-dimensional array. Element at [0][0] corresponds to the tile at 0,0. Element at [0][1] corresponds to the tile at 0,1, and so on. That way you don't need to store a Point structure in your tiles anymore because the indices imply the location of the tiles.

Share this post


Link to post
Share on other sites
Quote:
Original post by alnite
To answer your question, each node in the tree would contain a list of tiles. You then insert each tile to the correct node in the tree. For example, a tile that is located at 0,0 will be inserted to a node that is on the top-left corner of the map. Then when you draw, you simply iterate through all nodes and tiles in them.

Now, here's my suggestion. Quadtrees are a bit of an overkill for something as simple as tiles. Typically, tiles are stored sorted in the array. Element #0 in the array corresponds to tile at 0,0. Element #1 corresponds to tile at 1,0 or 0,1, depending on how you order your tiles, column-first or row-first. Or if you'd like, you can store them in a two-dimensional array. Element at [0][0] corresponds to the tile at 0,0. Element at [0][1] corresponds to the tile at 0,1, and so on. That way you don't need to store a Point structure in your tiles anymore because the indices imply the location of the tiles.
Hm... kinda makes me feel stupid for overlooking arrays and going to this much trouble haha.

Cheers though, will dump this Quadtree for the array idea since it's simpler.

Share this post


Link to post
Share on other sites
Quote:
Original post by alniteNow, here's my suggestion. Quadtrees are a bit of an overkill for something as simple as tiles. Typically, tiles are stored sorted in the array. Element #0 in the array corresponds to tile at 0,0. Element #1 corresponds to tile at 1,0 or 0,1, depending on how you order your tiles, column-first or row-first. Or if you'd like, you can store them in a two-dimensional array. Element at [0][0] corresponds to the tile at 0,0. Element at [0][1] corresponds to the tile at 0,1, and so on. That way you don't need to store a Point structure in your tiles anymore because the indices imply the location of the tiles.
How can you order/sort a Tile without anything to uniquely identify it? And how can the tile render itself without a position to go by? Or should the Level object it's stored in take care of that?

Still, even if the Level did render the tile based on it's index in the tiles array, how will the Tile render it's contents (e.g. items on that tile, etc.) without a position to go by? Or have I got that the wrong way around as well and do people usually keep a container of items corresponding to the tiles array?

Also, would a set (using the tile index as the key) be better than an array? If I do use an array, I'll have to dynamically allocate it won't I? This would mean I'd have to specify the size of the level upon construction, right?

[Edited by - Mybowlcut on October 25, 2008 7:38:32 AM]

Share this post


Link to post
Share on other sites
Quote:
Original post by Mybowlcut
Quote:
Original post by alniteNow, here's my suggestion. Quadtrees are a bit of an overkill for something as simple as tiles. Typically, tiles are stored sorted in the array. Element #0 in the array corresponds to tile at 0,0. Element #1 corresponds to tile at 1,0 or 0,1, depending on how you order your tiles, column-first or row-first. Or if you'd like, you can store them in a two-dimensional array. Element at [0][0] corresponds to the tile at 0,0. Element at [0][1] corresponds to the tile at 0,1, and so on. That way you don't need to store a Point structure in your tiles anymore because the indices imply the location of the tiles.
How can you order/sort a Tile without anything to uniquely identify it? And how can the tile render itself without a position to go by? Or should the Level object it's stored in take care of that?

The Level object should take care of that.

Quote:

Still, even if the Level did render the tile based on it's index in the tiles array, how will the Tile render it's contents (e.g. items on that tile, etc.) without a position to go by? Or have I got that the wrong way around as well and do people usually keep a container of items corresponding to the tiles array?

This really depends on the game you are making. If each tile can contain some items, and you can store the pointer to these items in each tile. When the tile is drawn, that tile will also draw the items. It's sort of like this:

void Tile::draw(Screen s)
{
// insert tile drawing routine here

// then draw item
item->draw(s);
}


Or, you can also put your items in a separate array, and each item would contain its position in the map. After you draw the tiles, you then draw the items. Tiles would not possess information on items, and items would not posses information on tiles. They are "modular".

drawTiles();
drawItems();

Quote:

Also, would a set (using the tile index as the key) be better than an array? If I do use an array, I'll have to dynamically allocate it won't I? This would mean I'd have to specify the size of the level upon construction, right?

Yes, you would have to dynamically allocate your array, but you have to do that no matter what kind of data structure you are using. Your code would look something like this (using a single dimensional array):

int map_size = map_width * map_height;
Tile* map = new TIle[map_size];
for (int i=0; i<map_size; ++i) {
map_size = getNextTileFromFile();
}


A set is just another data structure that sits on top of array. A set is useful when you want to have a container where each item in the set is unique. In this case, it is more likely that you'd have similar types of tiles in your level (at different locations), so you can't use sets.

Share this post


Link to post
Share on other sites
Cheers for that.

What I meant by dynamically allocating the array was that I have to do it instead of STL taking care of it for me. I'm not very good with arrays so I guess it's a good time to learn.

/*
Universal class. Edits affect multiple projects.
*/


#include "stdafx.h"

#include "Level.h"

#include "Party.h"

Level::Level()
: tiles(NULL)
, party(NULL)
{
}

Level::Level(const std::string& name, Level::uint width,
Level::uint height, Party* party)
: name(name)
, width(width)
, height(height)
, tiles(new Tile[width * height])
, party(party)
{
}

Level::Level(const Level& level)
: name(level.name)
, width(level.width)
, height(level.height)
, tiles(new Tile[level.width * level.height])
, party(level.party)
{
for(uint i = 0; i < level.width * level.height; ++i)
tiles = level.tiles;
}

Level::~Level()
{
if(tiles)
delete[] tiles;
}

void Level::Swap(Level& rhs)
{
name.swap(rhs.name);
std::swap(width, rhs.width);
std::swap(height, rhs.height);
std::swap(tiles, rhs.tiles);
std::swap(party, rhs.party);
}

Level& Level::operator=(const Level& level)
{
if(this == &level)
{
Level copy(level);
Swap(copy);
}
return *this;
}

bool operator==(const Level& lhs, const Level& rhs)
{
return &lhs == &rhs || lhs.name == rhs.name;
}

std::istream& operator>>(std::istream& stream, Level& level)
{
stream >> level.name >> level.width >> level.height;

bool done = false;
Tile buffer;
for(Level::uint y = 0; !done; ++y)
{
for(Level::uint x = 0; !done; ++x)
{
done = !(stream >> buffer);

if(!done) level.tiles[y * level.width + x] = buffer;
}
}

return stream;
}

std::ostream& operator<<(std::ostream& stream, const Level& level)
{
stream << level.name << " " << level.width << " " << level.height << "\n";

for(Level::uint i = 0; i < level.width * level.height; ++i)
{
stream << level.tiles;
}

return stream;
}

void Level::Update(const SDL_Event* event_)
{
if(party) party->Update(event_);
}

void Level::Draw(Renderer& renderer)
{
for(uint y = 0; y < height; ++y)
{
for(uint x = 0; x < width; ++x)
{
renderer.Render(Point(x * Tile::TILE_WIDTH, y * Tile::TILE_HEIGHT),
tiles[y * width + x].File_Name(), NULL);
}
}

// Once have layers, need to determine in above loop if tile is covering/below player
// and then draw player at that point.
if(party) party->Draw(renderer);
}

const std::string& Level::Name() const
{
return name;
}

bool Level::Can_Walk(Point position) const
{
Tile* find = NULL;

// Divides are to normalise position from pixels to tiles.
position = Normalise_Pixel_Coords(position);

// Determine if outside of level boundary.
if(!SDL_Tools::inside(position, SDL_Tools::rect(0, 0, width, height)))
return false;

try { find = &tiles[position.y * width + position.x]; }
catch (const std::exception& e) { e; return false; }

return find->Passability() != PASS_BLOCKED;
}

void Level::Set_Party(Party* party)
{
this->party = party;
}

Point Level::Normalise_Pixel_Coords(const Point& point)
{
return Point(point.x / Tile::TILE_WIDTH, point.y / Tile::TILE_HEIGHT);
}


Does this look ok to you so far? I got some help to code the constructors/destructors/assignment operators.

Also, with your version where the items and tiles are stored in separate containers, why would items need to have a position? What about when they're inside someone's inventory?

[Edited by - Mybowlcut on October 25, 2008 11:21:54 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by Mybowlcut
What I meant by dynamically allocating the array was that I have to do it instead of STL taking care of it for me.


std::vector<Tile> would be a far more robust solution than manually managing the memory yourself.

Share this post


Link to post
Share on other sites
Quote:
Original post by EasilyConfused
Quote:
Original post by Mybowlcut
What I meant by dynamically allocating the array was that I have to do it instead of STL taking care of it for me.


std::vector<Tile> would be a far more robust solution than manually managing the memory yourself.
I was stuck thinking that there was a reason I was using the array but now that I think about it there is no reason.. I will use vector instead haha.

Share this post


Link to post
Share on other sites
Hey.

I'm bringing this topic back up again because I've ran into a problem.

I followed alnite's advice and altered the Tile class to not store a position:
class Tile
{
public:
static const unsigned short TILE_WIDTH = 32, TILE_HEIGHT = 32;
static const SDL_Rect DEFAULT_TILE_CLIP;

Tile();
Tile(const std::string& file_name, PASSABILITY passability);
Tile(const Tile& rhs);
virtual ~Tile();

Tile& operator=(const Tile& rhs);

friend std::istream& operator>>(std::istream& stream, Tile& tile);
friend std::ostream& operator<<(std::ostream& stream, const Tile& tile);

const std::string& File_Name() const;
PASSABILITY Passability() const;

virtual void Render(Renderer& renderer);
virtual void Update(const SDL_Event* event_);
private:
std::string file_name;
PASSABILITY passability;
};

It works fine, but I can't miss tiles... In other words if I want to leave out a tile halfway through the container of tiles, then there won't be a space in the middle of the level... This is how I store my levels:
Quote:
level1 10 10
<
< tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tree.png 2 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile1.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 > < tile2.png 1 >
>
<
< level2 1 1 4 4 >
>
The top part contains the name of the level, its size and then every tile. The second part contains the portals (or warps).

The tiles are read into the Level like this:
template<typename Object>
static void Load_Objects(std::istream& stream, std::vector<Object>& v)
{
std::string buffer;
stream >> buffer;
IO::Check_Opening_Tag(buffer);

Object object;
bool ok = true;
while(ok)
{
try
{
stream >> object;
v.push_back(object);
}
catch(const std::exception& e) { e; ok = false; }
}
}

std::istream& operator>>(std::istream& stream, Level& level)
{
stream >> level.name >> level.width >> level.height;

if(!Level::Valid_Dimensions(level.width, level.height))
{
throw std::runtime_error("Invalid dimensions for: " + level.Name() + ".");
}

level.Load_Objects<Tile>(stream, level.tiles);
level.Load_Objects<Portal>(stream, level.portals);

if(level.tiles.size() != level.width * level.height)
{
throw std::runtime_error(level.Name() +
" has insufficient tiles for given width/height.");
}

return stream;
}
So I'm wondering... when it comes to having more than 1 layer of tiles, what do I do? The highest layer (that is drawn on top of everything in the level) will not be full of tiles... so how can I leave tiles out of it and only put in the ones I need? Does that even make sense?

Cheers...

Share this post


Link to post
Share on other sites
Your level file contains a lot of duplicate filenames. You should consider writing a list of unique filenames once, and storing references (indices) to them instead.

As for empty tiles, one way would be to use a transparent image. Another way would be to mark missing tiles. So, you'd create a Tile instance, but mark it as invisible. This keeps positioning correct but allows for empty tiles.


On a side note, using strings to select images with isn't very efficient. Consider storing references to images in your Tile instances, rather than strings, so you only have to look those images up once.

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.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!