# Unity Quadtree for 2D tiled-based level

## Recommended Posts

Mybowlcut    176
class Renderer;

{
public:

void Subdivide(unsigned int times);

void Draw(Renderer& renderer);
private:
};

Quadtree::Quadtree(const SDL_Rect& area)
: root(area)
{
}

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

{
root.Draw(renderer);
}

class Quad_Node
{
public:

bool Subdivide();

void Draw(Renderer& renderer);
private:

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

SDL_Rect area;
};

Quad_Node::Quad_Node(const SDL_Rect& area)
: area(area)
{
}

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

{
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 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 on other sites
alnite    3436
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 on other sites
Mybowlcut    176
Quote:
 Original post by alniteTo 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 on other sites
Mybowlcut    176
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 on other sites
alnite    3436
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[i] = 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 on other sites
Mybowlcut    176
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[i] = level.tiles[i];}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[i];	}	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 on other sites
Aardvajk    13207
Quote:
 Original post by MybowlcutWhat 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 on other sites
Mybowlcut    176
Quote:
Original post by EasilyConfused
Quote:
 Original post by MybowlcutWhat 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 on other sites
Mybowlcut    176
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 on other sites
Captain P    1092
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 on other sites
Mybowlcut    176
Quote:
 Original post by Captain PYour 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.

If I wrote a list of unique filenames, would I do it in a file? If so, wouldn't it be a hassle if I ever needed to/accidentally changed the order of the file names?

By mark missing tiles, do you mean create a Tile instance called invisible or something and store it in the level and draw it? The only way I could see it working is if when reading the level, a certain tile file name meant that it was an invisible tile.. but I didn't want to hard-code a check to see what tiles are invisible in my code.

The reason I'm using strings instead of references was discussed here. If you can be bothered, take a quick read and tell me what you think?

Cheers!

##### Share on other sites
Captain P    1092
Quote:
 Original post by MybowlcutIf I wrote a list of unique filenames, would I do it in a file? If so, wouldn't it be a hassle if I ever needed to/accidentally changed the order of the file names?

It'd be smart to store it in the file, yes. Something like the following could do:
level1 10 10< tile1.png tile2.png >< < 1 1 2 1 1 2 2 1 1 1 >(and so on)>

As for modifying the order, doing that manually is indeed a hassle (is it? find + replace...). Then again, modifying levels as text files is pretty much a hassle anyway. Consider using an existing 2D editor to create your levels with (you can write a small tool to convert it's output to your own level format). You could, of course, also write your own editor, or write an editor interface into your game, but that'll probably cost more time. Either way, this sort of optimization is easily automated.

Quote:
 By mark missing tiles, do you mean create a Tile instance called invisible or something and store it in the level and draw it? The only way I could see it working is if when reading the level, a certain tile file name meant that it was an invisible tile.. but I didn't want to hard-code a check to see what tiles are invisible in my code.

I don't think it's a bad thing to make invisible tiles a unique case. By using my above example, I chose to use indices starting at 1, which leaves 0 as a special value. By checking for 0's, you don't have to use filenames for your special case, instead, 0 is your special case value.

Of course, you could choose to store a visibility value for all your tiles, but that's probably over-engineering here. A good design is fine, but you can go too far and end up with a beautifully crafted, yet unpractical solution. I believe that's a balance you'll have to find through experience. For small tools, I usually just write the functionality with little to no scaffolding. For larger projects, I spend more time on the design and I often create a few prototypes before working on the final implementation.

Quote:
 The reason I'm using strings instead of references was discussed here. If you can be bothered, take a quick read and tell me what you think?

I don't see why separating the view from the model requires you to use strings here. These strings are essentially identifiers here - they tell the renderer what image to use. Now, filenames are pretty natural to work with, but that doesn't mean you'll have to use them all of the time. What if you could retrieve a faster handle with that filename, so you could use that handle afterwards? That handle could be a hash of the filename, for example, or a reference to the actual image.

Now, with modern-day PC's, comparing a few hundred strings every frame may not be a performance-killer, but it's easy to optimize with relatively little effort (at least from my experience).

##### Share on other sites
Mybowlcut    176
Quote:
 Original post by Captain PIt'd be smart to store it in the file, yes. Something like the following could do:level1 10 10< tile1.png tile2.png >< < 1 1 2 1 1 2 2 1 1 1 >(and so on)>As for modifying the order, doing that manually is indeed a hassle (is it? find + replace...). Then again, modifying levels as text files is pretty much a hassle anyway. Consider using an existing 2D editor to create your levels with (you can write a small tool to convert it's output to your own level format). You could, of course, also write your own editor, or write an editor interface into your game, but that'll probably cost more time. Either way, this sort of optimization is easily automated.
