Fixing Memory Usage Issue for Noah’s Ark

I recently ran into a memory usage defect for my Noah’s Ark game. Basically, as the player scrolled to different tile maps in the overworld, memory usage would continue to climb, eventually bringing the game to a crawl. The fix was really simple but involved some more subtleties of C++ smart pointers, so it seemed worth writing about.

Graphics Management
First, it is important to understand how graphics are currently managed in the game code. Different types of graphics components are created from the GraphicsSystem. The GraphicsSystem is then responsible for rendering all of the graphics on screen.

I’m not necessarily sure this is the “best design” for the game (if you have other ideas, feel free to suggest them!). It is just something I’m experimenting with from various things I’ve read (mostly on entity component systems or ways to avoid having all of my game objects have explicit render methods). My main goal was to be able to easily apply global settings to all of the rendered graphics without having to touch a bunch of classes. Time will tell how well this works out.

Map Scrolling
The second major piece of the puzzle is to understand how the game scrolls between individual tile maps in the overworld. At any given time, the OverworldMap holds the current, top, bottom, left, and right TileMaps (assuming they exist):

The tile maps in memory at any given time in the Noah's Ark game.

When the player reaches the edge of the current map, the game scrolls to the appropriate adjacent map (if one exists), and then reloads any new maps surrounding this new map being scrolled to.

The Bug
There is a bit of a problem with the above approach, if you look at the details of the specific data types used. The graphics components created by the GraphicsSystem are returned as shared_ptrs and were (before the fix) also being stored as shared_ptrs in the GraphicsSystem class. These shared_ptrs are then used by whatever objects the graphics are for. In this case, these shared_ptrs were also used by Tiles in the TileMap class.

When scrolling to new TileMaps, the old TileMaps would be destructed, decrementing the reference counts for the shared_ptrs for Tiles in the map. However, since the GraphicsSystem still stored these shared_ptrs for the tile graphics, the reference count would still be 1, so the tile graphics would persist in memory. New maps would be loaded, creating new tile graphics components, but all of the old tiles would still exist. Obviously, this is problematic and leads to increasing memory usage over time, which ended up slowing the game to a crawl.

The Solution
I actually was aware of this problem during original implementation of the design outlined above but forgot about it by the time the defect actually manifested itself. This was a pretty major architecture problem, but I didn’t want to abandon the idea of having a centralized place (away from the main game objects) to control rendering.

I couldn’t use unique_ptrs since the graphics components needed to be accessible by both the GraphicsSystem and the individual objects the graphics are for. There are ways around this, such as using raw pointers, but that would make communicating when the resources were to be deleted from the GraphicsSystem pretty ugly (I also don’t like the lack of clarity that raw pointers can present when reading code, but that is for another blog post).

Fortunately, C++ had an elegant solution. Enter the weak_ptr. The description on the linked page is best to read for an understanding (and examples help), but a weak_ptr allowed me to break the > 0 reference count problem described above in a pretty nice way.

When an object like a Tile (part of a TileMap) is destructed, I wanted it to communicate to the GraphicsSystem that the graphics for the Tile could be deleted. To accomplish this, I made the following changes:

The GraphicsSystem was changed to store its graphics components as weak_ptrs instead of shared_ptrs:

std::list< std::weak_ptr<IGraphicsComponent> > m_graphicsComponents;

One nice thing is that the weak_ptr class has a constructor that allows it to be constructed from a shared_ptr, meaning I didn’t have to touch the code that added items to the above container.

Next, I had to update the for loops that iterated over the graphics components to use weak_ptrs instead of shared_ptrs. Before updating/rendering an individual graphics component, I needed to check if the object had already been deleted elsewhere (i.e. the Tile destructor) using the expired method:

if (!graphicsComponentWeakReference.expired())

(See the Wikipedia page for an overview of the concept of weak references.)

Assuming that the weak_ptr hasn’t expired, then the lock method can be called to obtain a usable shared_ptr to the object:

std::shared_ptr<IGraphicsComponent> graphicsComponent = graphicsComponentWeakReference.lock();

Tada! We’re almost done. The above code allows for checking if a graphics component has been deleted elsewhere, but it doesn’t actually solve the problem of increasing memory usage. The weak_ptrs are still stored in the list, so they need to be removed at some point. Fortunately, the list container has a remove_if that allows us to easily remove elements from the container that meet a certain condition (without resorting to the erase-remove idiom). Removing the expired graphics components can be done in what is effectively a single line of code:

