Tom's Data Onion - A language a layer

I stumbled across a new programming puzzle on r/programming called “Tom’s Data Onion”. The puzzle (well actually set of puzzles) is built in layers such that solving one layer generates the instructions for the next layer. I’m not going to cover how I solved the puzzles (my solutions are on GitHub if anyone is interested) but instead talk a little bit about the languages I used to solve the puzzles.

I do quite a lot of coding challenges (CodinGame, Reddit Daily Programmer, Advent of Code, etc) mostly because I enjoy them but partly because I see them as a good opportunity to practice langauges I’ve not worked in for a while and also as a way to learn and test out new languages. I thought it would be fun to try and solve each layer of the Onion in a different language (BTW before this I’d never written an ascii85 decoder and now I have about 4 in various states of completeness).

I wanted to use a mixture of languages that had various styles, track records and different sized standard libraries. I ended up using the following:

  • Zig - Touted as a genuine replacement for C, I’ve been messing around with Zig recently and really enjoying its simplicity
  • Rust - Potential game dev language of the future. I’ve not used it in about a year and wanted to make sure I don’t forget how
  • Python - For these types of puzzles you often can’t beat Python for implementation time efficiency. I use Python quite a lot and puzzles can be a good way to probe new areas of the language
  • Go - Like with Rust, I haven’t used Go in a couple of years and wanted to refresh my memory
  • C++ - My bread and butter but I’ve been in C# land alot recently and wanted to brush off any cobwebs
  • Kotlin - Occasionally at work we have to interface with Android in Java. I wanted to explore Kotlin as an alternative to Java and hadn’t had a chance to look at it until now
  • Swift - Similar to Kotlin in that I wanted to evaluate Swift as an alternative to Obj-C and again hadn’t yet had a chance to mess around with it

Sort of in-keeping with what I felt the spirit of the challenge was (i.e. often the puzzle pointed to RFC docs) I was determined not to use any 3rd party libraries but to write the code myself. This also had the benefit of allowing anyone else to run my solutions without external dependencies - however I did allow myself to use any modules from the standard libraries. I know languages like Rust, Go and Python really shine with their support for external modules but I’d made my mind up.

An interesting side effect of using a language per layer when each layer required many of the same techniques (aside from writing about 4 different ascii85 decoders) is that I got a chance to see the relative strengths and weaknesses of the languages for solving these types of problems (mostly file reading/writing and bit manipulation). I thought I’d note down some of my observations about how each language faired for this particular puzzle.

Zig

I’ve only started using Zig recently but the more I use it the more I enjoy it. It’s probably the least well known of the languages on the list so will spend a bit more time outlining why I like it. Part of its ethos is that there is only one way to do something so you don’t get that analysis paralysis that you find with other languages (like Rust and C++). Despite it not having a large standard library, and therefore no off the shelf base85 decoder, (which is fine - I like the lean approach) I found I was able to implement the solution to layer 0 pretty quickly. I think this is largely because you don’t have to think too in-depth about what approach to take.

Even though it has quite a minimal standard library the file reading/writing support was good and as easy to use as any other language. While it is a “safe” language, and doesn’t allow implicit casting willy-nilly, I didn’t find doing low level bit manipulation too cumbersome (@truncate to the rescue). Another thing I discovered about Zig is how easy it is to write and run unit tests with its built in test framework - this was a nice surprise! Also it has Zig fmt so no squabbling over style (which I appreciate more and more as I get older). Plus like most modern lanaguages there’s no need for complex external build programs it comes with its own build toolchain. Something I’d never seen before in a language is that Zig supports arbitrary size integers; this can make bit packing super simple (for example in base64 encoding when you pack to 24 bits you could use a u24). One thing I actually really like about Zig is that it strongly encourages you to use pre-defined stack memory by default. For programs like my puzzle solver I can make very accurate, if not perfect, estimates of how much memory I need because the data is fixed - however I’m not sure how easy it is to use the allocators if the memory requirements weren’t as well defined (but TBH you usually have a good idea of the max memory requirements).

Zig’s documentation is pretty good but not complete and it doesn’t have a large community so not much of a Stack Overflow presence. Despite that I’ve been able to get up and running with it pretty easily; thanks to the existing documentation and the Zig GitHub which has tests and examples to reference. I think my only real gripe with Zig is that it doesn’t have any standard ‘for’ loop syntax. Range based looping is great (and with slices is probably sufficient in 99% percent of cases) but for this type of puzzle work you often need the index of the loop and the ability to increment in multiples of 1 and it feels cumbersome to use a while loop to do that.

Rust

It’s probably impossible not to have heard of Rust. I’m surprised they don’t have cold callers that rock up at your house and tell you to “rewrite all your software in Rust”. But evangelism aside, it really is a powerful language with a great toolchain. As a newbie getting into Rust the documentation is second to none and clippy is a great mechanism for learning Rust idioms on the job (except I will die on the hill that if x == false is more readable and less easily missed than if !x). Despite the evolution of the language, whenever I search for how to do something I seem to always find the most up to date way - this is great when I need to search how to write a file or convert a u32 to a u8 (I’m looking at you Swift!).

