Box2.5D

When I started my first proper game project, it was in libGDX, in Java. Eventually, I realized this was silly and rebooted the project in C++11/17. libGDX includes Box2D, so I got my first exposure to the library without using it directly. Actually, I think this is a common practice, as there are a number of different game engine/libraries that similarly include it prebuilt, via interface.

One of the issues I ran into was that Box2D does not support layers. Objects take up 2D space in the physics world, and they have a type (b2Filter) that describes their identity and what they collide with. At first, this wasn’t a big deal. The first use of 2.5D was for the floor. I made the floor its own physics type, and stuff that needed to “touch” the ground would collide with it.

When I started the project, I used Chipmunk 6. I later realized that Chipmunk 7 is evolved to be more like Box2D; it adds collision filters, but removes layers. It also adds swept collisions and a kinematic mass-type.

Chipmunk had some niceties, additional “out of the box” functionality: point/shape query, callback dispatch per combination of physics types, use of double floats, and of course layers. I was able to get away with using Chipmunk without having to actually modify it. But when I got to the point where I did want to modify it, well the code is rather ugly and not as easy to modify.

It is written in C, and uses a C-style simulation of object-oriented programming:

/// Perform a rectangle query against the spatial index, calling @c func for each potential match.
static inline void cpSpatialIndexQuery(cpSpatialIndex *index, void *obj, cpBB bb, cpSpatialIndexQueryFunc func, void *data)
{
index->klass->query(index, obj, bb, func, data);
}

/// Perform a segment query against the spatial index, calling @c func for each potential match.
static inline void cpSpatialIndexSegmentQuery(cpSpatialIndex *index, void *obj, cpVect a, cpVect b, cpFloat t_exit, cpSpatialIndexSegmentQueryFunc func, void *data)
{
index->klass->segmentQuery(index, obj, a, b, t_exit, func, data);
}

The logic of what constitutes a collision (do the objects have the same group), isn’t cleanly organized into a single function like it is in the b2 ShouldCollide. The queries that it includes don’t work the way I expect queries to work. Rather than specifying the type(s) of object to query for, it treats the query as though it is a virtual object of the provided type. Thus, similar to the pairwise callbacks, I ended up not using this functionality; all my queries were for type/group 0, so that I could check for multiple types of objects at once.

Actually, all of the physics objects had to be group zero: in Chipmunk 6, a physics object has a single type, and by default, it collides with everything of a different type, but not its own. Lots of objects of the same type need to collide. This meant a lot unnecessary callback dispatch, to return whether or not a specific combination of objects should collide. In the same way that the query system is deceptively cool — I end up having to query everything as type/group 0, so I can get all combination of objects in a single call — the callback system isn’t that useful. Since it’s in C, I can only use plain function pointers for callbacks, which means I can’t use templates functions or std::function / std::bind. So, I end up installing the callbacks for the various combinations of types, but it’s the same function pointer!

Similar to the way you have to provide a b2Transform in order to use a b2Shape, with Chipmunk you have to create a static body, and create a shape in order to do a shape query. The interface for this internally uses dynamic allocation, which isn’t necessary for the Box2.5D version.

Presumably, not all of the simplicity is really a benefit. For example, I realized my code had a problem in that certain AI functions would set the angle of agents during a callback. No issue in Chipmunk; Box2D has an assert for it. From b2’s perspective, updating the angle is updating the same linear transform as the position, and clearly the position wouldn’t be allowed to change. I didn’t find out if this was only allowed for circles (since the rotation of the circle doesn’t affect the linear transform of verticies, as it would for a polygon). (There are a number of possible solutions, such as not actually rotating the fixture, but having it be a game object field. Instead, I simply have a flag I set that indicates a physics step is running, and setPosition & setAngle will push a message to a function queue that will run after the physics step is over.

If your game is complicated enough, you will want to modify Box2D. But the good news is that it is clearly designed to be easily modifiable. However, Catto seems to be very conservative about what he wants to put in the engine. With my updates, I get the best of both worlds. All of the same functionality, but implemented with efficiency.

The Changes

First thing was to change it to use doubles; my earlier attempts first had me refactor all of the float literals to doubles. It makes logical sense, since the macro-defined type that b2 uses for its general arithmetic is a “float32”, which is misleading. But it involves changing too many lines of code, so I didn’t bother. float32 is actually double now.

Next thing was to add layers to the collision filter. While I was at it, I made all of the numbers in the b2Filter 32-bit. I already have almost 16 physics types, and at some point I plan to use more sub-types (or interface types).

const unordered_map<GType, uint32> physics_context::collisionMasks = {
    { GType::areaSensor, g(player) | g(enemy) | g(npc) | g(environment) },
    { GType::bomb, g(player) | g(enemy) | g(npc) | g(environment) | g(wall) | g(floorSegment) },
    { GType::enemy, g(player) | g(playerBullet) | g(playerGrazeRadar) | g(enemy) | g(environment) | g(npc) | g(floorSegment)| g(areaSensor) | g(wall)},
    { GType::enemyBullet, g(player) | g(playerBullet) | g(playerGrazeRadar) | g(environment) | g(wall) },
    { GType::enemySensor, g(player) | g(playerBullet) | g(enemy) | g(bomb)},
    { GType::environment, g(player) | g(playerBullet) | g(enemy) | g(enemyBullet) | g(environment) | g(wall) },
    { GType::foliage, g(player)},
    { GType::floorSegment, g(enemy) | g(environment) | g(npc) | g(player) },
    { GType::npc, g(player) | g(environment) | g(wall)},
    { GType::player, g(enemy) | g(enemyBullet) | g(environment) | g(playerPickup) | g(npc) | g(floorSegment) | g(areaSensor) | g(wall) | g(enemySensor) },
    { GType::playerPickup, g(player) },
    { GType::playerBullet, g(enemy) | g(enemyBullet) | g(environment) | g(npc) | g(wall) },
    { GType::playerGrazeRadar, g(enemyBullet) },
    { GType::wall, g(player) | g(playerBullet) | g(enemy) | g(enemyBullet) | g(environment) | g(npc) | g(floorSegment) | g(areaSensor) }
};

My previous experience with Box2D always involves defining the pairwise collisions, as shown above. Eventually, there were bugs. Certain things I forgot, like environment-bomb. In this case, the entries are supposed to be symmetrical, which means having to change two lines. Eventually, I realized two things. 1) Most of these types are a kind of physics group, “real” physics objects that aren’t supposed to go through any other “real” physics object. 2) I was wasting effort writing out the collision masks at all; the way my collision pairing was set up before, I needed to install a handler function with every combination of physics type that could collide. So, I simply changed it so that my AddHandler() function would set the appropriate bit for each physics type when installing a collision pair. For objects that should collide with each other, but which don’t need a callback (e.g. environmentObject-wall), they are all in group 1.

