Sabbatical Log: November 4th

This blog series is running about a week behind my actual work, giving me time to clean things up.  The date the actual work was done is in the title, horizontal lines indicate when I stopped writing and started coding.

Fun Saturday nights lead to somewhat less fun Sunday mornings. Still going to try and make some progress on the collision detection problem, but definitely not firing on all cylinders.

I’ve managed to get most of a collision detection algorithm implemented, at least to the point of determining which polygons will collide and at what times.

The gist is:

  • Only work over convex polygons (I’ll handle this shortcoming later)
  • For each pair of polygons…
    • Treat the first polygon as stationary and increase or decrease the velocity of the second polygon so the same “relative motion” is happening
    • For each line segment in their polygon, determine it’s normal
      • For a line running along the vector (x,y) the normal is (-y, x)
    • Keep any normal that isn’t parallel to a normal I’ve already found
      • Two lines are parallel if their cross product is 0
    • Project each polygon in the pair onto each normal, producing two line segments per normal
      • This is just taking the dot product between the normal and the start and end point of each line segment, and keeping the min and max over the whole polygon.
    • Take those line segments, and determine if the one corresponding to the second polygon (the only one moving) is moving towards the other line segment
      • If not, they will never collide on that axis
      • If so, the distance divided by its velocity (projected onto the same axis) is the time to collision
    • The minimum time of collision on all axises, if any, is the time these two polygons will collide

I’ve now got both the time and the point of collision working. I’ve decided what I’m going to consider the point of collision is point halfway between the closest vertices and/or line segments of the involved polygons.

This boils down to:

  • I’m given two polygons that are “colliding”
  • For both polygons
    • Enumerate one of their vertices and the others line segments
    • Determine the the closest point on the line segment to the vertex (I based my math on this article)
    • If there is no closest point, move on
    • Measure the distance between the found point and the vertex
    • Take all the vertices (and their paired points) with the smallest distance
      • There may be multiple!
  • If you have no vertices/points, then repeat the above but instead of measuring between vertices and line segments, compare only vertices
  • Average each set of points you found (one set is from the first polygon, one from the other) to create new points
    • Most of the time you’ll only have one, but if you’re in the case where two line segments are parallel and going to collide you’ll have more
  • The point of collision is the point halfway between these two average points

I’ve got some tests for these two separate algorithms covering collisions between different sized square, triangles, octagons, and pentagons. I have yet to stick the two system together into a generic “detect and resolve collisions”-pass, but I’m getting close.

Whelp, sticking them together revealed a real logic error. The algorithm I’ve implemented is reasoning about single axises, so I’m getting phantom collisions whenever two shapes overlap on a normal.

I’ve got some ideas on a fix, which I’ll get to exploring tomorrow.

Continue onto November 5th

Sabbatical Log: November 3rd

This blog series is running about a week behind my actual work, giving me time to clean things up.  The date the actual work was done is in the title, horizontal lines indicate when I stopped writing and started coding.

It’s the weekend, so I’m doing mostly social stuff and not coding. However, I have gotten started on a rough implementation of the Separating-Axis-Theorem with some tweaks to handle polygons in motion. I’m thinking I’ll avoid, at least in the final implementation, floating point and instead do a poor man’s fixed point by scaling everything by a large constant multiple.

I went down something of a rabbit hole on the fixed point representation, as I realized that a lot of the code I’d written for collision detection was using integers… that rapidly rounding to 0, causing explosions.

The most interesting bit on the fixed point representation (which is just a struct wrapped around a long, where the “raw value” is multiplied by 2^20 before storage) has been working out how to implement all the operations:

  • Addition (c = a + b) is straight forward
    • c * 2^20 = a * 2^20 + b * 2^20
  • Ditto for subtraction (c = a – b)
    • c * 2^20 = a * 2^20 – b * 2^20
  • Multiplication (c = a * b) is trickier because
    • a * 2^20 * b * 2^20 = (a * b) * (2^20)^2
    • So I divided by 2^20 at the end to correctly calculate c
  • Division (c = a / b) is likewise tricky, as
    • (a * 2^20) / (b * 2^20) = a / b
    • Even worse, this loses precision
    • So I multiply by 2^20 before dividing, correctly calculating c
    • This can still lose precision at the high end, but I’m expecting most numbers to be much less than int.MaxValue. Perhaps I’ll throw on that case in the future.
  • Square root (c = a^(1/2)) is also rather tricky
    • First, I’ve got to actually implement a square root algorithm without using built-in floating point
    • I stole the iterative algorithm from Wikipedia
    • Using it, I calculate ((2^20) * a)^(1/2) = 2^10 * (a^(1/2))
    • I then multiply by 2^10 to get the desired result.