As you would expect from a beast like Rust there is a lot of great built-in module support. Particularly for puzzles like this there are useful convenience functions for endianess handling and for packing/unpacking bytes, etc. that can take a lot of the boilerplate away from the developer. Like with Zig the built in testing framework is really great (and useful in puzzles like this to test that my ascii85 decoder worked ok). Curiously, despite me seeing Rust as a C++ alternative, I tend to write my Rust a bit more ‘functionally’ and find myself reaching for iterators more often than not (so my Rust programs look nothing like my C++ one). For puzzles like this which are often very explicitly about manipulating blocks of homogenous data there is nothing quite as satisfying as a functional one liner. I find that writing functionally in Rust is almost as easy as say Python or Scala (sometimes you do have to fight the borrow checker but for a non-GC language the functional support is excellent). Plus having 128-bit integers is great for bit manipulation puzzles!

I think because Rust is multi-paradigm and has a lot of functionality I find that I probably solve puzzles slower in Rust than other languages because I’m trying to find the ‘best’ or most idiomatic way to solve the problem. Despite being very similar to Zig when it comes to type safety I found the explicit truncation casting in Rust much noisier than Zig (which is weird because val as u8 is less text than @truncate(u8, val) - perhaps the infix operator is what makes it seem noisy ¯\(ツ)/¯.

Python

Nothing really beats Python for programming challenges in terms of implementation speed (can’t always say the same for run-time performance). It has a seemingly never ending library of hex functions, base85 and base64 encoders, etc. Despite not being a ‘systems’ language the bit manipulation and packing (using struct) is pretty good - especially if you need to be explicit about endianess.

I think my main concerns with using Python for the Onion (and other similar challenges) is that you are never quite sure how big your int actually is or whether it has been implicitly converted to a float. Sometimes I want a 16bit int and I don’t want it to expand but TBH the variability of the number type never gave me any problems for layer 2. I think writing solutions of this size are about as large as I’d ever want to write with dynamically typed languages.

Go

Go shares that same great trait as Zig in that there is no debating about how to go about implementing something - you really only have loops, conditionals and functions. I was also pleasantly surprised by how good the std lib was with encoding, decoding and file reading/writing functions (was particularly surprised that it had base85 decoding)

Similarly to Zig I was able to get up and running really quickly and again no real hesitation about the best way to tackle the problem. The documentation was really helpful and, like with Rust docs, having an API doc as well as tutorials and examples is great for finding out what functions are available.

Rust, Zig and Go have error handling approaches that really appeal to me (i.e. error returns). However with Go the error handling can get quite cumbersome and generate a lot of boilerplate code. Quite often (in fact almost always) when I’m writing puzzle solving code I don’t expect to gracefully handle any errors because I control the whole pipeline so usually an error is my error and I just want to terminate. My Go script is littered with if err panic and I feel like Go could do with a force unwrap (like Rust, Zig or Swift).

C++

C++ is C++. For a number of years I was lost in the wilderness of “modern C++” but now I tend to use more vanilla (non standard library) C++ and dip into std when there is something that I need (like threads or file loading). You really can’t beat C++ for certain types of puzzles (knowing how the types work and being able to easily and implicitly cast between them can make the code much easier to read). I actually picked the order of the languages before I saw the puzzles so it was quite fortuitous that the wheel landed on C++ for this one because C++ has the great ability of being able to easily view data through different lenses (where other languages tie the memory too tightly to types). In this particular layer the same block of memory had to be parsed into a header struct (containing length, etc) and also iterated in 2 byte chunks in order to calculate a checksum. This is pretty trivial in C++ just by changing the pointer type and iterating - no need to wrap or copy.

Of course all this convenience comes at a cost and when I ported my C++ ascii85 encoder to Kotlin it caught a bunch of overflow errors! A couple of things that annoyed me with C++ for this particular puzzle was a) there isn’t a standard way to prevent struct padding so you can’t safely reinterpret memory as a struct (which would have been great for reading the header) and b) There isn’t any built in endianess handling so I just had to assume little endian and byte swap the network order data. I think being able to reinterpret memory safely as a struct and at the same time swap endianess if needed would make these puzzle solutions much simpler. The other thing about C++ when compared to all the other languages here is the lack of default toolchain - sticking with clang/LLVM always seems the best approach for me.

Kotlin

Ideally I would have used Kotlin Native but the particular layer I used Kotlin for required some AES decryption and I had to leverage the weight of the JVM libraries.

