The Monkey in the Middle

*blows cobwebs off of blog*

I wrote this earlier this year when I was working on a MMO Scrabble game using Google Web Toolkit and Google App Engine. This chronicles the decision the team made for choosing a NoSQL database solution such as GAE. I thought I would add it here for safe keeping. Enjoy!

Choosing a database solution for any application is an extremely difficult, but critical decision. You are deciding the backbone of your application, whats going to be used to capture and store your applications precious data. When viewing all of the options out there, you need to evaluate their strengths and weakness, whether they play into or against the needs of your application. You need to look at your application and attempt to envision the end product. How many users will be using it? Will these users be accessing your data concurrently? Will you have a big fluctuation in the number of concurrent users at a time, say 50,000 users between the hours of 5 -8pm, but only 1,000 users during 6am-11am? How will you handle a large jump of overall users due to the applications increased popularity (hopefully!). In terms of hard disk space, how much data do you expect to store? At what rate will this grow? How complex do you expect your schema to be? Who do you have that can be your database administrator, and what kind of technologies can they manage and administrate based on their current skill set? What are the costs of operating and maintaining the server that will be housing the database? These are just a sample of questions that need to be answered.

Relational databases easily dominate the market. They are the popular choice, and for good reason. They have been proven to be viable solutions for a vast range of applications, from online retail stores to complex AAA MMORPGs. They have great transaction support, providing full ACID qualities. They can handle a high number of users concurrently accessing the same data. They support highly complex SQL queries and data manipulation, allowing developers, designers and business executives to query against their data to build much needed data metrics and analysis, able to answer questions such as “on our big annual 4th of July sale, for years 2003-current, for which item which was available during that date range, was the third best selling in our New York City customer base”, using these reports to further drive their business and sale tactics, or identify inefficiencies and help improve overall sales.

However, relational databases are not perfect. They have their weaknesses, more specifically in the realm of performance, scalability and object-relational impedance mismatch issues. Yet most applications simply choose to work around these imperfections due to a simple case of “the benefits of relational databases greatly outweigh their negative impact on my application”. In the case of massively-multiplayer-online-games (MMOGs), performance, scalability, completely avoiding object-relational impedance mismatch, high quality transaction support and complex SQL reporting are all needed, practically equally so. It’s been said that with regardless of which database solution you choose, you are allowed to only pick two items from the latter list and apparently most developers need highly complex SQL reporting as number one, leaving the second choice up in the air. Historically, however, transaction support tends to be a very close second in terms of desired features.

Cryptic Studios, in the quest for coming up with the perfect database solution, have gone as far as designing and developing their own database management systems, CrypticDB. The CCP Team of EVE Online actually use a single-shard SQL server architecture, and to combat performance issues, have thrown large sums of money into a mind bogglingly beefy server hardware configuration, A.K.A. scaling vertically (more on that later). While throwing money at the problem may be a viable solution to some, for many (start-ups for example) that’s not an option, at least it’s not the best.

From an engineers perspective, relational databases introduce the problem of object-relational impedance mismatch, making it difficult to translate the data that is used in a object-oriented application to store nicely within the relational databases strict structural confinements and incompatible datatypes. In order to store complex data structures, we are forced to develop wrapper classes to do the translation, which if not done perfectly, will have severe impact on performance, possibly so severe that the end user may be affected, like being forced to wait two seconds to loot a green item from a dead zombie. The issue of object-relational impedance mismatch is an extensive one, beyond the discussion of this particular post.

Luckily, we aren’t stuck with just relational database management systems to choose from. Leaving the realm of relational databases introduces the broad range of NoSQL databases. NoSQL are object-oriented based, and in general have the SQL query language omitted (thus the name, NoSQL). There are many different varieties of NoSQL databases, being categorized by their data storage methods. NoSQL databases were developed to primarily solve the issue of scalability, to scale horizontally rather than vertically (CCP, if you remember, decided to scale their database vertically by increasing their hardware configurations). Scaling horizontally means adding more nodes to a system, creating a distributed network. In a distributed environment, data integrity becomes an immediate concern, so the ultimatum of choosing “consistency vs. availability” comes into hand.

