New Library: SerializeQueue

Recently I completed the first draft of a new header only C++14 library I've been working: "SerializeQueue". The basic idea is that you push all your values onto the queue, serialize it to a binary file, then later load and deserialize the binary file back into a queue to pop data off of.

Github (project page): https://github.com/Salgat/SerializeQueue

This library has been especially fun because I've had a chance to delve into several programming tricks I wasn't familiar with before. The first and most basic is a method for converting a binary value into the specific type to be returned. SerializeQueue supports T pop< T >(), which, using type information, pulls the top information off the binary file and converts it to the type given. To prevent any compiler intervention, the binary is loaded directly into a uint64_t variable and then the following is done,

What this does is it takes the address of the variable, treats it as a pointer, then tells the compiler to treat that pointer as a pointer to a different type before dereferencing it.

The next "trick" I had to use was something called tag-dispatching. The purpose behind tag dispatching is that, for ambiguous cases, you create a way for the compiler to distinguish between two different overloads. Below is an example,

These functions are inline, and the tag itself is just an empty struct, so it ends up being optimized out of the program which eliminates the overhead of the tag. The basic idea behind this, for cases of std::vector, is that a special overload exists that accepts a tag of std::vector among other types specialized for.

The last and current problem I'm working on is implementing tuples. Tuples are difficult because it is a container that holds multiple data types, and requires template metaprogramming to implement. I just started reading Modern C++ Design to try to get a better grasp on this new programming method, but it's definitely a wall that I've hit with what I can do. Hopefully I can come back and flesh out the tuple implementation once I learn more about how to deal with generics. For now this library only supports tuples of basic types.

Game Release: BubbleGrow

Main Menu

After a month of development, BubbleGrow is finally ready to be released as open source. BubbleGrow is a simple game whose gameplay revolves around building an army of bubbles to gather resources and fight against other players, with the winner being the last man standing.

Github (project page): https://github.com/Salgat/BubbleGrow
Documentation (wiki): https://github.com/Salgat/BubbleGrow/wiki
Download (64 bit): https://github.com/Salgat/BubbleGrow/raw/master/BubbleGrow-V0.1-Windows-x64.zip

BubbleGrow's only dependency is SFML, which, along with only using the standard library, makes this game cross-platform across Windows, Linux, and OS X.  It's been tested on both 32 and 64 bit platforms with no performance issues (even ran it on an old dual core Pentium from 2007 with embedded graphics). BubbleGrow takes advantage of OpenMP to support multithreading up to as many cores as you can give it (assuming you have up to 1 thread per player, or up to 16 threads for default gameplay). The beauty of OpenMP is that it won't prevent compilation on compilers that do not support it, since it only uses preprocessor pragmas which can be ignored.

Gameplay: Two players battling each other

This game is almost completely licensed under the MIT license, with the only exception being the audio and font, which have their own licensing. The source code is completely open and free to modify, and for anyone who chooses to use the source code, they can do it without any requirements as long as they do not redistribute the source code without the MIT license.

Enumeration Iterator Library (EnumIt)

In the new game I'm making, I've been using enumerations along with constant arrays for some quick configurations and needed a quicker way to iterate through all available enumerations (for example, when loading images who are identified by their enum class value). I created an enum iterator library (EnumIt) which is a single header file. It comes with functions to get an enum's Begin and End iterator and also provides an interface which supports ranged-based for loops. Although very simple, hopefully it will be helpful to someone else. Below is an example which can be found on the github page: https://github.com/Salgat/Enum-Iterator

 #include <iostream>  
 #include <string>  
   
 #include "enumit.hpp"  
   
 enum class SampleId {  
   FIRST,  
   SECOND,  
   THIRD  
 };  
   
 /*  
 enum SampleId {  
   FIRST,  
   SECOND,  
   THIRD  
 };*/  
   
 int main() {  
   for (auto iter = enumit::Begin<SampleId>(); iter != enumit::End<SampleId>(SampleId::THIRD); ++iter) {  
     SampleId entry = *iter;  
     std::cout << "Current SampleId: " << static_cast<int>(entry) << std::endl;  
   }  
   
   for (auto entry : enumit::Iterate<SampleId>(SampleId::THIRD)) {  
     std::cout << "Current SampleId: " << static_cast<int>(entry) << std::endl;  
   }  
   
   return 0;  
 }  

