Super Mario Brothers in 2.5D

Introduction

A year or so ago I wrote a 2.5D Super Mario Brothers game in Unity 3D.  This has been done by countless developers who are inspired to recreate legendary games in a fun environment.  I did it for just that reason, fun.  I of course had grandiose plans to develop it as many different games.  Level 1 would be Mario, level 2 would be Mega Man, level 3 something else, etc.  Of course, as life always does, bigger things came up that I decided to work on.SMB1

Features

The game featured the following components of the original title:

  • Jumping and bonking of ? blocks
  • Squish-able Goombas
  • Stompable and kickable turtles
  • Mushrooms and Fire Flowers
  • Fireballs

Development

This process went smoothly, and horribly.

What Went Right

Much of the project came along smoothly.  The first thing I needed to do was create prefabs to duplicate around the level based on some data.  Then I needed to supply that data.  Doing some quick searches on map images turned up a great website resource such as Mario Brothers Maps.  This had pixel perfect maps, including showing where item blocks are, enemies, and more.

I took these images, ensured their pixels lined up in 16×16 increments and pulled out all the unique tiles.  From here I wrote a C++ tool to grab each 16×16 block of pixels, matched the block to a tile, gave it a UID and saved the results to file.

Then I updated the Unity 3D app to load in the appropriate prefab in the world location of each UID found in the level.  This generated the level, let me place enemies and let me tag prefab tiles as ? blocks.  Piece of cake.

It was fun seeing this as well.  Old-school levels, levels I adored as a kid seen for my first time in full 2.5D.  Mario Brothers, Mega Man, I tried a few levels of each and was nothing but excited by the results.

Next up was getting the enemies to move around, no problem here.  Squishing the Goomba’s was fun and rewarding, getting the turtles working was easy and the fireballs were a quick few minutes of work.

What Went Wrong

As always.  Collision.  I hate collision.  Floating point errors, bad math on my part, poor approaches, these have always plagued my collision detection and most of all, collision handling implementations.  One of these days I’ll set out to make it really work, but until then, I’ll continue to let engines implement it for me.  Too bad Unity 3D doesn’t do that.  They have 2 collision tools, character controller style capsules and rigid bodies.  Capsules slide off edges, bad for 2D side scrollers.  Rigid bodies are problematic to get working for actual movement of characters as they tend to prevent movement when on the ground, bounce poorly (especially in Unity) and don’t provide the custom support for jumping that Mario requires.  My own implementation did end up working, but it was re-written 4 times and I was never very happy with the results.  I don’t like saying that I couldn’t get it to work, but to be fair, I don’t exactly put my best foot forward when working on home projects.  I wasn’t super excited about making the collision perfect, I had other motivations.  Good enough is good enough for this project.

Results

In the end I had simple bonking of Goomba’s, fireballs killing Goomba’s, turtles being stomped and powerups.  This was enough to satisfy my interest in the project.  It was fun, worth the time, but far from educational from a gameplay perspective.  In terms of learning Unity 3D, it was educational and one of my deeper dives into Unity.

Here’s some more pictures you can enjoy!

SMB3

SMB2

SMB4

Magic the Gathering Card Cataloger

History

Several years ago while at Warner Brothers/Monolith I joined the MTG league that started up there.  Every new set that was released was accompanied by a 10 booster pack tournament, starting with 6 and opening 1 new pack every other week for 8 weeks total.  It was a ton of fun, and reintroduced my love for MTG.  I started buying up large swaths of cards from co-workers and ended up with a collection of over 10,000 cards.  I wanted to be able to build decks out of these cards without having to constantly go through them to find the cards I wanted.  While I had them sorted, it was still very time consuming to track the cards down.

Solution

So, I wrote a MTG card cataloger.  I wrote it in MFC, as I hadn’t used it much.  WB used it for some of their tools and I wanted to better understand it.  I learned what I didn’t like about it, or at least, what I did with it that made it a pain to use.  Adding new dialog boxes required about 10 minutes of copy/pasting of code to hook everything up.  Really fun stuff…

In the end I had a great tool with the following features:

  1. I can add new cards, including all of their data such as name, casting cost, power/toughness, abilities, type, subtype, some general themes (destroy creature, add mana, counter spell, draw card, etc) and more.
  2. I can edit existing cards.
  3. I can create a new collection of cards and add cards from my collection to it, including foils.
  4. I can browse a collection of cards.  This also shows how many of each card I have, and how many total in a particular set.
  5. I can create and edit decks that I build cards from.  This has even more features:
    1. A filter system to allow me to narrow down search results by color, type, ability, name, and more.
    2. A filter results area that shows all the resulting cards.  This includes a button to add this to my cards to consider for the deck.
    3. An area with cards I’m consider for the deck.  This includes a button to add cards to either the sideboard, or the deck itself.
    4. An area showing the cards in the deck and another area for the sideboard.
    5. An area that shows the total casting cost per color of the cards in the deck, the average per color and the total average.
    6. Each of the above areas show how many cards there are in total in each area.
    7. Finally, buttons to flag standard deck rules or EDH, allowing the system to apply those rules to what cards you can put in your deck (banned cards aren’t there).

Results

CardView

DeckView

I heavily used this tool.  I loved it.  I added thousands of cards.  While I had to download the images for each, that never took more than 10 minutes.  Adding each set of cards was roughly an hour of work and adding the cards from an entire booster box was about an hour as well.  I’ve created more than a dozen EDH decks from it, and building those decks from my actual catalog is quick and painless.  It’s easy to find the cards I want in the boxes as I know how I sorted the boxes.  This tool may not have paid off in terms of time, but I really enjoyed developing it and using it.