Once I've read in the list of unique tile names, would I access the list using the
Quote:
 < < 1 1 2 1 1 2 2 1 1 1 >
as indexes into the list to store the file name at that index into the Tile again?

Quote:
 I don't think it's a bad thing to make invisible tiles a unique case. By using my above example, I chose to use indices starting at 1, which leaves 0 as a special value. By checking for 0's, you don't have to use filenames for your special case, instead, 0 is your special case value.Of course, you could choose to store a visibility value for all your tiles, but that's probably over-engineering here. A good design is fine, but you can go too far and end up with a beautifully crafted, yet unpractical solution. I believe that's a balance you'll have to find through experience. For small tools, I usually just write the functionality with little to no scaffolding. For larger projects, I spend more time on the design and I often create a few prototypes before working on the final implementation.
Where would I check for 0's though? Does that mean that you would store an index into the list of unique file names in the Tile class as a member?

Quote:
 I don't see why separating the view from the model requires you to use strings here. These strings are essentially identifiers here - they tell the renderer what image to use. Now, filenames are pretty natural to work with, but that doesn't mean you'll have to use them all of the time. What if you could retrieve a faster handle with that filename, so you could use that handle afterwards? That handle could be a hash of the filename, for example, or a reference to the actual image.Now, with modern-day PC's, comparing a few hundred strings every frame may not be a performance-killer, but it's easy to optimize with relatively little effort (at least from my experience).
A reference to an actual image would be defeating the purpose of separating the view from the model, wouldn't it? How would a hash be any better than a string? Would it not take more work to translate it into a file name than it would to just store the file name directly as I do now?

##### Share on other sites
Captain P    1092
Quote:
Original post by Mybowlcut
Once I've read in the list of unique tile names, would I access the list using the
Quote:
 < < 1 1 2 1 1 2 2 1 1 1 >
as indexes into the list to store the file name at that index into the Tile again?

My suggestion to use a list of filenames, combined with indices, was mainly focused on your level file format, but not saving them in your tiles means less memory usage too. In the end however, it's your choice.

Quote:
 Where would I check for 0's though? Does that mean that you would store an index into the list of unique file names in the Tile class as a member?

You check for 0's in your loader code, obviously, but your renderer also needs to know that it shouldn't render those tiles. Whether you put that logic in the level code (oh, this is an invisible tile, let's not tell the renderer about it) or in the renderer (oh, this tile is invisible, I'm not going to draw it) is up to you. What matters is that it gets done. ;)

Quote:
 A reference to an actual image would be defeating the purpose of separating the view from the model, wouldn't it? How would a hash be any better than a string? Would it not take more work to translate it into a file name than it would to just store the file name directly as I do now?

You don't translate hashes into filenames, you translate filenames into hashes, and then use those hashes for faster lookups. I suggested this both to improve performance and to reduce memory usage (less strings stored in memory).

I don't think that storing a reference to an image defeats the purpose. It is perhaps inverting the model-view relationship, but I've found that to work quite well. My game objects tell the renderer where to create a Sprite (a Sprite is an Image, drawn at a certain position) and are given a reference to the Sprite they requested. This allows them to alter their Sprites properties, such as position, scale, visibility, etc. The Renderer takes care of actually rendering all those Sprites.

So, my view knows nothing about my model. This means that my game objects need to tell their Sprite(s) when to start another animation, when to move, etc. However, if I went with a pure MVC approach, I'd have to write distinct views for all my game objects, and place that logic there. That would allow me to change the representation by only rewriting the view, but I simply don't need that kind of flexibility, so I'm taking the practical route (for me). This approach allows me to easily swap the model, and that's something I do frequently, because I'm building quite a few prototypes using the same rendering code.

Perhaps that makes my comments less practical for you, because our situation and goals may differ. Then again, perhaps this approach fits your needs better than what you're currently striving for. Either way, don't use design patterns for the sake of it - use them when and where they are practical.

##### Share on other sites
Mybowlcut    176
Quote:
 Original post by Captain PMy suggestion to use a list of filenames, combined with indices, was mainly focused on your level file format, but not saving them in your tiles means less memory usage too. In the end however, it's your choice.
Got ya. :)

