Progress report April 2013

 

Introduction

There was a lot of changes under the hood and even a few visible ones during the past month:

• Meditation on game data model
• Programs for creating images
• Organized external dependencies
• OpenGL graphics

OpenGL graphics

This is last thing I've implemented last month but it is the root of most work. Also it is only visible progress so I'll explain it first. Last autumn was making a program (called it Grid Pixel Canvas) for creating vector graphics images. It didn't go far because I haven't elaborated how should tools (for drawing dots, lines, curves, polygons) be used but it was a great exercise in learning OpenTK. OpenTK (open toolkit library) is a library for .Net that among the other things wraps OpenGL. Other wrapper libraries mainly translate C functions and constants 1:1 to C# but this one it makes it feel C#-ish. Constants are translated to enums, matrices are proper C# objects instead of plain two-dimensional arrays and so on.

Galaxy map in the Stareater is now rendered with OpenGL provided by OpenTK. So far the rendering only draws red squares in place of stars but it's a foundation I can build upon. Rendering loop is implemented in such way to minimize unnecessary updates on one side and to allow smooth animations on the other. All game engines I've previously tried, including the one shipped with OpenTK, simply redraw a scene as often as possible. Upside of that approach is maximal possible frame count per second but the down side are constant CPU usage and consequently bigger energy usage. Energy usage can be an issue on laptops because an application with 100% CPU usage can drain the battery in less than an hour, maybe even less then half an hour. Stareater is not going to be graphics intensive game or generally constantly computationally demanding so it will not be designed in a way that clogs CPU. Way it done now is with a timer that triggers refresh roughly every 10 ms.

Along with rendering I've implemented map panning and zooming. When zooming, the point under the mouse is fixed. I'm pointing that out because I had to do some matrix calculus on paper for that and I was proud when it worked :). Anyway no more jumbo picture box with scrollbars and glitchy panning.

Old data model

In order to draw something on the map, star locations have to be stored somewhere. Data model used before remake (prior the version 0.5) was clunky. It was classic object composition and it turned out that I needed something that looks like relational database. To explain this, the situation was along this lines:

• Game object contains collection of stars and collection of players
• Player object contains collection of fleets and collection technologies

Sometimes the game needs collection of fleets of a certain player and sometimes collection of fleets at certain location. Old data model made one query straightforward and the other complex. Getting players fleet would look like game.players[playerNumber].fleets. Getting fleets at certain star would require looping through all fleets of all players and check if location matches star's location:

Collection fleetsAtStar = new Collection();
foreach(Player player in game.players)
    foreach(Fleet fleet in player.fleets)
        if (fleet.location == star.location)
            fleetsAtStar.Add(fleet);

As you can see, the code is visually complex. Performance is suboptimal but not a big issue. Why I'm complaining about visual part, because the code that is easier to read is easier to fix and build upon. Another big issue with object composition is that temporary data (such as player's total research points) also has to live within objects. Well, it doesn't necessarily have to but it's hard to move it somewhere else.  In properly designed relational database data organization is radically different. There are no nested objects and certain mechanism, called indexing, allows skipping the majority of uninteresting data when searching for objects that satisfy certain condition. Example from above would look like this in a database:

• Collection of stars
• Collection of players
• Collection of fleets with reference to owner (player) and location (star)
• Collection of technologies with reference to owner (player)

Getting data from database is this simple:

Collection fleetsAtStar = db.Fleets.Where(
    fleet => fleet.location == star.location
);

Code for getting fleets of certain player would look the same but with different "where clause". Easy, isn't it? For those unfamiliar with the syntax of lambda functions, the parameter of where method is a function that takes a fleet object and decides if it satisfies condition (returns bool). Performance-wise this code is by default equal to nested loop from object composition example but as I said, database "tables" (collections of data of certain type) can be indexed.

Simply put index is kind of parallel collection that groups references to objects in primary collection by certain property. If the database query (such as Where method in the code example above) involves property that has been indexed than an the query would be reduced to finding appropriate groups and loop only through elements in those groups. And just to be sure, finding a group is faster (O(log(n))) then checking all groups but that's enough details in this digression.

Custom collections

I was really tempted to use a database to store runtime data. With SQLite and an adapter library the size of game would increase by 3 MB. That may not seam as a problem in post the ADSL era but upload speed at my location is horrible, space on Google Code hosting is limited, code repository get clunkier and it simply can be done with less megabytes. In fact I've found solution that is as big as few C# classes. When translated to machine code it's merely a kB or two. The solution is custom collection implementation for each "database table" that groups elements on their own and exposes those groups. Now the kicker is that I'm using T4 to generate code for those classes. Instead of copy-pasting and modifying same but slightly different code I can write no more then a dozen lines in a text template file and the C# class is generated for me.