m_graphicsComponents.remove_if([](std::weak_ptr<IGraphicsComponent>& graphicsComponent) { return graphicsComponent.expired(); });

That’s it! You can browse the full set of changes for this fix here. Finding and fixing this bug was a good learning experience for me, so hopefully it will be of use to some of you.

Galactic Egg Snatchers – Postmortem Code Review

I recently finished leading a game project called Galactic Egg Snatchers as part of a hobbygamedev warm-up project where I was primarily a programmer. You can download the game here (with VC++2012 redistributable) or here (without VC++2012 redistributable. As hinted at, you need the Visual C++ 2012 redistributable installed to run the game.

With the game now complete, I figured it would be a good time to look back on the code written for the project. This “postmortem code review” won’t cover everything about the code – just some of the points more interesting to me. Of course, if anyone wants to know more about how some other portion of the code evolved, feel free to let me know.

There are two important things to keep in mind before digging into the details. First, the game was created within about a month, so the code quality suffered some for this slightly rushed pace (including some ugly instances of duplicated code). Second, this game is a very small game, so many of the design choices made in code probably don’t scale well to larger projects.

Separating the Game from the Window
A lot of the game code I’ve seen often has the “application” layer of the game, including management of windows, encapsulated in some kind of master “game” class. One thing I don’t necessarily like about this approach is that it couples the idea of the “game” to the “window”. This obviously doesn’t apply to many game platforms where conceptually there is just a “screen” for the game. Even though I have no intention of ever porting this game to any other platforms, I wanted to experiment with decoupling the game from an actual window.

This led to the game loop existing in main(). I’d prefer much of the loop to be encapsulated in the game class itself, but the loop needed to remain in main() in order to respond to certain window events – notably closing of the window and some keyboard presses. However, thanks to sf::RenderWindow inheriting from sf::RenderTarget, I was able to prevent the game class itself from depending directly a window. The concept of a “render target” corresponds more closely to the true dependency of a “screen” that I wanted to capture.

Size-Independent Code
In previous games, I’d often use hard-coded values for things like object/screen sizes in many different areas, even if they were centralized in some constants. This makes it harder to change code if dimensions of something change. I made a concerted effort to avoid this in this game. For example, instead of referring to constants somewhere, I could use methods like sf::Sprite::getGlobalBounds() to get dimensions of a sprite.

This means that I should be able to theoretically change the size of the game screen or many objects without having to worry about ripple effects throughout the code. While I haven’t tested most of this, there was definite benefit to this approach during the game’s development. Several times, I was able to drop-in new game art with different sizes without having the touch the code – things just worked. Of course, this was greatly simplified by the game art not being animated.

Monster Gameplay State
The different game “states” (or screens) all inherit from an IGameState interface. For the most part, these states aren’t too complicated. However, the GameplayState grew to be a rather large and complex class.

First off, one of the reasons this class is so complex is that I was intentionally trying to prevent complex logic from “polluting” the main game objects, thus hindering their reusability. By having an external class orchestrate the interactions of these objects, I could avoid some bad coupling (even though I have no intention of directly re-using any of these game object classes). Thus the GameplayState class became this monster class.

I haven’t taken the time yet to fully analyze this class to figure out how I would break up its responsibilities. However, one idea might be to have some kind of game object manager to handle most things related to the game objects in this existing state class.

Player Control and Interfaces
Initially, I had the KeyboardController supplying player input as a member of the EasterBunny class. However, I wanted to separate the bunny from being required to be attached to a source of user input. Therefore, I ended up keyboard supplying player input ended up in the GameplayState class.

This led to a lot of thinking about the interface to the EasterBunny class. I no longer could rely on a public “Update” or “HandleInput” methods. Instead, I had to really think about what I wanted the bunny to actually do. This led to what I think is a slightly clearer interface that truly exposes what the bunny can do (i.e. move left/right, fire a missile). Similar types of interfaces largely were applied to other game objects. I think I prefer this approach over handling everything in a single, vague method like “Update“/”HandleInput“, so I plan on applying this more for future game objects.

This approach also has led me to start re-thinking some of the conventional types of interfaces I’ve seen for game code. For instance, all of my main game objects inherit from an IGameObject interface, which has a single Update method. However, because of the approach taken to handling input described above, the Update method for the EasterBunny object doesn’t do anything. The other game objects all have logic in the Update methods, but the logic is extremely minimal – mostly focused on something that needs to be done due to the progression of time. Therefore, I’m starting to rethink interfaces such as a generic “Update” method. I’d prefer to capture logic in those methods in methods with more self-documenting names. However, it is clear that I still need some way to trigger updates to objects based on time.

Furthermore, a lot of the interface classes such as IGameObject weren’t really utilized in the game code. Since I found it clearer to treat distinct types of objects differently in the GameplayState, I didn’t have a reason to treat the objects polymorphically.

Dependency Injection
For most of the core game objects, I tried to follow a model of dependency injection for injecting required resources likes sprites or sound effects. You can see some examples in classes like Alien and Explosion. I didn’t want to tie the game objects to loading resources from a filesystem or resource manager, since that would inhibit reusability (even though I don’t intend on re-using any of these classes directly) and add a point of failure to the game objects that I didn’t think they should be responsible for.

Overall, I like how this approach turned out, but it isn’t without its downsides. For instance, it could lead to bloat in the constructor taking too many parameters. The resources were also stored in shared_ptrs, which were used primarily because they were an easy way to achieve this resource injection without worrying about memory management. This isn’t necessarily the intent I wanted to convey because I don’t really want the game objects to ever destruct the resources stored in these pointers (which is a possibility) – only the resource manager that loaded these resources should do that.

What I really want to convey is the concept of a pointer to an “externally managed” resource – the resource’s lifetime in memory is managed externally, so this external resource manager’s lifetime better outlive that of the game object to ensure the validity of the pointer. It might be possible to tweak one of the existing C++ smart pointer classes to achieve this, but it isn’t abundantly clear that this could be done in a clear way that would meet my requirements. A raw pointer in C++ would probably meet most of these requirements, but it isn’t very clear from just reading the code. I’d rather see something like external_ptr<Resource> that just a Resource * (so maybe I’ll create such a wrapper one day). Of course, for small games, a shared_ptr is probably sufficient since I’m not too worried about the resources hanging around in memory for a little longer than expected.

Ugly Handling of High Scores
As one of the last features implemented, the HighScores class was a nice idea initially but turned out to be pretty ugly. I liked the idea of encapsulating the high scores in a class, but the fact that loading/saving of the high scores is done externally to this class was probably a mistake. The interface to this class really isn’t that useful, so I probably would have been better just using C++ containers in raw form. Still, it gave me an opportunity to play around with std::stable_sort.

Todo Items
There are some items on my mental “todo” list from this game for re-usable code that I should probably take the time to develop (or find existing solutions) soon:

  • sf::Text is great, but I’d like to develop a library of slightly higher-level GUI components.
  • A library to generically read-in menu options (text + keyboard mappings) from file.
  • A library to generically read-in credits (names + roles for contributors).
  • A keyboard controller class with configurable key mappings (from file or code).

That mostly wraps up the main points of interest for me from a coding perspective. If you want to know more about some other portion of the code, just ask. Also, if you have your own criticism/advice/suggestions from your own review of the code, feel free to let me know.

Tiled TMX Map Loading and Rendering – Noah’s Ark Game

I recently resumed work on a game based on the Biblical story of Noah’s Ark.  You can find out more about the game (and view its source code) at GitHub.

Anyway, after getting the basic project framework up recently, I moved onto the first major task – loading and rendering a tile map for the game. The first decision to make was deciding on a tile map editor to use.

I’d previously used Mappy and Tile Studio to varying degrees. While great tools in and of themselves, they aren’t really maintained much anymore, and I’m not too fond of their output formats.

This time, I’ve settled on using Tiled. It has a less-obscure XML output format, which generally makes things easier to parse. Adding advanced features to the XML would have minimal effect on the complexity of any parsing logic. There are also a ton of XML parsing libraries out there, so if I needed to write my own parsing library, it wouldn’t be too difficult.

Like most tile map editors, there are already a bunch of of existing libraries for loading Tiled’s TMX maps. Most of these are tied to specific rendering libraries as well. This can be advantageous, but I really wanted a TMX loading library that wasn’t tied to SDL, SFML, or some other library. My intent is to hopefully have some reusable tile map code of my own that I can largely use regardless of rendering technology.

Thankfully, such a library exists: TmxParser. I was relatively impressed with how clean the library’s API is – reading and understanding the class headers was quick and simple. Throughout the course of the past week or so, I worked on integrating TmxParser into the Noah’s Ark game. The final result is a screen like this when booting up the game:

Rendering of a test map loaded from a TMX file

Rendering of a test map loaded from a TMX file

Next on my list of features for the game is adding an overworld map to connect tile maps. Scrolling between tile maps will soon follow. However, I’ll probably be taking a break from working on this game for the next month or so.