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;
}

/*	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);}

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;};

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;}