My implementation seems good to about 3 decimal places, and while I’m sure I’ll have to do some performance work (probably using lookup tables for common square roots) I’m pretty happy with it – I’ve got a small test verifying the above operations.

Continue onto November 4th

Sabbatical Log: November 2nd

This blog series is running about a week behind my actual work, giving me time to clean things up.  The date the actual work was done is in the title, horizontal lines indicate when I stopped writing and started coding.

Starting my second day of sabbatical, I’ve got a moving rectangle.

While there’s a lot going on behind the scenes, exciting this is not.

So my goal for now is to get some actual graphics going.

I’ve written up an AssetManager class that handles loading images (BMP and PNG) and mapping them to MonoGame’s Texture2D instances.

I’m not using the MonoGame content pipeline for a couple reasons:

  • I want to learn about this sort of thing
  • I want to maximize productivity, and allowing resources to be loaded dynamically helps that

Which means that now, not only am I rendering an actual sprite but I can edit the sprite and have it immediately update.

Now I wanna focus on getting a background and a of sorts camera working.

While preparing for camera work, I ended up spending some time optimizing asset loading. Once I was loading in a large map (Kakariko village, 4096×4096 pixels) to use for the background I discovered a few pointless O(n^2) loops where I was converting between pixel formats.

Nothing a little bit of Bitmap.LockBits and Marshal.Copy couldn’t cope with, but it burnt an hour or so of time. But now startup times are snappy again.

I’ve now got a pretty basic camera working. It’s modeled as an entity with position and dimension components, but it isn’t rendered (nor does it accept input). This is the first real chance to see the Entity-Component-System divide work, and I will say it feels elegant. N=2 isn’t exactly enough for me to be confident in it, but so far so good.

One thing that has felt weird is the way I’ve structured the System interface.

And here’s an implementer, CameraSystem.

Structuring the system such that they’re always working on enumerations of entities is conceptually nice, but I’m finding myself with lots of pretty janky foreach loops. In fact, I’ve added a helper to the base class (GetComponentFor in the previous picture) that does the really common “get the only one of these there is out of the enumeration”-task.

Since I haven’t gotten to any systems that operate on multiple entities, I’m not going to refactor just yet – but I’ve noticed the pain point.

Now I’m going to go work on testing the CameraSystem.

I’ve now got all the tests working for the camera system – I found a couple of bugs related to room sizes that were smaller than the “window” into the game. I added another test room to illustrate that the same systems are capable of handling either kind.

At this point it feels like it’s time to start implementing some other entities, probably static obstacles. But to do so I’ve got to implement the first part of a physics system, collision detection. Time to get reading.

Continue onto November 3rd

Sabbatical Log: November 1st

This blog series is running about a week behind my actual work, giving me time to clean things up.  The date the actual work was done is in the title, horizontal lines indicate when I stopped writing and started coding.

I’m on sabbatical for November, and am taking the time to play around with a kind of coding I’ve never dabbled in: Game Dev. I’ve read a decent amount (mostly Gamasutra and forums), watched a lot of videos (GDC and Handmade Hero), and certainly thought about it – but I haven’t actually done it.

I have no delusions of actually finishing this month, or even making something all that fun. I’m just aiming to Learn Me A Thing™.

The first decisions I’ve made are:

    1. What kind of game?
      • A top down action-RPG in the mold of one of my all time favorites
      • I’ve also bought Link To The Past a half-dozen times, so I don’t feel scruples about stealing some assets for this little exercise.
        1. However, I don’t intend to publish the code with assets.
    2. What language am I working in?
      • C#, solely because I like it and know it well. I considered TypeScript and Rust, but while TypeScript is better than JavaScript I still don’t really like working in it and I don’t consider myself proficient in Rust yet.
    3. What, if any, framework am I using?
      • I’m going to use MonoGame.
      • I only want something to handle the blitting of pixels into the screen for me, I intend to implement all other systems myself, and MonoGame looks like it fits the bill.