void PhysicsImpl::addCollide(GType a, GType b)
{
    emplaceIfEmpty(collisionMasks, a, to_uint(0));
    emplaceIfEmpty(collisionMasks, b, to_uint(0));

    collisionMasks.at(a) |= to_uint(b);
    collisionMasks.at(b) |= to_uint(a);
}

void PhysicsImpl::AddHandler(
    collision_type types,
    contact_func begin,
    contact_func end
){
    auto actual = types;
    if (actual.first > actual.second) {
        swap(actual.first, actual.second);
    }

    if (begin)
        beginContactHandlers[actual] = begin;
    if (end)
        endContactHandlers[actual] = end;

    addCollide(types.first, types.second);
}

My next issue is that my Bullets, which are sensor objects, didn’t have collision normals (for ricochet). There are actually two different issues here: 1) It turns out that b2 only computes this information (contact manifold) when it plans to use it for dynamic object collisions; i.e. at least one object is dynamic, and neither object is a sensor. 2) Even with it does compute a contact manifold between two circles, it doesn’t calculate the collision normal. Chipmunk 6 didn’t have kinematic mass-type, so my bullets were dynamic. But their mass was irrelevant, since they were also sensors.

First, I had to allow static/kinematic collisions. I don’t know why it is presumed that static/kinematic shouldn’t collide; obviously, there isn’t going to be dynamics, but there could be a game logic reason for it, just like sensors. This involves changing b2Body::ShouldCollide() – not to be confused with the b2Fixutre method of the same name. That one checks the filter; this one checks logic, like whether two fixtures are part of a constraint, or the same body. In this case, it was also unnecessarily requiring one to be dynamic. Once I changed this, I also had to change b2World::SolveTOI() – The sweep algorithm steps through current contacts, ignoring ones without dynamics; I changed the assert to a continue, so it steps past them, just as it does for sensor contacts. Contacts are used not only for dynamics, but to make sure endContact is called when appropriate.

As stated b2 normally only calculates contact manifolds for dynamic objects. We can change the code in b2Contact::Update(). Previously, it would use b2TestOverlap instead of evaluating a contact manifold. Contact manifold involves calculating a minimum separating line, and gives us contact points and collision normal. The idea is to avoid unnecessarily computing this, when we can simply check the shape overlap instead. However, I want a collision normal in all cases. This can be optimized, by setting a b2Body flag to mark whether a fixture cares about having a contact manifold (contact points & collision normal)  calculated, even if it is non-dynamic, otherwise use b2TestOverlap as before.

Queries

Box2D will assert/abort on a zero length raycast, which seems silly, since it should simply return without doing anything instead. I first noticed the bug when I had two enemies in the same position in the map. The agent’s view sensor does a raycast to check for line-of-sight.

I noticed, as I was exploring the b2 code, that it had a shape system. Shapes describe the geometric properties of a fixture. They have a size, but no position/orientation (linear transform). When I first refactored my code to use b2, I had to deal with the fact that it didn’t have a shape query (or point query). The closest thing it has is QueryAABB. But actually it isn’t the same. As the name implies, this callback actually steps through the spatial-tree (“broad-phase”), and in fact simply checks collision with the AABB of each fixture. So, my initial implementation of a rectangle query was incorrect (if used to query any kind of object that isn’t an axis-aligned box), as was my implementation of point query.

With ShapeQuery, I followed the convention of  RayCast and TestPoint; they are virtual b2Shape methods, that can take any other shape. This means each class has to dispatch the specific collide code based on its type and the type of the other shape, in a similar fashion:

bool b2CircleShape::ShapeQuery(
    const b2Shape* shape,
    const b2Transform& thisXF,
    const b2Transform& otherXF,
    int32 childIndex
) const {
    b2Manifold manifold;
    auto _type = shape->GetType();

    switch (_type)
    {
    case Type::e_circle:
        b2CollideCircles(&manifold, (b2CircleShape*)this, thisXF, (b2CircleShape*)shape, otherXF);
    break;
    case Type::e_polygon:
        b2CollidePolygonAndCircle(&manifold, (b2PolygonShape*)shape, otherXF, (b2CircleShape*)this, thisXF);
    break;
    case Type::e_edge:
        b2CollideEdgeAndCircle(&manifold, (b2EdgeShape*)shape, otherXF, (b2CircleShape*)this, thisXF);
    break;
    default:
    break;
    }

    return manifold.pointCount > 0;
}

