Sign in to follow this  
mdwheele

2D Sprite Data Structures

Recommended Posts

I've been lurking around the internet, looking for some ideas on how to implement a solid, scalable 2D sprite engine with animation. There really aren't many guides out there for someone should they go looking. Noted, there are maybe 3-4 okay sources. But these are either not complete implemented examples or are not scalable (i.e. Under heavy system load the data structures underneath, or lack thereof, will not perform well). Just trying to get an idea how you all are doing your sprites and animations. I don't really care about specifics with APIs and what not... Just the ideas and data structures you would use. Links to good resources are appreciated, although I've probably seen them. [google] Thanks! -mdwheele

Share this post


Link to post
Share on other sites
A class that internally keeps track of textures, the d3d devices and pointers and whatnot. Provides functionality to load and deload new textures, and a bunch to send "draw orders" to the screen, and tops it off with a draw() that goes through all the orders and does the drawing.

Textures get loaded, and draworders are issued with a texture to use, screen coords to draw to, and a source RECT of what part of the texture to draw.

All of the API specific stuff is tucked away neatly in the .cpp so even if I add new functions or change the way stuff works, it doesnt break my old code.

Its not a singleton (as it doesnt need to be), but Im not an anti-global activist so its ment to be in the global scope, and Im not entirely sure as to how not wanting it global would change it.

Prolly not the fastest thing around, but It has decent speed until i try and give it like, 9000 or so orders a frame, then it hangs a little.

[edit]: and as to the lack of links about this kind of stuff, thats because an engine is generally quite complex, and a guide would be more like an intruction book, which are no fun to write.

Best thing to do is pick an API, learn it, figure out what you want your engine to do, scale it back a bit, and then piece it together. The scaling back is important, as if you cant make a scaled back version of it work, getting the whole thing up and running just isnt in the cards.

Share this post


Link to post
Share on other sites
You're unlikely to find a full, complete example just lying around. What exactly were you having problems with? Which bits didn't appear to be scalable?