I guess it’s, time to get to work.

My first focus was on some infrastructure, namely a barebones Entity-Component-System.

I’ve decided that there are basically two “types” of Components (binary/flags and stateful ones), Entities are just id numbers, and Systems work over enumerations of entities having some component. All of entity management bits are wrapped up in an EntityManager class like so

Specifically, the EntityManager class handles:

      • Creating entities
      • Release entities
      • Attaching and removing flag components to entities
      • Attaching and removing stateful components to entities
      • Enumerating entities with specific flag or stateful components
      • Fetching flag or stateful components for specific entities

Since I expect garbage collection to be something of an enemy in this project, I’m keeping allocations to a minimum. For the EntityManager class that means I only allow a fixed number of entities, and a fixed number of stateful components per entity – the required space for tracking both sets is allocated up front, in the constructor. I’m also avoiding all LINQ-to-Objects, and using C#’s duck typing of foreach to avoid allocations during miscellaneous logic.

I’ve also written test cases for this class, and it is my intent to continue to do so for all future code. I’ve read it can be pretty hard to actually test games, so we’ll see how well I can keep to that.

I’ve now implemented enough systems and components to get a box moving on the screen; and it only took ~5 hours of work.

My solution now looks like so

I’ve got some components:

      • InputComponent receives “input” from a player
        • Although I don’t intend for their to be multiple players, this abstraction is nice because it lets me mock input handling more easily
      • PositionComponent holds an X & Y for an entity
        • I’m using subpixels, so this entity also does the conversion (only the subpixels are writable)
      • I also added FlagComponent.Player (my first “boolean” component) to mark the player entity
        • Although I’m also assuring that Id=1 is always the player elsewhere, it feels cleaner to have an explicit marker for the player

My first two systems are:

      • InputSystem, which takes input from MonoGame and updates InputComponent baring entities
        • This actually works off an interface, so it can be mocked. MonoGameHardwareInputAdapter does the actual mapping of GamePadState and KeyboardState to “PressedKeys”.
        • Testing so far is minimal, but still seems workable. For example:
      • UpdatePositionSystem is a temporary system that updates player entities’ PositionComponent based on their InputComponent.
        • All the logic it really does is keeping the player entity inbounds with some hardcoded sizes
        • I consider this temporary because I think it’d be more sensible to model velocity and have player movement handled by the same “physics” that moves everything else

And I’ve introduce a GameState class that wraps around the EntityManager and has an Update(TimeSpan) method which triggers the various systems in the appropriate order. Not putting any of the logic in the Game-derived class makes it easier to test – in fact you can see the creation and use of a GameState in the above test.

All of the above gets us to logically moving the player, but there’s no code for actually drawing it. To solve that, I introduce a FrameStateManager that is used to construct a FrameState which is used is then translated into Draw calls. While I could directly translate GameState into Draw calls, I like introducing an intermediary representation for a few reasons:

    • Once the FrameState is constructed, it’s safe to modify GameState again; so in theory I could get a leg up on the next frame while still rendering the previous one. I doubt that will be necessary, but it’s conceptually nice.
    • Going the other way, constructing a separate FrameState makes it much less likely I’ll accidentally modify GameState as part of rendering.
    • A separate FrameState makes it possible to “record” a play session into a parseable representation, which will hopefully make testing easier.
    • In the age of Twitch, YouTube, and speed running – recording gaming sessions is commonplace. Being able to “record” into something that can then be properly rendered later just strikes me as neat.

Continue onto November 2nd

LinqAF: Release 3.0.0

A new release (3.0.0) of LinqAF is now available on NuGet, and it’s got a decent amount of new stuff.

New Operators

LinqAF 3.0.0 introduces the following operators:

In particular I found myself really wanting ToHashSet() when I was playing around with converting existing projects to LinqAF, practically every project seems to have a homegrown version.

Convenience Methods

