Quadtree for 2D tiled-based level

Started by
15 comments, last by Mybowlcut 15 years, 5 months ago
Quote:Original post by Captain P
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.
Hey thanks for the reply.

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!

Advertisement
Quote:Original post by Mybowlcut
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?

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).
Create-ivity - a game development blog Mouseover for more information.
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?


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.
Create-ivity - a game development blog Mouseover for more information.
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.

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. :)
Create-ivity - a game development blog Mouseover for more information.
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.

:)

This topic is closed to new replies.

Advertisement