NoSQL was also introduced to deal with the issue of object-relational impedance mismatch, being able to handle and store a much wider range of datatypes and structure than a RDBMS could. As an extension, NoSQL also allows handling large volumes of data, quickly retrieving such information, virtually eliminating the need for expensive JOIN operations (which most NoSQL solutions decline to even offer). In essence, NoSQL offers either a high level of data integrity or availability and better compatibility and support for complex and object-oriented data.

When talking NoSQL, we can’t neglect to talk about the CAP theorem, first proposed by Eric Brewer in 2000. The CAP theorem states, in a distributed computing environment, you can optimize for only two of three priorities, Consistency, Availability and Partition Tolerance.

When considering walking down the NoSQL path, the needs of your application will need to dictate, the two priorities that you decide to go with in your NoSQL, distributed database solution. Choosing the correct combination is absolutely critical and choosing the wrong combination could very easily have a dire impact on your business. For example, Amazon claims that just an extra one tenth of a second on their response times will cost them 1% in sales. This should really drive home the importance of correctly choosing your applications database needs. No pressure ;)

There’s simply no “best” database solution to any application. It’s a constant battle of tipping the scales. It’s almost guaranteed that regardless of what solution you go with, it’ll have a negative impact somewhere. The trick is to limit that negative impact or at least direct it towards a aspect that can “afford” to be hit by it, where perhaps the developers can “make-up” for the short coming within the application’s design and implementation.

For WordWars, we knew from the beginning we wanted a database solution that was easily scalable, being able to handle 30 users one day, and scale up to 10,000 users the next day (we could only be so lucky to see a large jump of users like that!), with virtually no mediation required. With an increased user base, we also want to maintain the same high level of performance as our user-base fluctuates, while keeping in mind the fact that we have little to no money to scale vertically. We also need to rely heavily on transactions, due to the nature of gameplay and high probability of having many concurrent users playing at the same time, attempting to access the same data. We need consistency so that every user viewing a single board sees the same thing. We also need a certain level of data integrity. For example, we simply need to be able to gracefully handle the use case of two users attempting to play a word on the same board location, at the same time.

Google’s Big Table database solution attempts to play the middle ground. It is NoSQL based, offering a high level of speed and scalability that relational database tend to fail to deliver, but also provides transactions, a common feature standard in relational databases, but often missing from NoSQL databases. Big Table provides full transaction support, using optimistic concurrency. As you can see from the CAP theorem diagram above, Big Table provides Consistency and Partition Tolerance, which satisfies the needs of WordWars nicely. Yes, we are giving up complex SQL reporting. However, Big Table does use a similar query language called GQL, but at this time it’s still very simple and infant in it’s capabilities, which is more then enough to satisfy what we predict to be our reporting needs.

We are also sacrificing Availability, which may appear to be a huge sacrifice given the type of application we are developing. A failed transaction will happen when using Google’s datastore, for various reasons (timeout, concurrent modification issues, etc). It’s inevitable, it’s the nature of the beast. However, we are developing our application to handle these failures gracefully and greatly limit the impact of any transaction failure. It’s a sacrifice we can make-up for in our application design. If we decided to choose Availability over Partition Tolerance, then we would be losing the latter property completely, with virtually no way of recovering it or making up for it in some other way, at least not easily or efficiently.

Through Google’s App Engine service, we could start using Big Table immediately, have a full NoSQL database at our disposal within minutes with virtually zero effort on our part, leaving Google to the administration duties. Most importantly, we get everything completely free. We will only start getting charged once we have regular users and furthermore once we surpass the free quota thresholds. Since we are in the very early stages of development and prototyping, this aspect alone is enough to drive us toward Google App Engine.

I’m not going to go into great detail about the inner workings of Big Table. Instead, in Part II of this multi-part series, I’m going to talk about how we designed and developed our applications back-end to work with Google App Engine, the trials and tribulations of such, what we are doing to prevent Google App Engine quotas from sending us into bankruptcy, as well as how we are handling inevitable transaction failures. Most importantly, I will discuss how we are keeping our application as platform independent as possible, allowing us to migrate off of Google App Engine with relative ease, if that time were to ever arise.