Additional Work

Online Editor

After developing it I used it as a tool to learn web development.  I implemented a very simple version of a card editor that allowed me to add new cards and edit cards.  I write it in PHP and Javascript, leveraging SQL queries for the data.  I didn’t take this too far, but it was a useful introduction to web development.

Web Tool

I developed another quick tool that ran SQL queries on an XML catalog that I uploaded.  This catalog contained how many of each card I owned.  I could pull up my phone, hit the website, type in a card name and it would kick me the total count.  I found this really useful when doing trades with other MTG players and verifying that I don’t already have a particular card that I’m interested in.

The catalog was generated with console prints from my MFC tool.  I would copy paste the prints into the XML file and upload the file to the server.  There’s better solutions to this, but I didn’t need to do this very often, so this quick solution worked well for me.

C# App

I also developed it in C# as a better way to understand C# outside of Unity 3D.  This introduced me to WinForms and WPF, though at this point I don’t recall which one I ended up with.  I found the graphic user interface one to be very difficult to use and having separate sheets/pages to be error prone as hell.  I spent far more time trying to get the GUI tool to work right than I did actually writing code.

However, I only wrote the part of the tool that lets me browse cards and browse a catalog.  With this I wanted to know how much my collection was worth.  So, I hooked into C#’s interfaces to call into websites.  I found that my favorite website, magic.tcgplayer.com had a very convenient URL path for each card, that worked flawlessly with my format.  My cards were numbered the same way, named the same, etc.  From here I got the resulting HTML in a string, searched through it for the value tags and accumulated the results, saving the data with the catalog file so I don’t have to re-query the website every time.  Querying the website for my entire collection of cards took somewhere around an hour.  Hope they didn’t mind the extra traffic!  🙂

Takeaways

I had fun on this.  Lots of fun.  I had a direct goal in mind and I wanted nothing more than to achieve it.  This goal provided me with a rich tool that lets me keep track of my cards.  I learned MFC, HTML, Javascript, PHP and more C#.  I call that a win.

AI Spatial Awareness with Projected Volumes

Introduction

For part two of my spatial awareness prototyping I’ll present my solution to Problem #3 of the previous solution.  The previous solution can be found here:  AI Spatial Awareness with Renderable View.

Motivation

The previous solution had a few drawbacks, one of which was the lack of precision with edges of objects such as buildings along with it’s greatly stretched quads for objects near the ground.  I greatly disliked how this looked and sought to find a solution that would solve this.  This solution solves the problem with precision by providing detection of exact edges in geometry based on the desired resolution.

High Concept

Remembering back to my days of graphics rendering I realized projected volumes, such as shadow volumes were a great solution to this.  Using the shadow volume example, any area that is in shadow is hidden from the enemies view and any area that is “lit up” is in view.  It’s that simple.

Algorithm

As always, I love pretty pictures.  So lets go with that first.

SV1

This is an image showing the edges of the polygons from the sources viewpoint.  The white lines represent the detected edges, the green lines represent the normals of the planes that are generated by these lines and finally the blue boxes show what edges intersect with the ground.

A zoomed out picture of this isn’t very interesting without some clipping of the planes, which I have not done.  However, the end result is that an object has a volume extending along behind it.  Points inside this volume are hidden from view and points outside it are in view.

Did not do an exhaustive implementation of this algorithm, nor did I follow proper projected volume techniques, however I will detail what I have done, and my plans for it’s future.

  1. Pre-cache the neighbors of each triangle in the scene.
  2. Set our “camera” to the position of the object who is looking into the world (who our AI will try to hide from).
  3. Go through each object in the scene and each triangle on the object.
  4. If the triangle is forward facing, then check each neighbor.
  5. If the neighbor is backwards facing, create an edge.
  6. Go through each edge and generate a plane from it using the edge normal relative to the “camera” position.
  7. Store the resulting planes for each object in it’s own list.  This allows future convex or non-convex (depending upon your object) tests to be ran against them.
  8. Edges that intersect with the ground do not need planes extending beyond them.
  9. Finally, each forward facing triangle is turned into a plane.  This generates the front facing hull.  There is no need for a backfacing hull.

This provides us with projected volumes.  Any object who is enclosed entirely in the volume is fully hidden from view.  If an object is intersecting with a plane, then the part of the object that is outside of the plane (on the side that the normal points towards) is exposed.

Future work

To complete this prototype, code would need to be added to determine if a point or a shape is in view, hidden from view, or partially in view.  This can be solved with plane tests on the input object.  If the object is convex, such as a triangle, box or circular polygonal object, the solution is simple.  A point would be tested against the dot product with the normal of each plane.  If each returns a negative number, the point is fully hidden.  Doing this for a shape requires additional math that can be found with a simple google search.  Arbitrary shapes quickly become complex, so I would recommend simplifying it to at a minimum, a bounding sphere.

Solving this for the general case volume is a bigger challenge.  I have not researched this, however the issue that I’m presenting is non-convex objects, such as a torus, an L shaped object, bridges, etc.  To determine if an object is inside the non-convex object is more challenging and would need to be researched.  However, an approach that could help with this would be to break the object down into convex hulls.  This will increase the number of planes generated by the algorithm, but would greatly simplify the vision calculation by reducing it to a few dot products.  Hierarchical Approximate Convex Decomposition (HACD) is a great option for generating these convex hulls and would be worth evaluating.