IEnumerable<T> is used all over the place in .NET, and in prior versions of LinqAF you’d need to add an AsEnumerable call to call them.  Even worse, some methods (like those on String) take either IEnumerable<T> or object so porting to LinqAF could introduce bugs.

Now LinqAF provides implementations, as extension methods, of the following methods that take all of LinqAF’s enumerables:

Choosing relevant images is hard.

Choosing relevant images is hard.

  • HashSet<T>, ISet<T>, and SortedSet<T>’s
    • ExceptWith
    • IntersectWith
    • IsProperSubset
    • IsProperSuperset
    • IsSubsetOf
    • IsSupersetOf
    • Overlaps
    • SetEquals
    • SymmetricExceptWith
    • UnionWith
  • List<T>
    • AddRange
    • InsertRange

New classes have been added that provide implementations of commonly used static methods, as well as pass-throughs to the normal classes:

  • LinqAFString as an alternative to System.String, providing LinqAF friendly versions of
    • Concat
    • Join
  • LinqAFTask as an alternative to System.Threading.Task, with friendly versions of
    • WaitAll
    • WaitAny
    • WhenAll
    • WhenAny

Additionally, a helper class for calling the constructors of built-in collections has been added, LinqAFNew, which provides methods equivalent to the enumerable consuming constructors of:

  • HashSet<T>
  • LinkedList<T>
  • List<T>
  • Queue<T>
  • SortedSet<T>
  • Stack<T>

Performance Improvements

The biggest change is that RangeEnumerable and ReverseRangeEnumerable are no longer generic, making the performance of anything involving Enumerable.Range() considerably faster as there’s no reflection going on.

The Future

At this point LinqAF is pretty close to feature complete, I don’t think I’ll be adding many more operations.  I am quite interested in increasing the performance of the current operators, while LinqAF is always lower in allocations it remains slower than LINQ-to-Objects for many cases.

Checkout LinqAF on NuGet or GitHub

LinqAF: The (possible) future

This is part of a series on LinqAF, you should start with the first post.

What’s missing from LinqAF?

The number one missing thing is performance.  LinqAF isn’t terribly slow, but it’s not consistently faster than LINQ-to-Objects and there’s no real reason it couldn’t be.  This would take the form of much more extensive profiling, and a likely a decent chunk of unsafe code.

There are also lots of additional operators that could be added.  Operators new to 4.7.1 like Append, Prepend, SkipLast, TakeLast, and ToHashSet or the extensive operators available in packages like MoreLINQ.  While the nature of LinqAF means each additional operator adds significantly to the generated code size, the code generation infrastructure makes it entirely feasible.

There are built-in enumerables that aren’t optimized for, like the Dictionary<TKey, TValue> and SortedDictionary<TKey, TValue> types, because they require more effort as a consequence of having two generic parameters.  It’d be neat to include the immutable collections introduced in .NET 4.5 as well.

What’s missing from C#?


Missing from this blog?  On topic images.

A few changes to C# would make it possible to meaningfully improve LinqAF – ref extension methods, and improvements to generic type inferencing.

In the places where LinqAF does use extension methods (mostly in the numerical operators like Max, Average, and Sum), it’s forced to pass the source enumerable by value.  This entails making a copy of a (potentially quite large) struct, which has a deleterious impact on performance.  It is because of this copying cost that internally LinqAF passes all enumerables by reference.  Ref extension methods, allowing something like static MyEnumerable<TSource> MyOperator<TSource>(this ref TSource source), would prevent this copying.  This feature may make it into a future version of C#, and is presently championed by Mads Torgersen.

The reason LinqAF doesn’t use extension methods more extensively is because of weaknesses in C#’s generic type inferencing.  In a nutshell,

