2014-01-28

A Tutorial; Step-by-step

I've been planning to add a tutorial to my game from the beginning, and finally got around to really working on it a few weeks ago. Similar to my previous post about simple solutions, I found that once I tinkered with ideas enough and came up with a clear idea of how to implement it, my tutorial code just fell into place quite smoothly and fit satisfyingly into the existing architecture.

Making a point

I decided that the best way to communicate how to play the game was to have an image of a finger moving on the screen indicating touch actions. You can see an example of this in the image to the right. I created the hand image by taking a photo of a hand (my eldest daughter's) and then manipulating it a bit to flatten the colors and such. In the tutorial it is opaque when touching the screen (the left image), or mostly transparent when not touching the screen (the right image).

After creating the finger I needed a way to move it around the screen easily and also initiate the touch events. For this I created a Finger class that extends Symbol (see my previous post for a discussion on this) and holds the image of the finger. This class also has new animation functionality mostly implemented in the methods shown below.

BeginAnimation is called once for each single animation step (e.g., moving from point A to point B with the finger touching the screen or not, as indicated). This animation is then handled as part of the normal Animate method, which is called once for each Widget during the main animation loop, by calling DoFingerAnimation. As you can see it mostly just updates the finger's position and, once complete, calls the _fingerCompletionAction.

public void BeginAnimation(Point start, Point finish, bool isTouchingScreen, TimeSpan duration, Func<bool> completionChecker, Action completionAction)
{
    _fingerMoveStartTime = DateTime.Now;
    _fingerMoveDuration = duration;
    AnimationStartPosition = start;
    AnimationFinishPosition = finish;
    IsTouchingScreen = isTouchingScreen;
    _fingerCompletionChecker = completionChecker;
    _fingerCompletionAction = completionAction;
}

private void DoFingerAnimation()
{
    TimeSpan elapsed = DateTime.Now - _fingerMoveStartTime;
    if(elapsed < _fingerMoveDuration)
    {
        Position = Animator.Interpolate(
            AnimationStartPosition,
            AnimationFinishPosition,
            _fingerMoveDuration.TotalSeconds,
            elapsed.TotalSeconds,
            Animator.Curve.Linear
        );
        AnimationCurrentPosition = Position;
    }
    else if(IsBeingAnimated && _fingerCompletionChecker())
    {
        _fingerMoveStartTime = DateTime.MinValue;
        _fingerCompletionAction();
    }
}

Stepping it up

So, now that I can perform a single step of an animation controlling the finger, I need to string these together into multiple steps that show a complete tutorial lesson. To do this I created a couple of data holders within my Tutorial class. The first, Step, represents a single step of the tutorial and performs a single finger animation movement. The second, Lesson, holds all of the data for a single tutorial lesson including the game elements to show on the screen and the sequence of steps.

One thing to note, there is a slightly confusing use of the term "completion checker" here, since it is used twice. It basically serves the same purpose for two different levels of the lesson. Inside Step it is used to determine if that step should end. Of course the step has a set duration, but even after that duration there can be other conditions that must be met (see the actual lesson examples later). Similarly, in Lesson this is used to determine if the lesson is complete.

private struct Step
{
    public Step(double destinationX, double destinationY, bool touchScreen, double duration, Func<Tutorial, bool> completionChecker)
    {
        Finish = new Point((float)destinationX, (float)destinationY);
        TouchScreen = touchScreen;
        Duration = TimeSpan.FromSeconds(duration);
        CompletionChecker = completionChecker ?? (foo => { return true; });
    }

    public Point Finish;
    public bool TouchScreen;
    public TimeSpan Duration;
    public Func<Tutorial, bool> CompletionChecker;
}

private struct Lesson
{
    public int Width;
    public int Height;
    public IEnumerable<Point> Goals;
    public IEnumerable<ShipInfo> Ships;
    public IEnumerable<Tuple<int, int, WallLocation>> Walls;
    public Func<Tutorial, bool> CompletionChecker;
    public IEnumerable<Step> Steps;
}

A lesson plan

Fortunately I was able to use a combination of the yield return technique for enumerations and C#'s object initializers to compactly define individual lessons. I do this statically and populate an array to hold them all.

private static Lesson[] All = Tutorials.ToArray();

private static IEnumerable<Lesson> Tutorials
{
    get
    {
        int width = 4;
        int height = 6;

        // Create one simple diagonal.
        yield return new Lesson
        {
            Width = width,
            Height = height,
            Goals = new Point[] { new Point(width - 2, height - 2) },
            Ships = new ShipInfo[] { new ShipInfo(ShipType.Hero, new Point(0.5f, 0.5f), Direction.East, 0.025f) },
            Walls = new Tuple<int, int, WallLocation>[0],
            CompletionChecker = tutorial => { return tutorial.AchievedAllGoals; },
            Steps = new Step[] {
                new Step(width * 0.6, height * 0.4, false, 3, null),
                new Step(width - 2, 0, false, 2.5, null),
                new Step(width - 1, 1, true, 1.5, tutorial => { return tutorial.Ships.First().Position.X < width - 2.5; }),
                new Step(width - 0.5, 1.5, false, 1.5, null)
            }
        };
        .
        .
        .

Pulling apart this first Lesson, the interesting part is the 3rd step that has the non-null completion check. This check ensures that the Ship is far enough to the left before taking the finger off of the screen, and therefore completing the diagonal. Without doing this the ship could end up on the wrong side of the diagonal and not bounce to where it is supposed to.

There are a number of interim lessons I'm not including here, but one interesting one (shown below) is the lesson showing how to pause the game, which is done by swiping all the way across the screen horizontally in either direction. The interesting part here is that I needed to show the pause symbol, and then the continue symbol. To do this I cheated a little in two ways. First, in the step before I want the appropriate symbol to be visible, I used the completion check to create the needed symbol, although it's alpha was initially set to 100% transparent. This is done via the CreatePauseSymbol and CreateContinueSymbol methods, not shown here. Second, also not shown here, I adjust the transparency of the pause symbol to become more opaque as the finger completes its animation. This was a little hackish, but worked out pretty well.

        .
        .
        .
        // How to pause.
        yield return new Lesson
        {
            Width = width,
            Height = height,
            Goals = new Point[] { new Point(width - 2, height - 2) },
            Ships = new ShipInfo[] { new ShipInfo(ShipType.Hero, new Point(0.5f, 0.5f), Direction.South, 0.045f) },
            Walls = new Tuple<int, int, WallLocation>[0],
            CompletionChecker = tutorial => { return true; },
            Steps = new Step[] {
                new Step(width * 0.6, height * 0.8, false, 2, null),
                new Step(0, height * 0.45, false, 1, tutorial => tutorial.CreatePauseSymbol()),
                new Step(width, height * 0.55, true, 3, tutorial => tutorial.CreateContinueSymbol()),
                new Step(width - 1.5f, height - 1.5f, false, 1.5, null),
                new Step(width * 0.5, height * 0.5, false, 1.5, null),
                new Step(width * 0.5, height * 0.5, true, 0.05, tutorial => tutorial.RemoveContinueSymbol()),
                new Step(width * 0.65, height * 0.65, false, 0.5, null),
                new Step(0, height - 2, false, 0.75, null),
                new Step(1, height - 1, true, 0.75, tutorial => { return tutorial.Ships.First().Position.Y < height - 2; }),
                new Step(width * 0.75, height * 0.55, false, 1, null),
            }
        };
    }
}

Linking them together

Finally, now that the lessons are defined, I need to do two more things: make the finger's touch actually behave like a normal touch in a normal game, and queue up the steps so they play in order. The first was pretty easy by just calling the existing touch handlers with the appropriate touch points. The second also turned out particularly well because I used the built in onComplete action in the finger animations to recursively call a method that dequeues each successive step.

private void DoTutorialSteps(Queue<Step> queue)
{
    if(queue.Count > 0)
    {
        Step step = queue.Dequeue();
        Action onComplete = step.TouchScreen
            ? new Action(() =>
                {
                    HandleTouch(BoardToScreen(_finger.AnimationStartPosition), BoardToScreen(_finger.AnimationCurrentPosition), true);
                    base.HandleBoardTouch(_finger.AnimationStartPosition, _finger.AnimationCurrentPosition, true);
                    DoTutorialSteps(queue);
                })
            : new Action(() => { DoTutorialSteps(queue); });
        _finger.BeginAnimation(_finger.Position, step.Finish, step.TouchScreen, step.Duration, () => step.CompletionCheck(this), onComplete);
    }
}

I'm now almost done with the tutorial and have only one more lesson to add.

Next time: Alpha layering.

2014-01-27

Simple Solutions

Unlike the in depth investigation and learning required to understand premultiplied alpha, as discussed in my previous post, today's topic is simple and satisfying.

Collections of collections

I've structured the graphical elements of my game into a number of logical layers (not display layers). I won't go into all of them, but to give you an idea, here are some of the key parts, from the most fundamental to the most complex:

  1. The most basic layer is a Texture, which is an abstract class that represents a picture that is loaded from a file.
  2. Above that is an OpenGLES20Texture, which is an implementation of Texture specifically for OpenGL ES 2.0.
  3. Above that is a Graphic, which includes information about the Texture, plus information about its orientation, size, and color.
  4. The next layer up is Widget, which is an abstract class that has a 2D position, an abstract Animate method, and an abstract Render method.
  5. One layer above that is Symbol, which implements Widget and provides a number of concrete features, including references to one or more Graphic instances. I use this class for all of the interactive controls in the game, like the checkmark to start a game, the question mark icon for starting the tutorial, etc.
  6. Another layer above Widget are all of the game UI elements, like Ship, which is the white ball that moves around and bounces off of walls. This also implements Widget and contains the logic to make the ship do what it is supposed to. I have similar classes for the other game UI elements like Wall, Diagonal, etc.

Given the above structure, this means that all graphical elements that I need to render inherit from Widget. In the various game screens I keep track of these in collections that inherit from the following:

public interface IWidgetEnumeration
{
    /// <summary>Returns the <see cref="Widget"/>s in the collection.</summary>
    IEnumerable<Widget> Widgets { get; }
}

For example, the game screen parent class collects all of these multiple collections via the following:

protected sealed override IEnumerable<IWidgetEnumeration> WidgetsToRender
{
    get
    {
        foreach(IWidgetEnumeration collection in LowerWidgetsToRender)
        {
            yield return collection;
        }
        yield return WallsHorizontal;
        yield return WallsVertical;
        yield return Goals;
        yield return Diagonals;
        yield return Poles;
        yield return _diagonalMarkers;
        yield return Ships;
        yield return Collisions;
        foreach(IWidgetEnumeration collection in UpperWidgetsToRender)
        {
            yield return collection;
        }
        yield return _pauseSymbols;
    }
}

What's a little interesting here is that this accessor is an IEnumerable<IWidgetEnumeration>, or an enumeration of collections. This allows subclasses to override LowerWidgetsToRender and UpperWidgetsToRender to add additional widgets as necessary. What's been slightly annoying to me for a while, and what finally gets to the point of this blog entry, is that there have been a number of instances when I needed to only add a single new graphical element in a sub-class. But, since I need to return an IWidgetEnumeration I kept needing to create a collection to contain that single graphical element. This made the override of LowerWidgetsToRender look something like this:

protected override IEnumerable<IWidgetEnumeration> LowerWidgetsToRender
{
    get { yield return _lowerWidgets; }
}

Where _lowerWidgets is an IWidgetEnumeration that contains just one Widget. I couldn't just return the Widget directly, because I must return an IWidgetEnumeration. This seems inefficient to create this collection just to contain one element. But wait, IWidgetEnumeration is an interface. What's to stop me from implementing that directly on Widget so I can just return that directly? Well, that's exactly what I did. I made Widget implement IWidgetEnumeration and added the following simple bit of code to it.

public IEnumerable<Widget> Widgets
{
    get { yield return this; }
}

This allowed me to change the above LowerWidgetsToRender accessor into the following, where _tutorialCounter is the single Widget that was inside the previous collection.

protected override IEnumerable<IWidgetEnumeration> LowerWidgetsToRender
{
    get { yield return _tutorialCounter; }
}

I don't think this refactor improves the performance of the code in any measurable way, but it does make things a bit more straight forward and easier to understand. It's obviously not particularly clever or exciting, but I was happy when I thought of the solution and do feel the code is better because of it.

Next: A Tutorial; Step-by-step.

2014-01-23

Premultiplied alpha

Sorry I've been gone

It's been a while since my last post about OpenGL and OpenTK Fun. This is because the challenge I described in that article, and ultimately resolving that issue, unstuck me from making real progress on my development and I've been putting much more effort into my game since then and am now much further along. That's all good news, but now I need to both make progress on the game and try to keep this blog going too.

I'll start today with a discussion about OpenGL premultiplied alpha textures, but before that I want to send a quick thank you out to a new code syntax highlighter by Alex Gorbatchev. It's JavaScript based, so I no longer need to manipulate my code entries before posting them in these articles. Also a thank you to Carter Cole and his blog entry describing how to easily setup the syntax highlighting in Blogger.

So, what is "premultiplied alpha" and why do I care?

As for what it is, there are plenty of pages out there that can describe it much better that me, so I'm not even going to try. I found a good succinct description on Martin Stone's blog, which points to a more detailed description on Tom Forsyth's blog. Please check those pages out if you want to learn more.

As for why I care, that I can describe in more detail. Initially I knew almost nothing about premultiplied alpha. I had seen the term a few times, for example when compiling my app there is some log message mentioning that it is precompiling my PNG textures, but I never tried to understand that more since everything was working fine. The reason I started to care more, and look into it more, are due to a couple things.

First, there was always something bothering me about a portion of my OpenGL code. From the beginning when I got the code working on both iOS and in Windows I found that I had to have a platform specific check for texture blending:

// on iPhone this is needed to apply the color adjustment (on PC this is our normal setting)
if(colorAdjustment.Alpha != 1)
{
    GL.BlendFunc(BlendingFactorSrc.SrcAlpha, BlendingFactorDest.OneMinusSrcAlpha);
}
#if MONOTOUCH
else
{
    GL.BlendFunc(BlendingFactorSrc.One, BlendingFactorDest.OneMinusSrcAlpha);
}
#endif

I put this code into place after trial and error. The #if MONOTOUCH section only compiles and runs on the MonoTouch framework, which means only on iOS. What I didn't understand was, given that OpenGL is supposed to be a consistent interface across platforms, why did I need to have this condition depending on the platform? All other code and image assets related to OpenGL textures and blending was the same between the two platforms, so why was this needed?

Well, the answer goes back to what I mentioned above about where I had previously heard about premultiplied alpha; the iOS compilation log message. What that message means is that my assumption that I'm using the same image assets (PNG images in my case) is not true. Although I have the same PNGs referenced in both the iOS project and Windows project, when the iOS version gets built the PNGs are adjusted to have alpha premultiplied.

So, why does that require the adjustment in GL.BlendFunc? Well, first we need to know what GL.BlendFunc does. The first parameter is how to use the incoming (source) colors when blending them with the existing (destination) pixels. The second parameter is how to adjust those destination pixels. There is ample documentation about this on many sites, so I won't go into all of the parameter options, but I will discuss the two that I was using. The first version, GL.BlendFunc(BlendingFactorSrc.SrcAlpha, BlendingFactorDest.OneMinusSrcAlpha); says two things:

  1. For the source color, take the alpha (or transparency) component and multiply it by each other component. For example, if the RGB color is (1, 0.8, 0.5)       then after the multiplication it would become (0.5, 0.4, 0.25)      . This is the same color, but darkened.
  2. For the destination color, take the alpha component of the source, subtract that from one, and multiply that by each component of the destination. In this case the alpha is 0.5, so subtracting that from 1 is also 0.5, which would be multiplied by the destination color. For example, if the existing destination RGB color was (0.2, 1, 1)       then after multiplying it would become (0.1, 0.5, 0.5)      . Again, the same color, but darkened.

After completing the above calculations on the source and destination colors then are blended by adding them together. That is (0.5, 0.4, 0.25) + (0.1, 0.5, 0.5) = (0.6, 0.9, 0.75)      . Looking at the two original colors you can see that this works and the resulting blended color is correct.

Ok then, what's up with the second version: GL.BlendFunc(BlendingFactorSrc.One, BlendingFactorDest.OneMinusSrcAlpha);? How does this change things? I won't go through all the steps in detail, but starting with the same two first colors you would get a final function of (1, 0.8, 0.5) + (0.1, 0.5, 0.5) = (1.1, 1.3, 1.0) or pure white, since each component exceeds the maximum value of one and is therefore limited to one. Clearly that is too bright and doesn't work work. So, why would you want to do that? Well, that's where premultiplied alpha comes in. The first version used BlendingFactorSrc.SrcAlpha, which multiplies the alpha by the color. And what do you think premultiplied alpha does? It did that exact same calculation when the texture asset was created (or built, in this case). This means that we don't need to do it again now while blending. Instead we use the color as is, which is what BlendingFactorSrc.One does.

So, final question, why do this premultiplied alpha in the first place? I'll quote Tom Forsyth from his blog post (referenced above) for a pretty good explanation. For a much more in depth discussion please read his whole post.

"Normal" alpha-blending munges together two physically separate effects - the amount of light this layer of rendering lets through from behind, and the amount of light this layer adds to the image. Instead, it keeps the two related - you can't have a surface that adds a bunch of light to a scene without it also masking off what is behind it. Physically, this makes no sense - just because you add a bunch of photons into a scene, doesn't mean all the other photons are blocked. Premultiplied alpha fixes this by keeping the two concepts separate - the blocking is done by the alpha channel, the addition of light is done by the colour channel. This is not just a neat concept, it's really useful in practice.

Doing premultiplied alpha on Windows

Ok, so now I understand what's going on, but how do I fix it for Windows since I don't have a build step modifying my PNG files? I did some research and it seems there are some tools that will convert a normal PNG to a premultiplied alpha PNG, specifically it seems GIMP will do this, although I didn't try it myself. I didn't really want to have to convert my existing assets each time I modified them, or complicate my Windows build process by using addition tools, so I made a code change to do the alpha multiplication at the time I load my PNGs. That's a somewhat wasteful operation, but it only happens once, and considering I don't have very many textures I felt it was a good and simple solution.

Below is the code that does this. You'll notice some strange BGRA to RGBA conversion as well. This is due to using the Bitmap class and it's how Windows works.

public static Texture LoadTexture(string fileName, Func<byte[], int, int, Texture> textureCreator)
{
    if(textureCreator == null)
    {
        throw new ArgumentNullException("textureCreator");
    }

    using(Bitmap image = new Bitmap(fileName))
    {
        BitmapData bitmapData = image.LockBits(
            new Rectangle(0, 0, image.Width, image.Height),
            ImageLockMode.ReadOnly,
            PixelFormat.Format32bppArgb
        );
        image.UnlockBits(bitmapData);
        IntPtr rawData = bitmapData.Scan0;

        Texture texture;
        unsafe
        {
            int length = image.Width * image.Height * 4;
            byte[] data = new byte[length];
            Marshal.Copy(rawData, data, 0, length);

            for(int i = 0; i < length; i += 4)
            {
                float alpha = (float)data[i + 3] / 255;
                byte r = data[i + 2];
                byte g = data[i + 1];
                byte b = data[i + 0];
                data[i + 0] = MultiplyByAlpha(alpha, r);
                data[i + 1] = MultiplyByAlpha(alpha, g);
                data[i + 2] = MultiplyByAlpha(alpha, b);
                data[i + 3] = (byte)(alpha * 255);
            }

            texture = textureCreator(data, image.Width, image.Height);
        }

        return texture;
    }
}

private static byte MultiplyByAlpha(float alpha, byte channel)
{
    return (byte)(channel * alpha);
}

After putting this code in place, so that my textures turn into premultiplied alpha data as I load them, I was able to simplify my original platform dependent code into just this:

GL.BlendFunc(colorAdjustment.Alpha != 1 ? BlendingFactorSrc.SrcAlpha : BlendingFactorSrc.One, BlendingFactorDest.OneMinusSrcAlpha);

Removing that platform specific code is a very minor improvement, but more than that I'm happy to understand all of this quite a bit more.

Next: Simple Solutions.

2013-10-05

OpenGL and OpenTK Fun

I've been working on updating my OpenGL code to use OpenGL ES 2.0 (instead of 1.1). I've run into a number of problems doing this, many of which are exasperated because I don't if my problems are related to my OpenGL code or the underlying libraries I'm using (OpenTK and the PowerVR OpenGL ES implementation for Windows).

To try to diagnose the problems I tried to start with a simple OpenGL ES 2.0 example. Unfortunately, all of the examples I found were either for native OpenGL ES (not via .NET) or specifically from Xamarin for iOS or Android, where I wanted a simple OpenTK example. The OpenTK distribution actually includes one very simple example (just showing an empty window with a colored fill), but as I mentioned in my previous post, the latest official OpenTK release is from 2010 and has some issues.

I searched around and found what appears to be the most active development branch of OpenTK on GitHub at https://github.com/andykorth/opentk. I downloaded that branch and tried to run the same example, but continued to run into problems.

At first I got a System.PlatformNotSupportedException.
System.PlatformNotSupportedException at OpenTK.Platform.Factory.UnsupportedPlatform.CreateGLContext(GraphicsMode mode, IWindowInfo window, IGraphicsContext shareContext, Boolean directRendering, Int32 major, Int32 minor, GraphicsContextFlags flags) in opentk\Source\OpenTK\Platform\Factory.cs:line 171
   at OpenTK.Graphics.GraphicsContext..ctor(GraphicsMode mode, IWindowInfo window, Int32 major, Int32 minor, GraphicsContextFlags flags) in opentk\Source\OpenTK\Graphics\GraphicsContext.cs:line 134
   at OpenTK.GameWindow..ctor(Int32 width, Int32 height, GraphicsMode mode, String title, GameWindowFlags options, DisplayDevice device, Int32 major, Int32 minor, GraphicsContextFlags flags, IGraphicsContext sharedContext) in opentk\Source\OpenTK\GameWindow.cs:line 222
   at OpenTK.GameWindow..ctor(Int32 width, Int32 height, GraphicsMode mode, String title, GameWindowFlags options, DisplayDevice device, Int32 major, Int32 minor, GraphicsContextFlags flags) in opentk\Source\OpenTK\GameWindow.cs:line 180
   at Examples.Tutorial.SimpleES20Window..ctor(GraphicsContextFlags flags) in opentk\Source\Examples\OpenGLES\2.0\SimpleWindow20.cs:line 26
   at Examples.Tutorial.SimpleES20Window.Main() in opentk\Source\Examples\OpenGLES\2.0\SimpleWindow20.cs:line 112
   at System.AppDomain._nExecuteAssembly(RuntimeAssembly assembly, String[] args)
   at Microsoft.VisualStudio.HostingProcess.HostProc.RunUsersAssembly()
   at System.Threading.ExecutionContext.RunInternal(ExecutionContext executionContext, ContextCallback callback, Object state, Boolean preserveSyncCtx)
   at System.Threading.ExecutionContext.Run(ExecutionContext executionContext, ContextCallback callback, Object state, Boolean preserveSyncCtx)
   at System.Threading.ExecutionContext.Run(ExecutionContext executionContext, ContextCallback callback, Object state)
   at System.Threading.ThreadHelper.ThreadStart()

This led me down a little side road of trying to confirm that I had the PowerVR OpenGL ES library properly installed. After confirming it was, as far as I could tell, I stepped through the code in the debugger and got to the Factory constructor in opentk\Source\OpenTK\Platform\Factory.cs.

While stepping through I kept finding that Egl.Egl.IsSupported was false. That code for IsSupported is below.

Oh great, a swallowed exception, maybe that would tell me something helpful. Stepping through the code again and examining the exception showed me a System.BadImageFormatException.

System.BadImageFormatException: An attempt was made to load a program with an incorrect format. (Exception from HRESULT: 0x8007000B)
   at OpenTK.Platform.Egl.Egl.GetCurrentContext()
   at OpenTK.Platform.Egl.Egl.get_IsSupported() in opentk\Source\OpenTK\Platform\Egl\Egl.cs:line 316 

I'm sure some web searching would find it, but I've run into this problem in the past and remembered it had to do with incompatible binary formats. For example, if you have a .NET program compiled for x64 and try to load an 32bit x86 native DLL. I checked the OpenTK solution's build configuration, and indeed, it was set to "AnyCPU". I changed it to x86 and tried again and the above exception went away, but it still didn't work.

Next I got an entirely unhelpful System.Collections.Generic.KeyNotFoundException. With the below stack-trace.

System.Collections.Generic.KeyNotFoundException: The given key was not present in the dictionary.
   at System.Collections.Generic.Dictionary`2.get_Item(TKey key)
   at OpenTK.Graphics.GraphicsContext.get_CurrentContext() in opentk\Source\OpenTK\Graphics\GraphicsContext.cs:line 344
   at OpenTK.Graphics.GraphicsContext.LoadAll() in opentk\Source\OpenTK\Graphics\GraphicsContext.cs:line 512
   at OpenTK.GameWindow..ctor(Int32 width, Int32 height, GraphicsMode mode, String title, GameWindowFlags options, DisplayDevice device, Int32 major, Int32 minor, GraphicsContextFlags flags, IGraphicsContext sharedContext) in opentk\Source\OpenTK\GameWindow.cs:line 220
   at OpenTK.GameWindow..ctor(Int32 width, Int32 height, GraphicsMode mode, String title, GameWindowFlags options, DisplayDevice device, Int32 major, Int32 minor, GraphicsContextFlags flags) in opentk\Source\OpenTK\GameWindow.cs:line 180
   at Examples.Tutorial.SimpleES20Window..ctor(GraphicsContextFlags flags) in opentk\Source\Examples\OpenGLES\2.0\SimpleWindow20.cs:line 26
   at Examples.Tutorial.SimpleES20Window.Main() in opentk\Source\Examples\OpenGLES\2.0\SimpleWindow20.cs:line 112
   at System.AppDomain._nExecuteAssembly(RuntimeAssembly assembly, String[] args)
   at System.AppDomain.ExecuteAssembly(String assemblyFile, Evidence assemblySecurity, String[] args)
   at Microsoft.VisualStudio.HostingProcess.HostProc.RunUsersAssembly()
   at System.Threading.ThreadHelper.ThreadStart_Context(Object state)
   at System.Threading.ExecutionContext.RunInternal(ExecutionContext executionContext, ContextCallback callback, Object state, Boolean preserveSyncCtx)
   at System.Threading.ExecutionContext.Run(ExecutionContext executionContext, ContextCallback callback, Object state, Boolean preserveSyncCtx)
   at System.Threading.ExecutionContext.Run(ExecutionContext executionContext, ContextCallback callback, Object state)
   at System.Threading.ThreadHelper.ThreadStart()

Well, for a pretty low-level media platform this isn't very encouraging as it doesn't describe anything about the real problem and is clearly happening deep in the library. After a lot of debugging I finally found the below bit of code in opentk\Source\OpenTK\Graphics\GraphicsContext.cs.

I missed it the first few times I was stepping through the code, but the comment says it all: Note: this property will not function correctly when both desktop and EGL contexts are available in the same process. This scenario is very unlikely to appear in practice. In my case, since I'm running on Windows, I do actually have both desktop and EGL available. I didn't feel like digging into the code to fix this so that both contexts could actually exist simultaneously, but I remembered the Factory class that's I'd looked into above and made an easier fix. I did this in opentk\Source\OpenTK\Platform\Factory.cs in the constructor. My updated version is below.

You can compare to the original version above, but basically I made it such that the library first tries to see if EGL is available, and if so, uses it. If it is not available then the desktop version is instantiated. You can see that the Default context isn't instantiated unless the EGL contexts don't work.

After all of this I could run the sample program and was rewarded with a 800x600 blue window. Woohoo! Ok, it's not that exciting, but at least it was running and I can now try to get my OpenGL ES 2.0 code working.

Next: Premultiplied alpha

2013-09-25

I'm Back

After more than 2.5 years I'm back. I'm going to try hard to get back into spending regular time on my game and actually get it published. So far I've spent about 15 hours just getting it back to the point it was when I last left it. A lot has changed since then, which is why it took so long to just get it working at all. Here're a few things that have changed and some details about what I've had to do to fix them.

  1. I've changed my home computer. I used to have a tower Windows PC and a Macbook Air for doing the iOS-specific development portions. I now have just a Macbook Pro Retina, which I run VMWare Fusion and Windows 8. I made this migration a while ago, but finally getting my development environment working well took some work.
  2. OpenTK seems to have made some changes, which I don't fully understand since their release date is 2010-10-06 and should have been before I took a hiatus. See more details below.
  3. In the interim 2.5 years both XCode and Xamarin MonoDevelop have evolved and new versions have been released that required more updates. Xamarin's product has been renamed to Xamarin Studio and now has some interesting integration with Visual Studio, which hopefully will make development a bit easier. See more detail below.

OpenTK Issues

When I tried to run my game on Windows using OpenTK I got a PInvokeStackImbalance exception saying: This is likely because the managed PInvoke signature does not match the unmanaged target signature. Check that the calling convention and parameters of the PInvoke signature match the target unmanaged signature. Since I was running against the release build of OpenTK, which doesn't contain debug symbols this error occurred in my GLView class' constructor. It is an implementation of OpenTK's GameWindow. After compiling a debug build of OpenTK, I eventually traced this to the function GetProcAddress in Egl.cs, which is a PInvoke call.

The problem is the EntryPoint should be eglGetProcAddress, not eglCopyBuffers. After changing this and rebuilding OpenTK it worked fine. Doing some searching on the net shows this has been fixed in GitHub, but no new official build containing the fix has been released. It was an easy fix, but a bit disappointing that OpenTK's current official release has such a basic bug in it.

Beyond this, it seems that the latest official OpenTK release differs from what is released with MonoTouch. I'm still not sure of the extend of these differences, but I may write more on this later once I get a better understanding.

Xamarin and Visual Studio

As I discussed in a previous post, I've been using Visual Studio as my primary development environment and only switching to MonoDevelop Xamarin Studio when I wanted to actually deploy my code to my iPhone. Apparently others also are interested in doing this because Xamarin has integrated their product with Visual Studio; you can read more about this on their site. Because they're now providing .NET DLLs that can be used in Visual Studio to compile iOS .NET apps, it means I can simplify one of the issues I had with maintaining and building my code.

I have my game broken into 4 projects, each of which builds into a separate binary. One of these, which I call "Launcher", is the most device dependent, and references device specific libraries. This project can't actually be shared across platforms because the code is too different, so I have both a Launcher.iOS project and a Launcher.PC (in the future I hope to add Launcher.Android and Launcher.WinPhone). For the other three projects I also need separate project files, but 100% of the code is shared. This leaves me with this folder hierarchy:

  • Zoing
    • Launcher.iOS
      • Launcher.iOS.csproj (project file that references iOS specific libraries)
      • ...iOS specific code files...
    • Launcher.PC
      • Launcher.PC.csproj (project file that references PC specific libraries)
      • ...PC specific code files...
    • MediaFramework
      • MediaFramework.iOS.csproj (project files that references MonoTouch .NET libraries)
      • MediaFramework.PC.csproj (project files that reference Windows .NET libraries)
      • ...device independent C# files included in both project files...
    • OpenTKConnector
      • OpenTKConnector.iOS.csproj (project files that references MonoTouch .NET libraries)
      • OpenTKConnector.PC.csproj (project files that reference Windows .NET libraries)
      • ...device independent C# files included in both project files...
    • Zoing
      • Zoing.iOS.csproj (project files that references MonoTouch .NET libraries)
      • Zoing.PC.csproj (project files that reference Windows .NET libraries)
      • ...device independent C# files included in both project files...

MediaFramework is a set of device and framework independent classes that define the building blocks for my game. This includes things like: Audio/AudioSample, Device/Orientation, Graphics/Texture, Graphics/TextureArea, Graphics/MutableShape, Graphics/Shape, Graphics/Size, etc.

OpenTKConnector is a concrete implementation of the MediaFramework abstract classes using OpenTK (OpenAL and OpenGL). For example there is OpenGLES11/OpenGLES11Texture and OpenGLES20/OpenGLES20Texture, both of which implement MediaFramework/Graphics/Texture. Similarly there is OpenAL/OpenALAudioSample, which implements MediaFramework/Audio/AudioSample.

The benefit of having this separation is that my Zoing game just needs to know about the abstract classes in MediaFramework and complete ignores the platform details. For example, AudioSample has a Play method, which plays the sample. That is common for any platforms I will eventually support.


Anyway, restructuring my solution to have the project files arranged as above took a bit of time. I had to recreate the iOS project files to reference the MonoTouch library properly. I also had to move these files around, which is made a little more difficult with version control. Some of this meant examining and tweaking the project files' XML by hand.

This reminds me of one small bug in Visual Studio 2010 that caused me some confusion until I understood it. When you unload a project, then edit the project's .csproj XML file, then reload the project, it seems that Visual Studio doesn't recognize the manual changes you made. To fix this simple unload it again, then reload it again. This is a bit annoying, but once you know about it the workaround is simple.

Next: OpenGL and OpenTK Fun

2011-01-06

More Optimizations

In my previous post I discussed some challenges and interesting compromises I had to make to simulate physics in my game as much as I needed given how I was trying to make the game behave in ways that conflict with the real world. In this post I revisit optimization and discuss some recent work I've put into that area.

Introduction

I'll start with a brief explanation of why it has been so long since my last entry. Partly this is because I've been busy with other things and the recent holidays have also taken up some of my time, but the main reason is that this round of optimizations has been quite a bit more complex than I anticipated. Interestingly, it hasn't been the actual code changes that have been challenging, it has been my efforts to carefully analyze my code's slow areas and fully understand the optimizations I've made.

In some ways this is related to my previous post on optimizations. In that post I left with a conclusion that you need to be careful when optimizing to make sure you understand if and how the changes are really improving performance. To that end I tried to be more diligent in this round of optimizations.

My initial goal in this round was to optimize my game's calculations when advancing the game state frame by frame. I'm currently targeting 30 FPS, but would like that to be as efficient as possible in order to preserve battery life. Also, even though the iPhone can do graphics up to 60 FPS, I examined what my game does and found that there is very little perceivable visual improvement moving from 30 FPS to 60 FPS, which is why I decided to target the former.

To be able to properly analyze the performance of my code's calculations, as opposed to time taken by the actual graphics chip's rendering, I created a benchmark mode for my game that does all calculations as normal, but doesn't do any of the OpenGL API calls. I also do this outside of the top-level game loop, since the OpenTK framework imposes its own FPS limitations in this loop.

Sample Size

I should mention that all of this optimization work was done on my PC in Visual Studio. Since my goal is to optimize my algorithms, I'm working on the assumption that the improvements will also be reflected in code when running on an actual iPhone.

When I started testing this benchmark mode I tried running for a few thousand frames. I got results around 1200 FPS. I initially assumed this number of frames was enough to produce useful results and started the process of running under various conditions both for generating performance statistics to measure improvements and for running within VS' performance analysis tools to see what areas of the code were slowest and the best target for optimization efforts.

The problem I found was that the performance differed wildly from run to run. I ended up wasting quite a lot of time doing analysis with these too-short runs that produced inconsistent results. I finally found that the only real way to get more consistent results was to simply increase the number of frames to render and therefore the test time. Eventually I settled on running for 100,000 frames, or about one minute. At this number of frames I found that I could get multiple runs to finish within a few milliseconds of one another, which, over 1 minute, is quite consistent.

First Optimization - Math

Using this sample size, my baseline analysis produced a run in 78.05 seconds at 1281.23 FPS. I then ran this through the VS performance analysis tools. This revealed a lot of information, but I decided to start with one particular method I though I could quickly optimize.

I have an object called Shape. This represents a set of vertices that are connected to define a 2D shape. So far I'm using it for triangles or quads only, but it is flexible up to any number of points. This object also supports some transform operations like moving it in the 2D plane, resizing it, and rotating it (both around it's own center point as well as some other point). The way I've implemented these transform operations is to, at the time they're called, only remember what the operations are, but not to actually do the transform calculations until needed. This is to optimize when multiple transforms occur at the same time, such as an offset, resize, and rotation.

When the final transformed shape is needed I have a method called MakeClean that, if needed, performs the calculations. When I did my first performance analysis I found that this method was taking 20.8% of total time with these details:

I rewrote this to remove temporary object creation (actually Vector2 is a struct, not an object, but same idea), reduce repeated property accesses, combine multiple calculations, etc. This reduced the time to 9.8% and produced these details:

The result of this was the 100,000 frames finished in 68.9 seconds at 1451.38 FPS. That's 88% of the original time, and 113% of the original FPS.

Second Optimization - LINQ

After the above optimization I did another performance analysis in VS and received this summary report:

I was not surprised to see the LINQ entry there since when I was originally writing that area of the code I knew it wasn't particularly efficient. At the time, however, I wrote it as simply as possible and decided I would optimize it if necessary later. Well, now it's later and time to optimize.

For this area, I can't do any simple localized calculation optimizations, however. That LINQ code is all in the .NET framework and out of my control. In the VS performance analyzer, if I dig into that method, no source code is shown at all, since it is part of the core libraries. In fact, trying to determine where this code is called from is slightly complicated because VS shows this only indirectly. It shows the caller of this LINQ as:

But, in this there's no ConcatIterator to be seen anywhere. Fortunately, it isn't too hard to guess that it is somewhere in ElementsToRender. The code for that initially was:

Hah, see, I told you I wasn't surprised to see this as taking a lot of time. I even wrote a comment to myself about it. One thing the VS performance analysis doesn't show very well is why this is slow. Although this code clearly has a lot of stringed-together Concat calls, I suspect that the embedded Cast operations are also quite a performance hit.

The reason my original code was like this is because I'm developing in .NET 3.5, which does not support covariance and contravariance and therefore doesn't allow casting collections of subclasses into collections of common supperclasses. This is supported in .NET 4.0, however.

My solution to this was to create simple collection classes that hold my GameElement objects, and that can provide those objects both in their subclass typed state as well as their superclass form, and do this efficiently. The basic way I do this is to have have the collections detect when they are modified (added to, removed from, etc) and mark themselves as dirty in that case. Then, when I request the collection in the superclass form, that list is generated and cached, if necessary. This allows me to reduce the above code to this:

At a different area in the code I do a SelectMany to combine all of these collections together. The result of this was the 100,000 frames finished in 55.59 seconds at 1799.04 FPS. That's 81% of the previous time, and 124% of the original FPS.

Third Optimization

I also spent a bit of time on a third optimization. The end result of that was no performance improvement at all, in fact, it was 3% slower that the previous version. I won't describe this optimization in detail now, and I'm actually keeping the slower version for now. The reason is that I think it lays a good foundation for possibly making a more significant optimization in the future, and in some ways is cleaner that the earlier version. If I do such an optimization later I'll then describe it more.

Summary

The end result of all of the above was that my original performance of 78.05 seconds at 1281.23 FPS was improved to 57.08 seconds at 1752.04 FPS. This is 73% of the original time and 137% of the original FPS.

All in all I'm pretty happy with that result. I'm now able to continue feature development and will hopefully be able to blog more regularly again.

Next: I'm Back

2010-12-08

Phunky Physics

In my previous post I discussed some issues I ran into running my .NET code in the MonoTouch environment. In this post I'm switching gears a bit and will discuss an issue I've been struggling with for a while related physics simulation in my game.


Before Diagonal

After Diagonal

90° in the Shade

The issue came up because I was trying to make some of my physics interactions behave different from how they do in reality. You would think that bending reality or completely changing how physics works should be possible in a computer simulation's implementation, but I found out that changing how things work quickly leads to unintended problems. I wonder if this says something about the necessity of how physics actually works in real life.

If you look at the "Before Diagonal" image on the right, you see a white ball heading towards a collision with a blue diagonal. Then, in "After Diagonal", you can see the white ball after it has bounced off of the blue diagonal. For the purposes of my game the white ball must always be exactly halfway between a row or column of purple stars. Before the bounce it is travelling horizontally, and is halfway vertically in a row. After it bounces it is travelling vertically, and is halfway horizontally in a column. The problem is that in an actual 90° bounce like this, with a ball that has a non-zero radius, it would not bounce from halfway-vertical-in-row to halfway-horizontal-in-column like this. The lower part of leading edge of the ball would hit the diagonal first, before the halfway point, and then the ball would bounce upwards, but to the left of the halfway-horizontal-in-column point.

I initially tried to resolve this problem by simply teleporting the ball from the one halfway point to the next halfway point when the bounce occurred. This looked fine, and seemed to work ok, until I added interactions between multiple balls. The problem was that if there was already another ball in the place to where the first ball is teleported, then they would become overlapped and not properly bounce off of one another.

I solved this problem by not doing the teleportation and having the ball bounce as if it has a zero radius. This works fine for my purposes, but has another small problem. For the skin shown in the images to the right, the ball is fuzzy and the diagonal is lightning-like, so having the ball overlap the diagonal when it bounces looks fine. For an alternative skin, though, where the ball is completely solid and the diagonal is more physical-looking, it will not look ok. My plan to solve this is to have the interaction calculation done as if the radius is zero, but have the rendering adjust the ball's visible position so it doesn't overlap the diagonal.


Before Collision

After Collision

Collision!

Billiards this is Not

After resolving the above issue I then started working on ball-to-ball collisions. When the two balls are on the same row or column this is easy. The issue is when they are moving perpendicular to one another.

If you look an the "Before Collision" image to the right you can see that the tow balls are heading towards one another and will collide in the lower-left area of the image. If these were actual balls, like billiard balls, then the result of the collision is that the one moving down would head left and the one moving left would head down. The angle each ball changes to would depend on their speed and mass. My problem with implementing this type of collision is the same as that I described above related to bouncing off of diagonals. Basically, I want the balls to remain exactly in the halfway point between a row or a column. In this scenario, though, that would not happen.

For ball-to-ball collisions I could not use the same strategy I used above for diagonal collisions; calculating as if the ball had a zero radius. I actually initially tried this, and it worked ok for two balls, but once more than two were involved it became possible that all of the balls come to be in exactly the same position and could never resolve their collisions. Also, adjusting the rendering of the overlapped balls so that the don't appear to be overlapping is more difficult.

The solution I eventually came up with was to have the balls simply bounce and reverse directions entirely (see "After Collision" image). As I said, in real physics, that would not happen, and I wanted to make it look reasonable. To attempt do that I added a graphic element that is shown when the collision occurs, and implies that something more than just a normal real-life, ball-to-ball collision is happening. Currently I'm using the graphic shown in the "Collision!" image, but this is tentative, and also can be customized for each skin. Even though the physics of this collision isn't even close to real physics, it actually works pretty well in the game.

Summary

Resolving both of the problems described above took quite a while. I experimented with a number of different solutions before settling on the current one. I also tried to get things working in the early stages when I had the balls teleporting during a diagonal bounce. This seemed we work for some cases, but was never reliable. I find it interesting that even the small adjustment to physical rules I was trying to make in having the balls bounce and maintain their position halfway in a row or column caused problems that were basically impossible to solve. Of course the other side if this is that even my final solution goes against how physics works in real life.

One other thing that makes me feel pretty comfortable with my current solution is that it ended up in much cleaner code. In other strategies I always had a number of special cases, that made the code messy. Once I changed to my current solution they went away.

Next time: More Optimizations.