Pathfinding

This solution works well for grid or node based pathfinding solutions.  Each grid could be considered a box or a center position and be tested for visibility.  A node based solution is typically done with points which is the same simple implementation.

Nav meshes are a bit more tricky.  Often pathfinders across nav meshes use the edges of the nav mesh to pathfind rather than the centers.  However, both solutions have the problem that some areas of the polygon may be visible while other parts of it are not.  An option that could work would be to determine how much of the polygon/edge is visible and consider the entire polygon/edge hidden for pathfinding purposes based on a threshold.  Another alternative is to split up a polygon/edge into multiple pieces if it’s found to be partially visible and partially obscured.  From here the resulting connection to other polygons/edges would determine how visible that connection is.  This is then factored into the cost of pathfinding along that connection.

Performance

Projected volumes are expensive to calculate.  If they prove to be too expensive to calculate on the CPU then the GPU is a great alternative.  When generating the volumes, it’s recommended that you use lower resolution geometry.  This however will decrease accuracy and create false positives for the AI.  If that becomes a problem then this can be solved by extruding out the geometry to fill in these gaps at modelling time or runtime or to simply require each evaluated point to be a certain distance behind each plane.

While I haven’t explicitly evaluated it, I would recommend convex hulls over non-convex hulls.  This should be researched if you intend to use this approach.  By storing each plane with it’s corresponding object, we can guarantee convexity.

Another consideration is that when testing if a point is hidden from view, there is no need to test against each object and each plane.  A quick dot product can be ran against the location of each object and only objects that are within a tolerance would be used.  It would be valuable to store the angle to the object relative to the “camera” position’s “look vector” and then the maximum angle that any of it’s planes generate relative to the “camera” position.  This will provide you a cone with the max angle that a point can be relative to the object and allow quick rejection.  An alternative is to create a low resolution set of 4 planes to enclose the entire object if the object has enough planes to warrant it.  As always, performance evaluation of this is prudent.

If the “camera” position is stationary, then this data can be calculated once at tool time or level load time and will never need to be calculated again.  If the “camera” position is not fast moving, then the edges used to generate the planes can be cached with each plane and only those edges need to be updated each frame (or less often for edges that are far away – based on angle).  If an edge was used and becomes invalid, then neighbor edges to the original edges triangles would need to be reconsidered.  Edges that are not in the current set of planes could be reconsidered less often, based on how far the “camera” position moves relative to the object.

In Conclusion

I’m quite happy with this solution to spatial awareness.  It provides as much accuracy as desired through the use of geometry resolution.  View lookups can be performed quickly for convex objects.  Performance may be a drawback, however this can be remedied with some caching concepts presented above.  This is definitely a solution that would be interesting to pull into a large scale game to evaluate.

AI Spatial Awareness with Renderable View

Introduction

Some time ago I began research on AI spatial awareness.  I was saddened to see a dramatic lack of information on the topic.  Generally spatial awareness was solved with influence maps or other fairly rudimentary solutions.  None of these really gave the AI the ability to know where they can safely hide from an enemy and where they can stand in order to peek out and fire at an enemy.  I will present two of the initial solutions I implemented in two separate articles.

Motivation

The influence behind this research was the desire for AI objects in a 3D world to have the ability to dynamically find cover that will provide them safety from an enemy target while providing them a quick and easy “peek and shoot” location.  Leveraging pre-placed cover locations wasn’t something I was interested in.  Games in today’s market demand greater immersion and more realistic, robust and emergent gameplay.

High Concept

My first article will present the first possible solution I considered to this problem.  It uses GPGPU shaders to perform view space calculations on the scene from the perspective of the enemy AI object towards the AI seeking to find cover.  The high concept is that the enemy AI will render the scene from it’s point of view, we will then calculate ground positions, normals, etc for each corner of every pixel and map the resulting valid quads to 3D geometry which will be read back in by the game.  This geometry would overlay on the pathfinding system to define “unsafe” areas for the AI to move to.  With this, the AI knows exactly where it can go to be safe, and it can determine an “unsafe” edge that it can stay close to in order to do “peek and shoot” behaviors. Sound interesting?  Lets dive into the details.

Algorithm

First off, lets see a pretty picture.  I like pretty pictures.  Below you will see an image of the final results.  The red boxes represent the 3D quads, the white lines represent the quad normals and the blue lines represent the pixels corners that did not generate valid quads.  Finally, the capsule in the lower left represents the enemy looking into the scene.  This enemy, for reference is well above the ground. Image The solution that I implemented in Unity 3D was a software rasterizer that is able to quickly prototype this idea and easily display any pieces of information I need to.  Extending this to the GPGPU’s would be trivial enough.  Here are the steps for the software rasterizer.

  1. Generate a 2D array of a desired resolution, the higher the resolution, the smaller and more accurate the final results will be.
  2. For each index in our array, cast a ray from the enemy position along it’s look direction offset by the field of view and our current screen space x/y.  It isn’t necessary to cast out for each corner as this becomes redundant with the next pixels corners.  This data can be merged, but for my implementation this offset by a half pixel is not a concern.
  3. Take the resulting collision information and cache the normal and position.  In addition to this the face of the object hit will need to be recorded and compared to neighboring pixels to ensure that it resides on the same object.  If it doesn’t, additional calculations may need to be performed.
  4. To generate the quads we determine if each array indices 3 neighbors (those that compose of our quad) have a relatively similar normal and have intersection positions that are relatively close to the average of the corner locations.  If a corner is too far away, it’s possible it is on another object, or perhaps on the ground behind an object.  If a corner has a very different normal, then it may be on a wall.
  5. From here we have a quick and dirty version of world space quads for pathfinding.