T4 is a markup language much like ASP (or PHP and JSP) that allows mixing of content and generation logic. In this case the content is C# code. Generation logic is either VB or C# code that direct the flow of content generation. Sound like inception, using C# to generate C# code :). Another feature I'm using or even exploiting is including one text template file to another. One text template is a base, a set of helper methods and variables and class generator with placeholders. Other templates fill those placeholders and use base template to generate desired code. And they are quite short:

<#@ template debug="false" hostspecific="false" language="C#" #>
<#@ output extension=".cs" #>
<#@ include file="$(ProjectDir)/Utils/Collections/IndexedCollectionBase.tt" #><#
  
  namespaceName = "Stareater";
  usings.Add("Stareater.Utils.Collections");
  usings.Add("Stareater.Maps");
  usings.Add("Stareater.Players");
  
  Generate("VisitedStarsCollection", "VisitedStars",
   new GroupInfo("Stars","StarData","Star",ViewType.Collection),
   new GroupInfo("Players","Player","Player",ViewType.Collection)
  );
#>

First two lines are overhead, what langauge is used in template code and what extension to append to generated file. Third line includes the base template file. Next four lines fill certain optional parameters in base template and finally, call to Generate method fills placeholders and does all the heavy lifting. Parameters of that method are collection attributes (class name, type of elements) and group descriptors

New data model

After I got a way of storing data it was the time to see what data does the game needs and how exactly to organize it. To do that I went through all classes that contained some kind of dynamic data and plotted it on a graph. A tool specialized for creating class diagrams would be more appropriate but I wanted to learn and test the limits of GraphViz.

Analysis showed that the game operates with four kinds of data:

• Static (doesn't change over the game, for example technology "tree" or types of ship equipment)
• State descriptors (describes current turn, for example colony population or ship position)
• Change descriptors (players' decisions such as spending ratios or fleet orders)
• Temporary data (temporary values used when calculating the state of the next turn)

This figure show new data organization model where blue nodes are classes and gray nodes their properties. Static data is boring so I skipped it in the deeper analysis. Boring in a sense that they don't interact with or depend on other data, they are for all intents and purposes constants. Among dynamic data, state descriptors are the biggest. What surprised is that change data is small. Don't be fooled by the number of gray nodes in temporary data, effects are very big structures.

This is the graph of old data model. Rectangles are classes a ellipses are their properties. Property colors depict their placement in new model (green = state, orange = change, pink = temporary). Blue properties will be used as grouping keys and red will be either changed, moved to controller (layer between game logic and user interface) or removed entirely. Some nodes have multiple colors which means they multiple roles in new model. Names are copied from source file (plus prefix to make nodes unique since by that time I didn't know how to use a certain feature in GraphViz) so if you don't understand Croatian you may have a hard time to read the graph. That is one issues I'm correcting in current code rewrite, all code is being written in "common trade language" (English).

Separation of state, change and temporary data is perhaps the change with the biggest impact to the code rewrite. Partly because I didn't expected it when planning the rewrite, partly because it allows better separation of concerns and it improves readability.

External dependencies

I touched the subject of external dependencies earlier. Two new external dependencies were introduced to Stareater last month: NGenerics and OpenTK. OpenTK, as mentioned, interface to OpenGL (pretty graphics on user interface). It also provides OpenAL (open audio library) that may come handy in the future. NGenerics provides additional data structures that are needed in the code, namely priority queue, 2D vectors and graph vertices and edges. Those classes are relatively simple to write but I weighted that cost of the existing library is lower then reinventing the wheel. Size of the DLL is acceptable, about 160 kB. In my humble opinion it would be better if they have had split the library to a few smaller because serious stuff is mixed with educational (like gnome sort) and algorithms and data structures can be separated.

To manage external dependencies I learned and started to use NuGet. It's the tool for managing dependencies that integrates well with Visual Studio C# projects. For professional and higher editions of VS there is the NuGet extension. For others there is a command line tool which is fairly simple to use. The benefits of the tool are simplified installation of dependencies, easy updating and separation of library repository and code repository. Separation is neat thing because the versioning system doesn't have to track DLL file which can be quite large compared to the rest of the files.

Conclusion

Last month I learned a lot of new stuff in order to make a progress in the Stareater. I learned how to use GraphViz, NuGet and T4,  i4o and C# Expression Evaluator. Last two weren't used in the project but they were a learning material.

As usual, majority of progress isn't visible but will add it's value along the line. Now on the menu are the cool things: playing with OpenGL, exploitation of the gained knowledge, experimentation with starlane generation algorithms and experimentation with procedural image generation. Oh, now I see I haven't touched the subject of my programs for creating graphics. The post is too lengthy as is. I'll write about it some other time.

In retrospective, for me the blog turned out to be horrible medium for reporting progress. At first there is nothing to write about and then there are either many small subjects or a few hard ones. For instance, this post took me more than a week to write it. It was still April when I started. I could have used that time do work on the game. That's why I've decided to either blog even less often or write simpler posts and use Twitter in the mean time. Hash tag is #stareater4x.