There isn’t too much to say about Kotlin that hasn’t already been covered by the other languages. It’s documentation was good and I really liked the iterator support and despite my worries about how much of a PITA bit manipulation would be, because of how strict Java is, it wasn’t too bad (obviously there was a lot of explicit casting and I had to keep correcting to the non-standard bit operation syntax shr, shl, etc). I’d really like to give Native a try in future.

One of the little things that caught me out with Kotlin - why is 0..N an inclusive range when in every other language that is exclusive? 0 until N is more cumbersome and is by far the more common case right?

Swift

Initially the puzzle only had 5 layers so I had a toss up between Kotlin and Swift to see which one I would use. I chose Kotlin because I was worried about having to introduce a dependency on the Xcode toolchain and I wanted to keep the solutions as standalone simple scripts. Thankfully it is actually easy to build and run Swift scripts independently from the command line.

Swift has a lot of the same plus points as the other modern languages I’ve listed - strong typing, nice error handling, etc. However of all the languages I used (bearing in mind I used Zig which has a small community and Rust that has had several breaking evolutions) I didn’t expect Swift was going to the hardest language to pick up - but it was by far! For some reason it seems to be really difficult to find up to date documentation for Swift. I kept finding no longer supported solutions for previous versions. The first party tutorial site was pretty good for grasping the basics but that was it. I found it really hard to find how to read/write files or how to convert bytes to strings (ASCII or UTF-8). I think part of the problem is because Swift and Apple are so linked and there is toll-free bridging with Obj-C libraries it can often be hard to figure out where Swift stops and Cocoa/Foundation/etc. start. FileManager is a carbon copy of the one for Obj-C and has the same PITA hoops regarding URL, document directories, etc to jump through just to read or write a file (feels like there should be a lower level File API implemented in Swift that FileManager wraps).

A couple of things that really killed me with Swift: 1) Why do slices keep the same indices as the underlying array? When is that ever useful? 2) When running from command line without the power of Xcode any crash logs were unsymbolised (and didn’t point to a line number) this wasn’t the case for any of the other languages.

Conclusion

There isn’t really anything profound in this doc. I picked the order of the languages at random so I think that shows you could really make any of them work for puzzles like this. It was just interesting to get a sense of the frustration points for each language on a mini-project. It was nice to try our Kotlin and Swift but I don’t think I’d use them out of anything but necessity - simply because I’d probably use Rust instead. For quick single script puzzles in particular having to symbolicate the crash logs is a bit of a pain with Swift. Kotlin still seems to be in the process of separating from the JVM so perhaps I’ll try again in a couple of years. It’s nice to see some of the same patterns emerging across the modern languages - built-in toolchains, auto-formatters/linters, built-in test frameworks, immutable by default, return based error handling, etc. If I find time perhaps I’ll go back through the layers and thread anything that can can be done so trivially to test out the relative threading capabilities and I’m definitely going to keep messing around with Zig.

If you haven’t had a bash at Tom’s Data Onion I’d encourage you to do so - but perhaps just re-use the same ascii85 decoder.

Keep world abstractions out of the type system

Something that I see farily frequently, particularly in OOP codebases, is programmers bringing real-world or design-world abstractions into the type system. Type systems in statically typed languages are useful but very inflexible and introducing the wrong types can make the type-system work against you. I find that often people work around this with interfaces or inheritance but I believe these are sticking plasters that introduce additional complexity at the cost of comprehension (and flexibility) and that the problem is best solved at the root.

Example

Here is a paraphrased example that I came across recently:

The game had a central character that the player could upgrade by unlocking new items (upgrades) and applying them.

class Upgrade
{
	int GetHealthUpgradeAmount()
	int GetAttackUpgradeAmount()
	int GetDefenceUpgradeAmount()
}

class CharacterStats
{
	void ApplyUpgrade(Upgrade upgrade)

	Upgrades[] m_upgrades

	int m_baseHealth
	int m_baseAttack
	int m_baseDefence
}

There was also a feature that triggered events that had time limited impacts on the character stats - the designers referred to these as Mod Events.

class ModEvent : Upgrade
{
	float GetDurationSecs()
}

class CharacterStats
{
	void ApplyUpgrade(Upgrade upgrade)
	void ApplyModEvent(ModEvent modEvent)

	void RemoveExpiredModEvents()

	Upgrade[] m_upgrades
	ModEvent[] m_modEvents

	int m_baseHealth
	int m_baseAttack
	int m_baseDefence
}

Finally there was a ‘trait’ feature where the character stats were increased or decreased based on who they were pitted against.

class Trait : Upgrade
{
	//Had stuff specific to traits like names but they aren't important for this example
}

class CharacterStats
{
	void ApplyUpgrade(Upgrade upgrade)
	void ApplyModEvent(ModEvent modEvent)
	void ApplyTrait(Trait trait)

	void RemoveExpiredModEvents()

	Upgrade[] m_upgrades //Including traits
	ModEvent[] m_modEvents

	int m_baseHealth
	int m_baseAttack
	int m_baseDefence
}