Here is an image to show the rays being cast: ImageThis solution gives us a great pathfinding benefit.  Pathfinding queries can use these quads to increase the weight of pathing through the navmesh.  Due to the increased weight, AI will prefer not to follow a path that overlaps a quad.  This allows them to know spatially, and in a 3D world where they can and cannot move to remain safe from an enemy target.

GPGPU Algorithm To expand upon this, my thoughts on the required steps for a GPGPU solution are as follows:

  1. Setup a render target for the enemy.
  2. Set the camera to the enemy, point it towards the AI who requires this query to be run.
  3. Render the scene to the render target with as few render objects as necessary.
  4. For each pixel, either use the center of the pixel or each corner, noting that each corner will need to cache it’s results for the next pixel if that solution is used.
  5. Take the depth information in that pixel and convert it to a 3D position.  This should be easy enough to calculate given the camera matrix.  I’ll leave that as an exercise for the reader.
  6. Generate quads from the results on a per pixel basis.  Optionally you can merge quads as needed to create a minimal set of geometry.
  7. Game code will read this geometry off the graphics card, overlay it over the pathfinding solution and apply weights to the data.  If this pathfinding solution is a nav grid, then simply determine which path nodes are inside the geometry (2D math on this for a world where Y is up will be close enough) and update the weight on each of those nodes.  Low density nav grids have precision issues that will need to be considered.  If the solution uses a nav map then the solution requires additional processing to cut up the nav geometry dynamically.  This may be too performance intensive but there may be other solutions, such as leveraging two nav maps instead.

Problems

My solution has three key problems that I will detail below.  I have not vetted these first two problems in a final implementation and do not intend to pursue them at this time.  The third problem I address in my second article through an alternative implementation.

Problem #1

The end results depend heavily on resolution and the location in the world of the enemy.  In the first picture above, the resolution is fairly low, but the enemy is fairly high in the air.  In the below image, the enemy is low to the ground and the resolution is low.  Notice the distinct lack of precision in the left most quad.  Also notice that the quad that attempted to be generated to it’s left wasn’t generated, but that the area to the left of the left-most quad is considered “safe” to the AI when in fact it’s not. Also notice that the precision is very high close to the enemy, yet very low as you get farther away.  When the enemy is close to the ground it emphasizes this problem, but when the enemy is high in the air, this problem largely goes away as you see in the first image in the article.Image To address the above issue, the GPGPU shader will be required to determine where the edge of the valid part of a given quad is.  In the above case, the quad to the left of the leftmost quad will determine that the right two vertices are valid, and the left two are on the wall.  It will need to find the cutoff of where the wall starts, and the plane defining the wall.  This could be generalized with a binary search of raycasts which may perform well enough and give good enough results.  The resulting corners would be used instead of the ones on the wall.

Problem #2

The second problem also that of precision.  If an object is small enough to fit inside of a pixel, it could be missed.  If that pixel covers a screen space that is too large (i.e., the AI object can fit entirely inside of it), then the AI may not find cover in that location that could otherwise be valid.  This problem is easy to solve, increase the resolution of the render target, or perform raycasts into the world on a per pixel basis in order to find these objects.

Problem #3

Another problem is that the AI does not have hard edges of things that it knows are or are not safe.  The AI has to use the resulting path map to determine where it can move.  This may make it hard for the AI to easily find a location to peek out from to shoot.  While this is not a big issue, I found it less desirable.  My second article on this will present a solution to that problem by implementing a different form of spacial awareness.

Render Target Resolution and Performance

The resolution of the render target is another important thing to consider.  It is necessary for an object close to the ground to use a tall render target, perhaps 64×256 in order to get pretty good results.  If the above quad splitting solution is too expensive, then perhaps a lower resolution would be better and get good enough results.  An object that is higher off the ground can leverage a slightly more square render target. Another performance consideration would be to ignore quads who’s vertices are fairly close to each other.  There’s no reason to split a quad who’s normal’s are on the ground and the wall if the total size of the object is smaller than the diameter of the AI object.

Another pretty picture.  This one shows higher resolution image of the previous image in the article.  The previous image was 40×25 and this one is 70×150.  Notice the increased precision along the forward and along the left/right axis from the enemy. Image The super high precision at the bottom of the image is unfortunate.  However, it’s possible that this could be reduced by clamping the vertical FOV to a number that makes the initial quads be farther out into the world.

In Conclusion

I am relatively happy with the results that this solution provided.  The flaws that it has are solvable, however performance is my biggest concern.  I like that this solution generates ground quads that can easily be overlayed onto a pathfinding solution, in particular a node map. Please feel free to comment with your thoughts on the solution and any alternative ideas you have that could add to this solution or spatial awareness in general.

Data Tracking Architecture

At a previous company I wrote a data tracking system that was used to track statistics on players, design tuning values and player profile progression for in-game challenges and achievements. This system needed to track a large permutation of data, up to 50,000 unique pieces of data. This presented a fun set of challenges to solve ranging from the cost of updating a piece of data, accessing a piece of data, in-memory overhead, serialization, uploading to a server and finally, code structure to allow ease of use and maintenance.

