Sign in to follow this  
The_Marlboro_Man

SDL: C++, speed, inheritance and sprite sorting.

Recommended Posts

Hi! Recently I fed my C++ addiction again and started to make what could be the beginnings of some simple 2d game engine (after miserably failing in doing a platform game because of moving platforms and collision logic... But that's another story and I sort of have a solution). Well, as you can see from the title, the thing would be programmed in C++ with help of the SDL libraries. Let me get you started a bit on the idea: I would like to code something completely 2d in a pseudo-overhead perspective, like the one used in old arcades like "Dark Seal" or in classic RPG games like, say, "Secret of Mana", "Terranigma" and all of them. This image could give you the feel. As you can see, is not an overhead perspective a la "Gauntlet" (wich would be easier) but some sort of trick: decorations are clearly plain tiles but a sense of depth and 3d is achieved because of the way everything is presented (a little from the top, a little from the front... Oh, I wish I knew how this perspective is called... Maybe top-down?). This perspective presents an interesting problem for me in sorting the order of the things: obviosly things that are in the top of the screen are drawn first and things at the bottom are drawn later, on top but... What happens, for example, with the bell in the picture?. If I remember correctly the solution of those games was on carelessly avoiding the player walking across them, revealing the tile nature of the game but let's imagine a tall tree: the player should be able to walk in the front (and be drawn later) and behind it (being drawn sooner). This is where the questions come. Everything in a level will be placed in stacks or queues (I could use arrays, but I don't like them that much). There would be a stack of "Background tiles", a stack of "Decoration tiles" (The tree, for example), a stack of "Enemies"... These would be unordered, sort by the order in wich they were created. I won't be using tiles though, but "rectangles" of variable size, filled with flood fill algorithms. Now, I've thought about this algorithm of sorting the tiles (actually rectangles): -Run through each of the queues and mark the "tiles" that will be on camera. -Run again and place references to each of the marked tiles in an array. -Sort this array according to "depth". -Draw the elements in the array in order. -Do this with each step of the game, as elements may change position and thus, "depth". My main question is: won't this be too slow?. The steps one and two could be unified but still it needs time. I could draw the background on camera without sorting and leave decorations for later but still, wouldn't it take much time?. Remember that I would need to sort this with every step... One added problem, all the "Enemies", "Decorations", "Projectiles" and stuffs would be classes inherited from a "Master tile". The sorting array would contain them all together so, it is possible to create an array or stack of "Master tiles" wich actually contains a lot of objects of different classes inherited from "Master tile"?. This would save me a lot of hassle: "For this depth, are there any projectiles to be drawn?. Is the player there?", would be treated as "For this depth draw all this different things". So, okay, there's the problem. I've got hints of solutions but maybe there are much more effective methods, so my ears are open to suggestions and my fingers ready for further ellaboration. Thanks a lot for any replies in advance.

Share this post


Link to post
Share on other sites
Gage64    1235
Quote:
Original post by The_Marlboro_Man
Oh, I wish I knew how this perspective is called...


Isometric.

There are some articles on this subject here. There are also some links here.

Share this post


Link to post
Share on other sites
riku    194
Your design is coupling the graphics ("the view") and the game logic ("the model") together. I came up with this design that could suit your problem, hope it gives you ideas.

Instead of having a big list of "master tiles", you could have a list of tile objects that represent a drawable tile in your view. Then you would have separate classes for Players, Projectiles, Decorations, Level, etc. This is your model, and it should implement the game logic.

The view should implement the drawing routines. You should store all the tiles in a data structure that suits your drawing the best. For example, you could use a sorted tree structure to store your tiles. C++'s std::multimap could work great. Just use the depth values as keys and you have a very fast depth sorted scene graph (please note that the keys in std::multimap are immutable). The view should know absolutely nothing about the existance of the model part.


// A simple view, pseudo code

struct Tile
{
float x, y;
Image image;
};

class View
{
public:
typedef std::multimap<float, Tile> DepthMap;
typedef DepthMap::iterator TileHandle;

TileHandle addTile(float depth, Tile tile)
{
return depthMap.insert(std::make_pair(depth, tile));
}

void removeTile(TileHandle handle)
{
depthMap.remove(handle);
}

void draw() const
{
std::foreach(depthMap.begin(), depthMap.end(), drawTile);
}

private:
DepthMap depthMap;
};



The model part should implement the game logic. You should have all your game objects stored in your model. You may use polymorphism, inheritance and OOP here if it's applicable to your needs. The model should not need to know about the view.


class GameActor { virtual void update(float timestep); };
class Player : public GameActor { ... };
class Projectile : public GameActor { ... };


Finally, in your game main loop (the "controller"), you store the game logic objects and their views together.


struct GameObject
{
GameActor actor;
Image image;
View::TileHandle tileHandle;
}

class Objects
{
public:
void update(float timestep)
{
for(obj in objects)
{
obj.actor.update(timestep);
if(obj.actor.hasMoved())
{
view.removeTile(obj.tileHandle);
obj.tileHandle = view.addTile(obj.actor.getDepth(),
Tile(obj.actor.getX(), obj.actor.getY(), obj.image));

}
}
}

void addGameObject(GameActor actor, Image image)
{
GameObject obj(actor, image);
obj.tileHandle = view.addTile(obj.actor.getDepth(),
Tile(obj.actor.getX(), obj.actor.getY(), obj.image));
objects.insert(obj);
}

void draw() const
{
view.draw();
}
private:
GameObject[] objects;
View view;
};

void mainLoop()
{
Objects objects;

Player player;
Image playerImage;
objects.addGameObject(player, playerImage);

while(running)
{
objects.update();
objects.draw();

// read user input
player.setSpeed((keyState[KEY_LEFT] ? -1 : 0) +
(keyState[KEY_RIGHT] ? 1 : 0),
(keyState[KEY_UP] ? -1 : 0) +
(keyState[KEY_DOWN] ? 1 : 0));
}
}

// Add references, pointers, std::vectors, std::lists and other C++ gimmicks.


This is a simple design that you should be able to use as a foundation to your game design.

-Riku

Share this post


Link to post
Share on other sites
Riku, that's most excellent!. I was reading through Gage64 reply but found nothing I could use in the links I read so I started to look on the other side of the problem: the inheritance thing. I think I am allowed to treat a derived class like a parent class but while thinking of this I came with a different idea similar to yours: why don't get the array of "Surfaces" (SDL surfaces) and sort and draw them acoording to their coordinates ignoring the kind of objects they belong to?.

But yours is even better. Though there are many things I still don't understand in your code (still learning... been learning a bit but I don't have the chance to feed my c++ addiction often) but I think I can catch the idea and translate to something I can relate to:

-Each mapobject can contain a "Draw_me_on_the_map" class, with the SDL surface and the drawing coordinates.
-When drawing I just run through every object in the map and collect the "Draw_me_on_the_map" elements that fit inside the camera. I should put them into an array or stack.
-I just sort the array or stack and draw it.

That's much easier that what I started thinking about first... I guess that I could create a "view" class to encapsulate things a bit, like you did, but mine's would use code I could understand (I'm not keen on the std:: things...).

Anyway, I must study it a bit before coding anything: right now there are different ways of drawing (just stamp the sprite for sprites and flood fill rectangles for other areas) and I should make something about it so I can put them in the "Draw_me_on_the_map". Also, I should look at how the "camera" (the levels are larger than the screen, the camera is just an abstraction of the rectangle the player views) relates to these new entities and I should also look at how the "level" class (containing the stacks of objects) does.

This should take a bit of time, but it has been indeed very helpful to open my mind :). I will spend a bit of time thinking about how to implement this into my code since the changes will make it grow a lot. My most sincere thanks to both :).

I'll try and keep the thread updated, in case it helps other members.

Share this post


Link to post
Share on other sites
Just as I said, I update the thread a bit...

I managed to create the "Draw_me_on_screen" class and succesfully migrated everything that should be drawn. Now the player has its logic and display separated, as the level blocks do. I also encountered an evil problem with slowdowns: when there were large levels blocks the framerate would drop.

The solution?. Every single block had the color key active and that was slow as hell!. Once I turned it off for level blocks it worked fine. I also did a bit more work on the flood fill algorithm as it attempted to draw every part of a block that was outside the screen (blocks can be of any size and they're filled with a bmp. The fill would begin outside the screen if part of the block was outside)... I still don't like the algorithm as it still draws little bits outside. Nothing wrong with 32x32 tiles, but with 256x256 tiles could mean like... A lot of pixels being drawn when they don't have to.

Anyway, here's a screenshot of the result, not to show off (actually it's quite ugly) but to show my appreciation to what I have been helped on doing. So far it is quite fake as it doesn't perform any depth calculations but it will as soon as I craft the "level" class, outline the different kinds of blocks that there will be and create a suitable level editor... I guess text-based, the old one I had in Lazarus is quite rusty.

Thanks for everything so far.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this