The approach above perhaps doesn’t seem too bad, and in this case the actual impact on the codebase was fairly minimal (I’ll cover it in a second), but I think when we reach for inheritance (and I don’t want to get into an explanation here of why inheritance is a bit of a code smell) it is usually because we’ve made sub-optimal decisions earlier on.

Splitting along data usage boundaries

I think root of the problem is conflating actual differences in usage with conceptual differences influenced by the world (in this case the game world). Where something comes from doesn’t necessarily fundamentally change what it is. If we look at Upgrades, ModEvents and Traits the only actual difference between them (besides where they are applied) is that one of them is time-limited. You could argue that the time-limitation isn’t actually a property of the type but of the context and if you follow that logic and think about what the data is, where it is stored, read and written (i.e. how it is actually used) and split along those lines (and in keeping with the original structure) you would probably end up with something like this:

struct StatMod
{
	int m_id
	int m_healthMod
	int m_attackMod
	int m_defenceMod
}

struct TimeRemaining
{
	int m_id
	float m_timeRemaining
}

class CharacterStats
{
	void ApplyStatMod(StatMod statMod)
	void ApplyTimeLimitedStatMod(StatMod statMod, float durationSecs)

	void RemoveExpiredStatMods()

	StatMod[] m_statMods
	TimeRemaining[] m_statModTimers

	int m_baseHealth
	int m_baseAttack
	int m_baseDefence
}

Having a single type now gives you the flexibility to group or categorise to best meet the usage and not by some arbitrary conceptual difference. For example if you need to display the total affect of all mods to the player (which is exactly what the game needed to do: e.g. "Attack 7 (+7)") you can store all the StatMods in one array and sum them. If instead the design changed so the complete breakdown is displayed to the player (e.g. "Attack 7 (Upgrade +6) (Trait -2) (Power-Up +3)") you could go back to storing each conceptual type in a different container. Essentially the name of the variable can be used to represent the context.

By splitting the data along usage boundaries it is trivial to evlove the codebase as the design evolves. We can easily make certain upgrades time-limited or we can support the ability for upgrades to have names (just by associating them with an id) without having fundamentally change how mods are applied.

Think about what types are being introduced

If you think about the most successful types they aren’t influenced by their context. An integer doesn’t have to change type based on whether it represents an age or a number of sandwiches (int m_age, int m_numSandwiches). What’s the difference between a stool and table - functionally nothing, they are both raised surfaces and making a distiniction between them makes it difficult to treat them the same whenit is best to do so (what if I want to sit on the table). Introducing new types into the program should be thought out carefully and always along the lines of how the data is used and not based on real world naming which, if English is anything to go by, is messy, inconsistent and often not helpful.

We're not building The Matrix

I love a good tech structure discussion at work and there’s one that’s been rumbling on and off for years that prompted one of my colleagues to exclaim the phrase that became the title of this post – “We’re not building The Matrix”. The debate is about how much autonomy an object/entity/game object/component should be given and ultimately how to structure the logic of a program.

Autonomous Monty

Firstly let me clarify what I mean by autonomy; the level of autonomy of an object is a measure of its ability to take decisions and to execute code based on those decisions. Let’s use the example of a simple 2 state enemy AI guard (called Monty). Monty has the following states and behaviour:

  1. If Monty cannot see the player he is patrolling.
  2. If he sees the player, he is attacking.

If Monty is designed autonomously he is responsible (by him I mean the code that comprises the entity “Monty”) for checking if he can see the player and for taking the appropriate action. Now it doesn’t matter if this behaviour is coded directly into the entity or whether the behaviour exists via components attached to the entity or any other way we wish to build Monty; ultimately Monty has been given the ability to make a decision (execute code) based on whether or not he can see the player. There is a certain allure with this type of design as it maps quite nicely to how people operate in the real world, however I believe (as did my colleague who made the Matrix reference) that building programs this way quickly leads to control flow issues, lack of flexibility and fragile codebases.

Through the Keyhole

For the rest of this post let’s assume that Monty is a single MonoBehaviour attached to a Unity GameObject and that he has his own update loop (called by Unity when the GameObject is active) that runs his behaviour. The problem is that up until now we have been considering Monty almost in isolation (my colleague describes this rather brilliantly like “programming through a keyhole”)…

Monty in isolation

…but if we think about the bigger picture…

Monty and friends

…Ok. So Monty has a bunch of mates who are also guards. This makes sense “where there’s one there’s many” right? Let’s add some complexity and see how our structure holds up:

Complexity modifier 1: The game designer slides over and tells you that the player can now become invisible and when invisible cannot be seen by “Monty” or any of his patrolling pals. You’re not worried, Monty can handle this:

Monty already has access to some of the player state right? At the very least the player position in order to decide whether he can see the player or not. We can just give Monty access to the data that states whether the player is invisible or not and use that to influence his decision – job done, ticket closed. However something rankles a bit because the player is invisible to all patrollers and yet all of them are now checking every update loop whether the player is invisible or not. Never mind it’s not that big of a deal.