I solved all but one of these while implementing and maintaining this system over a period of 2 or 3 months. The one that I didn’t solve on the job was the code structure. I left that task as any programmer would in this situation, unhappy. I went home with the lessons learned and re-wrote it myself. I felt good enough about my solution to present it here. Please note that this is not final code. I’ve abandoned my work on it, but there is much that can be added to it and a few minor details to work out. Those are noted below.

Please do give your thoughts on this!

First off I present a quick layout of the original architecture for reference and to explain what it was that caused me problems. From here I’ll explain how I went about solving this.

enum EStatEvent
{
	kDeath,
	kKill,
	kLevelUp,
};

class CStats
{
private:
	vector<CCharacter>	m_vCharacters;
};

class CCharacter
{
	CCharacter() : m_nID(0), m_nLevel(0), m_nKills(0), m_nTimesPlayed(0) {}

	CCharacter(CCharacter& character)
	{
		m_nID = character.m_nID;
		m_nLevel = character.m_nLevel;
		m_nKills = character.m_nKills;
		m_nTimesPlayed = character.m_nTimesPlayed;
		...
	}

	CCharacter& operator = (const CCharacter &character) {
		m_nID = character.m_nID;
		m_nLevel = character.m_nLevel;
		m_nKills = character.m_nKills;
		m_nTimesPlayed = character.m_nTimesPlayed;
		...
		return *this;
	}

	void OnEvent(EStatEvent eEvent, CStatParams *pParams)
	{
		switch(eEvent)
		{
		case EStatEvent.kDeath:
			//  Increment our m_vDeathsFrom
			break;
		case EStatEvent.kLevelUp:
			++m_nLevel;
			break;
		...
		}
	}

	void OnSave(Stream stream)
	{
		stream.WriteUINT("ID", m_nID);
		stream.WriteUINT("Level", m_nLevel);
		stream.WriteUINT("Kills", m_nKills);
		stream.WriteUINT("TimesPlayed", m_nTimesPlayed);
	}

	void OnLoad(Stream stream)
	{
		...
	}

	void UploadToServer(Packet packet)
	{
		...
	}

	void GetValue()
	{
		...
	}

	void DebugPrint()
	{
		...
	}

private:
	UINT				m_nID;
	UINT				m_nLevel;
	UINT				m_nKills;
	UINT				m_nTimesPlayed;
	vector<CCharacter>		m_vDeathsFrom;
	vector<CWeapon>			m_vWeapons;
};

class CWeapon
{
private:
	UINT			m_nID;
	float			m_nTotalDamage;
	UINT			m_nKills;
}

The above architectures goal was to track data about each character the player played, each weapon they used, how many kills they got as that character, how many kills they got with each weapon, how many times they died from each character, etc. This provided the ability for design to watch a players progression over time, through each level and see if they stop playing and if so, when or why it was. They can perform statistical analysis on the data to determine if certain characters are too strong or too weak and how updates to the game data effect these statistics.

The problem I ran into was adding a new stat. In our code base this required adding that stat to about 11 different functions. The constructor, copy constructor, equals operator, Load(), Save(), OnEvent(), DebugPrint(), Upload(), Download(), Get() and several more. This was a pain in the ass. If I missed a single function I would have a bug that I wouldn’t hear about until a week later. My workflow to add a single value was to update each function and then test each function in order to ensure that it worked properly. This was about a 30 minute process. When we added well over 100 variables (and changed half of them before we shipped), this was a lot of wasted time.

Why not have the variables do all this work themselves? I wish I’d thought of that before!

That’s what I set out to fix.

First off I considered an alternative implementation and some alternatives on it. I summarized it with its benefits and drawbacks. Notice I only have 1 alternative. After some thought, this was all I came up with and if at the time I’d considered others, the tree plan caught my attention the most.

My above implementation:

  • Benefits: Easy to debug, easy to visualize
  • Drawbacks: Game specific, hard-coded, hard to maintain

A tree structure:

  • Benefits: Flexible, dynamic at run-time, less code, less buggy, custom generated types
  • Drawbacks: Hard to debug, tricky code, more custom classes

I then considered a variety of options for the leaves and parent nodes. This factored in leaves being individual stats and class leaves being the “leaf” level of a class itself. Then I had to consider how to add stats. This could be done with run-time pushes, data driven (load time) or at compile time. Then event handling was considered with direct access or events. Events could be solved with leaves registering themselves directly for the event, or each class simply passing it along until it’s consumed. Then I needed to determine which stat to update from an event. An event, such as a kill event needs to know who died, who killed them, what weapon was used, etc. Each piece of data that cares about this needs to know to be updated. This could be solved with a params structure, UID’s or custom callbacks. There’s even more to consider but you get the picture.

The key things I wanted to solve were:

  • Minimize code updates when adding a new stat.
  • Prevent game specific class hierarchies, allowing this to be a core system games build on top of.

I didn’t personally care to solve for data driven stats vs. hard-coded stats, so I chose hard-coded stats. A compile time structure vs. a run-time structure was also not important. Either solution was just fine with me. As it turns out, my implementation supports data driven stat hierarchies as well.

Here’s what I implemented. Again note that this is sample code, it’s far from complete functionality and has flaws here and there. The goal is to present the high level concept of the architecture.

Engine level header file:

enum EStatEvent
{
	eStatEvent_Invalid,
	eStatEvent_EngineSpecificEnum,
	eStatEvent_Count,
};

class CStatParams
{
public:
	CStatParams();
	virtual ~CStatParams()