// in some static class
public static WhereEnumerable<TItem, TInnerEnumerable, TInnerEnumerator> 
  Where<TItem, TInnerEnumerable, TInnerEnumerator>(
    this TInnerEnumerable source,
    Func<TItem, bool> predicate
  where TInnerEnumerable: struct, IStructEnumerable<TItem, TInnerEnumerator>
  where TInnerEnumerator: struct, IStructEnumerator<TItem>
{ /* ... */ }

will not successfully be invoked by code like

var e = /* some struct implementing IStructEnumerable<...>
e.Where(i => true);

instead it fails with a CS0411 error (type arguments for the method cannot be inferred).  If this weren’t the case everything except the overrides in LinqAF could be implemented as extension methods, which would drastically reduce the size of the codebase and the final DLL.  The one attempt in this direction that I’m aware of came to nothing due to problems with backwards compatibility.  With compatibility concerns, the increase in complexity, and presumably compile times – I’d be a little surprised if it were done in a future C# version.  That said, LinqAF would benefit from it if it were.

What could be improved?

As mentioned in an earlier post, I’m very interested in alternatives to BoxedEnumerable<T>.  I spent a decent amount of time playing around with a tagged union approach, but could never come up with anything workable.

The RangeEnumerable<T> type being generic over T instead of being bound to int is a blemish.  Fixing this would let me remove the MiscUtil dependency, and would improve the performance of the Range operator. The major stumbling block is that the LinqAF.Generator project assumes all enumerables are generic over T, and Range being an exception would require significant amounts of work.

And that’s it!

This is the end of my series on LinqAF.  Once again, the code is on Github and a Nuget package is available.  Below is a table of contents for easy reference.

Thanks for reading!

Table of contents

LinqAF: Benchmarks

This is part of a series on LinqAF, you should start with the first post.

How is LinqAF benchmarked?

I make use of the excellent BenchmarkDotNet library which makes it easy to profile different configurations, and calculate meaningful statistics.  Concretely, I profile both the legacy x86 JIT and the x64 RyuJit configurations with the concurrent server garbage collector.

I created separate benchmarks for:

  • Each LINQ operator, including different overrides
  • Nullable and non-nullable versions for Average, Max, Min, and Sum
  • Both typed and untyped underlying enumerables for Cast
  • Sized and unsized underlying enumerables for Reverse, ToArray, ToDictionary, and ToList
  • Three actual LINQ uses from the Stack Overflow, Jil, and Roslyn codebases
  • One giant synthetic case that uses very nearly every operator at once

I ran all benchmarks on a machine with the following specs (as output by BenchmarkDotNet):

BenchmarkDotNet=v0.10.9, OS=Windows 10 Redstone 1 (10.0.14393)
Processor=Intel Core i7-6900K CPU 3.20GHz (Skylake), ProcessorCount=16


Cats reacting to poor performance.

My goal with LinqAF was to produce a (very nearly) allocation free implementation of LINQ-to-Objects, and so that is what I focused on when benchmarking – either zero allocations when possible, or fewer allocations than the equivalent LINQ-to-Objects operator.  Ultimately, I did achieve my goal with LinqAF – however, since I didn’t focus on performance, there are plenty of cases where LINQ-to-Objects is faster than LinqAF.

In particular, the following operators are slower in LinqAF than in LINQ-to-Objects:

  • Any (without predicate)
  • Average
  • Cast (if the underlying type is actually an IEnumerable<T>)
  • Concat
  • DefaultIfEmpty (with a parameter)
  • Distinct
  • Except
  • GroupBy
  • GroupJoin
  • Intersect
  • Join
  • Max (for nullable types)
  • Min (for nullable types)
  • OrderBy & OrderByDescending
  • Range
  • Select
  • SelectMany
  • SequenceEqual
  • Skip & SkipWhile
  • Sum (for nullable types)
  • Take & TakeWhile
  • ThenBy & ThenByDescending
  • ToArray (if the underlying type isn’t an IList<T>)
  • ToDictionary
  • ToList
  • ToLookup
  • Union
  • Where
  • Zip

Most of these operations are only a little slower, but Cast is actually quite a bit slower (taking more than twice as much time).  This is because an optimization that is available to LINQ-to-Objects is made impossible by LinqAF’s “everything is a struct”-design.

You can run all the benchmarks on your own by executing the LinqAF.Benchmark project – be sure to build in Release mode, or you’ll get inaccurate results.  A full log of the run I did for this post can be found here – at the end of the file you’ll find all the slower benchmarks, and how much slower they were exactly.

Benchmarking is always fraught with issues – if you have any interesting cases where LinqAF allocates more than LINQ-to-Objects or is incredibly slower I’d be interested in hearing about it.

What’s next?

In the last post in this series, I’ll go over what’s missing for LinqAF as well as what direction future work could take.