Complexity modifier 2: The designer enters stage left and whispers in your ear that the player now has a flash-bang grenade that when deployed will disable guards and allow the player to be “invisible” to any guards in an unspecified radius for an unspecified time period. Hmm, a little more tricky:

Ok, so we subscribe Monty and his friends to an event that is triggered whenever the player uses a flash-bang. Monty can then check if he is within the unspecified radius and start a timer during which he will consider the player invisible. Seems pretty elegant.

Complexity modifier 3: The designer apparates behind you and declares that focus tests have found that the flash-bang is too powerful and has made the game too easy. It is being swapped out for a “McGuffin” which is a new weapon that will fire sleeping darts at the closest 2 guards – same result as the flash-bang, the player will be invisible to sleeping guards for a certain time period.

No problem, clickety-clack of the keyboard and Monty now knows about all his friends and their locations and they all know about him and they all listen to the event on the player and when the event is triggered they all calculate who is closest to the player and two of them come to the conclusion it is them and put themselves into the “sleep” state and start their timers, right?

Making Informed Decisions

Okay so that’s a bit of a contrived example and no-one would really design a system in that way surely? Let’s make it simpler, let’s pretend that Monty isn’t a hotshot, AI guard but instead a humble UI button (well he is a MonoBehaviour that exists on a UI object that has a button component and is hooked up to the button click event – but you get the gist). Monty has one job; when he is pressed he presents a pop-up to the user – simples. Monty is very good at his job, every time he is pressed he dutifully presents his pop-up. Doesn’t matter if another pop-up is already being shown, doesn’t matter if the player is mid-tutorial and Monty just happens to be on-screen, doesn’t matter that he might break the game flow. It’s not Monty’s fault, it’s not that he doesn’t care, it’s that he doesn’t know!

All jokey examples aside, that is why this kind of autonomous programming is bad. How many projects have you worked on where an object took some action that broke the program flow because the object did not first check the state of the program before modifying it in some way (a la the Monty button)? Or when game rules end up scattered throughout the codebase with everything having access to the state of everything else and coupling turned up to 11?

In order to make a correct (informed) decision the object making the decision must have access to all the information. In the weapon example that information is the location of the player and the location of all guards. In the UI example it is the awareness of the state of the application and whether it is in a tutorial or whether a pop-up is already displayed (and what the rules are – do we delay showing our pop-up, do we hide the existing one, do we appear over the top?). We can give the autonomous objects access to that information but these objects then become large complex beasts, full of state checks and decision flow logic that is really above their pay grade. Not to mention getting access to that data can be tricky (how does Monty get access to the locations of all the other guards?).

Programs are typically structured as hierarchies – think about the basic Unity structure:

But having a hierarchy alone is not enough unless the decisions are made from the top (even if you add a “GuardManager” to the above example, that creates and holds references to all guards, it doesn’t help the flow if the guards are still calling the shots). The hierarchy should not just represent ownership, it should also reflect the flow of code execution. Think about any corporate structure, you might make suggestions to your boss but the decision on what you should work on is his/hers to take because he/she has access to the bigger picture. This repeats all the way to the root of the hierarchy, decisions should be taken by those who have access to all the information, if you only have access to some of the information and still take a decision (like poor Monty) then that’s when issues arise.

Control from Top to Bottom

Autonomy is an illusion because looking back over the code you can clearly see the constraints placed on autonomous objects by the rules of the application (e.g. “Don’t attack the player if he is invisible”, “Don’t show a pop-up if one is already showing”). When structuring a program, information can flow in the direction from the leaves to the root (“I’ve spotted the player” or “I’ve been clicked”) but execution of state manipulating code should always come from the direction of the root to the leaves (“Attack the player”, “Go to sleep” or “Show/hide a pop-up”). Doing this makes it easier to implement more complex logic rules that operate on a set rather than a single object (e.g. only put 2 guards to sleep, make the guards split up to flank the player’s position, queue a new pop-up until the other one has been dismissed). If we restructured the guard example above to defer all decisions to the “GuardManager” then we have no trouble implementing the “McGuffin” weapon; as the manager can easily determine the closest 2 guards to the player and notify them to “go to sleep”.