	int	m_nInt;		//  Sample required param
	float	m_fFloat;	//  Sample required param
	UINT	m_nUID;		//  For array indexing
};

//  Base class for a stat
class CStatBase
{
public:
	CStatBase();
	CStatBase(const char* pName, EStatEvent eStatEvent);
	virtual ~CStatBase();

	virtual void OnEvent( EStatEvent eEvent, CStatParams* pParams ) = 0;

protected:
	const char*	m_pName;
	EStatEvent	m_eEvent;
};

//  Implementation of a built in data type for int.
class CStatInt : public CStatBase
{
public:
	CStatInt();
	CStatInt(const char* pName, EStatEvent eStatEvent, int nDefaultValue=0);

	virtual void OnEvent( EStatEvent eEvent, CStatParams* pParams ) {
		if( m_eEvent == eEvent ) {
			m_nData += pParams ? pParams->m_nInt : 1;
		}
	}

private:
	int		m_nData;
};

//  Implementation of an array stat
template  class CStatArray : public CStatBase {
public:
	CStatArray() : m_nArraySize(nArraySize) {}
	CStatArray(const char* pName, EStatEvent eStatEvent)
		: CStatBase(pName, eStatEvent)
		, m_nArraySize(nArraySize)
	{
		for( UINT i = 0; i < nArraySize; ++i ) {
			m_nArray[i] = T("", eStatEvent);
		}
	}

	virtual void OnEvent( EStatEvent eEvent, CStatParams* pParams ) {
		if( m_eEvent == eEvent ) {
			//  NOTE:  Could use a validation callback instead of m_nUID
			if(    pParams
				&& pParams->m_nUID < m_nArraySize )
			{
				m_nArray[pParams->m_nUID].OnEvent(eEvent, pParams);
			}
		}
	}

private:
	T	m_nArray[nArraySize];
	UINT	m_nArraySize;
};

//  The base class representing a collection of related stats
class CStatClass : public CStatBase {
public:
	CStatClass(const char* pName);
	~CStatClass() {
		for( UINT i = 0; i < m_vStats.size(); ++i ) {
			if( m_vStats[i] ) {
				delete m_vStats[i];
				m_vStats[i] = NULL;
			}
		}
		m_vStats.clear();
	}

	bool AddStat( CStatBase* pStat ) {
		if( !pStat ) {
			return false;
		}
		m_vStats.push_back( pStat );
		return true;
	}

	virtual void OnEvent( EStatEvent eEvent, CStatParams* pParams ) {
		for( UINT i = 0; i < m_vStats.size(); ++i ) {
			m_vStats[i]->OnEvent(eEvent, pParams);
		}
	}

private:
	vector<CStatBase*>	m_vStats;	//  All the stats contained in this class
};

//  The root stats class.  Clients store one of these.
//  It contains all stats in a tree structure.
class CStats {
public:
	CStats() : m_pStats(NULL) {}
	~CStats() { delete m_pStats; m_pStats = NULL; }

	void Init( CStatClass* pRoot ) {
		m_pStats = pRoot;
	}

	bool AddStat( CStatBase* pStat, CStatClass* pParent ) {
		if( !pParent ) {
			return false;
		}

		return pParent->AddStat( pStat );
	}

	void OnEvent( EStatEvent eEvent, CStatParams* params ) {
		if( !m_pStats ) {
			return;
		}

		m_pStats->OnEvent(eEvent, params);
	}

private:
	CStatClass*	m_pStats;
};

In the above implementation I have a core CStats class which clients use as their entryway to the stats system. This class has a single CStatClass class inside of it which holds the root of the stats tree. The interface for adding a new class or adding a new stat to a particular class is clean and easy to use. CStatBase is the base class/interface for all the stats. It contains pure virtual functions for all the functions we want implemented such as Load(), Save(), OnEvent(), etc. CStatClass contains each stat which could be anything from another stat class to a specific data value or an array. Specific data values simply derive off of CStatBase, such as CStatInt. These derived classes simply implement the specific functions for the data type they define. Along with this, the system will need a validation function to ensure that a value that is passed in is the correct one to update a specific stat with. This could be a UID comparison, but it could also be a callback that does game specific work. That has been omitted from the above code.

Now here’s how a client uses this system.

Client level header file:

enum EGameStatEvent
{
	eStatEvent_Kill = EStatEvent::eStatEvent_Count,
	eStatEvent_Death,
	...
};

//  Custom client kill params
class CKillParams : public CStatParams
{
public:
	CKillParams() : CStatParams() {
		m_nKillerID = INVALID_INDEX;
		m_nVictimID = INVALID_INDEX;
	}
	CKillParams(UINT nKillerID, UINT nVictimID) : CStatParams() {
		m_nKillerID = nUINT;
		m_nVictimID = nUINT;
	}

	UINT m_nKillerID;
	UINT m_nVictimID;
};

//  Custom client data type (ignore that killer ID
//  updates m_nData, it's just an example!)
class CStatUINT : public CStatBase
{
public:
	CStatUINT() : m_nData(0) {}
	CStatUINT(const char* pName, EStatEvent eStatEvent, UINT nDefaultValue=0)
		: CStatBase(pName, eStatEvent)
		, m_nData(0)
	{
	}

	virtual void OnEvent( EStatEvent eEvent, CStatParams* pParams ) {
		CKillParams *pKillParams = dynamic_cast<CKillParams*> (pParams);
		if( m_eEvent == eEvent ) {
			m_nData += pKillParams ? pKillParams->m_nKillerID : 1;
		}
	}

private:
	UINT	m_nData;
};