Quote:
 You check for 0's in your loader code, obviously, but your renderer also needs to know that it shouldn't render those tiles. Whether you put that logic in the level code (oh, this is an invisible tile, let's not tell the renderer about it) or in the renderer (oh, this tile is invisible, I'm not going to draw it) is up to you. What matters is that it gets done. ;)
Cheers.

Quote:
 I don't think that storing a reference to an image defeats the purpose. It is perhaps inverting the model-view relationship, but I've found that to work quite well. My game objects tell the renderer where to create a Sprite (a Sprite is an Image, drawn at a certain position) and are given a reference to the Sprite they requested. This allows them to alter their Sprites properties, such as position, scale, visibility, etc. The Renderer takes care of actually rendering all those Sprites.So, my view knows nothing about my model. This means that my game objects need to tell their Sprite(s) when to start another animation, when to move, etc. However, if I went with a pure MVC approach, I'd have to write distinct views for all my game objects, and place that logic there. That would allow me to change the representation by only rewriting the view, but I simply don't need that kind of flexibility, so I'm taking the practical route (for me). This approach allows me to easily swap the model, and that's something I do frequently, because I'm building quite a few prototypes using the same rendering code.
:|

I really don't understand.. I thought using MVC would be better than storing graphical information in a game object? But then you say that you MVC is overkill? I feel as if there is no right way to design something anymore... I've been through sooo many variations of my code and they all end up being suboptimal more or less.

Quote:
 Perhaps that makes my comments less practical for you, because our situation and goals may differ. Then again, perhaps this approach fits your needs better than what you're currently striving for. Either way, don't use design patterns for the sake of it - use them when and where they are practical.
Well to be honest, the only reason I tried MVC was because I thought that game objects, etc. shouldn't care how they are being drawn, hearing twice from two highly rated people on different forums that the game should be able to be played without graphical information... or played on a console or something like that. :s

My plans were only ever to use SDL for this engine... hence my project is and always has been called SDL_Game_Engine. The only time I can think back to when the flexibility MVC provides could be useful was when I was overseas bored as hell with my laptop that didn't have SDL.

I'm now a bit unsure where to go with all of this stuff.

##### Share on other sites
Captain P    1092
Quote:
 Original post by Mybowlcut:|I really don't understand.. I thought using MVC would be better than storing graphical information in a game object? But then you say that you MVC is overkill? I feel as if there is no right way to design something anymore... I've been through sooo many variations of my code and they all end up being suboptimal more or less.

This depends a lot on your requirements. However, it seems that the real problem here is that you're trying to go for the perfect approach. But there is no perfect solution. So go with something that works well enough and just finish your game. Then, look back and see what worked well and what didn't.

Quote:
 Well to be honest, the only reason I tried MVC was because I thought that game objects, etc. shouldn't care how they are being drawn, hearing twice from two highly rated people on different forums that the game should be able to be played without graphical information... or played on a console or something like that. :s

Different people will have different opinions. Don't just look at the solutions presented by others, also look at why they chose for those solutions, and if those reasons apply to your situation.

Quote:
 My plans were only ever to use SDL for this engine... hence my project is and always has been called SDL_Game_Engine. The only time I can think back to when the flexibility MVC provides could be useful was when I was overseas bored as hell with my laptop that didn't have SDL.

In other words, the advantages that a strict MVC design offer aren't really that important to you, right? In that case, there's little reason to adhere strictly to MVC. Just do what seems practical now.

Note that, with my Renderer design, it's still relatively easy to swap the underlying rendering code. I just need to keep my Renderer and Sprite interfaces the same. Whether they use SDL or OpenGL or whatever under the hood doesn't matter for game objects. What I can't easily do is change the whole Renderer design without breaking the whole game. However, since I've been tweaking that throughout various games, it's pretty well suited to my needs, so that's not a problem.

Quote:
 I'm now a bit unsure where to go with all of this stuff.

I'd say, just finish your game without bothering too much about ideal designs. The more games you build, the better insight you will gain in design issues such as these. Don't stare yourself blind at issues, decide something and go with it. Sometimes it'll be a bad decision, but when that happens, take it as an opportunity to learn. :)

##### Share on other sites
Mybowlcut    176
Quote:
Original post by Captain P
Quote:
 Original post by Mybowlcut:|I really don't understand.. I thought using MVC would be better than storing graphical information in a game object? But then you say that you MVC is overkill? I feel as if there is no right way to design something anymore... I've been through sooo many variations of my code and they all end up being suboptimal more or less.