Going back to basics

I stumbled upon this fantastic article on the basics of matrices and how they are used for rotation in 3D graphics programming. I wanted to share it because when I first started to get serious with graphics programming, the math aspects were the biggest humps I had trouble getting over; I’m always whipping out the 3D math textbooks and articles for a refresher. Also note, all pictures used here are from the article linked below, and I take no credit for their creation. Full credit goes to Steve Hazen.

http://stevehazen.wordpress.com/2010/02/15/matrix-basics-how-to-step-away-from-storing-an-orientation-as-3-angles/

Steve Hazen explains the basics of matrices so well, and the added pictures and videos truly help drive the concepts home. The pictures and videos truly make this article so clear and easy to absorb. Many 3D math textbooks fail to provide these, or quite simply, include bad ones. As a beginner, I found it hard to translate (no pun intended) how a bunch of numbers in a 4 x 4 grid manipulate a 3D model on screen. The following picture alone is priceless is aiding this;

The picture depicts an orthonormal matrix. This is a matrix in which is both orthogonal and normalized. Lets break that down even more. For a set of vectors to be considered orthogonal, they must be mutually perpendicular. For a vector to be normalized, they need to have a length of 1. Lets look at another matrix;

[ 5, 0, 0, 0 ]
[ 0, 6, 0, 0 ]
[ 0, 0, 2, 0 ]
[ 0, 0, 0, 0 ]

This matrix is also orthogonal, because the vectors are still mutually perpendicular, but it is not considered orthonormal due to the vectors not being normalized. Look at the picture above and try to view how each row vector in the orthogonal matrix above would look like in 3D space.

The last row in a 4 x 4 matrix is reserved for translation. In both our orthonormal and orthogonal matrices we’ve discussed so far, they were located at 0, 0, 0 in world coordinates, or the origin. We can situate our vector model elsewhere in the world by changing the fourth vector row values. Take a look at the following picture;

Imagine we are using this matrix for a 3D model. As we now know, the first three row vectors will indicate how it will orient itself in our 3D space. The fourth row vector will tell us where in world coordinates the model will actually be, in this case the end of the black arrow.

See how easy it is to visualize a matrix now? I guess it’s true, a picture can say a thousand words.

 

TiledLib

As mentioned in my last post, I was going to be making use of Nick Gravelyn’s awesome TiledLib XNA library and Content Pipeline extension. His TiledPipelineExtensions simply takes a tile map made in Tiled, and  allows you to import it into an XNA game with minimal effort. When you create a map in Tiled, it saves as a .tmx file, which is nothing more than an XML file, holding property information about the map, including information about the tile set used, tile layers and objects, and the actual data of the map compressed. Tiled is a wonderful, powerful and robust tile map editor. Yes, you could create your own but why keep reinventing the wheel?

It’s probably useful to quickly go over how the XNA Content Pipeline works at a high level. When XNA was first being developed, one of the primary goals was to remove the requirement to write boilerplate code to provide basic functionality that every game engine needs, such as importing content data, such as art assets, to be used by the game. At the very high level, there are three major processes that an asset must go through,

  1. Importer
  2. Processor
  3. Writer
  4. Loader

The importer takes the game asset and ultimately converts it into the XNA Game Studio Content Document Object Model (DOM), which are consumable by the standard content processors. The Processor then compiles these objects into managed code objects that can be handled by the Writer process which will finally write out an XNB file that can be used by the XNA game at run time. All of this occurs at build time. At run time, the Loader will actually load the XNB file to be used. This is a very high level overview of the Content Pipeline. There are plenty of resources that go deeper into the inner workings of the Content Pipeline if you are so inclined to research (MSDN Article). Out of the box, XNA Game Studio 4 handles a wide range of asset types. However, you can also extend the Content Pipeline to handle assets types that it doesn’t handle, such as a .tmx map made in Tiled! To extend the Content Pipeline to handle custom assets, you need to create a Pipeline Extension project, which will be referenced by your games Content Pipeline. At a minimum, this project will consist of just four classes, a class to hold the input data you’re importing, and your Imported, Processor and Writer classes, deriving from ContentImporter, ContentProcessor and ContentTypeWriter<>, respectively. Lets go over the Importer, Processor and Writer classes of Nick Gravelyn’s Tiled importer.