New Project: BubbleGrow

In game screenshot

A couple weeks ago I decided to do one more project before going back to developing my other game. From the above screenshot, you can see a preview of the game, titled "BubbleGrow". The basic idea is that you collect resources (green bubbles), purchase and upgrade your bubbles, travel around the map, and fight other players (such as you (red) fighting the computer (teal) in the above screenshot). The arrow indicators on the edges of the window show where other players are.

The goal for this game isn't so much being fun or for selling, but as a free and open-source project for learning. I've been using GitHub for revision control. I've kept the external dependencies to a minimum (only SFML at this point) and licensed everything (including the artwork I made) under the MIT license, so that anyone can use anything from this project for whatever they wish.

Mock-up main menu (only Quick Match games are currently supported)

The game is structured in a simple manner, is well commented, and is designed to be easy to dive into. To break it down quickly, there exists a "World" class that holds all players, a "Player" class that holds the state of each player, and a "Unit" class that holds the state of each bubble. There is a single subclass ("Resources") that is a specialization of the "Player" class in that it handles those green resource bubbles that the players can mine for purchasing units. The only other class is a "Renderer" class that handles the display and input. I plan to expand the "Renderer" class since it's approaching over 500 lines of code and has way too much scope. A few additional classes are needed to handle sound and batch drawing.

As a learning resource (which is the whole point of making this open source) I hope this project allows people the chance to learn how to download and setup a build environment for a medium sized project. I plan to heavily document instructions for new programmers to be able to build and modify the game. As of now, all that's needed to build BubbleGrow are the library and include files downloaded from the SFML website, CMake, Make.exe, and MinGW.

The different bubble types you can purchase and upgrade to

Additionally, with the way the program is structured, it should be easier for newer programmers to dive right in and start changing things. The entire game state is focused around 3 major functions, "Update" which updates the unit's health and other stats, "MakeDecision", where each unit has a view of the game state and submits a Request for processing, and "ProcessRequest", where the Unit executes either its current action (such as finishing an attack) or starts a new action based on the Request (decision) it just made.