//  Custom client stat classes for “game mode” data and “root” data
class CStatGameMode : public CStatClass {
public:
	CStatGameMode(const char* pName) : CStatClass(pName) { }
	~CStatGameMode();
};

class CStatRoot : public CStatClass {
public:
	CStatRoot(const char* pName) : CStatClass(pName) { }
	~CStatRoot();
};

//  Some client game class that tracks the stats
class CClientGame {
	...
	CStats		m_Stats;
}

 

Notice how the client of the system defines an “extension” enum. This is my least favorite part as C++ doesn’t provide a way to extend a lower level systems enum. More on this below. The client can create custom params classes to handle things like kill events which would contain data such as who the killer was, who was killed, what weapon was used, etc. The client can define its own stat types, such as my example of the UINT. The client can additionally define their own game specific stat classes. Finally, all that’s needed is an instance of the CStats class somewhere in the code base.

Client level source file:

void CClientGame::AllocateStats() {
	CStatRoot* pRoot = new CStatRoot("root");
	m_Stats.Init( pRoot );
	{
		CStatMode* pMode = new CStatMode("create");
		m_Stats.AddStat( pMode, pRoot );
		{
			// Adding an array, float and UINT stat
			CStatArray<CStatInt, 10>* pIntArray = new CStatArray<CStatInt, 10="">("Sample Int Array", eStatEvent_Kill);
			m_Stats.AddStat( pIntArray, pMode );

			CStatFloat* pFloat = new CStatFloat("Sample Float", eStatEvent_Death);
			m_Stats.AddStat( pFloat, pMode );

			CStatUINT* pUINT = new CStatUINT("Sample UINT", (EStatEvent)eStatEvent_Kill);
			m_Stats.AddStat( pUINT, pMode );
		}
	}
}

void CClientGame::StatTestFunction() {
	CKillParams params(1);
	params.m_nUID = 3;	// This will access pIntArray[3]
	params.m_fFloat = 1.3f;
	m_Stats.OnEvent( eStatEvent_Death, &params );

	CKillParams params2(1);
	m_Stats.OnEvent( (EStatEvent)eStatEvent_Kill, &params2 );
}

 

Now for the final bits of the implementation. Above you will see that we define the structure of the stats system dynamically in code. It’s hard-coded sure, but this could be data driven or extended at run-time. This defines the tree structure of the stats system itself.

Issues with this implementation:

Back to my least favorite part of this. The enum. This is quite upsetting. C++ seems really limited here. I wanted to use enums as they provide type safety and a clear name to prevent bugs. If I defined an enum in a game level header file, I could easily extend it with another game level header file using some #include magic. However, with an engine level file, I don’t see a good way to do this. I could have it look for a required header file in a higher level folder, but this doesn’t allow the clients to have the convenience of placing this file where they want. Any recommendations or thoughts on this are appreciated!

My current implementation causes a few problems. It requires users to cast from their game enum to the lower level enum at the call-site. This is far from ideal. This also may cause an implicit cast to an int, though I’m uncertain without scrutinizing the code further. What I like least of all is that when viewing the stat’s event enum in the debugger, it will show “eStatEvent_Count (x)” where x is the enum value of your game level enum, for example 10. It does not show your game level enum. This makes debugging this code less clear.

An alternative is to use strings. Obviously string comparisons aren’t cheap and they would take up large amounts of space, so that’s an alternative that should be shot down quickly. Another alternative is string hashes. This has much better performance however it’s far less readable when debugging. Maybe this is an acceptable tradeoff. A downside is that I may be required to use at least 2 bytes to represent the hash in order to prevent hash collisions. I’d prefer to use 1 byte for the enum representation to cut down on memory costs as there may very well be less than 256 events in a game. I could of course, just use int’s (or char’s in my 1 byte case). This has the same cost as hashes, same memory footprint as hashes and same lack of clarity when debugging. I could use my enums still and all parameters are implicitly cast to an int. It’s still not ideal, but given the alternatives, it may be the best. A final thought is that I could implement a OnEvent() function that accepts EGameStatEvent and internally cast the parameter to an int. This would remove the need to cast it at the call site.

What do you think? How do you like this overall architecture with regards to it minimizing errors when adding a new stat? Can you think of alternative architectures that may prove to be better?

Macro fun

For my very first post I thought I would present a piece of code that I recently found.  It was an interesting exercise for me and I wanted to share my findings.  Here they are.  Enjoy!

Consider the following piece of code:

# define FAIL_RETURN(x) \
 if (0) \
   return x; \
 else \
   for (Result _result_no_collide_ = (x); _result_no_collide_ != gk_ResultOk; ) \
     if (g_breakOnFailure && (__debugbreak(), false)) \
       ; \
     else \
       return _result_no_collide_

I know what you’re thinking.  The first time I saw this my brain wanted to explode.  It looks like a mess, it’s hard to understand and it’s undocumented.  Is all this really necessary?

The answer to that question is mostly.  Here’s why.

1.  if(0) else:  This appears to be simply a convention the programmer followed.  It also allows changing this to an if(1) so we can ignore all the code in the else.  We can safely remove this from the macro without side effects.