I feel that Unity (and despite my protests ChilliSource) encourage this kind of autonomous structure by giving entities/game objects update loops tied to the scene rather than an owning system. If we want to stop updating all guards we have to disable them all rather than just not updating the GuardManager that in turn doesn’t update the guards. We are encouraged to think of entities like self-contained actors in the world rather than as data/state in a system. If we want to use composition to build complex behaviours we can and we should; but choosing when to execute those behaviours is not the domain of the entity. The guard entity is really nothing more than data – a position and a state, if we choose to add methods for manipulating that state (e.g. move to, go to sleep, attack, etc) into the guard entity for syntactic sugar then fine as along as those methods don’t affect any state other than the internal state of the guard. If the guard wishes to attack the player he may pass information up the chain stating that he has attacked (or rather wishes to attack) the player but it is not the guard’s responsibility to remove health from the player directly (what if the player has a shield? What if the player is invincible during the tutorial?). The alternative is to add even more state to the guard and to toggle that state based on the state of the program (e.g. the tutorial is active so Monty you are blind until told otherwise) and that leads to even more complex objects.

Some Rules

Here is the crux of the above distilled into rules that I try to follow when structuring a program:

  1. A system (I’m using the term system as a catch-all for logic and state) should only directly manipulate its internal state (in our example the GuardManager is a system and the guards are its internal data). Never change core state when you can’t see the bigger picture and never bypass the team leader and ask his/her team to do something directly – that’s bad form (and the lead (e.g. GuardManager) may know of rules or have access to information that the boss doesn’t!).

  2. If a system wishes to manipulate state external to it (i.e. show a pop-up, decrease the player’s health, etc.), then it must make a request up the tree to do so (remember information flow is bi-directional).

  3. Code (especially when it manipulates core state) should be executed by systems that have all the information (as specified by the application rules). These systems deal with the requests that are passed up the tree to them.

And that’s it. By ensuring that the flow of the application goes from the root to the leaves we have made it easier to apply game rules, enable/disable entire branches of the program and to perform operations on groups of data. Hopefully we also reduce bugs caused by mismanagement of game state. Ultimately when programming we have full control of the flow, rules and data of our programs why would we want to mimic the real world and all its problems? Unless, of course, we were building The Matrix.

What were you thinking?

One of the interesting things about keeping a blog is reading back over your old posts. It’s a bit like coming across old code, sometimes I read things that I’ve written and find myself disagreeing with my past self, other times I cringe at how naive I was or at my lack of understanding of the subject matter. Those feelings often prevent me from writing or publishing new posts because I worry what others will think or what I will think in the future. It’s funny because there is no better indicator of self-improvement than looking back and realising how little you knew and it will probably be far more worrisome the day I look at old code and cannot see any room for improvement.

I’m sure everyone experiences that kind of retrospective cringe and there probably isn’t much you can do about it. The one feeling that you can tackle is guilt. I’m wracked with professional guilt. I feel guilty for not keeping my blog up to date and I feel guilty for not finishing any of the dozens of side projects I’ve undertaken over the years. I read blog posts saying how important it is to finish what you start and to get it out to the community, how you should finish one project before starting on another and what not finishing projects says about you as a developer. Ultimately I’ve decided to stop feeling guilty because 1) there’s more to life than programming and 2) who can be bothered? Seriously, who can be bothered nudging UI around the screen until it’s pixel perfect or adding dozens of audio queues or tracking down a crash bug on one particular device running some custom flavour of a really old Android version. If you want to do all that in your spare time then I applaud you; but frankly I do enough of that tedious stuff day-to-day at work. I don’t need to prove I can finish games in my spare time because I finish and ship games as a day job.

What I want to do in my spare time is have fun. I enjoy programming and I enjoy tackling new challenges. The best thing about programming at home is getting a chance to do something you wouldn’t do at work. Once you’ve solved the problem and completed the challenge, why bother with all the other stuff required to make it into a product. Here’s a list of some of the stuff that I’ve done in my spare time over the last year:

  1. Implemented a half finished top-down racer in Pico-8 (just to see what programming on the Pico-8 was like).
  2. Started learning functional programming and wrote a program that simulated turns of a simple battle game (with no graphics).
  3. Started writing a Gameboy emulator (to see how different it was from the Chip-8 one – turns out quite a bit different).
  4. Solved like half the puzzles on CodinGame using C, C++, Python or Scala.
  5. Wrote an AI bot to compete in one of those online battles (I won a couple of fights and lost a couple of fights but I was more interested in finding out how to host that kind of thing).
  6. Wrote a Python script to play Countdown (worked well for the letters but couldn’t always get the best number).
  7. Ported some of my early programming attempts from OOP to data oriented.
  8. Learned how they implemented the fire in Far Cry 2 and replicated it (without any visuals or actual fire).

The point of all these projects was to have fun and learn something new. Often the learning outcomes made me a better and more effective programmer in my day-to-day work, but some of the stuff I learned I’ll probably never use again – and you know what? I knew that at the time! It wasn’t the point.

So I’m not going to feel guilty for not finishing stuff or for having 6 projects on at the same time. However what I will do more of is blog about, and put on GitHub, some of my half-finished, half-baked projects, if for no other reason than so I can look back in 5 years and say of my past self “What were you thinking?”.

P.S: This should hopefully kickstart a run of blog posts about things that have been rattling round in my head for a while, but if it doesn’t then so what?