b2World::QueryShape is similar to QueryAABB, except that it takes a b2Shape* & b2Tranform rather than an AABB. For convenience, b2Fixture::ShapeQuery wraps the call to b2Shape::ShapeQuery, also supplying the shape’s transform. As an added optimization & to reduce redudancy, I decided that I should be able to pass in a b2Filter to the query. This reduces unnecessary callback dispatch. In case you’re curious, it looks like the all of the various queries in b2World step through the broad-phase and run a callback for each applicable filter. That’s true, but note that the function that steps through the broadphase is templated, so it’s not the same as the overhead of having a callback (function pointer or vptr invoke).

I refactored filter into its own file so that it could be used in b2World.h, and made another change: I refactored the code from b2Fixture::ShouldCollide – into b2Filter::shouldCollide(). this works the same as before, it is just refactored. The new bit is the isBlankType & isQueryCollide. I want query filter semantics to work such that I can pass in a filter that represents the identity of an object, and check what it collides against (Chipmunk functionality). But mostly, what I want is to simply avoid giving the filter a type or group, and simply use the mask & layers. This is what isQueryCollide does; if it’s a blank type, it just uses the mask directly. As written, it will do positive group collision: if I give the filter a group, then it has an identity, and will collide with that same group according to the usual rules. However, as written, it doesn’t work for negative groups (which I am not currently using). I don’t see the point of using negative groups, since by default things will not collide. I can’t currently query for a negative group object using the query filter as written, since by definition the filter isn’t going to collide with a matching negative group. In this case, pass in an all 1’s bitmask, and then check for the group directly.

Once I had the structure, I refactored RayCast, QueryAABB to use filters. And then added QueryPoint.

Later, I started making more extensive use of RoomSensor. Some AI functions, and object sprite fade, depend on knowing what room an object is in compared to the player. The dumb way to do this is have a list of rectangles to represent your rooms and search through them to find a point match. The smarter way would be to organize these rectangles in a spatial-tree. Since the physics engine is already doing this, we can simply point query when we want to know what room an obje t is in. Except, we don’t even need to do that. The smartest way is to have the object collide with RoomSensor and set the current room. It already worked for agents. It didn’t work for static environmental objects.

One solution would be to have classes of objects that might be static mass-type, that need to know their room, do a point query on initialization. For certain object types that don’t really need to collide with RoomSensor, like Bomb and InventoryObject, this was the approach I used. In other cases, the idea that a static sensor needed to handle detection of static objects as a special case was too much. I changed the contact updating logic a bit more so that it would process collisions between static objects, if at least one of them is a sensor. This allows RoomSensor to collide with all environmental objects again, which it was already supposed to be doing, and not have to worry about handling static objects as a special case.