This depends a lot on your requirements. However, it seems that the real problem here is that you're trying to go for the perfect approach. But there is no perfect solution. So go with something that works well enough and just finish your game. Then, look back and see what worked well and what didn't.

Quote:
 Well to be honest, the only reason I tried MVC was because I thought that game objects, etc. shouldn't care how they are being drawn, hearing twice from two highly rated people on different forums that the game should be able to be played without graphical information... or played on a console or something like that. :s

Different people will have different opinions. Don't just look at the solutions presented by others, also look at why they chose for those solutions, and if those reasons apply to your situation.

Quote:
 My plans were only ever to use SDL for this engine... hence my project is and always has been called SDL_Game_Engine. The only time I can think back to when the flexibility MVC provides could be useful was when I was overseas bored as hell with my laptop that didn't have SDL.

In other words, the advantages that a strict MVC design offer aren't really that important to you, right? In that case, there's little reason to adhere strictly to MVC. Just do what seems practical now.

Note that, with my Renderer design, it's still relatively easy to swap the underlying rendering code. I just need to keep my Renderer and Sprite interfaces the same. Whether they use SDL or OpenGL or whatever under the hood doesn't matter for game objects. What I can't easily do is change the whole Renderer design without breaking the whole game. However, since I've been tweaking that throughout various games, it's pretty well suited to my needs, so that's not a problem.

Quote:
 I'm now a bit unsure where to go with all of this stuff.

I'd say, just finish your game without bothering too much about ideal designs. The more games you build, the better insight you will gain in design issues such as these. Don't stare yourself blind at issues, decide something and go with it. Sometimes it'll be a bad decision, but when that happens, take it as an opportunity to learn. :)
Thanks a lot for the advice. It is really appreciated to someone who is still trying to grasp game development.

:)

## Create an account

Register a new account

• ### Similar Content

• You - the chief doctor of the hospital. Working late into the evening, did not notice the majority of hospital workers went home ... But where you disappeared the night shift is also not known. Hastily taking important documents, go home, but something went wrong as usual ... Can you get out of the hospital alive?

We are looking for every position. From Game designer, to marketer, to programmer, to 3D modeler. Any further questions can be discussed through discord
DISCORD: Gator#5635

• Wind Of Fear is a game where we have to kill different kinds of waves of monsters packing weapons. The main goal is to survive the waves and pump up your own weapons. There is a store where you will buy new weapons, scattered crystals that restore your life are also on the map!

Controls:
WASD - Walking
Shift - Running
Mouse1 - Attack
Space - Jump
ScrolDown - weapon change
T - Deceleration of time
Esc - Exit, pause

• Continuation of the first part of the game, Invention. While you were on the island exploring the underground laboratory, the infection was busy spreading throughout the world. In this episode, you have to go through a city populated by monsters in search of salvation aided by weapons that you will find during your travels. The gloomy atmosphere, music and atmosphere and a crowd of walking meat will keep you on your toes!