ChilliSource Chip-8 Emulator

Getting started…

I’ve long wanted to write an emulator for one of my childhood consoles either the Master System, Mega Drive or Gameboy, and recently worked up the energy to get started on one. I had a rough idea how to create an emulator but rather than cracking on foolishly with a more complex console, most emulation sites recommend starting with a Chip-8 emulator - so that’s what I did.

C8 Brix

Chip-8 is not a physical machine but a virtual machine with an interpreted language. It is a very basic machine with only 2 colour graphics, 4k memory, 16k stack, 17 registers, 2 simple timers and 32 opcode instructions. Chip-8 has none of the features found in more complex consoles such as interrupts, sprites, memory banking, etc; and is therefore a good machine to use to learn about emulation. There are also a few game available freely online such as: Pong, Space Invaders, Breakout and other classics.

I’m not going to write in-depth about how to create a Chip-8 emulator, as plenty of good information can be found online:

Instead I’ll write about how I used Chilli Source to create this and point out some of the areas that tripped me up.

Getting the timings right…

When emulating a system, it is vital that execution and update timings are spot on. Unfortunately the Chip-8 specs are pretty vague on what these timings should be. Lots of reading around suggests that the timers and screen refresh run at 60Hz and the CPU executes either 60 or 600 opcodes per second. Let me tell you, I tried running at 6o opcodes and it was like pulling teeth, so I’d recommend going with 600.

In Chilli Source it is pretty easy to regulate update speed to 6o FPS by setting 60 as the preferred FPS in App.config and Application’s fixed update interval to 1/60. Then, in order to ensure the correct number of updates are performed, use OnFixedUpdate inside a state to drive the timers, graphics and the CPU’s fetch, decode and execute cycle:

void Chip8State::OnFixedUpdate(f32 in_dt)
{
    if(m_paused == false)
    {
        m_keyboard.UpdateKeyStates(m_state);
        m_cpu.FetchDecodeExecute(m_state);
        m_renderer.Draw(m_state);
    }
}

The above code ensures that the application runs at 60Hz but more is required to ensure the CPU executes 600 opcodes per second:

void Chip8CPU::FetchDecodeExecute(Chip8MutableState& inout_state)
{
    for(u32 i=0; i<Chip8Constants::k_opcodesPerUpdate; ++i)
    {
        auto nextOpCode = FetchNextOpcode(inout_state.m_memory, inout_state.m_programCounter);
        auto action = Decode(nextOpCode);
        //Execute decoded action which will change the chip state.
        action(inout_state);
    }
    //Timers are updated at 60Hz independently of opcodes.
    inout_state.m_delayTimer = UpdateTimer(inout_state.m_delayTimer);
    inout_state.m_soundTimer = UpdateTimer(inout_state.m_soundTimer);
    if(inout_state.m_soundTimer > 0)
    {
         CS_LOG_VERBOSE("Beep!");
    }
}

Pretty straightforward, if we know that this method executes 60 times per second then we should execute 10 opcode each time (in more complex systems this can be made more accurate using the opcode execution times from the specs).

Getting the CPU to do something…

The articles I linked to above cover opcode instructions pretty explicitly so I’m not going into detail about how to decode opcodes or what each opcode does (which is usually manipulating register data), however most the tutorials I have found online use a giant, nested switch statement to handle each opcode - this is less than ideal as it makes testing of each opcode messy (and you will need to test each opcode I can tell you).

Opcodes operate on graphics memory, standard memory, registers, the program counter and the stack; these can be combined into a struct and effectively hold the entire state of the VM. Creating a standardised opcode function signature that takes and manipulates the state allows each opcode to be implemented as a standalone function:

//Clear the screen
void x00E0(OpCode in_opCode, Chip8MutableState& inout_state)
{
    std::fill(std::begin(inout_state.m_graphicsMemory), std::end(inout_state.m_graphicsMemory), 0);
    inout_state.m_shouldRedraw = true;
    inout_state.m_programCounter += 2;
}
//Jump program to NNN
void x1NNN(OpCode in_opCode, Chip8MutableState& inout_state)
{
    inout_state.m_programCounter = C8_MASK_NNN(in_opCode);
}
//Jump to NNN and push the stack (call subroutine)
void x2NNN(OpCode in_opCode, Chip8MutableState& inout_state)
{
    inout_state.m_stack[inout_state.m_stackPointer] = inout_state.m_programCounter;
    ++inout_state.m_stackPointer;
    inout_state.m_programCounter = C8_MASK_NNN(in_opCode);
}

Now that each opcode has a functional representation it can be mapped to an opcode hex value and whenever that value is interpreted the correct function can be called. Opcodes are mapped on the first nibble i.e. 0x2000, 0x3000, etc. Rather than using a map or dictionary to pair the functions with the correct opcode I used an array and filled all the blanks in with an error function should an unknown opcode be executed:

//Fill with NoOps which are called for missing or unknown instructions
std::fill(std::begin(m_opcodeActions), std::end(m_opcodeActions), CSCore::MakeDelegate(&OpCodeActions::NoOp));
m_opcodeActions[0x00e0] = CSCore::MakeDelegate(&OpCodeActions::x00E0);
m_opcodeActions[0x00ee] = CSCore::MakeDelegate(&OpCodeActions::x00EE);

This isn’t the full story as some opcodes share the same first nibble, for example 0x8FF0, 0x8FF1, etc, and therefore will both fall through to 0x8000. 0x8000 is a routing function which checks the remaining bytes and routes to the correct function. Other routing functions include 0x0000, 0xE000 and 0xF000.

Ultimately this means there are at most 2 look-ups to find the correct function to call for an opcode.

Getting something on screen…

The Chip-8 has a resolution of 64x32, which is pretty small. Most tutorials recommend using glDrawPixels to blit to screen. This isn’t very platform agnostic so I prefer a more brute force approach that makes use of modern GPUs abilities to devour vertices - I create a sprite for each pixel.

Firstly I create an orthographic camera with viewport size 64x32 (in Chilli Source this defaults to fill the screen or window; this is what I want but obviously loses the aspect ratio). I then create 1x1 sprites tiled to fill the entire screen and set them to invisible. I set the scene clear colour to the desired background colour and each sprite to the desired foreground colour (in this case a garish fruit salad palette) and then simply hide and show sprites based on the graphics memory state (e.g. if gfx[1, 2] == 1 then sprite[0, 2] = visible). Simple!

Getting user input…

Weirdly the Chip-8 has a hex keyboard (yep. 16 keys labeled 0 - F). Feel free to map these to a QWERTY keyboard any way you wish but I chose the following and used the Chilli-Source keyboard system to fetch the user input:

void Chip8Keyboard::UpdateKeyStates(Chip8MutableState& inout_state)
{
    if(m_keyboard != nullptr)
    {
        inout_state.m_keyState[0] = (u8)m_keyboard->IsKeyDown(CSInput::KeyCode::k_num1);
        inout_state.m_keyState[1] = (u8)m_keyboard->IsKeyDown(CSInput::KeyCode::k_num2);
        inout_state.m_keyState[2] = (u8)m_keyboard->IsKeyDown(CSInput::KeyCode::k_num3);
        inout_state.m_keyState[3] = (u8)m_keyboard->IsKeyDown(CSInput::KeyCode::k_num4);
        inout_state.m_keyState[4] = (u8)m_keyboard->IsKeyDown(CSInput::KeyCode::k_q);
        inout_state.m_keyState[5] = (u8)m_keyboard->IsKeyDown(CSInput::KeyCode::k_w);
        inout_state.m_keyState[6] = (u8)m_keyboard->IsKeyDown(CSInput::KeyCode::k_e);
        inout_state.m_keyState[7] = (u8)m_keyboard->IsKeyDown(CSInput::KeyCode::k_r);
        inout_state.m_keyState[8] = (u8)m_keyboard->IsKeyDown(CSInput::KeyCode::k_a);
        inout_state.m_keyState[9] = (u8)m_keyboard->IsKeyDown(CSInput::KeyCode::k_s);
        inout_state.m_keyState[10] = (u8)m_keyboard->IsKeyDown(CSInput::KeyCode::k_d);
        inout_state.m_keyState[11] = (u8)m_keyboard->IsKeyDown(CSInput::KeyCode::k_f);
        inout_state.m_keyState[12] = (u8)m_keyboard->IsKeyDown(CSInput::KeyCode::k_z);
        inout_state.m_keyState[13] = (u8)m_keyboard->IsKeyDown(CSInput::KeyCode::k_x);
        inout_state.m_keyState[14] = (u8)m_keyboard->IsKeyDown(CSInput::KeyCode::k_c);
        inout_state.m_keyState[15] = (u8)m_keyboard->IsKeyDown(CSInput::KeyCode::k_v);
    }
}

Getting it to make some noise…

The Chip-8 can only make a single, annoying, beep. If you check out the code in the timing section you should see that there is a sound timer that counts down at 60Hz. A couple of the online references get this wrong and it tripped me up too - the specs state that while the timer is greater than zero the beep plays. Not when the timer reaches zero, which is what a few of the online tutorials do. This makes things slightly harder as you have to either find a looping beep sound or a beep sound that’s duration is greater than 4.25 secs (timer max. is 255 and one is deducted 60 times a second) and then stop and start it based on the sound timer.

Getting the source code…

Now that I have cut my teeth on the Chip-8 I’ll move onto something a bit more meaty - probably the Gameboy or Master System. I’m going to finish off the Chip-8 emulator by adding a ROM picker and pause/reset buttons with the CS UI system.

Feel free to browse through the source code to check out how to implement all the opcodes CSChip8Emulator