TmxImporter

As mentioned prior, Tiled saves a map as a .tmx file which is basically an XML file that stores all of the information regarding the tile map. Below is an example of a very simple .tmx XML file, as provided by Nick’s TiledLib Demo project.

<?xml version="1.0" encoding="UTF-8"?>
<map version="1.0" orientation="orthogonal" width="20" height="12" tilewidth="40" tileheight="40">
 <tileset firstgid="1" name="Tiles" tilewidth="40" tileheight="40" spacing="4">
  <image source="Tiles.png" width="128" height="40"/>
 </tileset>
 <layer name="Tiles" width="20" height="12">
  <data encoding="base64" compression="zlib">
   eJxjZmBgYKYyphZANo8QjabvAJR2INY8Bhx8UszDZj42c7CIOxByHx73HkDjOyCxyYoPkJnMDPj9Sw0wVMxjwoJB4owkYmrnMxAGAIovBhw=
  </data>
 </layer>
 <objectgroup name="Objects" width="20" height="12">
  <object name="Point" x="613" y="354"/>
  <object name="Box" x="336" y="261" width="120" height="120">
   <properties>
    <property name="B" value="203"/>
    <property name="G" value="192"/>
    <property name="R" value="255"/>
   </properties>
  </object>
 </objectgroup>
</map>

As you can see, there’s not much magic to it. The TmxImporter class simply reads this XML file, creating a MapContent object to store all of the data within the XML nodes of the .tmx file. For example, MapContent will read the orientation, width and height of the map in tiles, width and height of the tiles in pixels, etc. Once we’ve stored all of the important information we need from the .tmx file into our MapContent, TmxProcessor can start, um, processing it.

TmxProcessor

Now that we have read in all of our .tmx data into an MapContent object, we need to actually process it. Shockingly, TmxProcessor is where we’ll actually create our tile map, via the MapContent object that we created from the data in the .tmx file. The important thing to get this to work correctly is to ensure you also import the correct tile set texture(s) that were used to create the .tmx map file. Using the MapContent data, we’ll be able to generate our actual Tile objects that make up an entire map. For example, we know from our .tmx file that the tile textures used by Tiled to make the map are 40 x 40 in size. We also know that the Tiles.png file is 128 x 40 and that the single layer, named Tiles in this case, is 20 x 12 tiles in size. Using the compressed data in the .tmx, which tells us exactly what kind of Tiles are used at which location in the layer, we have all of the information we need to re-create the Tiled map in XNA. While I say things like “using the compressed data in the .tmx…” I’m really referring to all the data that has been stored in the MapContent object. At this point, we no longer actually read from the .tmx file, only from the tile set image file and the MapContent object. This is just a very high level description of this class.  I could explain the class line by line, but the code itself is fairly straightforward and commented well to not need further explanation. I encourage you to take a peek yourself. The next and final class in this Pipeline Extension will take all of this glorious data and convert it into an format actually usable by our XNA game.

TmxWriter

TmxWriter simply takes the processed MapContent object and writes it to an XNB file to be used by the actual game. As with TmxProcessor, the code is fairly straightforward and commented well. I don’t need to explain it line by line, but just know this is where the MapContent object is converted into an object that’s usable by the XNA game.

And there you have it. That about sums up the inner workings of Nick Gravelyn’s TiledPipelineExtensions. Not complicated really. If you download the actual source code for this, you’ll get a much better understanding of it at a lower level, and realize it’s not that daunting. I didn’t discuss the other Content classes that are included in the Pipeline Extension project, because I felt I would be regurgitating the code too much. To summarize, these classes provide support when reading the .tmx file. For instance, the LayerContent class will be used to store information about each layer (name, width, height, etc). The MapContent will store LayerContent objects in a List, and will represent all of the layers in the Map.