I'm on about the third attempt at a 2d renderer, and I think I've finally got it about right this time. But it's very hard to write a general purpose renderer (especially as a one-person project). You'll have much more success if you nail down your exact requirements and goals beforehand (in particular how you'd like to trade off flexibility vs. performance vs. maintainability vs. ease of use).

Share this post


Link to post
Share on other sites
Quote:
Original post by OrangyTang
But it's very hard to write a general purpose renderer (especially as a one-person project). You'll have much more success if you nail down your exact requirements and goals beforehand (in particular how you'd like to trade off flexibility vs. performance vs. maintainability vs. ease of use).


A specific tradeoff: texture atlases. Drawing different sprites as small pieces of the same big texture is a good thing for performance reasons, but:

- it might not make a large difference, especially if sprites are already sorted by texture for other purposes or if frame rate is already ridiculous;

- the texture atlas could be automatically assembled in memory from small image files (wastes some effort but allows you to add, remove and resize sprites more easily and to manage packing automatically), or defined by hand from a large image (not foolproof, but allows you to control packing and texture edges and to edit everything at once), or compiled ahead of time by ad hoc tools, or a more flexible but more complex mixture of the above approaches (e.g. automatic assembly from separate filmstrips for each animated sprite);

- the texture coordinates of each sprite can be more or less explicit for the programmer, for example automatically calculated, loaded from configuration files, or generically provided by program code, trading off convenience (never touching them) vs flexibility (for example animating texture coordinates within a sprite);

- sprites from texture atlases might or might not need to coexist peacefully, with a coherent architecture, with other displayable entities such as individual "special" sprites, non-sprites such as lines, points and filled polygons, 3D objects, animated textures (such as movie clips).



Share this post


Link to post
Share on other sites
Well, these are the relevant data structures I am going to be using:


Sprite
Size
cx
cy

Pivot
x
y

Metadata[]
{ key = value... }

Textures[]
Texture...

Animations[]
Animation...
Texture ID // when loaded, turns into Texture Pointer

RegionSet ID // turns into Region Pointer

Frame Count

Frame Duration // how many seconds per frame

Frames[]
Frame
Source Coordinates
x
y

Region ID // per pixel collision data for this frame, optional

Metadata ID
Metadata[][]
{ key = value... }

-------------------------------------------------------------

RegionSet // for per pixel collision

Region

CollisionData[][]

-------------------------------------------------------------

Actor
Name

Class Name // for dynamic creation through callback binded to class name

Flags

Sprite Pointer

Sprite Animation ID

Animation Instance Cached

Animation Pointer

Time Started

Time Last Updated

Current Frame Pointer

Material Instance Container

Material Instance Pointer

Transform

Rotation Angle Radians
Z

Scale
X
Y

Bounding Volumes[]

Bounding Volume...

virtual Render() // updates animation only when renders

virtual Update() // does nothing by default, subclassed by client

-------------------------------------------------------------

Bounding Volume

virtual Intersection(const Bounding Volume*, const Velocity* out Contact Info*, out Penetration Info*)

Bounding Volume AABB: Bounding Volume

Bounding Volume OBB: Bounding Volume

Bounding Volume Circle: Bounding Volume

Bounding Volume Convex Polygon: Bounding Volume

Contact Info

Contact Point

x
y

Contact Normal

x
y

Penetration Info

Penetration

x
y

-------------------------------------------------------------

Material Instance

Material Pointer

Dynamic Parameter Values[]

Parameter...

-------------------------------------------------------------

Material

Effect Pointer

Static Parameter Values[]

Parameter...

-------------------------------------------------------------

Effect

D3DXEffect Pointer

-------------------------------------------------------------

Effect Pool

Shared Parameter Values[]

Shared Parameter...

Effects That Use This Shared Parameter[]

-------------------------------------------------------------

Graphics // Renderer

D3D Device Management

Cached Render States[]

Cached Sampler States[][]

Cached Texture Stage States[][]

Effect Pool

Vertex Buffer // for batching

Index Buffer // for batching

Render Queue

Order by ZOrder

Order by Effect Pointer

Order by Texture Pointer

Order by Material Pointer

Order by Material Instance Pointer

Order by Matrix (identity vs not identity)

Statistics - FPS, state changes, texture memory

void Clear(...)

void BeginScene(...)

void EndScene(...)

void BeginBatch(...)

void EndBatch(...)

void BeginClipping(...) // using clip rect

void EndClipping(...)

void RenderQuad(...)

void RenderLine(...)

void RenderMesh(...)

void RenderPoints(...)



This of course doesn't include the tile map structures, the spacial partitioning structures (I use uniform grid), the pathfinding, the physics, the resource manager, the resources, the class factory, the file IO for binary/text, GUI, GUI themes, input, sound, music, video, diagnostics, error handling, global event handling and scripting.

Share this post


Link to post
Share on other sites

virtual Render() // updates animation only when renders


I'd think about that if I were you - is Render() really the right time to be updating the animation?

There's some very good advice on gaffer.org about decoupling your physics from your rendering and allowing each to update at different rates.

If you wish to plug your sprite system into a system using decoupled physics and render rates, it would be far, far easier to update your animation in the Update() method (which would normally be passed some kind of time delta saying how much time had elapsed since last call to Update or be running at a preset rate) rather than inside the Render() method.

The Render() method should really only draw the object in its current (or interpolated) state rather than make any changes to the state.

Just a thought that occurred as I read down your (very comprehensive) structure.

Share this post


Link to post
Share on other sites
EasilyConfused, the problem is that Animation Instance is also used in Tiles, not just in Actors. For a 500x500 tile map filled with animated tiles (an unlikely real world scenario, but still), you would have to perform 250000 updates each frame. Each update would take very little time, but with so many updates you would become seriously CPU bound, because at the very least all this animation would leave less time for AI & physics, graphics sorting and culling.

When AnimationInstance is updated only when the object is being drawn, you in effect restrict the number of updates to the number of currently visible objects. I suppose you could argue that it's better to keep a separate list of active animation instances, but that solution would be pretty much identical to simply updating animation when the object is about to be drawn (since we use batching anyway).

If you notice, AnimationInstance also has a Last Update Time member, which is used for incremental updates. So when the animated object becomes visible after being invisible, Cache() function is called to update animation "for the first time" using the Time Started member (CurrentFrame = (Now - TimeStarted) Mod AnimationDuration). As long as animated object continues to be visible, Update() function is called for the animation instance, and it performs incremental updates (if Now >= LastTimeUpdated + AnimationFrameDuration then CurrentFrame++).

When every frame has the same duration, the cost of modulus instruction is negligible and incremental update mechanism is not really required. However I am planning to update my animation system to include a duration for every frame, so first-time update would involve looping through frames which could be slow, and incremental updates would be just as fast.

For a 3D game the animation update mechanism would work differently, because at any time there is a relatively low number of animated objects (environments are traditionally static), so coding animation updates (where you basically update the matrices for all bones and pass them to vertex shader) can be done on Update(). In addition, animation in 3D games often involves animation controllers, such as the ragdoll controller which gives up control of bone matrices to the physics system (inverse kinematics is in the same category). In 2D games on the other hand, you just play "walking" animation and then animate sprite position using physics. All we care about is that animation stops or changes when we need it to - trying to sync individual frames perfectly is normally not worth the trouble.

Share this post


Link to post
Share on other sites
I hear you. I have animated tiles in my current game but it works a little different, kind of a bit like the flyweight pattern.

Rather than have each tile in the (potentially large) map contain information about the tile directly, I have a std::vector<> of MapCell structures, one per each distinct type of tile.

The Map data itself is just a grid of ints that each index into this vector. When retrieving information from the Map about the tile at a particular location, I grab the int from the location in the map then use this to index into the MapCell in the std::vector.

In essence, each cell of the same type "shares" the attribute information in this vector.

With animations, each MapCell structure contains an Animation instance and when the cell is drawn, the frame to use is gained by grabbing the int, indexing into the MapCell array and then querying the Animation instance for the frame.

Each game loop, I just run through the MapCell vector and call Update() on each Animation, so this is done once per type of cell, not once per actual cell.

Obviously this means each type of cell will have to run its animation in sync with all the others of the same type, but it avoids the issues you describe above, as well as making the map smaller and gives animated map tiles with a small overhead that is not related to the size of the map.

So we can go back to seperating update logic from render logic.

I can also then add additional attributes to each type of cell without it increasing the size of the map itself.

Share this post


Link to post
Share on other sites
Yeah, this was actually on my todo list for the past two months, but I didn't realize this would also help with tile animation. I thought I would just have a function called Optimize() that the map editor would call when saving the user-edited map. All tiles would be saved in a 1D array, so then I would sort and remove duplicates, then re-point the 2D array of pointers to tiles. Currently my engine already uses 1D array of tiles and 2D array of tile pointers, so this would be the logical next step.

I also cache all the visible tiles for the camera, by "expanding" them to contain their pixel coordinates, changing all indexes to pointers, etc. So there would be no cache cost of accessing through pointers in the 2D array when drawing, and the whole visible tile cache would probably fit in the L1/L2.

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