To see the complete code, check it out here: (https://github.com/afluriach/Box2.5D)

Advertisements

Scarlet Devil Underground – Libraries used

The project started as “simply” a Cocos2D project. Cocos2D is in turn a rather large library, not just including its 500+ compilation units, but also the pre-built libraries it includes.

The default Cocos2D project on Windows builds as a DLL. This poses a couple of problems: one is that it is a rather large library, and my project only uses a small fraction of it. The compiled release DLL is almost a dozen megabytes. The whole application exe, which includes everything that it uses from cocos2d and everything else is only 5 MB!

The other problem is that the compiler & code generator has limited ability to optimize code in different libraries. The program has no specific knowledge of the code that implements a certain function in an external library file, just that it is supposed be available in a certain library at a certain address. Even statically linking typically poses this problem: the library is compiled to optimized binary, and the application simply pastes in this code. This is solved with /LTCG (link-time code generation) and whole program optimization.

When I started on the project, I spent a fair amount of time lost in the weeds over Lua. It was nice to build it from source, so I could put timer & profiling code in Lua. I ended up not keeping any of the changes, and moreover it doesn’t really matter: although I do sort of have a working mod API, it is not ready yet. Currently, Lua is only used for the dev scripting console.

Chipmunk has sort of a similar story. I built it from source in order to get Chipmunk++ working; it later turned out that physics objects such as shapes were not getting deallocated when I expected (memory leak), and it required extra boilerplate code to write wrappers for query functions that weren’t part of the library. Solution: remove Chipmunk++ and just use Chipmunk directly. I did make one change to Chipmunk, reducing “slop” so that objects don’t sink into each other as much. Either way, once I was building it from source, I was able to turn on build optimizations.

OpenGL/GLFW – Cocos2D was originally created for iOS (OpenGL ES), and was later ported to desktop. On desktop, it uses GLFW; it handles the platform-specific details of opening a window with an OpenGL context and device input. Cocos2D includes a pre-built library, but I build it from source so that I can get max optimizations.

libnoise – I use this libary just for its Perlin noise model, which is currently only used to calculate torch light flicker.

OpenAL – (technically OpenAL-Soft) When I first tried to implement sound, I found out that the Cocos2D “sound engine” is kind of a joke. The Windows implementation didn’t even support gain or panning, i.e. not even stereo sound. First, I tried FMOD. I was able to basically get it working in a single work session, except that I didn’t get the listener orientation vectors right on the first time (the surround sound was sideways). Unfortunately, it is proprietary software. I do qualify for a free independent license; in fact, I had to sign up for one to download the API. But then when I contacted support to confirm the license, they basically told me I wasn’t welcome to use their product until I divulged all of the details about my game project. Since it was an unreleased demo, and I didn’t want to disclose details to them beforehand, I simply gave up on FMOD. OpenAL takes a bit more boilerplate code, but it basically provides the same features. Just like FMOD, DirectSound, & XAudio, it is actually a 3D sound engine. Just as my game makes use of 2.5D physics, so also it technically has 2.5D sound: most sounds play at the default y-position of 0, and that is the y-position of the listener (player’s head). However, footsteps actually play at a y-position of -1. And when I make more advanced use of 2.5D features, all sound-producing objects will have a y-position. I don’t have a pair of 3D headphones, so I wasn’t able to test this, only regular 2D surround sound.

libsndfile – The most annoying thing about OpenAL is that it doesn’t include helper code for loading audo files–seemingly obvious, basical functionality. FMOD does, but DirectSound & XAudio doesn’t either.

libgainput – GLFW supposedly supports gamepads, but it won’t detect my XBOX360 controller on either Mac or Windows. libgainput provides multi-platform gamepad support.

The only code included in the project that isn’t fully optimized is the pre-built libraries included with Cocos2D. The only one I use that happens to be a DLL is zlib. When you build Cocos2D, it in turn statically links against libraries such as libpng and freetype; the relevant parts of these libraries are in turn indirectly linked into the final product. Cocos2D uses a cache system for sprites & fonts, so each file is only loaded once–or once in a while–ideally all at once when the program is started, or between scenes. Thus, this code isn’t performance critical. Everything performance critical, code that runs every frame, is statically linked with full optimization (/O2 and /SSE2). (Note: shortly after releasing v0.1 of the demo, I did get around to statically linking OpenAL-Soft with the same optimizations as the other libraries. This also removes the requirement for the Visual C++ 2012 runtime):

Cocos2D
GLFW
Lua
Chipmunk
OpenAL
libnoise
libgainput

 

XCode (boost) static linking woes

My project has finally evolved to the point where I am pulling in the Boost libraries.

I ran into an odd problem, where I configured XCode to use a static library, yet when I tried to run the program, it halted with an error, claiming that it was trying to find a dynamic library image.

Here’s what I found out:

-When you build Boost using the default  b2 script, it actually creates both static libraries (.a) and dynamic libraries (.dylib).

When you add a library to a project, it actually generates a linker directive like -llibboost_serialization; so it actually strips the file system information. If there is a dylib file with the same name, the linker assumes you are tried to dynamically link against the file.

I was able to fix the problem by moving all of the Boost .dylib files to a separate folder that was not a linker search target.

C++11 – Concurrency

Early in the development of the project, multithreading wasn’t used. The cocos2d::Director runs the current Scene. This in turn contains the game logic. I never used the convention of cocos2d::Node <–> game object. Instead, this functionality was moved into an game word (GSpace) early on. Rather than looking up objects by Node name, or using the provided wrapper for making Nodes physics objects, I did that sepeartely. It didn’t really take much extra code, once the boilerplate for creating the different kinds of physics bodies and callbacks is set up. And, I knew early on that at some point, I would probably want to move game logic (physics and object update) out of the (application main) graphics thread.

Most of Cocos2D is not thread-safe. In particular, the Scene/Layer/Node graph, which it recursively steps through to build the OpenGL linear transform (matrix) for each element as it draws it to the screen. If you try to do certain things concurrently when cocos2d is rendering, particularly add or remove nodes, it will mess up the transform stack and crash–usuawly with some kind of memory corruption in the Renderer.

During my first attempt at this, I ran into conceptual problems: since I can’t create a cocos2d::Sprite in the game logic thread, I have to create a command to create the Sprite, and wait for it to actually be created. This also creates issues when the initialization code wants to do something to the sprite, like set its color transform or run an animation on it before it has actually been created.

The solution to the problem is rather simple, although it takes some amount of boilerplate code: since the game world logic runs in its own thread, it should not directly manipulate Cocos2D objects at all. Instead, the GSpace, which every game object has access to and is thread-safe (for them), has an interface for making graphical changes.

In GScene (my polymorphic Scene god class), I have to manage the lifecycle of the Nodes; this interface uses unique integer IDs:

typedef unsigned int SpriteID;
atomic_uint nextSpriteID = 1;
unordered_map<SpriteID, Node*> graphicsNodes;
void createSprite(SpriteID id, string path, GraphicsLayer sceneLayer, Vec2 pos, float zoom);

template<typename... Args>
inline SpriteID createSprite(void (GScene::*m)(SpriteID, Args...), Args... args)
{
	SpriteID id = gscene->getSpriteID();

	if (isMultithread())
		sceneActions.push_back(bind(m, gscene, id, args...));
	else
		(gscene->*m)(id, args...);

	return id;
}

I need the initialization code in the game object to get the sprite ID of the sprite it just queued a command to create, but that hasn’t been created yet. When a game object creates a sprite, it doesn’t run the GScene command, it pushes a function bind for that method (a message or comamnd) into a queue in the GSpace, and it will basically get run on the next graphics update in the main thread.

Thus, when the initialization code for the game object runs, it actually gets the next spriteID and provides it to the createSprite() function bind. (In case you are confused, there are number of different “create sprite” methods in GScene, for creating different kinds of Nodes like Sprites, DrawNodes, ShaderNodes, TimedLoodpAnimations, etc.) By doing so, the object’s sprite ID is initialized so that it can be used, even though the object hasn’t been created yet. i.e. It might create a GScene messagae to update the position of the Sprite on the first frame, if it is a kinematic object like a bullet that is initialized with a velocity and moves every frame. This isn’t a concern, since the GScene messages will be processed in the order they are created, so the sprite will be created before the messasgaes that try to use it. The messages that do try to use it are defensive, they look up the Node by ID in the map, and check for end/invalid iterator (i.e. invalid ID).

When the GSpace runs its update tick, which includes updating the relevant objects, it will then push all of the graphics update messages for that frame. If I didn’t do this, I would run into issues where the camera would sometimes stutter, because the message to set the Player’s position, and the message to set the camera position, didn’t run in the same frame.

Actually, at first, I didn’t have the GScene action queue set up in GSpace, only in GScene. What this means is that every call to a scene method to update the graphics would be mutex-protected, and the function would be pushed into a queue. Of course, this is potentially rather wasteful, since it involves lots of mutex acquisitions per frame, instead of just one. But it actually turned out not to have any particular performance effect.

When you have a multi-threaded game where the game logic only takes a couple of milliseconds per frame, you can turn off the frame rate limiter and run things in very fast motion. This allows me to stress test memory leaks and concurrency problems, for example with a spell card that creates a huge number of bullets. I also originally gave bullets light sources just to test the thread-safety of the GScene lightmap code (it uses a similar message-passing convention as the sprite code).

In the production code, it doesn’t use this. If multithread is being used, it runs the space thread in “lock-step” with the main thread, at the same frame rate. If the GSpace update were run at a different frame rate, the game would be in slow-motion or fast-motion. The main thread is still the master timing/update thread; it handles controls, including copying the control state of the current frame to the GSpace. before setting its condition variable.

class GScene {
//...
	unique_ptr<thread> spaceUpdateThread;
	mutex spaceUpdateConditionMutex;
	condition_variable spaceUpdateCondition;

	atomic_bool spaceUpdateToRun;
	atomic_bool isPaused;
	atomic_bool isExit;
//...
}

GScene::~GScene()
{
	isExit.store(true);
	if (App::multithread) {
		spaceUpdateCondition.notify_one();
		spaceUpdateThread->join();
	}
	delete gspace;
}

void GScene::waitForSpaceThread()
{
	if (!App::multithread) return;

	unique_lock<mutex> mlock(spaceUpdateConditionMutex);
	spaceUpdateCondition.wait(
		mlock,
		[this]()-> bool { return !spaceUpdateToRun.load(); }
	);
}

void GScene::spaceUpdateMain()
{
	while (!isExit)
	{
		unique_lock<mutex> mlock(spaceUpdateConditionMutex);
		spaceUpdateCondition.wait(
			mlock,
			[this]() -> bool { return isExit.load() || spaceUpdateToRun.load(); }
		);

		if (!isExit) {
			gspace->update();
			spaceUpdateToRun.store(false);
			spaceUpdateCondition.notify_one();
		}
	}
}

void GScene::update(float dt)
{	
	if (!isPaused) {
		ControlInfo info = App::control_register->getControlInfo();
		gspace->addObjectAction(bind(
			&GSpace::setControlInfo,
			gspace,
			info
		));

		if (App::multithread) {
			spaceUpdateToRun.store(true);
			spaceUpdateCondition.notify_one();
		}
		else {
			gspace->update();
		}

		runActions();
		checkPendingScript();
		runScriptUpdate();
		renderSpace();
	}
}

 

 

Static polymorpism

At some point, I wanted to implement objects that might or might load, rather than unconditionally creating every object in the tile map. The quick & dirty hack is to simply have objects that check if they should exist, and add themselves to the removal queue in their own init() if not. The better way is to provide an interface that can be used to determine if an object should be loaded.

I already have a reflection system, where I map the type-name of an object to a [function that wraps the] constructor that takes a map object and returns the created object:

//Adapters for mapping the name of a class to a factory adapter.
template <typename T>
constexpr GObject::AdapterType consAdapter()
{
	return [](GSpace* space, ObjectIDType id, const ValueMap& args) -> GObject* {
		return new T(space,id,args);
	};
}

template<typename T>
GObject::AdapterType conditionalLoadAdapter()
{
	return [=](GSpace* space, ObjectIDType id, const ValueMap& args) -> GObject* {
		if (!T::conditionalLoad(space, id, args) )
			return nullptr;
		else return new T(space, id, args);
	};
}

#define entry(name,cls) {name, consAdapter<cls>()}
//To make an entry where the name matches the class
#define entry_same(cls) entry(#cls, cls)
#define conditional_entry(name) {#name, conditionalLoadAdapter<name>()}

I implemented this before using SFINAE expressions & member detectors. At some point, I can refactor this to use SFINAE to check whether the class template parameter has a static conditionalLoad() method or not. But when conditionalLoadAdapter<Cls>() is instantiated, it creates a function that will call Cls::conditionalLoad with the map object, and decide statically if that object should be created.

SFINAE expressions & if constexpr – static inheritence with member detectors

In the game, I have Spell objects. It uses a polymorphic interface as you might expect. However, at some point I want to polymorphically get information about a spell before casting it (like its MP cost). This is easy enough in cases where code is checking if it can run a specific spell; that could static polymorphism just as the above case, except cost would be a static field instead of a method. But what if I want to represent a description of a spell as a polymorphic object, i.e. I want to be able to provide a spell descriptor as an parameter to an AI state, or in the case of player, I need equip slots and a set of the spells that are available to the player.

//(C++14)++ SFINAE expressions - the minimum amount of boilerplate requires to make a member detector.
#define make_static_member_detector(x) \
template<typename T> \
struct has_##x \
{ \
	template<typename U> \
	static auto test(int) -> decltype(U::x, true_type()); \
\
	template<typename> \
	static false_type test(...); \
	static constexpr bool value = is_same<decltype(test<T>(0)), true_type>::value; \
}; \

make_static_member_detector(cost)
make_static_member_detector(costType)
make_static_member_detector(icon)

class SpellDesc
{
public:
	virtual string getName() const = 0;
	virtual string getDescription() const = 0;
	virtual string getIcon() const = 0;

	virtual float getCost() const = 0;
	virtual SpellCostType getCostType() const = 0;

	virtual shared_ptr<Spell> generate(GObject* caster) = 0;
	virtual SpellGeneratorType getGenerator() = 0;
};

//Use CRTP to get static constants from Spell class.
template<class T>
class SpellDescImpl : public SpellDesc
{
public:
	virtual inline string getName() const { return T::name; }
	virtual inline string getDescription() const { return T::description; }

	virtual inline string getIcon() const {
		if constexpr(has_icon<T>::value)
			return T::icon;
		else
			return "";
	}

	virtual inline float getCost() const {
		if constexpr(has_cost<T>::value)
			return T::cost;
		else
			return 0.0f;
	}

	virtual inline SpellCostType getCostType() const {
		if constexpr(has_costType<T>::value)
			return T::costType;
		else
			return SpellCostType::none;
	}

	virtual inline shared_ptr<Spell> generate(GObject* caster){
		return make_shared<T>(caster);
	}

	virtual inline SpellGeneratorType getGenerator(){
		return make_spell_generator<T>();
	}
};

This is technically static polymorphism, except it uses template inheritence (similar to but not actually CRTP) to expose static polymorphism via regular (dynamic) polymorphic inheritence. i.e. SpellDesc is the virtual interface class, SpellDescImpl<PlayerBatMode>, SpellDescImpl<DarknessSignDemarcation>, etc. are the specific classes that implement the interface. All SpellDescImpl<SpellCls> does is make getter wrappers to the static const data from SpellCls and expose it as a virtual method. Since they simply wrap static const data, they are not mutable and only one needs to exist for each spell.

#define entry(name,cls) {name, createDesc<cls>()}
//To make an entry where the name matches the class
#define entry_same(cls) entry(#cls, cls)

template<typename T>
constexpr shared_ptr<SpellDesc> createDesc()
{
	return make_shared<SpellDescImpl<T>>();
}

const unordered_map<string, shared_ptr<SpellDesc>> Spell::spellDescriptors = {
	entry_same(DarknessSignDemarcation),
	entry_same(DarknessSignDemarcation2),
	entry_same(FireStarburst),
	entry_same(FlameFence),
	entry_same(IllusionDial),
	...
};

Curiously Recurring Template Pattern

The Agent class basically exclusively uses AttributeSystem. It provides an virtual interface that can be used for the object to provide it default attributes (max HP, agility, etc.). In the simple case, this is static const data and we can use CRTP static polymorphism to provide the attribute map regular polymorphism:

//in class Agent
virtual AttributeMap getBaseAttributes() const = 0;

//CRTP mixin
template<class T>
class BaseAttributes : virtual public Agent
{
public:
	inline BaseAttributes() {}

	inline virtual AttributeMap getBaseAttributes() const {
		return T::baseAttributes;
	}
};

class RedFairy : public Enemy, public BaseAttributes<RedFairy>
{
public:
	static const AttributeMap baseAttributes;
};

const AttributeMap RedFairy::baseAttributes = {
	{ Attribute::maxHP, 120.0f },
	{ Attribute::maxMP, 80.0f },
	{ Attribute::agility, 1.5f },
	...
};

RedFairy inherits from a template class that is templated with RedFairy. That is the definition of CRTP.

Now, what if I don’t want the agent’s starting attributes to be a class constant? Well, the simplest way to do that is to replace baseAttributes (an AttributeMap) with an unordered_map<string,AttributeMap>. In this case, we can created a number of named attribute set variations, and one can be specified in the map object.

template<class C>
class AttributesPackage : virtual public Agent
{
public:
	inline AttributesPackage(C* agent, const ValueMap& args) :
	agent(agent),
	attributes(C::baseAttributes)
	{
		string packageName = getStringOrDefault(args, "attributes_package", "");

		if (!packageName.empty())
		{
			auto it = C::attributePackages.find(packageName);
			if (it != C::attributePackages.end()) {
				attributes = it->second;
			}
		}
	}

	inline virtual AttributeMap getBaseAttributes() const {
		return attributes;
	}

protected:
	AttributeMap attributes;
	C* agent;
};

Out of an abundance of caution, it stores the AttributeMap by value. However, since attributePackages is presumed to be static const (maybe there should be a static_assert to verify), it should be able to store a const pointer to the AttributeMap instead. This is basically prototype code; I have used it to test different variations of enemy attributes, but have yet to particularly want enemies that have the same C++ class (and type_index) but different stats. And of course, all of this is just for convenience. Any Agent class can simply override getBaseAttributes() and procedurally generate its attributes. But if it doesn’t implement getBaseAttributes(), it is a virtual class that can’t be directly instantiated. There is also a convenience NoAttribute mixins that simply implements getBaseAttributes() by returning an empty AttributeMap.

boost library

boost::filesystem – Used for reading directories – neither the standard C++ library nor Cocos2D filesystem libraries have this. This allows the game engine to list all of the *.profile & *.replay files in the directory, instead of merely looking up specific files by name.

boost::archive/boost::serialize – used for File I/O. Both GState (savestate or persistent game state) and ControlReplay are plain-ol-data structs. ControlReplay of course has a variable size container, since there is no fixed length for a replay.

boost::assign – With (C++11)++ initializer lists, this is mostly obsolete. However, some boost data structures (boost::bimap) don’t support initializer lists (for static const data) and require boost::assign::map_list_of.

boost::functional::hash – C++ provides default hashing functionality for primitive, built-in types, but it doesn’t include a default std::hash for enums, or for pairs/tuples of types that do have a default hash. In GSpace, I want to map a pair of physics types (player,enemy), (player,enemyBullet), (playerBullet,wall), and so on to the corresponding function that handles it. The key in this unordered_map is a pair of enum class values. Thus, you must template the std::unordered_map with an appropriate hash function:

	typedef pair<GType, GType> collision_type;
	unordered_map<collision_type, int(GSpace::*)(GObject*, GObject*, cpArbiter*), boost::hash<collision_type>> beginContactHandlers;

boost::icl::interval_map – Used for HP sequence casting as well as damage sprites. In both cases, we want to map ranges of HP to a value, such as a sprite reprsenting a certain range of damage. Or the ID of the spell that should be active when a boss is at a certain HP. It uses a half-open (right-open) interval by default for floating point values. So, this allows for adjacent intervals (a boss that switches from one spell to another at a certain threshold), as well as points in between where there is no spellcasting. Technically, it supports overlapping intervals, and find returns an iterator that may give you multiple entries for overlapping intervals. The game engine doesn’t support an object casting multiple spells active at once, but it could have a number of different magic effects that were active at various HP intervals.

boost::format – Just like printf/sprintf/etc., except that it uses C++ strings instead. It is also templated. boost::format is not a variadic function (neither with C va_args nor (C++11)++ variadic templates); instead it returns an object that is like a stream object, that has the percent sign operator defined for combining it with the data going into the formatter. I wanted to replace the calls to cocos2d::log, which in turn uses printf and other things, to improve thread safety, but also to have an output log. cocos2d::log uses C va_args just like printf.

template<typename... T>
void log_print(string s, T... args)
{
	boost::format fmt(s);
	string result = boost::str((fmt % ... % forward<T>(args)));

	Director::getInstance()->logOutput(result);
}

I added Director::logOutput – it is mutex-protected and simply pushes the string into a buffer to be printed and logged during the next Director update().

As far as I know, there is only one printf feature that it lacks: the asterisk precision operator. In C formatted print, you may express the number of decimal places with a literal number value in the format string, or put an (*) and it will expect that as an additional argument before the next field.

printf("Cash balance: %.2f", balance);
printf("Cash balance: %.*f", balance, isWholeNumber(balance) ? 0 : 2);

I ended up wanting to basically do this, so that damage indicators in the game were printed as whole numbers when they were, otherwise with two decimal places. This either requires conditinally choosing a format string (preferable in this simple case), or using a format string to generate a format string to generate the actual output.

BTW, yes, I have seen Office Space: since 100 is not a power of two, cent values (other than .00, .25, .5, and .75) do not have an exact representation in floating-point numbers. And of course with a 22-bit mantissa, a float also has less than 0.01 precision if used to represent values over 2^15 or about 32k; it takes seven bits (128 values) to get at least two decimal digits of precision–in this case. In general, the better nmemomic is 10 bits (1024 values) is 3 decimal places.

(C++11)++ features – Variadic templates & type_index

Variadic template functions with parameter packs & variadic invoke

In App, I have a number of different setter methods that can be called to set a certain property, such as framerate or difficulty scale. The actual input (a line from config.txt) is merely a vector of tokens split by whitespace. The first token is the name of the directive, and the rest are the parameters for that directive (if applicable).

#define entry(x) { #x , makeInterfaceFunction(function(&App::x))}
#define entry2(s,x) { #s , makeInterfaceFunction(function(&App::x))}

const unordered_map<string, InterfaceFunction> App::interfaceFuntions = {
	entry2(framerate, setFramerate),
	entry2(fullscreen, setFullscreen),
	entry2(multithread, setMultithread),
	entry2(resolution, setResolution),
	entry2(vsync, setVsync),
	entry2(difficulty, setDifficulty),
	entry2(timers, setShowTimers),

	//Control register config commands
	{ "button", &App::assignButton },
	{ "key", &App::assignKey },
	entry2(clear_all_keys, clearAllKeys),
	entry2(clear_all_buttons, clearAllButtons),
	entry2(clear_button, clearButtonAction),
	entry2(clear_key, clearKeyAction),
	entry2(add_key_action, addKeyAction),
	entry2(add_button_action, addButtonAction),
	entry2(southpaw, setSouthpaw),
};

I want to map the string name of the directive (not necessarily the name of the method, but the string that I want to be recognized in the config file) to the function. Except, none of the App methods take a vector of strings. Thus, I need to write a variadic template adapter function; it is templated according to the parameters of the function it is going to invoke, and it will try to convert each token (assuming there are the right number of them) to the corresponding type. The Params (the variable number of template arguments corresponding to the type of each parameter to the function it is wrapping) can be done with C++11 variadic templates:

template<typename... T>
inline void callAdapter(function<void(T...)> static_method, vector<string> tokens)
{
	size_t n_args = tuple_size<tuple<T...>>::value;

	if (tokens.empty()) {
		log("callAdapter: empty input");
		return;
	}
	else if (tokens.size() - 1 != n_args) {
		log("callAdapter: %d arguments expected, %d found", n_args, tokens.size() - 1);
		return;
	}

	tuple<T...> args = parse<T...>(tokens, 1);
	variadic_call<void>(static_method, args);
}

inline void voidCallAdapter(function<void(void)> static_method, vector<string> tokens)
{
	static_method();
}

template<typename... T>
inline InterfaceFunction makeInterfaceFunction(function<void(T...)> static_method)
{
	if constexpr(tuple_size<tuple<T...>>::value > 0) {
		return [static_method](const vector<string>& tokens)->void {
			callAdapter(static_method, tokens);
		};
	}
	else {
		return [static_method](const vector<string>& tokens)->void {
			voidCallAdapter(static_method, tokens);
		};
	}
}

But the part that builds the tuple has to recurisvely concatenate the tuple one element at a time. This part still uses ol-fashioned SFINAE recursive templates:

template<typename T>
inline tuple<T> parse(const vector<string>& _v, int idx)
{
	return tuple<T>(boost::lexical_cast<T>(_v.at(idx)));
}

template <typename Crnt, typename Next, typename... Rest>
inline tuple<Crnt, Next, Rest...> parse(const vector<string>& _v, int idx)
{
	return tuple_cat(
		parse<Crnt>(_v, idx),
		parse<Next, Rest...>(_v, idx + 1)
	);
}

namespace boost {
	template<>
	inline bool lexical_cast(const string& s)
	{
		if (boost::iequals(s, "true") || s == "1") return true;
		else if (boost::iequals(s, "false") || s == "0") return false;
		else throw boost::bad_lexical_cast();
	}
}

 

type_index

At some point, I want to look up objects by type. For example, the map menu needs pointers to doors, floors, walls, enemies in order to get their position and other information that might be color-coded. These are polymorphic types, or at least for code maintainability I assume they might be. The natural way to maintain sets of objects by each type would be something like this:

unordered_map<type_index, unordered_set<GObject*>> objByType;

//on create/add
if (isTrackedType(typeid(*obj))) {
	objByType[typeid(*obj)].insert(obj);
}
//on destroy/remove
if (isTrackedType(typeid(*obj))) {
	objByType[typeid(*obj)].erase(obj);
}

We don’t need to check whether an unordered_set has already been created for the corresponding type_index, since on construction, GSpace initializes objByType for each type in trackedTypes (a static const vector<type_index>). We don’t need to track most environmental objects, and to reduce overhead we don’t need to track bullets either. However, I want BreakableWalls to show up when looking up type_index(typeid(Wall)). So, in this case, I also have to do a polymorphic check (dynamic_cast) for virtual types:

template<class C>
inline void addVirtualTrack(GObject* obj)
{
	if (dynamic_cast<C*>(obj)) {
		objByType[typeid(C)].insert(obj);
	}
}

template<class C>
inline void removeVirtualTrack(GObject* obj)
{
	if (dynamic_cast<C*>(obj)) {
		objByType[typeid(C)].erase(obj);
	}
}

addVirtualTrack<Enemy>(obj);
addVirtualTrack<FloorSegment>(obj);
addVirtualTrack<Wall>(obj);
addVirtualTrack<Door>(obj);

type_index is also used to calculate enemy defeated stats. We want to remember the number of enemies of each type that were statically placed in the tile map and were in the loading area at the beginning, as well as the number that can be dynamically spawned, and the number that have been defeated. When a RoomSensor loads an AI state that implements dynamically spawning enemies, it will register that with GSpace, which tells it the total number of enemies that can be defeated in a level.

unordered_map<type_index, unsigned int> initialObjectCount;
unordered_map<type_index, unsigned int> totalSpawnCount;
unordered_map<type_index, unsigned int> enemiesDefeated;

MultiSpawnSequence::MultiSpawnSequence(GSpace* space, const ValueMap& args)
{
	vector<type_index> types = getObjectVector<type_index>(args, &GObject::getTypeIndex, "type");
	vector<int> totalCounts = getObjectVector<int>(args, &boost::lexical_cast<int, string>, "totalCount");

	if (types.size() == totalCounts.size()) {
		vector<int> minCounts = getObjectVector<int>(
			args,
			&boost::lexical_cast<int, string>,
			"minCount",
			1,
			types.size(),
			0
		);
		vector<int> waveCounts = getObjectVector<int>(
			args,
			&boost::lexical_cast<int, string>,
			"waveCount",
			1,
			types.size(),
			1
		);

		for_irange(i, 0, types.size()) {
			spawnEntries.push_back(sequence_entry{
				types.at(i),
				minCounts.at(i),
				waveCounts.at(i),
				totalCounts.at(i)
			});
			space->increaseSpawnTotal(types.at(i), totalCounts.at(i));
			totalSpawns.insert_or_assign(types.at(i), 0);
		}
	}
}