2.  for:  The for loop is here to provide scope to the _result_no_collide_ variable.  Without the for loop (or a do/while loop) we would be forced to put curly braces around the result variable that is created to store and test the result of ‘x’.  This causes a semi-colon on the caller’s side of things when using it inside an if/else statement that doesn’t use curly braces to fail to compile.  Without curly braces we run into two obvious problems; First the _result_no_collide_ is now able to be used by the caller’s code.  Second the if/else statement without curly braces will fail when a semi-colon is used.

3.  (x):  This is just good macro programming practice.  Unless you have a specific reason to not wrap your parameter in a parenthesis, wrap it.  It prevents order of operations bugs with parameters passed into a macro.  In the case of our macro though, these parenthesis are unnecessary.  See this link if you would like to read more about why we wrap parameters in parenthesis, and when you don’t need to:  https://www.securecoding.cert.org/confluence/display/seccode/PRE01-C.+Use+parentheses+within+macros+around+parameter+names

4.  Infinite for loop:  This looks like a for loop that will continue to loop forever.  If you don’t get a gk_ResultOk you will enter the for loop.  If you then hit the __debugbreak() and press F5, it appears that it will just run the for loop again.  As point 6 below explains, it won’t do this, however that’s very not clear.  We could remove the conditional in the for loop and add it as an if statement inside the for loop.  This works too and is documented below.  It looks a bit uglier, but could be considered easier to follow by some.

# define FAIL_RETURN(x) \
  if (0) \
    return x; \
  else \
    for (Result _result_no_collide_ = (x); ; ) \
      if(_result_no_collide_ != gk_ResultOk) \
      { \
        if (g_breakOnFailure && (__debugbreak(), false)) \
          ; \
        return _result_no_collide_ \
      } \
      else \
        break

5.  The for loops internal if/else:  This seems redundant at first glance.  However if you were to instead write the macro as follows:

# define FAIL_RETURN(x) \
 if (0) \
   return x; \
 else \
   for (Result _result_no_collide_ = (x); _result_no_collide_ != gk_ResultOk; ) \
     if (g_breakOnFailure && (__debugbreak(), false)) \
       ; \
     return _result_no_collide_

The code would fail to compile due to the empty control statement in the for loops if statement.  So, what about changing that into a return _result_no_collide_?  This doesn’t work either as the final lines return _result_no_collide_ will fail to compile as we are no longer inside the scope of the for loop.  So we could add curly braces to the for loop and a semi-colon after the final return.  Does this work?

# define FAIL_RETURN(x) \
 if (0) \
   return x; \
 else \
   for (Result _result_no_collide_ = (x); _result_no_collide_ != gk_ResultOk; ) \
   { \
     if (g_breakOnFailure && (__debugbreak(), false)) \
       return _result_no_collide_; \
     return _result_no_collide_; \
   }

Not quite. This looks correct but breaks down in a specific case for the callee.


if (a == 0)
    FAIL_RETURN(0);
else
    ...

In this above case, the semi-colon is a natural thing to place after the FAIL_RETURN() call.  C++’s convention says to do it, but in this case, it breaks the else statement after the FAIL_RETURN call.  Removing the semi-colon successfully compiles the code.  Thus, while this solution works, it makes the code awkward due to this obscure and hidden rule.  Programmers should be able to put a semicolon there and not break everything!  Now, one thing that isn’t clear is why the semicolon at the end breaks the statement?  An empty else with a semi colon is ok, but a for loop with a colon after the curly brace breaks the callee’s else statement.  Comment if you know the answer!

6.  if( g_debugBreak && (__debugbreak(), false)):  This is an obscure one.  Most people see this code and think, that won’t compile.  So did I.  C has an obscure operator, the comma operator. In short, the comma operator will execute each expression before it but only use the final one in the overall expression.  Visit this link for more information (Comma section):  http://www.cplusplus.com/doc/tutorial/operators/.  So, what this expression says is “if g_debugBreak” then call “__debugbreak()” and ignore it’s return value, after that, it says “false”.  Thus we have 3 expressions, the g_debugBreak, __debugbreak() and false.  __debugbreak() is ignored due to the comma operator and the end result is the following if statement:

if (g_breakOnFailure && false)

Hence the entire statement fails.  However, if g_debugBreak is true, it fires the __debugbreak, fails the if statement and passes flow control to the else statement.  Also, recall topic #5’s scoping issue for why we can’t refactor out the comma operator and just say:

if (g_breakOnFailure) \
    __debugbreak();
return _result_no_collide_; \

So, in conclusion this messy looking code protects us from many unsafe uses of the macro. Developers don’t have to worry about where they can or cannot use it and they don’t have to worry about enclosed curly braces or hidden else statements. They can use FAIL_RETURN() in single line (non-curly braced) if statements. They won’t be able to use them in ?: operators as it evaluates a condition or an expression, not a statement. It cannot be called inside of a function parameter list. A “return FAIL_RETURN()” will fail as well for syntactic reasons as well as flow control reasons.  If the parameter ‘x’ doesn’t fail, what is returned? You cannot call it with if(FAIL_RETURN()) {} as this fails to compile.  Finally for(FAIL_RETURN(); ; ) {} fails to compile as well.

Some might wonder why not a do {} while(); loop?  That’s a matter of personal preference.  It would be written as follows:

# define FAIL_RETURN(x) \
 do { \
   Result r = x; \
   if( g_breakOnFailure && r != gk_ResultOk ) \
   { \
     __debugbreak(); \
     return r; \
   } \
   break; \
 } while(false)

This would work as well. Note the missing semi-colon after the while(true). This forces the caller of the macro to add the semi-colon, as we would naturally type.