Finally, as a bonus, this game supports multithreading using OpenMP, which is awesome because it is both cross-platform and compiler safe (since OpenMP uses pragma compiler directives which will simply be ignored if not supported) and because this is accomplished without using any threading libraries. While it would have been nice to use a concurrent container from a library like Threading Building Blocks, by following certain rules (such as only calling const methods on containers that don't modify the internal state of the container) and setting only a few variables to atomic, thread-safety is maintained.

Anyways, progress is rapidly underway and I hope to finish it in the next couple weeks. It's certainly a fun personal project and hopefully will be helpful to others!

Using Python's PIL library to remove "green screen" background.

For some of the sprite sheets used in the game, the renders use a solid background color; these need to be removed to show only the object that was meant to be rendered. An easy way to do this is using Python's image editing library, PIL. Check out the source below.

 from PIL import Image  
 from PIL import ImageFilter  
 import os  
 for filename in os.listdir("."): # parse through file list in the current directory  
      if filename[-3:] == "png":  
           img = Image.open(filename)  
           img = img.convert("RGBA")  
           pixdata = img.load()  
           for y in xrange(img.size[1]):  
                for x in xrange(img.size[0]):  
                     r, g, b, a = img.getpixel((x, y))  
                     if (r < 130) and (g < 60) and (b < 60):  
                          pixdata[x, y] = (255, 255, 255, 0)  
                     #Remove anti-aliasing outline of body.  
                     if r == 0 and g == 0 and b == 0:  
                          pixdata[x, y] = (255, 255, 255, 0)  
           img2 = img.filter(ImageFilter.GaussianBlur(radius=1))  
           img2.save(filename, "PNG")  

The basic idea is to load each frame of the animation, loop through each pixel of each frame, and remove the color of the "green screen" background color, including a small range to account for the semi-transparent pixels on the edge of the rendered object that are mixed with the green screen. Finally, a small blurring filter is added to soften the edges of the image, otherwise at the edge where the green screen is removed, it looks more obvious that it was "cut out". As a final touch, after creating the sprite sheet you can use a program like GIMP to add some additional filters to adjust the color and contrast. You can also use GIMP to get the exact RGBA numbers to specify which color to filter out in your program.

Concurrent Map

Before moving on, I decided to add one more concurrent container to the library I mentioned in my last post. Stack and queue are relatively primitive in that they are a singly linked list of data with either one or two pointers held by the class. Operations such as push and pop can be simplified to just changing the head or tail of the data structure. I really wanted to do one more that is an especially useful data structure so I wrote a pretty basic implementation of std::map but concurrent.

The concurrent map was implemented using a combination of buckets for a very small and basic hash, and then for any collisions in these buckets were stored in a balanced binary tree (AVL, which is contrary to the STL's red-black tree implementation). A simple hash was used because it allowed me to partition the values into "thread-safe zones" that I could wrap a mutex around. It's a pretty naive/basic way of adding concurrency to a map compared to more advanced lock and wait-free methods but it does work.

At this point I'm very anxious to get back to programming for my game and have already started reading a new book on ZeroMQ, which is a very robust library for handling many network connections in a simplified manner. I'm not sure if this is the library I will end up using for networking in the game, but it's extremely interesting none-the-less and I look forward to learning more about it.

Anyways, for those interested in checking out the source for the new concurrent map, check it out at: https://github.com/Salgat/Concurrent-Containers-Library/blob/master/containers/map.hpp

Concurrent Data Structures

For the past 6 weeks I've been on a different schedule due to training at work that has unfortunately restricted much of my time that can be devoted towards programming. Although I've been busy with work, that doesn't mean I haven't had any free time left! On my days off I've been studying concurrency in a much more in-depth manner and even wrote a basic concurrent data structures library. It's published on github and supports a concurrent stack, queue, and a third data structure similar to stack and queue (in that it supports push and pop) but the pop order is not guaranteed (it must be assumed that the pop order can be random).

 #include "ccl.hpp"  
 #include <iostream>  
   
 int main() {  
   std::cout << "Starting concurrent data pool test" << std::endl;  
   ccl::data_pool<std::string> pool;  
   
   pool.push("Hello!");  
   
   std::string popped_value = "Empty";  
   if(pool.try_pop(popped_value)) {  
     std::cout << "Popped value: " << popped_value << std::endl;  
   } else {  
     std::cout << "Value did not pop, variable is still: " << popped_value << std::endl;  
   }  
 }  

For the concurrent stack and queue, I used a technique called "Flat-Combining" to maintain thread-safety when accessing the containers. The idea behind flat-combining is that each thread gets access to a special record that they can publish their desired action to. They then wait for a response on that record indicating that the action has been processed on the data structure. A global lock exists that limits only 1 thread to be able to process the requests of the other threads. If the lock is available, any thread that is waiting for a response will try to take the lock and take it upon themselves to publish the actions of all the threads to the data structure. I found this data structure to not only be more performant but also much easier to implement compared to a traditional lock-free data structure.

For the last data structure (which I called "data_pool" since I'm not sure what the right name is for it), it is what I consider more concurrent friendly because it compromises by allowing any order for data popping. Data is stored in vectors of successively growing size (larger vectors are added as more data is pushed to an already full data structure), which helps with spatial locality, and since the the same vectors are used repeatedly, temporal locality is improved (instead of allocating a new node on the heap every time a value is pushed).

If interested in checking out the source code and some examples, the project's page can be found at: https://github.com/Salgat/Concurrent-Containers-Library. It should be noted that these are naive implementations and are neither guaranteed nor fully tested.