Besides the TiledPipelineExtension, there is also a TiledLib XNA library project. This is what you use in your actual game code. There are several classes, such as the Map class which represents a full map built in Tiled. There are also classes to represent each tile layer in the Map, a Tile class to represent each individual tile in the layers and even a TileGrid class so you can access a single Tile in a layer of the map.

To actually load the Tiled map in your game, it’s as simple as importing the .tmx file into your game project’s Content Pipeline, declaring your Map reference variable, making a call in LoadContent like so ( map = Content.Load<Map>(“Map”); ) and adding it to your Draw method. Bam! You’re done. The heavy lifting has been done for us so we can focus on our level design. Admittingly, I still feel dirty about not creating the Content Pipeline Extension and TiledLib on my own, but that’s something I just need to get over. What’s important is that I learned a lot about the XNA Content Pipeline and can now create my own extension if I need to in the future.

OverDeveloping

Why hello there. Another blog? Really? Yes, really. This blog is more to help me than educate others, as I find recording my pursuits help strengthen my neural synapses; although I’d be more than ecstatic if others find what I post here educational and useful. The purpose of this blog is to record my trials, tribulations and successes in XNA game development. I’m not a complete XNA n00b, though I’m not l33t either (it’s getting all 1998 up in here!). Having just completed earning my Master of Science in Computer Science, my Master’s project was a 2D side-scrolling space shooter done in XNA. I’m also a professional Software Developer at a medical software company. So if I’m not at work or dealing with other life matters, I’m working with XNA. As you can imagine, I’m always trying to find more hours in the day.

I’m also deeply interested in using games as a more expressive medium and an interactive way to communicate. I feel games can aspire to be more than just “fun”, more than just something a person plays for entertainment value. Sure, those types of games most certainly have their place, and a game needs to be “fun” and enjoyable or else no one will play them, but I feel there is more to be had. Don’t worry, I understand I’m just one man and that there are much smarter people out there attempting the same thing (I hope, at least), but I love video games and game development. Why wouldn’t I try to help advance my most beloved medium?

For my next XNA project, I’m greatly leaning towards a RPG in the style of classic SNES SquareSoft RPGs. Right now, the project is nothing more than ideas swimming around in my head. I’ve started to think about the game engine, what I need, how to approach implementing them in XNA. I’ve done some research on how I will handle the Tile Engine. The XNA RPG Game Kit/Tutorial renders tile maps via your standard sprite sheet, and an XML file to map out the map layers and other details. While this may seem like a good approach, I’m not keen on doing the level design in the manner of creating an arbitrary grid of numbers for each map layer; this is cumbersome. The next step up would be to make my own WinForm level editor which I could create a whole tile map from, visually. However, I believe I will take Nick Gravelyn’s advice on this one and be lazy. I’m going to use a proven and very robust tile map creator, Tiled, and adapt Nick Gravelyn’s TiledLib, a .tmx XNA importer. At first I was apprehensive about this, because I tend be strong headed at times about not inventing everything myself. In the end, it’s all about growth. Learning from others is a major key in educating yourself and how you learn. I’ll use Nick’s .tmx importer for XNA, but not until I fully and truly understand how it works, to the point where I’d feel comfortable enough in developing the same thing nearly on my own. And there’s simply not enough hours in the day to reinvent the wheel, all the time.

I don’t expect to try any experimental game design with this project (that may change), but it’s the type of game I’ve always wanted to develop. It’ll also be a great way to strength my core design and XNA development skills. You can’t write the next grand musical opus without learning Greensleeves first (yay analogies!). So during the development of this game, I’ll come here and post updates, share knowledge I’ve learned along the way, warn people of my mistakes and to not repeat them, etc. My next post will probably be about Nick’s TiledLib in more depth, and perhaps some initial design thoughts. But for now, I need to get back to playing Final Fantasy VI, it’s research time ;)