•
Intro - "The challenges of dynamic system design"
Custom Quest evolved during development, from a minor quest system used for our own needs in our own game production Quest Accepted, to something entirely more dynamic and customizable, now finally released, these are our thoughts on quest design and developing standalone subsystems.
Splitting what is a major production for a small indie team, into smaller installments such as a quest system was a good idea we thought, this way we can get some releases out there and fuel the development of our game. But building a system that works for yourself is one thing, building a unity plugin that will let other developers create quests, missions, and objectives, you would never have thought of is something else entirely.
The first thing we had to realize was that when building a quest system, the task is not to design great quests, the task is to enable the users to create great quests.
That still meant we had to find out what good quest design is and what a quest really is.
Our task was to create a system where the user is free to create creative engaging and rewarding mission experiences for their players.
What is a quest? - "Cut to the core"
First off, we need to know what a quest really is.
A quest is the pursuit, search, expedition, task or assignment a person(s) does in order to find, gain or obtain something.
In games, quests and missions function in many different ways depending on the genre.
A single game can contain a multitude of different types of quests put together in just as many ways. In an MMO, for instance, quests are vehicles for the story and the player's progression. In many cases they are formulaic and simple, some can even be repeated, there are hundreds of them and everyone can do them. In other games quests are for single player campaigns only, here they shape each level giving the player a sense of purpose.
Quests can span the whole game or just be a minor optional task on the way, there are so many design philosophies and creative quest designs that we had to narrow it down and really cut to the core of what is needed for good quest design.
What all quests have in common is the task, the criteria for successful completion of the quest, and the reward, the goal of the quest, what the player gets out of doing what we ask of him.
Quests cover an incredible variety of tasks so it was important for us to base our decisions on thorough research. In our research, we found that there are three layers to quest design.
The type, the pattern and the superstructure.
Quest types exist within quest patterns and quest patterns exist within the quest superstructure.
We found that there are 8 basic types of quests these are the various tasks/criteria the player must do in order to complete the specific quest.
There are 12 quest patterns. These are ways designers can use their quests, connect multiple quests set them up in engaging ways or teach players how to interact with and get the most out of the game world creating variety and engaging the player.
Enveloping the patterns is the quest superstructure, the overall structure of quests in the game, we found that there are two main ways of structuring your quests.
Historically quest have a quest giver, an NPC or object that informs the player about the quest, what they need to do, the story behind it and perhaps even what their reward will be should they complete the quest.
Quest types - "Do this, do that"
The core task each quest consists of, the criteria for completing part of or all of a single quest. These are the actions we want Custom Quest to be able to handle.
Kill
Probably the most basic quest type, the task is to kill something in the game, for example; kill 10 goblins. Gather
Again very simple, the task is to gather x things in the game world, collecting berries or the like. Escort
The player must escort or follow a person or object from point A to B while keeping it safe. FedX
The player is the delivery boy, they must deliver an item to a person or point. Defend
The player has to defend a location from oncoming enemies, often for a set number of waves or time. Profit
The player must have a certain amount of resources to complete the quest, contrary to gather quests these resources are resources the player would otherwise be able to use himself. Activate
The player's task is to activate/interact with one or more objects in the game world or talk to a number of NPC’s. In some cases, this must be done in a certain order for a puzzle effect. Search
Search an area, discover an area of the game world. This is useful for introducing areas of the map to the player and giving them a sense of accomplishment right off the bat, showing them a new quest hub or the like. Quest Patterns - "An engaging experience"
Tasks are one thing, and in many games, that might be plenty but we wanted custom quest to let the users create chains of quests, specialize them and set them up in ways that draw the player into the experience, there are many ways to go about this.

The most basic quest pattern, the quest chain starts out broad and easy, the player has to kill some low-level cronies. The next quest is narrower, the player must kill fewer but tougher enemies, lets say the boss' bodyguards. The last quest is the boss fight, the player has killed the gang and can now kill the boss. This quest pattern is very straightforward and works well, giving rewards either at every stage or only when the boss is dead.
Side stub
A side stub is an optional part of the overlapping quest. Lets say quest A leads to quest C but there is an option to complete a side objective B, which makes completing C easier or it changes the reward, for example. The player must escape prison, the side stub is “free the other prisoners” in this example escaping with all the prisoners is voluntary but it might make it easier to overpower the guards or the prisoners might reward the player when he gets them out. The side stub differs from a generic side quest in that it is tied to the main quest directly.
Continuous side-quests
These are side-quests that evolve throughout the game, one unlocks the next, but they are also affected by external requirements such as story progress. This pattern is often found with party members in RPG games, where the player must befriend the party member to unlock their story quests.

As the name implies these quests are time sensitive. The task can be of any type, the important thing is that the quest fails if time runs out. This could also be used for a quest with a side quest where the side quest is timed for extra rewards but the main objective is not.

Deja-vu quests
This kind of quest pattern gives the player a quest they have done or seen before. In some cases, this “new” quest will have a twist or something that sets it apart. It can also be the same sort of quest that exists in different areas of the game world, perhaps there is more than one goblin camp? or perhaps the player has to pick berries daily.

Delayed impact
Delayed consequences of a previous decision. Often used in games where the story is important and the players’ choices matter. These quests are tied together without the player knowing. Let's say the player is set the optional task of giving a beggar some gold to feed himself. The player gives the beggar a few gold and is on his way. The next time he meets the beggar the beggar has become rich and rewards the player for his kindness with ten times what he gave.
One of many
The player is presented with a number of quests, they have to choose which one to complete, they can only choose one. The others will not be available.

Hidden quests
Hidden tasks that aren’t obviously quests at first glance or are hidden away for only the most intrepid players to find. This could be an item the player picks up with an inscription in it if the player then finds the person the inscription is about he can get a reward for delivering it. A good quest pattern for puzzles, these kinds of quests can really make the game world come alive and feel a lot more engaging, allowing the player to uncover secrets, Easter eggs and discover all of the world created for them
Moral dilemma
Punish the bread thief who stole to feed his family? often used in games that have a good/ evil alignment level for the players, these kinds of quests make the player make a choice about what kind of character they want to play, they get to choose if their character is good or evil.

Side quests
Optional quests, these quests are often found in level based games where the overall quest must be completed to get to the next level, the player can optionally do some extra tasks to get more points. The important part is that these are optional but they give the player a reward for, getting everything they can out of the game.

Tournament
Tournament style quests, a series of quests that get harder as the player progresses. An example could be a gladiatorial arena if the player defeats five enemies one after the other he gets rewarded as the champion of the arena, but if for example, he fails at the third, the whole tournament is failed and he has to start all over from quest 1.

Vehicle missions
Despite the name these quests are not confined to being about cars, these are simply quests where the players control scheme changes to complete the quest(s). An example could be; changing from running around in the game world to driving a tank to destroy a fort.
Quest superstructure - "The whole package"
With quest superstructures, we are venturing into general game design. The superstructure is how the player is allowed to complete quests in the game world. It's basically a question of whether the game is “open world” or a linear experience.

The diamond structure
The open world model, think games like The Elder Scrolls V: Skyrim, the player is introduced to the game through a quest, but after that, they can go wherever and do whatever quests they want. There are tons of quests of the above types and patterns, the player is free to pick and choose which to do, giving the player the illusion of freedom within the game world (the diamond). However, the game still ends by completing a quest that is locked and always a requirement to complete the game. This can, of course, be varied by different choices the player has made throughout the game or even have multiple endings. Quests can be concentrated into quest hubs, i.e. towns with lots to do or the like, but they don't have to be completed in a linear fashion

Linear hub structure
This structure consists of a number of required “bridge” quests that need to be completed in order to unlock the next area or “hub”, each hub can have any number of quests, this could be a town full of people in trouble, each with their own quests and quest chains to complete, when they are all done, the player moves on to the next hub through another bridge quest. Limiting the quest size of the hubs will make the quest structure feel more linear and thereby the game linear, and creating larger more open hubs can make the player feel freer.

Outcome - "So many options!"
The development of custom quest has been the quest to allow game developers to create quests and missions that use these types. However, no matter how well we have researched, some one will come up with a new and creative way of doing quests.

The solution for us was to make the system more customizable. Letting users convert their quest prefabs to quest scripts that automatically inherits the core functionality, so the user can freely add their own additional functionality on top of the existing core
Asset development as fuel - "A learning experience"
Developing this way, splitting the production into sub systems that can function on their own and even be used by others is not something that should be taken lightly, but if you can build something lasting, something others can find value in using, then the final product will be all the better for it. Custom Quest started as a project we thought could be completed in a couple of months, it ended up taking 7.
In part this is because we realised that if we were going to release the system, we might as well do it right, that meant creating a system that was customizable and robust, a system that can be added to the users game and not the other way around, a system we could be proud of.
The experience of developing for other developers is quite different to developing a game. One that has made us much stronger as programmers and as a company, it forced us to think in new ways, in order to create a dynamic and customizable solution. Custom quest has evolved from an asset we could use in Quest Accepted, into a tool others can use to create a unique game experience. All in all, the experience has been a good one and Random Dragon is stronger for it, I would, however, recommend thinking about your plugin and extra time before you start developing.

Sources:
www.pcgamesn.com -"We know you aren't stupid" - a quest design master class from CD Projekt RED
http://www.pcgamesn.com/the-witcher-3-wild-hunt/the-witcher-quest-design-cd-projekt-masterclass
http://www.gamasutra.com/ - Game Design Essentials: 20 RPGs - http://www.gamasutra.com/view/feature/4066/game_design_essentials_20_rpgs.php?print=1
Extra credits - Quest Design I - Why Many MMOs Rely on Repetitive Grind Quests https://www.youtube.com/watch?v=otAkP5VjIv8&t=219s
Extra credits - Quest Design II - How to Create Interesting MMO and RPG Quests https://www.youtube.com/watch?v=ur6GQp5mCYs
Center for Games and Playable Media - Situating Quests: Design Patterns for Quest and Level Design in Role-Playing Games - http://sokath.com/main/files/1/smith-icids11.pdf
Center for Games and Playable Media - RPG Design patterns https://rpgpatterns.soe.ucsc.edu/doku.php?id=patterns:questindex

Special thanks to Allan Schnoor, Kenneth Lodahl and Kristian Wulff for feedback, constructive criticism and background materials.

• 15
• 13
• 15
• 10
• 18