Planet Maclab

April 17, 2022

Josh

1² + i² = 0²

Mathematical joke playing on the Pythagorean Theorem and imaginary numbers

Observe the above mathematical joke. Really breathe it in - enjoy it. Feel free to click through to the Wikipedia article it came from. I’m about to explain the joke, and explaining a joke is how you ruin it. So enjoy it now while you can.


A key motivation of algebra is the solution of problems in geometry, but sometimes the working, or even the answer itself, is strange. Imaginary numbers are great examples.

I tweeted that there was a way to draw the triangle such that it made sense. Before I get to that though, I will need to provide a small amount of background. I’m going to ignore most of Philosophy of Triangles and, without backing evidence or additional explanation, skip straight to this unusual definition:

Definition 1: A triangle (of lengths a, b, and c) is a shape that can be traced by the following algorithm:

  1. Go forward a units of length.
  2. Turn left (by some angle not specified).
  3. Go forward b units.
  4. Turn towards the starting point.
  5. Go forward all the way to the starting point, and no further (c units).
A triangle

A right triangle is usually defined to be a triangle where two of the sides are perpendicular (at right angles to one another). Instead, I will repeat the unusual definition above with a key detail.

Definition 2: A right triangle (of lengths a, b, and c) is a shape that can be traced by the following algorithm:

  1. Go forward a units.
  2. Turn left by 90 degrees.
  3. Go forward b units.
  4. Turn towards the starting point.
  5. Go forward all the way to the starting point, and no further (c units).
A right triangle

The Pythagorean Theorem applies to right triangles:

Theorem (Pythagorean Theorem): For any right triangle of lengths a, b, and c, $$ a^2 + b^2 = c^2. $$ (Proof omitted for brevity.)

Now, you may be wondering why I chose an unusual, yet still understandable, definition of a right triangle above. To understand the joke, we need to deal with an imaginary amount of length. To understand imaginary length, we need the intermediate step of understanding negative length, because the foundational equation of imaginary numbers is that \( i^2 = -1 \). Fortunately, the definitions above make “negative length” easy to deal with: “go forward -x units” can be treated as “go backward x units”. But walking backwards is hard for some people, so for the sake of accessibility I will break it down even further.

Note that every negative number -x is the product of -1 and a positive number x: \( -x = (-1)x \). Therefore we can factorise the step “go forward -x units” into two sub-steps: the “-1 part”, followed by “go forward x units”, and to avoid “going backwards”, I will make “the -1 part” to mean “turn left 180 degrees”.

For example, “go forward -2 units” really means “turn left 180 degrees then go forward 2 units”, and reality is once again rescued from the jaws of nonsense geometry.

Negative length

And guess what? The Pythagorean Theorem still holds, because \( x^2 = (-x)^2 \) for any length x! Hooray for the ancient Greeks!

Back to imaginary length. What does it mean to “go forward i units”?

Well, i really means i times 1, so analogously with the above, we need to factorise the step “go forward i units” into two sub-parts: “the i part”, followed by “go forward 1 unit”.

What’s “the i part”? Consider the foundational equation of imaginary numbers: \( i^2 = -1 \), or said another way, we can factorise -1 into i times i. “The -1 part” above was “turn left by 180 degrees”, so, factorising that into two sub-steps, we need something that, when done twice, is the same as turning left 180 degrees. It follows that “the i part” must be “turn left by 90 degrees”! Thus “go forward i units” means “turn left 90 degrees and then go forward 1 unit”.

Imaginary length

Armed with this information, I can now provide a more accurate drawing of the right triangle from the joke, as traced by the algorithm (a right triangle of lengths 1, i, and 0):

  1. Go forward 1 unit.
  2. Turn left 90 degrees.
  3. “Go forward i units”, i.e. turn left 90 degrees (again) then go forward 1 unit.
  4. Turn towards the starting point.
  5. Go forward all the way to the starting point, and no further.

(Proof that step 5 traverses 0 units of length is left as an exercise to the reader.)

The joke triangle, correctly rendered

April 17, 2022 06:39 AM

April 14, 2022

Josh

Ghosts

Scene: The Internet, late 2015. Two computers are talking via HTTP.

Computer 1: “Hello friend! Can I have /?feed=atom please?”

Computer 2: “Yes, here you go. Stay in touch! 😄”

Almost exactly 90 minutes later, they have almost the exact same conversation.


This blog has feeds, in three different flavours. If you care about RSS you might already know this, because of the <link> tags in the source of the page describing the URLs where you can find them, and you might be browsing this page with software that recognises these tags.


They would have had the same conversation 90 minutes later. Something changed. After pedantically checking the Domain Name System (as always), Computer 1 was instead directed to talk to Computer 3.

Computer 1: “Can I have /?feed=atom please?”

Computer 3: “Never heard of it! Go away!”

This conversation repeated every 30 minutes or so, for a while. A while.

Computer 1 misses its friend.


Back in the heyday of RSS, feeds were often aggregated into other feeds. This was a matter of convenience: with so many good RSS feeds available, it was easier to configure your RSS reader to follow just one aggregated feed on a topic that someone else had done the work to curate, as opposed to inputting the URL of each and every feed of interest. (Google Reader would subsequently improve, and then demolish, the feed-following experience.)

Aggregating feeds was a straightforward-seeming software engineering exercise: periodically consume a list of source feeds, process the content, and format it into a single output feed.

One implementation of such an aggregator, in Python, was called Planet Planet. To handle the small array of different feed types, as well as fetching the feeds, Planet Planet used the Universal Feed Parser. You can recognise requests from Universal Feed Parser in a web server log by its User Agent string.

Planet Planet was configured with a config.ini file with a set of URLs to ingest as feeds, and was typically run periodically on its host using cron.


Computer 1 (tired of this): “Friend, are you there?”

Computer 3: “I’ve been upgraded. Look, have you tried talking to me with HTTPS? It’s better for everybody’s security if you do.”

Computer 1 (to itself): “😔 Well, I tried.”

Computer 1 gives up… for now. It will strike up the conversation again, with perfectly programmed optimism, in almost exactly 30 minutes. Again. And again. And again. And again. And again. And again. And…

For several years.


WordPress is a popular website CMS and blogging platform, implemented in PHP. It was commonly deployed on a LAMP-stack (Linux, Apache, MySQL, PHP), but a centralised form of it also exists. As a blogging platform, it also serves up RSS feeds.

The RSS feed is typically available on a WordPress site at /feed/. There are other ways of requesting the same feed, presumably for compatibility with earlier conventions - these are /?feed=rss and /?feed=atom.


Computers 4 through N (in chorus, seemingly unprompted): “Hey, I heard you have this file? /wp-content/plugins/latex/cache/tex_174ea3aa1e90a695b482fe253768676b.gif?”

Computers 4 through N: “Hey, I heard you have this file? /wp-content/plugins/latex/cache/tex_aad18c0a88969b4c1bdc3711475796c2.gif?”

Computers 4 through N: “Hey, I heard you have …” etc

Computer 3: “What? No! Buzz off, all of you. Where are you even getting these paths?”

Computer N: “You used to have them…”


After consuming its configured feeds, Planet Planet produces static HTML and RSS output that is intended to be served by some web server software - often Apache. The text or HTML content of each article is copied to the output largely unmodified. Some potentially dangerous HTML is scrubbed. Other HTML tags, like <img>, remain. Such images are not scraped by Planet Planet, rather, the URLs remain pointing wherever they were pointing originally, as provided by the source RSS feed.

In other words, Planet Planet outputs hot-links to images hosted elsewhere.

Sometimes, Universal Feed Parser (used by Planet Planet) can’t fetch a feed it is configured to. Being quite old and defunct, Universal Feed Parser doesn’t follow 302 redirects - at least, not to the same feed available under HTTPS.

In any case, if the feed isn’t fetched, Planet Planet will try again later, but in the meantime it keeps a copy of the articles it already had, and uses those.

Search engines also pass around rumors of secret URLs that exist, opening to the right sequence of door-knocks and magic passwords, but when queried during business hours under the bright light of the full overhead sun, are vanished, like ghosts.


Computer 1 (weary): “The usual…honestly not expecting anything…”

Computer 3 (interrupting): “Hello! You want the Atom feed? Here you go! Nice to hear from you! Let’s be friends! 😄”

Computer 1: “😯 … 🤯”


I’m glad our computers can be friends again.

April 14, 2022 01:14 AM

April 11, 2022

Alex B

Hello world!

Welcome to WordPress. This is your first post. Edit or delete it, then start writing!

April 11, 2022 11:20 AM

January 08, 2022

Josh

Algebra with Go generics

I have been playing with the Go 1.18 beta. 1.18 is the version they are adding generics, so this is a good time to get up to speed with the changes. So far, I am reasonably fond of it, so here I am blogging about my experimentation.

Here’s a problem related to interfaces in pre-generics Go. Suppose we want an interface that captures the idea of a type where a value can make copies of itself. Since the copy of a value should have the same type as the original, it too can be copied. Thus, a first draft of Copier:

type Copier interface {
    Copy() Copier
}

And an example implementation:

type Foo struct {
    // ...some fields here...
}

func (f *Foo) Copy() Copier {
    // A shallow copy
    g := *f
    return &g
}

Note that Foo basically must be defined in the same package as Copier. This is a problem because interfaces are best defined where they are used (that is, there is some code that uses the methods defined by the interface), not where there happens to be some type that implements the interface - see code review comments. What happens when we try to separate Foo from Copier?

// .../usescopy/uses.go
package usescopy

// Copier defined here because Process needs to make copies
// of its input (for some reason).
type Copier interface {
    Copy() Copier
}

// Process makes a copy of x and then does something to it.
func Process(x Copier) {
    y := x.Copy()
    // ...
}

// .../foo/foo.go
package foo

import "usescopy"

type Foo struct { ... }

func (f *Foo) Copy() usescopy.Copier {
    g := *f
    return &g
}

To implement Copier, Foo has to return a Copier from Copy. In order for Copier to make sense in foo.go, the package defining it has to be imported. But the usescopy package defines Copier only in order to use it, and foo still has to be aware of the interface it is implementing! Heaven forbid usescopy also needs to refer to anything in foo:

package usescopy

import "foo" // but foo imports usescopy in order to implement Copier...

func Process(x Copier) {
    switch x.(type) {
    case *foo.Foo:
        //...
    }
}

The usual way around this issue is to let Copier be significantly weaker:

type Copier interface {
    Copy() interface{}
}

Now Foo just has to return interface{}. This is acceptable (Process can use a type switch or type assertion to recover the original type from the copy) but is unnatural for Foo. Surely foo’s Copy should return a *Foo?

We can! With generics. Let’s make Copier generic:

package usescopy

type Copier[T any] interface {
    Copy() T
}

It might look like this Copier is as weak as the one where Copy returns interface{}. Any method called Copy, with no arguments, that returns anything at all will satisfy some Copier, when what we want is for Copy to return the same type as the receiver. But this is about as good as we can do in the interface, because Copier can’t be used as a constraint on its own type parameter.

We probably want to use Copier generically too, so here is the genericised Process:

func Process[T Copier[T]](x T) {
    y := x.Copy()
    // ...
}

What nonsense is that? Actually it’s not - it’s totally fine.

Here, Copier[T] is being used as a constraint on the type argument T. A constraint that refers to the type being constrained? Yes, this works! What does it mean? It means T has to satisfy Copier[T], i.e. T has a Copy method that returns values of type T.

Since Process can only be called with things of any type T so long as T implements a Copy method that returns values of that same type T, the issue of Copier being apparently weak is a non-issue. Process gets a value of type T, and Copy returns another value of type T. Which was what we wanted.

This also solves the interface-implementation separation problem. The foo package can be completely unaware of Copier, and Copy can return the more useful and specific type *Foo instead of some interface:

package foo

// Look ma, no imports!

type Foo struct { ... }

// Copy returns a pointer to a shallow copy of *f.
func (f *Foo) Copy() *Foo {
    g := *f
    return &g
}

Here’s a Go playground showing this in action.

What was that about algebra?

With that taster out of the way, I thought it might be nice to write some generic types that implement some ideas from algebra. This is going to use the “constraints referencing the type arguments being constrained” technique from above.

Go has a variety of inbuilt numeric types (int, float64, complex128, etc), and these can be fashioned into good examples. I like quite complex128, even though I rarely have a use for it. This built-in type implements complex numbers with floating-point components.

But suppose we only care about complex numbers that have integer real and imaginary components, and complex128 is for whatever reason unsuitable - maybe there is a need for exact integer precision but no need for range. There’s no inbuilt complexWithIntParts, so let’s implement it (and call it by its more traditional name):

type GaussianInteger struct {
    Real, Imag int
}

// Add returns z+w.
func (z GaussianInteger) Add(w GaussianInteger) GaussianInteger {
    return GaussianInteger{
        Real: z.Real + w.Real,
        Imag: z.Imag + w.Imag,
    }
}

// Neg returns -z.
func (z GaussianInteger) Neg() GaussianInteger {
    return GaussianInteger{
        Real: -z.Real,
        Imag: -z.Imag,
    }
}

// Mul returns z*w.
func (z GaussianInteger) Mul(w GaussianInteger) GaussianInteger {
    return GaussianInteger{
        Real: z.Real*w.Real - z.Imag*w.Imag,
        Imag: z.Real*w.Imag + z.Imag*w.Real,
    }
}

and so on.

I’ve used Neg and Mul instead of Negation and Multiply because expressions with these methods can get verbose. Go (even 1.18) does not have operator overloading (I think this is a good thing!) so we must do with reasonably short method names. Hopefully they are still clear. (math/big uses the same names for the same operations.)

But! These methods would be exactly the same if we substituted for int any other arithmetic type like uint8, int32, float64 or, heck, even complex64 or complex128 (Complex numbers with complex parts! 😏😏😏) Good candidate for being generic.

// Arithmetic matches any of the built-in numeric types,
// as well as types whose underlying types are any of the
// built-in numeric types.
type Arithmetic interface {
    ~int | ~int8 | ~int16 | ~int32 | ~int64 | ~uint | ~uint8 | ...
    ... | ~float32 | ~float64 | ~complex64 | ~complex128
}

// Complex implements complex numbers with real and imaginary
// parts of type T.
type Complex[T Arithmetic] struct {
    Real, Imag T
}

// Add returns z+w.
func (z Complex[T]) Add(w Complex[T]) Complex[T] {
    return Complex[T]{
        Real: z.Real + w.Real,
        Imag: z.Imag + w.Imag,
    }
}

// Neg returns -z.
func (z Complex[T]) Neg() Complex[T] {
    return Complex[T]{
        Real: -z.Real,
        Imag: -z.Imag,
    }
}

// Mul returns z*w.
func (z Complex[T]) Mul(w Complex[T]) Complex[T] {
    return Complex[T]{
        Real: z.Real*w.Real - z.Imag*w.Imag,
        Imag: z.Real*w.Imag + z.Imag*w.Real,
    }
}

// Then GaussianInteger is as easy as:
type GaussianInteger = Complex[int]

// I can't believe it's not complex128:
type Complex128 = Complex[float64]

// Just for fun:
type ComplexComplex = Complex[complex128]

I’m not done genericising Complex, however. So far, Add, Neg, and Mul of Complex[T] are implemented using built-in addition, negation, and multiplication operators of whatever T is. But what if we want to make complex numbers out of some other type, like big.Int, big.Float, big.Rat, or some other FunkyNumber I’ve never heard of? Well, as long as it has methods called Add, Neg, Mul, and so on that behave as expected, it could be made to work.

// Ring describes an algebraic structure having addition, 
// negation. and multiplication. Rings also have a zero element
// and an identity element.
type Ring[T any] interface {
    Add(T, T) T
    Neg(T) T
    Mul(T, T) T
    Zero() T
    Identity() T
}

// Complex implements complex numbers with components of any type T,
// using the arithmetic operations of any ring over T.
type Complex[T any, R Ring[T]] struct {
    Real, Imag T
}

// Add returns z+w.
func (Complex[T, R]) Add(z, w Complex[T, R]) Complex[T, R] {
    var r R
    return Complex[T, R]{
        Real: r.Add(z.Real, w.Real),
        Imag: r.Add(z.Imag, w.Imag),
    }
}

// Neg returns -z.
func (Complex[T, R]) Neg(z Complex[T, R]) Complex[T, R] {
    var r R
    return Complex[T, R]{
        Real: r.Neg(z.Real),
        Imag: r.Neg(z.Imag),
    }
}

// Mul returns z*w.
func (Complex[T, R]) Mul(z, w Complex[T, R]) Complex[T, R] {
    var r R
    return Complex[T, R]{
        Real: r.Add(r.Mul(z.Real, w.Real), r.Neg(r.Mul(z.Imag, w.Imag))),
        Imag: r.Add(r.Mul(z.Real, w.Imag), r.Mul(z.Imag, w.Real)),
    }
}

// Zero returns 0 + 0i.
func (Complex[T, R]) Zero() Complex[T, R] {
    var r R
    return Complex[T, R]{
        Real: r.Zero(),
        Imag: r.Zero(),
    }
}

// Identity returns 1 + 0i.
func (Complex[T, R]) Identity() Complex[T, R] {
    var r R
    return Complex[T, R]{
        Real: r.Identity(),
        Imag: r.Zero(),
    }
}

Note that the math/big types don’t have methods Zero or Identity, so Complex doesn’t work out of the box with those. But it would be reasonably straightforward to implement adapters for them.

The only thing from this that grates against my Go instincts is the need for var r R to access the methods of R, but this is a minor complaint.

Ring is a decent approximation of what we want from an algebraic ring. What is missing from Ring is constraints on the behaviour of the methods: Add should be associative and commutative, Zero should return the additive identity, Mul should be distributive over Add, and so on. For now it is considerably beyond the capability of Go interfaces, so I will leave it for unit tests.

Complex[T, R] is both a struct containing Real, Imag T, and the operations using those values, but in the style of math/big: instead of adding z and w with z.Add(w), it is now z.Add(z, w). Since none of the methods of Complex[T, R] make use of the receiver value, it may make sense to make them all functions instead of methods, but there is no such thing as a “package interface” in Go.

Complex[T, R] is itself a Ring[Complex[T, R]]. So we can make complexes out of complexes out of complexes…

Finally, if we want this new Complex to work with the built-in types, we can use a generic to implement the operations defined by Ring:

// BuiltinRing implements Ring[T] using the built-in operators of T.
type BuiltinRing[T Arithmetic] struct{}

// Add returns x+y.
func (BuiltinRing[T]) Add(x, y T) T { return x + y }

// Neg returns -x.
func (BuiltinRing[T]) Neg(x T) T { return -x }

// Zero returns 0.
func (BuiltinRing[T]) Zero() T { return 0 }

// Mul returns x*y.
func (BuiltinRing[T]) Mul(x, y T) T { return x * y }

// Identity returns 1.
func (BuiltinRing[T]) Identity() T { return 1 }

// Some examples:

// Integer adapts int into a Ring.
type Integer = BuiltinRing[int]

// Real adapts float64 into a Ring.
type Real = BuiltinRing[float64]

// Cmplx adapts complex128 into a Ring.
// This is "Cmplx" and not "Complex" to distinguish it from the
// generic Complex type above.
type Cmplx = BuiltinRing[complex128]

// GaussianInteger implements the integral domain Z[i] as complex
// numbers with int parts, and operations from the ring of integers.
type GaussianInteger = Complex[int, Integer]

January 08, 2022 06:14 AM

November 15, 2021

Josh

Rusty gutters

I was thinking about the guttering on our house. For as long as we’ve owned it, the guttering out the front and some up the back has leaked a little bit. But it is getting to the point where the gutters are quite literally falling apart from rusting. So I have finally taken to try to fix them. It wasn’t a priority before, when they still (barely) worked and carried most of the rainwater to the downpipe. Hang on, there’s a quote about this. Ah, that’s right:

“Broken gets fixed, but shitty lasts forever.” - @littleidea

The original context of the quote above was likely something tech-related. It could easily be invoked in a conversation on memory-unsafe languages or various internet protocols. These things will be with us for a long time in spite of flaws, because they’re flawed in acceptable ways, and they are highly entrenched, which incentivises quickly developing patches and workarounds whenever things reach a breaking point.

Which brings me to cryptocurrencies and NFTs.

I won’t be re-litigating all the ways in which cryptocurrencies and NFTs are shitty in this post. If you think they are good, you can stop reading until you educate yourself. If you won’t do that, you’re not welcome here - kindly fuck off. Note that I’m not defending traditional financial systems. Of course these are far from perfect. But it is fair to say the world is straight-up worse for having cryptocurrencies and NFTs in it.

The bad outcomes of cryptocurrencies and NFTs are deemed acceptable by many people participating in them. At best, some participants may concede that some outcomes (like the exorbitant energy consumption or e-waste production associated with Bitcoin) are shitty, but not broken enough to do something about. In fact, they are usually financially motivated to keep their shitty thing running in the same shitty way - for example, Bitcoin miners would vote to keep using double-SHA256-based proof-of-work, as that maximises their future income relative to their “investments” in specialised future e-waste. Coin HODLers are motiviated to keep the network nodes and markets running, NFT owners are motivated to keep the NFT markets running, and so on.

Sometimes a new group splinters off to make a successor system with a marginal improvement (e.g. Proof-of-Stake v.s. Proof-of-Work, or Ethereum’s ethash vs. Bitcoin’s hashcash). Sometimes, some intrinsic shitty thing gets attention because it upsets the users (e.g. the Lightning Network as a fix for Bitcoin’s glacial transaction rate). However, whatever marginal improvement is made, either the rest of the system and its shitty ways of doing things become further entrenched, or the legacy system (still running) benefits by association with the new system (e.g. by trading between them on an exchange).

“The purpose of a system is what it does.” - Stafford Beer

And what the system does is: consume vast amounts of energy, produce piles of e-waste, worsen inequality, jack up the price of graphics cards and worsen the chip shortage, and provide support for scams, tax evasion, ransomware, DDoS rackets, and money laundering. Among other things.

Those of us who aren’t blinded by our own involvement, that can see the whole thing as broken, have little recourse. It’s not as though we can reach our arms through the internet to unplug the mining rigs - a good thing, or they would be able to do the same to us, after all.

Breaking Bitcoin

So what can we do?

If I had a lot of money, I could help stop Bitcoin by using my money in a variety of ways:

We can’t hold out hope for the hyper-wealthy to actually help, because they are likely to own cryptoassets themselves (some openly admit it), and helping would go against their self-interest. Some of the options above are unethical (this is the domain of the hyper-wealthy). Some scenarios would also have easy workarounds - for instance, the Bitcoin clients could be made to reject blocks with less than a few transactions in them.

We also can’t hold out hope for a cryptanalytic attack on SHA256 powerful enough to render current Bitcoin mining hardware worthless (but this will hardly stop me thinking about it).

Satoshi N. didn’t design true democracy into Bitcoin, no matter what lofty rhetoric about a decentralised libertarian utopia he wrote, or what Bitcoin acolytes claim. Our given options are:

The second option isn’t a vote against Bitcoin. In democratic terms, it is abstention. Unanimous support again? Glory to the party!

Maybe we can build a true democracy. Here is a thought experiement that shows a sufficiently large group of motivated, internet-connected people could put a dent into cryptocurrency and NFT systems as they exist currently, without spending lots of money, creating a large environmental burden, manipulating markets, or resorting to t3h cyb3r-cr1mes.

I suppose we can all vote in real democracies for policies that ban cryptocurrencies and NFTs. Because cryptocurrencies and NFTs are shitty, but don’t properly break the real economy, it would be a low priority for major political parties. Anything else?

The large group of motivated people (People Against Bitcoin, or something) agree on the following beliefs:

  1. Bitcoins are worthless.
  2. Therefore, relaying Bitcoin transactions would be a waste of energy.
  3. Therefore, we won’t relay any Bitcoin transactions.

We can encode this policy into a piece of software that connects to the peer-to-peer Bitcoin network. To the existing nodes, this new software would look like any other Bitcoin node. However, no transactions would ever be received from the node (as it relays none) and any transactions sent to it would be silently dropped (again, it relays none). With only a few such non-relaying nodes connected, there would be no impact on the Bitcoin network. But with enough people running it, Bitcoin transactions would grind to a halt as the nodes with transactions become increasingly fragmented from one another.

Would this work? I see Bitcoin as having three possible reactions. The first would most likely be to find ways to fingerprint the People Against Bitcoin client and deny it connecting, leading to an arms race between the new software (that must evade detection) and the Bitcoin authors developing new detection methods. This raises the cost of continuing to develop and run the Bitcoin software, which is a step in the right direction. The second reaction would be to run more instances of the relaying Bitcoin clients, which again raises the cost. The third reaction would be to centralise a list of either “good” or “bad” nodes, which would violate one of Bitcoin’s core principles (no centralisation). Providing a list of “good” nodes also paints a target on them for the less scrupulous to instigate DoS attacks.

Is this approach itself a DDoS? That’s a bit of a philosophical question. As a question of intention, yes, the aim is to deny the usual service of Bitcoin, which is notionally to process transactions (incredibly slowly). Unlike a typical DDoS orchestrated with a botnet, the People Against Bitcoin would all individually consciously choose to run a non-relaying client. The software is also not trying to disrupt service by overwhelming network links or processing power of the relaying nodes - if anything, by refusing to relay any transactions, they would be reducing the network and processing load, minimising collateral damage on the internet. Finally, the target is not one single person or company but the Bitcoin system as a whole, and no Bitcoins are ever lost in the process. Bitcoins could still be transacted in exchanges, or outside the network. So what is the damage?

November 15, 2021 06:22 AM

October 23, 2021

Josh

Making a Game in Go, part 7

And now, something completely different. A dialogue system!

Please don’t tell me you are going to implement your own dialogue system too! Aren’t you friends with the Yarn Spinner people?

Exactly. Why reimplement something that already exists and does a good job?

Ok, so… Yarn Spinner. A dialogue system for games, “the friendly tool for writing game dialogue”. Why put dialogue in a game? I dunno, but narrative seems to be an element of many popular games, and I would like to have some in mine too.

Yarn Spinner is not written in Go, which would make it easy to interoperate with directly, nor is it written in C/C++, which would be slightly awkward yet feasible (via CGo).

Yarn Spinner is written in C#. This makes sense because Yarn Spinner is (so far) intended to run as a Unity package, and Unity uses C#.

I wonder what the state of .NET-Go interop is? Some things I found:

Wait, that’s it?

Reimplementing, like, half of Yarn Spinner

tl;dr: the code’s up on GitHub.

Yarn Spinner consists of a few high-level parts:

High level diagram showing key Yarn Spinner components

Since the dialogue runner is the closest part to the game, and the language grammar and compiler can be used stand-alone (they don’t have to be shipped with the game), if I have to reimplement anything it would be the dialogue runner.

Tailwinds for writing a reimplementation of the Yarn Spinner VM in Go:

Oh, also I began implementing it in like 2016 (but had other things to do than complete it).

The virtual machine

The Yarn Spinner virtual machine is the core of the dialogue system at game run time. Its primary responsibilities are:

This suggests an interface for the game to implement that the VM can talk to. Yarn Spinner’s dialogue runner needs a similar sort of interface. The idiom in Yarn Spinner’s C# implementation is to use various separate properties of delegate type as callbacks for each event. While it would be simple in Go to either have 7 different interfaces with 1 method each, or have 7 fields of func type, neither approach makes a ton of sense. Responsibility for handling game dialogue is likely to be concentrated in one location, so making that thing handle all the different events produced by the virtual machine, whether or not they are needed by the game, is reasonable. For implementations that ignore most of the methods, there’s also a FakeDialogueHandler that can be embedded to provide no-op implementations.

type DialogueHandler interface {
    Line(line Line) error
    Options(options []Option) (int, error)
    Command(command string) error
    PrepareForLines(lineIDs []string) error
    NodeStart(nodeName string) error
    NodeComplete(nodeName string) error
    DialogueComplete() error
}

Imitating the original Yarn Spinner API is desirable for two reasons:

But there are a few deliberate API differences that I want to touch on.

Yarn Spinner’s implementation pauses execution after delivering lines, options, and commands. When the game is ready for more content from the dialogue system, it must call Continue to make the VM continue executing. This makes a lot of sense when you consider that a game only rarely needs more content from the dialogue system. Most of the time is spent waiting for player inputs, or otherwise allowing the player to enjoy the content. So suspending execution and requiring an explicit Continue allows the dialogue system to get out of the way.

Sequence diagram showing non-blocking Yarn Spinner dialogue runner operation

However, it is unnecessary to do this in Go - there is a more *Go*thic way. The VM can run concurrently in a separate goroutine, and deliver the content as fast as it likes. When the game needs to spend more time between bits of content, it can block.

Blocking the VM goroutine (with, say, a channel operation or a mutex lock) isn’t as expensive as it sounds (it doesn’t “waste a thread”). In fact concurrency is very useful even where operations don’t need to happen in parallel. The goroutine scheduler is aware of channel operations and mutexes and so on, and while a goroutine is waiting on these, the scheduler won’t schedule that goroutine. When the game is ready to receive more dialogue, it can unblock its handling of the current Line, Options, Command (etc), and return.

“Sequence diagram”-esque diagram showing blocking concurrent operation

Aside from simplifying away execution state tracking and the Continue method, doing it this way enables Options to return the chosen option directly, rather than requiring another VM method for telling the VM about it (SetSelectedOption). The API is clearer.

Because goroutines and channels are so useful for adapting between blocking and non-blocking needs in this way, well-designed Go APIs usually block. If non-blocking is needed, the caller can wrap the API call in a goroutine, with results passed later on via a channels entirely managed by the user of the API. Blocking APIs tend to be easier to understand than either non-blocking APIs or APIs that try to do both by taking channel arguments or returns.

Another key difference between my implementation and the Yarn Spinner API is a Go practical necessity: C# has the concept of exceptions, but the Go way is to return errors like any other value. So each method in the DialogueHandler returns error, and the VM checks the error value before continuing, providing the dialogue handler the opportunity to halt the VM in much the same way as raising an unhandled exception in C# land.

The virtual machine implementation is also inspired by Yarn Spinner’s. Having the source code and a suite of ready-made test cases has been a massive time-saver when trying to debug or understand differences in behaviour. Given that virtual machine is essentially a loop that considers program instructions one at a time, many similarities between implementations will happen naturally.

Choosing what to do based on the current instruction sounds a lot like a switch statement (and that is how Yarn Spinner does it) but for the sake of reducing code indentation (and “cyclomatic complexity”) I ended up with a slightly different device:

var dispatchTable = []func(*VirtualMachine, []*yarnpb.Operand) error{
    yarnpb.Instruction_JUMP_TO:        (*VirtualMachine).execJumpTo,
    yarnpb.Instruction_JUMP:           (*VirtualMachine).execJump,
    yarnpb.Instruction_RUN_LINE:       (*VirtualMachine).execRunLine,
    yarnpb.Instruction_RUN_COMMAND:    (*VirtualMachine).execRunCommand,
    yarnpb.Instruction_ADD_OPTION:     (*VirtualMachine).execAddOption,
    yarnpb.Instruction_SHOW_OPTIONS:   (*VirtualMachine).execShowOptions,
    yarnpb.Instruction_PUSH_STRING:    (*VirtualMachine).execPushString,
    yarnpb.Instruction_PUSH_FLOAT:     (*VirtualMachine).execPushFloat,
    yarnpb.Instruction_PUSH_BOOL:      (*VirtualMachine).execPushBool,
    yarnpb.Instruction_PUSH_NULL:      (*VirtualMachine).execPushNull,
    yarnpb.Instruction_JUMP_IF_FALSE:  (*VirtualMachine).execJumpIfFalse,
    yarnpb.Instruction_POP:            (*VirtualMachine).execPop,
    yarnpb.Instruction_CALL_FUNC:      (*VirtualMachine).execCallFunc,
    yarnpb.Instruction_PUSH_VARIABLE:  (*VirtualMachine).execPushVariable,
    yarnpb.Instruction_STORE_VARIABLE: (*VirtualMachine).execStoreVariable,
    yarnpb.Instruction_STOP:           (*VirtualMachine).execStop,
    yarnpb.Instruction_RUN_NODE:       (*VirtualMachine).execRunNode,
}

func (vm *VirtualMachine) execute(inst *yarnpb.Instruction) error {
    if inst.Opcode < 0 || int(inst.Opcode) >= len(dispatchTable) {
        return fmt.Errorf("invalid opcode %v", inst.Opcode)
    }
    exec := dispatchTable[inst.Opcode]
    if exec == nil {
        return fmt.Errorf("invalid opcode %v", inst.Opcode)
    }
    return exec(vm, inst.Operands)
}

This demonstrates two things.

First, array and slice literals in Go can be written similarly to map and struct literals (with keyed elements), so long as the “keys” are integer indexes (and protobuf enums are int32 values in Go). What happens if you leave a gap (or start after index 0)? Any uninitialised elements between 0 and the maximum index key take the zero value for the type. In the case of Yarn Spinner, there are no unused instructions between JUMP_TO and RUN_NODE, so the nil check is strictly unnecessary.

Each instruction is implemented as its own method, with a common signature:

func (vm *VirtualMachine) execSomething(operands []*yarnpb.Operand) error

Given any method, there are two short ways to get a func value that calls the method, using method expressions. Of course one could write a closure that calls the method, but method expressions are shorter and make a lot of sense when you see them at work.

The more common method expression style is to write a method call but without the parentheses or arguments:

var vm *VirtualMachine
vm.execSomething   // is a func([]*yarnpb.Operand) error

The less common, but still very useful syntax, is to use the type itself instead of a value.

(*VirtualMachine).execSomething
// is a func(*VirtualMachine, []*yarnpb.Operand) error

Since the *VirtualMachine isn’t known when taking the method expression, the func has to take a value of that type as an arg.

Why use the second kind of method expression here, when the first has fewer args and the value of vm is known? e.g. why not something like

func (vm *VirtualMachine) execute(inst *yarnpb.Instruction) error {
    dispatchTable := []func([]*yarnpb.Operand) error {
        yarnpb.Instruction_JUMP_TO:  vm.execJumpTo,
        yarnpb.Instruction_JUMP:     vm.execJump,
        // ... snip ...
        yarnpb.Instruction_RUN_NODE: vm.execRunNode,
    }
    // ...snip...
    exec := dispatchTable[inst.Opcode]
    // ...snip...
    return exec(inst.Operands)
}

Well, unless the compiler is clever, it is likely dispatchTable would be recreated on every execute call (i.e. every VM instruction), which seems wasteful.

The standard functions

One VM opcode stands out from the others - CALL_FUNC. It is noteworthy because all arithmetic operations, Boolean expressions, numeric comparisons, and string concatenation in Yarn Spinner programs happens using CALL_FUNC, rather than with dedicated instructions for those purposes.

As an example, the expression 2+3 is compiled into:

PUSH_FLOAT 2     ; first argument
PUSH_FLOAT 3     ; second argument
PUSH_FLOAT 2     ; number of args being passed
CALL_FUNC "Add"  ; invoke the function
; top of stack now contains the result (5)

Yarn Spinner defines 17 standard functions that implement the basic operations. (Making the functions into their own opcodes would double the opcode count!) Some functions are shared across different types, for example, the Boolean expression functions (Or, And, Xor, Not) clearly work with Boolean args, but also floats (0 is false) and strings (empty is false, non-empty is true). Add is shared between floats (arithmetic addition) and strings (concatenation). This is required because (as of this writing) the Yarn Spinner compiler makes “truthiness” and other implicit type conversions the responsibility of the functions, rather than inserting comparisons or explicit conversions.

CALL_FUNC isn’t limited to the standard Yarn Spinner functions, either. Custom functions, with any number of arguments of any type, including variadic functions, can be registered to be called. This flexibility makes the implementation of CALL_FUNC the most complicated instruction. Supporting variadic functions implies that the program has to communicate how many values on the stack are function args - this is why the arg count is always pushed before CALL_FUNC. Yarn Spinner could adopt two different calling conventions to avoid the unnecessary push for non-variadic functions, but that shuffles the responsibility back from the runtime to the compiler.

Both C# and Go have reflection. In Go reflection is done via the reflect package, which I mentioned in the previous post. reflect.Type has a number of methods relevant to interrogating the args of a function. After checking that the custom function’s Kind is indeed reflect.Func, the reflect.Type supports NumIn, NumOut, and IsVariadic methods to find how many args the function has, and In and Out methods to inspect the type of each.

The logic of matching the types of items on the VM stack with args of each function is a bit tedious, especially to support both non-variadic functions (where the number of args must match exactly) and variadic functions (where the last In arg is the implicit slice type, and the number of args provided by the program can be one fewer than NumIn!).

The cool part is actually calling a function via reflection. After wrapping all the input args with reflect.Value (no special logic is needed for variadic functions - that is taken care of by reflect!) the call can be made on a reflect.Value wrapping the function:

// Params built from stack values
params := []reflect.Value{ ... }

// function is the function we wish to call
result := reflect.ValueOf(function).Call(params)
// result is now another []reflect.Value with
// the return values.

The string table

Reading a CSV file with encoding/csv and then putting all the rows into a map keyed by line ID isn’t particularly thrilling code. What is a bit more interesting is what happens with lines when they need to be presented, because Yarn Spinner lines can be more complex than plain strings.

Firstly, there are string substitutions. A substitution happens in lines, options, and commands, when the author writes an inline expression. For example, the line Hello, {$name}! would be compiled into two parts: bytecode to load the value of $name to be used as a substitution, and a corresponding line in the string table of the form Hello, {0}!. When the VM runs a line, it not only passes the ID of the string in the table, but also all the values that need to replace curly-braced numbers.

Yarn Spinner, and an earlier version of my Go package, implement substitutions with repeated string replacement:

type Line struct {
    ID string
    Substitutions []string
}

func (t *StringTable) Render(line Line) (string, error) {
    row, found := t.table[line.ID]
    if !found {
        return "", fmt.Errorf("line ID %q not in string table", line.ID)
    }
    text := row.Text
    for i, subst := range line.Substitutions {
        token := "{" + strconv.Itoa(i) + "}"
        // alternatively token := fmt.Sprintf("{%d}", i)
        text = strings.ReplaceAll(text, token, subst)
    }
    return text, nil
}

This hardly needs to be optimised, because dialogue content only needs to be delivered as fast as the player can consume it - string replacements won’t be the bottleneck in that process. But, just for fun, here’s how the substitutions could be processed in a single pass over the line text using a strings.Builder for minimising allocations:

func (t *StringTable) Render(line Line) (string, error) {
    row, found := t.table[line.ID]
    if !found {
        return "", fmt.Errorf("line ID %q not in string table", line.ID)
    }
    text := row.Text
    
    var sb strings.Builder
    token := false
    tokenStart := 0

    for i, r := range text {
        switch {
        case !token && r == '{':
            // Entering token mode -
            // record the start position of the token
            token = true
            tokenStart = i
        case token && r == '}':
            // Exiting token mode -
            // token should have a substitution index n
            n, err := strconv.Atoi(text[tokenStart+1:i])
            if err != nil || n < 0 || n >= len(line.Substitutions) {
                // Either the token was malformed
                // or the index requested wasn't
                // provided by the program.
                // Oh well, output the token-like thing
                sb.WriteString(text[tokenStart:i+1])
                continue
            }
            token = false
            // write the substitution
            sb.WriteString(line.Substitutions[n])
        case token:
            // not a closing brace, hopefully a digit - skip
        default:
            // not-token mode
            sb.WriteRune(r)
        }
    }
    if token {
        // ended in token mode
        // output the partial token
        sb.WriteString(text[tokenStart:])
    }
    return sb.String(), nil
}

The other language feature that is the responsibility of the dialogue runner is format functions. The idea with format functions is to defer some expressions that produce text, where the text would vary both by game state and potentially by language. Different string tables for different languages can be translated in a way that produces more natural dialogue across languages.

Format functions are written with square brackets [, ] and have a more sophisticated syntax than substitutions. Thankfully there are only 3 supported format functions: select, plural, and ordinal (and the latter two are fairly similar). Examples:

Hey [select "{0}" m="bro" f="sis" nb="doc"]
That'll be [plural "{0}" one="% dollar" other="% dollars"]
You are currently [ordinal "{0}" one="%st" two="%nd" few="%rd" other="%th"] in the queue

Note these examples have one main difference with the syntax described in the Yarn Spinner docs. Yarn Spinner compiles the inline expressions used as input to the function into a substitution token. The examples above would be what appears in the compiled string table.

Format functions would be, uh, challenging to implement with a repeated-replacement algorithm. While {0}, {69}, {420}, ... tokens can be easily search’n’replaced for each substitution provided by the program, there are no limits on what strings each format function could contain, nor how many key/value pairs appear after the selector input.

At this writing the Yarn Spinner develop branch implements format functions with a big loop. I wanted to try something a bit different - between substitutions, format functions, and the necessary escape sequences, there’s practically a whole (small) language, and across my career I have barely dipped my toes into the waters of lexers and parsers.

After some quick looking around for text parsing packages for Go, I settled on participle, because it looks nice and one of the examples shown in the README looks kind of like what format functions need (if you squint a bit): let a = "hello ${name + ", ${last + "!"}"}" can be lexed with participle’s stateful lexer. Yarn Spinner format functions similarly require nested evaluation - the tokens % and {0} are substituted into strings, which are inside format functions (which are inside lines of text, which are kind of like strings).

The lexer and parser details are in strings.go, and while it does not match what Yarn Spinner does exactly… the tests pass 🤷

One final word on participle: using participle to parse a grammar that uses double-quoted strings, together with a Go linter that complains that participle’s easy struct tags violate the convention for field tags, led to a few escaping dramas, particularly parser:"\"\\\"\" @@ \"\\\"\"" 🤪

For the pluarl and ordinal format functions, Yarn Spinner uses the wonderful Unicode CLDR to pick the value. Having spotted the golang.org/x/text package, in particular feature/plural, I figured it would be easier than generating the information from LDML myself. And it was! It just has two minor problems.

That’s more of a bridge I can pester someone to build when I need to cross it. In the meantime, maybe someone has something better? A search for “cldr” among Go packages reveals a variety of other efforts to load and make useful the CLDR. I tried using razor-1’s localizer package, but despite cardinal data working fine, ordinal data wasn’t present, leading to a nil pointer panic. Or maybe I was holding it wrong. Still, the NewOperands function was useful for figuring out what to pass to golang.org/x/text’s MatchPlural:

import (
    //...snip...
	cldr "github.com/razor-1/localizer-cldr"
	"golang.org/x/text/feature/plural"
)

//...snip...

case "plural":
    ops, _ := cldr.NewOperands(in)
    form := plural.Cardinal.MatchPlural(lang, int(ops.I), 
        int(ops.V), int(ops.W), int(ops.F), int(ops.T))
    //...snip...

case "ordinal":
    ops, _ := cldr.NewOperands(in)
    form := plural.Ordinal.MatchPlural(lang, int(ops.I),
        int(ops.V), int(ops.W), int(ops.F), int(ops.T))
    //...snip...

October 23, 2021 04:40 AM

October 14, 2021

Josh

Making a Game in Go, part 6

In parts 1 through 5 I built up something of a “game engine” that was increasingly flexible in terms of when each (drawable) component was drawn. In doing so the amount of book-keeping in the central Game structure increased.

What even is a game? I (jokingly) suggest the following definition:

A game is a database of game components.

Database?

You: (sobbing) You can’t just make everything a database… please…

Josh: (points at a seagull) Database!

Yeah - though I won’t be shipping PostgreSQL with my game. I mean “database” as in “an organised collection of information”, not as in “Microsoft SQL Server”.

In the first few posts, Game was managing draw ordering, but in part 5 I refactored that part out into DrawDAG. So the Game’s most important field became a helper data structure for tracking the parent component of every component.

type Game struct {
    //...snip...
    parent map[interface{}]interface{}
}

In a SQL database metaphor, parent is like a table with two columns, and a unique index on the first column. parent is useful for a number of things, but it can’t speed up everything. Time to add more tables to the database?

Some things I can think of that could benefit from more data structures inside Game:

Quickly finding the component corresponding to an identifier would be useful for any component that wants to directly talk to other components.

Being able to quickly find components of a particular type would help for “checks”. For example, suppose a component needs to check for collision. There may be only a few distinct colliders among all the components, so it doesn’t make sense to have the check scan all the components in the game.

These features make a lot of sense as the basis for adding scripting. Analogously, scripts on the web need to make use of functions for finding DOM elements (getElementByID, getElementsByClassName, etc), so similarly, at some point we must provide a way for scripts to find and interact with game components.

Beyond having fast querying over the components, there’s another reason why pushing more book-keeping into Game is useful. The set of components is not necessarily fixed. New components can be added, and existing components might be removed, after the game has begun running. Does it really make sense for the responsibility of tracking all the additions and removals to fall on each component that might have subcomponents? That’s extra logic that would have to be added to each type of component (and there could be many), that doesn’t relate to the purpose of the component itself. Centralising this in Game would mean it is implemented just once, and avoids diffusing responsibility.

Components by ID

Let’s define a new interface for component types that want to opt-in to this:

type Identifier interface {
    Ident() string
}

And provide an implementation, designed to make it easy to adopt by embedding:

type ID string

func (id ID) Ident() string { return string(id) }

// Example embedding:
type Foo struct {
    ID
    // other fields
}
  • Because the type ID is designed to be embedded, it cannot be called Ident (neither could it be called ID if that were the name of the method) because then the embedding type (Foo in the example) would have both a field and a method with the same name, which is disallowed.
  • A named type is not the same type as its underlying type, so id can’t be returned from Ident directly. But it can be cast back to the underlying type.
  • However, a string literal is still fine as a value for the field in a struct literal (Foo{ID: "foo"}) because of the way literals work.

The data structure for the job is a textbook Go map:

type Game struct {
    //...snip...
    
    byID map[string]Identifier
}

Why not map[string]interface{}? No particular reason. All the components in the map will satisfy the Identifier interface, so using map[string]Identifier avoids the (very unlikely) programmer error of putting other things into the map.

Finally, when the component is registered and unregistered from Game, byID needs to be updated. Even if a component type is an Identifier, Ident might return an empty string, making the component anonymous.

Why not require all components to have an ID method? No particular reason, except that would mean adding it to every component type, including those that definitely don’t need it.

An alternative might be to provide an ID string as an argument to Game’s register function.

func (g *Game) registerOne(component, parent interface{}) error {
    // ... snip ...
    
    if id, ok := component.(Identifier); ok && id.Ident() != "" {
        if _, exists := g.byID[id.Ident()]; exists {
            return fmt.Errorf("duplicate registration of ID: %q", id.Ident())
        }
        g.byID[id.Ident()] = id
    }
    
    // ... snip ...
}

func (g *Game) unregisterOne(component interface{}) {
    // ... snip ...
    
    if id, ok := component.(Identifier); ok && id.Ident() != "" {
        delete(g.byID, id.Ident())
    }
    
    // ... snip ...
}

Components by parent

… that is, find subcomponents of a given component. No special interface is needed. There is a choice to be made around how to store the children of each parent. Attempt #1:

type Game struct {
    //...snip...
    
    // component -> subcomponents in a set of type map[interface{}]struct{}
    chidren map[interface{}]map[interface{}]struct{}
}

That looks a bit untidy and (this second part arguably not a problem) the iteration order of each set of children is unpredictable. Using a slice (as in map[interface{}][]interface{}) looks a bit neater and maintains order, but component removals happen in linear time with the number of child components.

To cut a long story short, I ended up implementing an “order-preserving” type Container that uses a slice for main storage but a map for reverse lookups and set-like operations. Here’s the core of the idea:

type Container struct {
    items []interface{}
    reverse map[interface{}]int
}

func MakeContainer(items ...interface{}) *Container {
    c := &Container{
        // in here, the items arg has type []interface{}
        items: items,
        reverse: make(map[interface{}]int),
    }
    for i, x := range items {
        c.reverse[x] = i
    }
    return c
}

// ... various other methods omitted ...

func (c *Container) Add(item interface{}) {
    c.reverse[item] = len(c.items)
    c.items = append(c.items, item)
}

func (c *Container) Remove(item interface{}) {
    i, ok := c.reverse[item]
    if !ok {
        // not present in the container
        return
    }
    c.items[i] = nil
    delete(c.reverse, item)
    if len(c.items) > 2*len(c.reverse) {
        c.compact()
    }
}

func (c *Container) compact() {
	i := 0
	for _, x := range c.items {
		if x == nil {
			continue
		}
		c.items[i] = x
		c.reverse[x] = i
		i++
	}
	c.items = c.items[:i]
}

c.items = c.items[:i] reduces the length of the slice, but it continues using the same underlying array, maintaining the same capacity. I did it this way, instead of allocating a new slice, because it seems likely that a Container that previously had a lot of items would have a similar number of items at a later point. However, compact then never frees any memory.

The children data structure then becomes:

type Game struct {
    // ...snip...
    
    // component -> children of component
    children map[interface{}]*Container
}

Components by path

I haven’t felt the need to implement this yet, but I gave it some thought. Two likely choices for a data structure in Game for speeding up path lookups might be:

// Direct: path string -> component
map[string]identifier{}

// Layers: Component -> name -> subcomponent
map[interface{}]map[string]interface{}

In the first case, lookup by a path string would need len(path) work to hash the path, but the total memory to store path strings would be quadratic in the depth of the game tree. That doesn’t seem ideal.

In the second case, once path is split by whatever the path separator token is into the path \(P\), there are \(O(|P|)\) lookups - but the whole path doesn’t need to be stored for each leaf component, avoiding the quadratic complexity. Seems like a winner.

Components by type

The fun one! First we need a way to represent types. Fortunately Go has this solved already with the reflect package: values of type reflect.Type are comparable and can be used as a map key:

type Game struct {
    //...snip...
    byType map[reflect.Type]*Container
}

But which types are worth “indexing”? Just take whatever reflect.TypeOf returns? This has the downside that matching interfaces aren’t recorded, only the concrete type.Consider the problem of finding all colliders. It’s unlikely that they will all have the same concrete type (Wall, Floor, Enemy, etc), but is more likely that they all satisfy an interface such as:

type Collider interface {
    CollidesWith(geom.Box) bool
}

Rather than capture concrete types, then, it seems better to capture behaviours (as represented by interfaces).

If we know all the interesting interface types, we can check them in register using type assertions (without resorting to reflect), but reflect is still needed to obtain the key in the map - the reflect.Type value representing each interface.

This is slightly contorted in Go. Because every value has a concrete type, reflect.TypeOf will never return a type representing an interface. One workaround recommended by the reflect package is to reflect.TypeOf a value of type pointer-to-interface (e.g. (*Collider)(nil)), and then use the Elem method to get the type being pointed to.

func (g *Game) registerOne(component, parent interface{}) error {
    
    // ...snip...
    
    // Register by concrete type
    g.byType[reflect.TypeOf(component)].Add(component)
    
    // Register by each interface type
    if _, ok := component.(BoundingBoxer); ok {
        g.byType[reflect.TypeOf((*BoundingBoxer)(nil)).Elem()].Add(component)
    }
    if _, ok := component.(Collider); ok {
        g.byType[reflect.TypeOf((*Collider)(nil)).Elem()].Add(component)
    }
    if _, ok := component.(Drawer); ok {
        g.byType[reflect.TypeOf((*Drawer)(nil)).Elem()].Add(component)
    }
    if _, ok := component.(Updater); ok {
        g.byType[reflect.TypeOf((*Updater)(nil)).Elem()].Add(component)
    }
    // etc
}

Can this be improved? Yes. reflect.Type can be used for interface checks using the Implements method. So if we put all the interesting interface types into a slice, we can loop over them - and we even get a chance to put more types into the slice at runtime before registering any components, in case the user of the game engine comes up with any more:

// Various values of reflect.Type to save us having to do the pointer-elem dance
var (
    BoundingBoxerType = reflect.TypeOf((*BoundingBoxer)(nil)).Elem()
    ColliderType      = reflect.TypeOf((*Collider)(nil)).Elem()
    DrawerType        = reflect.TypeOf((*Drawer)(nil)).Elem()
    UpdaterType       = reflect.TypeOf((*Updater)(nil)).Elem()
    // etc
)

// Behaviours contains all the interface types that are indexed in Game.byType.
var Behaviours = []reflect.Type{
    BoundingBoxerType,
    ColliderType,
    DrawerType,
    UpdaterType,
    // etc
}

func (g *Game) registerOne(component, parent interface{}) error {
    // ...snip...
    
    g.byType[reflect.TypeOf(component)].Add(component)
    
    for _, b := range Behaviours {
        if reflect.TypeOf(component).Implements(b) {
            g.byType[b].Add(component)
        }
    }
}

Since the number of behaviours should be fixed and small, there should not be much issue in storing a reference to each component per interface.

Combinations of the above

With more indexes comes more work required to update indexes. Even worse, there will be a point where adding yet more data structures to speed up finding components is increasing work for increasingly specific use-cases. That said, one combination of the above that I did end up implementing was between components by type and by ancestor…ish.

Going back to the collider example, it occurred to me that it’s not enough to simply find all the Colliders in the game. Suppose multiple levels are loaded at once, but only one is being shown at any given moment. byType[ColliderType] would end up containing Colliders from all the levels, and it would be bad if they all affected collision detection if the geometry overlapped. Even if not, avoiding collision detection between different levels might have merit for efficiency reasons. We want to find Colliders that descent from the same level.

The first iteration of the data structure worked a bit like this:

type abKey struct {
    ancestor  interface{}
    behaviour reflect.Type
}

type Game struct {
    //...snip...
    
    // {ancestor,behaviour} -> all the descendants of ancestor
    //    implementing the behaviour
    byAB map[abKey]*Container
}

func (g *Game) registerOne(component, parent interface{}) error {
    // Set parent first, since this is used later for byAB
    g.parent[component] = parent

    //...snip...
    
    for _, b := range Behaviours {
        if !reflect.TypeOf(component).Implements(b) {
            continue
        }
        // Starting with component and proceeding upwards,
        // add component to byAB for the current component
        // and behaviour.
        for p := component; p != nil; p = g.parent[p] {
            key := abKey{
                ancestor: p,
                behaviour: b,
            }
            if g.byAB[key] == nil {
                // can't add to a nil *Container
                g.byAB[key] = MakeContainer(component)
                continue
            }
            g.byAB[key].Add(component)
        }
    }
}

This structure is fast for lookups: g.byAB[key] returns the collection of components of a given type that are descendants of a given component in \(O(1)\). But, yet again, I wrote code that is quadratic in the depth of the game tree. The deeper a component is, the more ancestors it gets added to, and in the worst case every component is on the path of descendants. So for a tree that is \(D\) layers deep, byAB stores at least \(O(D^2)\) references to components, and that was beginning to use a few megabytes of RAM even in my small example game.

To fix this, I went with a similar approach to how I would index paths above. Instead of storing a reference to each component against every ancestor, I instead store it once against its parent (and the parent against its parent, and so on):

type abKey struct {
    parent    interface{}
    behaviour reflect.Type
}

type Game struct {
    //...snip...
    
    // {parent,behaviour} -> subcomponents of parent either
    //    implementing the behaviour, or themselves having
    //    descendants implementing that behaviour (or both).
    byAB map[abKey]*Container
}

func (g *Game) registerOne(component, parent interface{}) error {
    // Set parent first, since this is used later for byAB
    g.parent[component] = parent

    //...snip...
    
    for _, b := range Behaviours {
        if !reflect.TypeOf(component).Implements(b) {
            continue
        }
        // At each step, c is the direct subcomponent of p.
        // Note the double assignments.
        for c, p := component, g.parent[component]; p != nil; c, p = p, g.parent[p] {
            key := abKey{
                parent: p,
                behaviour: b,
            }
            if g.byAB[key] == nil {
                // can't add to a nil *Container
                g.byAB[key] = MakeContainer(c)
                continue
            }
            if g.byAB[key].Contains(c) {
                // c is already a child of p in byAB, so
                // no need to continue up the tree.
                break
            }
            g.byAB[key].Add(c)
        }
    }
}

The downside to avoiding the quadratic memory consumption is that lookups in this new byAB are more involved. The basic recursive approach is as follows:

// Query returns all components that descend from the
// given component and implement a given behaviour.
func (g *Game) Query(component interface{}, behaviour reflect.Type) []interface{} {
    var result []interface{}
    // component is its own ancestor, so check it first
    if reflect.TypeOf(ancestor).Implements(behaviour) {
        result = append(result, component)
    }
    key := abKey{
        parent: component,
        behaviour: behaviour,
    }
    for _, x := range g.byAB[key].items {
        if x == nil {
            continue
        }
        result = append(result, g.Query(x, behaviour)...)
    }
    return result
}

The built-in append, like MakeContainer above, is variadic. The ellipsis operator ... lets you provide a slice of arguments to a variadic argument in one go, instead of having to call append once for each item.

This implementation has the minor downside that each call to Query, including the recursive calls, allocates its own result slice (likely a few times as items grow it beyond capacity).

Maybe the calling code is happy to be given components one at a time. Oh! Sounds like a visitor pattern!

// Query visits all components that descend from the
// given component and implement a given behaviour.
func (g *Game) Query(component interface{}, behaviour reflect.Type, visit func(interface{})) {
    // component is its own ancestor, so check it first
    if reflect.TypeOf(ancestor).Implements(behaviour) {
        visit(component)
    }
    key := abKey{
        parent: component,
        behaviour: behaviour,
    }
    for _, x := range g.byAB[key].items {
        if x == nil {
            continue
        }
        g.Query(x, behaviour, visit)
    }
}

In my eagerness, I really wanted to use this for more than just collisions. What about drawing? Well, aside from components that draw, there are also components that affect the drawing of their descendants. Query(game, DrawerType, visit) will call visit for each Drawer under game, but skip calling visit with all those components in the middle that are not Drawers. This is surmountable using parent, but Query itself is recursively visiting those intermediate components. Each visit function takes interface{} as its argument, and is therefore responsible for ensuring the value has the desired type, so all that is needed is to remove the reflective type check within Query.

Finally, since it looked like Query was fast becoming the new PreorderWalk, why not implement postorder traversal as well? (This is in fact necessary - if additional state has to be set up before visiting descendants, e.g. a draw transform, then that state might have to be un-wound after visiting the descendants.)

// Query visits all components that descend from the
// given component and either implements the given behaviour
// or has descendants implementing that behaviour.
func (g *Game) Query(component interface{}, behaviour reflect.Type, visitPre, visitPost func(interface{})) {
    // Look ma, no check that component implements behaviour!
    // (And it often does not!)
    visitPre(component)
    key := abKey{
        parent: component,
        behaviour: behaviour,
    }
    for _, x := range g.byAB[key].items {
        if x == nil {
            continue
        }
        g.Query(x, behaviour, visitPre, visitPost)
    }
    visitPost(component)
}

With that, hopefully I have no more to say about recursion.

October 14, 2021 05:28 AM

September 24, 2021

Josh

Making a Game in Go, part 5

Last post about draw ordering, I promise.

In the first four posts of this series, I iterated on an implementation for a 2D game engine, starting from a minimal implementation of the ebiten.Game interface through to a system for organising components both in a logical hierarchy as well as a data structure for drawing the right component at the right time (assuming the components can be totally ordered). The previous post ended on some open pondering on whether switching from sort.Sort to a topological ordering made sense, from both an ease-of-use perspective (the user can define fewer ordering constraints) and an efficiency perspective (big-O amount of work is potentially quadratic).

Friends, it does make sense to implement topological ordering. And all the other kinds, too.

Making things easier for the users of a library is often a good call. Accidentally sorting things incorrectly, because they happen to not be totally ordered, could be really confusing.

And it’s not always the library writer’s job to shield the users from inefficiencies. While a library should ideally aim to avoid needless inefficiency, there are other concerns to balance, like maintainability and ease-of-use, and some problems are by their very nature intractable, or at least difficult in the sense of requiring a lot of processing to solve.

A library or framework can embody the opinions of its author. A responsible library author would clearly document the chosen tradeoffs - at least a big fat “this implementation is hella slow” in the godoc and example code would go a long way. Designing the library interface to avoid or discourage inefficient usage could be even better.

If a game maker wants to overlap thousands of components in the same place, knowing that it would probably be inefficient given the engine being used, then that’s a little bit on them.

And good library might offer a few different approaches, and let the user pick among them.

But all discussion of theoretical efficiency is kind of moot. What matters is how the program behaves when it is actually run. As long as the game’s performance isn’t annoying players, it almost doesn’t matter what kind of algorithm is being used.

By performance I don’t just mean framerate. Other concerns players might have include memory usage, remaining battery, GPU fan noise, wear on the hard drive, secretly mining cryptocurrencies (which, to be clear, are all evil - this isn’t hyperbole - if you support cryptocurrencies or NFTs then you are morally bankrupt and any rights you might have had to read my blog are revoked), the ongoing climate catastrophe…

Benchmarking and profiling tools exist to measure how fast an implementation is. A heuristic I’ve been using is to take a CPU profile, and compare how long is spent preparing to draw versus actually drawing. Actually drawing should take a bit longer.

For my own goals, I’m aiming to make my game run at 60fps under WebAssembly on an iPad. In a rough early cut of implementing topological ordering, the framerate on my iPad began to dip a bit below 60. But, with a little work, it runs about as quickly (often faster) than the previous sort method, even though it would be even slower in the worst case (and, bonus: everything is correctly ordered now).

The gory details

Let’s start with a few data structures.

More data structures? Why not keep everything in a flat slice? Because incremental changes to the right data structure might be more efficient overall compared with doing processing in-place on a flat slice.

Firstly, here is a type that is a set (of things to draw):

type drawerSet map[Drawer]struct{}

// Creating a drawerSet:
s := make(drawerSet)

// Inserting v into s:
s[v] = struct{}{}

// Removing v from s:
delete(s, v)

// Iterating over s:
for v := range s {
    ...
}

struct{} has no fields and there’s only one value of the type, which is struct{}{}, but you can still use it as a value type in a map.

Representing a set as map[...]struct{} versus map[...]bool is a stylistic choice.

On the one hand, iterating over map[...]struct{} does not require checking if the corresponding value is false, if that is a possibility, and there is (theoretically) no memory required to store each struct{}{}.

On the other, testing to see if something is an element is easier in map[...]bool, because failed lookups result in the zero value for the value type (false). if m[key] { instead of the longer if _, found := m[key]; found {. Also, true is slightly easier to type on many keyboards, compared with struct{}{}, when adding new values.

Secondly, a direct acyclic graph (DAG) data structure, implemented in a two-sided edge-set fashion:

type edges struct {
    in, out drawerSet
}

type dag map[Drawer]edges

This dag maps things to draw (type Drawer) to two sets: a set of things to draw before it (in) and a set of things to draw after it (out). I will now switch terminology: the things to draw are the vertices, and the ordering constraints are the edges linking the vertices together.

Some edge-list or edge-set implementations of graphs focus only on the outgoing edges from each vertex. I’m also recording ingoing edges, for reasons that will be explained soon. What is important is that if v is an element of d[u].out, then u should be an element of d[v].in.

Here’s a few methods for managing edges and vertices in dag:

// addVertex ensures the vertex is present, even if there are
// no edges.
func (d dag) addVertex(v Drawer) {
    if _, found := d[v]; found {
        return
    }
    d[v] = edges{
        in:  make(drawerSet),
        out: make(drawerSet),
    }
}

// removeVertex removes v, and all edges associated with v,
// in O(degree(v)).
func (d dag) removeVertex(v Drawer) {
    for u := range d[v].in {
        delete(d[u].out, v)
    }
    for w := range d[v].out {
        delete(d[w].in, v)
    }
    delete(d, v)
}

// addEdge adds the edge (u -> v) in O(1).
func (d dag) addEdge(u, v Drawer) {
    d.addVertex(u)
    d.addVertex(v)
    d[v].in[u] = struct{}{}
    d[u].out[v] = struct{}{}
}

// removeEdge removes the edge (u -> v) in O(1).
func (d dag) removeEdge(u, v Drawer) {
    delete(d[v].in, u)
    delete(d[u].out, v)
}

A quick note about addEdge and removeEdge. If u isn’t already in d, then d[u] has the value edges{}, or more verbosely, edges{in: nil, out: nil}. Using .in and .out on this value is safe (unlike, say, if the map stored pointers to edges, because then d[u] would be nil if u is not in the map) and deleting from .in and .out is also safe (because delete is documented to do nothing for nil maps). Setting values in .in and .out (where nil) would panic, however. This is why addEdge needs to call addVertex to ensure the maps exist, but removeEdge does not.

The degree of a vertex is how many edges connect to it. In a directed graph, the outdegree of a vertex is how many edges start with that vertex, and the indegree is how many end with that vertex. In- and out-degrees can be counted easily with dag: indegree of v is len(d[v].in) and outdegree is len(d[v].out)

Ease of counting indegrees and iterating out-edges suggests using a topological sorting algorithm based on… counting indegrees and iterating out-edges (Kahn’s Algorithm):

// topWalk visits each vertex in topological order, in time 
// O(|V| + |E|) and temporary memory O(|V|).
func (d dag) topWalk(visit func(Drawer)) {
    // We know the queue will contain each vertex at some point,
    // so preallocate to the full size.
    queue := make([]Drawer, 0, len(d))
    indegree := make(map[Drawer]int, len(d))
    for v, e := range d {
        if len(e.in) == 0 {
            queue = append(queue, v)
        } else {
            indegree[v] = len(e.in)
        }
    }

    // Visit every vertex (O(|V|)) and decrement indegrees for
    // every out-edge of each vertex visited (O(|E|)). 
    // Total: O(|V|+|E|).
    for len(queue) > 0 {
        u := queue[0]
        visit(u)
        queue = queue[1:]

        // Decrement indegree of each vertex v on an out-edge of u,
        // and enqueue v if its indegree is now 0.
        for v := range d[u].out {
            indegree[v]--
            if indegree[v] == 0 {
                queue = append(queue, v)
            }
        }
    }
}

This can be extended to tolerate (though not truly “support”) cyclic graphs; if there is a cycle, the queue will become empty but some vertices will remain unvisited. But, if there is a cycle, then there is no draw ordering that respects all the constraints. At this level of the library, it may be appropriate to enqueue an arbitrary unvisited vertex, perhaps one with minimal indegree, let it draw, and hope for the best.

Hope? What happened to “hope is not a strategy”?

Actually, hope is a strategy, just often a bad one.

Using the dag

Now I just have to get a dag loaded up with stuff to draw and enough ordering constraints, and we’re good to go. In the previous post this is where I threw my hands up, exlaiming “comparing everything against everything else is quadratic! This is going to suck!”. And that’s still true, in the worst case.

In practice, a game consisting of lots of things overlapping a small area is likely to be inscrutable to the player, and there might be easier ways to achieve the intended effect (e.g. a single flat image or animation instead).

The number of comparisons and ordering constraints can be reduced in the following two ways, among others:

  1. If something hasn’t moved (e.g. components that are “fixed terrain”), then we don’t have to re-evaluate its ordering against other fixed things.
  2. If, after projecting into screen space, two items don’t overlap, we don’t have to compare them. We can speed up finding potentially overlapping things in a variety of ways.

To simplify the rest of the discussion, I will assume every component that needs drawing also has a 3D bounding box, i.e. the Drawer interface now looks like:

type Drawer interface {
    Draw(*ebiten.Image, *ebiten.DrawImageOpts)
    BoundingBox() geom.Box
}

where geom.Box is a 3D analogue of image.Rectangle. This definition makes it harder on components that “just want to provide a Z value”, since they now have to invent a bounding box. Though, that bounding box could be:

geom.Box{
    Min: geom.Point{math.MinInt, math.MinInt, z},
    Max: geom.Point{math.MaxInt, math.MaxInt, z},
}

This is an edge case worth keeping in mind later - what happens with incredibly huge components?

For the sake of letting the game maker choose different draw-ordering approaches, let’s expose the DAG-based drawing code via a new type:

// DrawDAG manages drawing all subcomponents via a directed
// acyclic graph (DAG) to provide a topological ordering that
// satisfies draw ordering constraints.
type DrawDAG struct {
    Components []interface{}

    dag
    // TODO: any other helper data structures
}

Other approaches to drawing can have their own type. For instance, DrawDFS (short for “draw depth-first search”) could draw subcomponents in a depth-first traversal of the tree, without regard to whether the components have other ideas about their draw ordering. The game maker can then pick and choose which “draw manager” to use, or even write their own. With a bit of care, multiple draw managers could be used for different parts of the game tree!

Anyway.

The API for DrawDog DrawDAG will involve being notified of subcomponents being added and removed, as well as needing to take stock of all subcomponents initially. Since each component is actually a tree of components, registering and unregistering will have to happen recursively (recall Scan for finding immediate subcomponents of a component).

// Prepare prepares the DrawDAG by registering subcomponents.
func (d *DrawDAG) Prepare() {
    d.dag = make(dag)

    for _, c := range d.Components {
        d.Register(c)
    }
}

// Register registers the component and all subcomponents,
// recursively.
func (d *DrawDAG) Register(component interface{}) {
    if dr, ok := component.(Drawer); ok { 
        d.registerOne(dr)
    }
    if sc, ok := component.(Scanner); ok {
        for _, x := range sc.Scan() {
            d.Register(x)
        }
    }
}

// Unregister unregisters the component and all subcomponents,
// recursively.
func (d *DrawDAG) Unregister(component interface{}) {
    if sc, ok := component.(Scanner); ok {
        for _, x := range sc.Scan() {
            d.Unregister(x)
        }
    }
    if dr, ok := component.(Drawer); ok { 
        d.unregisterOne(dr)
    }
}

func (d *DrawDAG) registerOne(x Drawer) {
    d.dag.addVertex(x)
    
    // TODO: compare x against other vertices to find
    // draw ordering constraints to add to d.dag as edges.
    
    // For a slow quadratic-time implementation, imagine a
    // loop that compares x against every v in d.dag. 
}

func (d *DrawDAG) unregisterOne(x Drawer) {
    d.dag.removeVertex(x)
}

// Draw draws everything in the DAG in topological order.
func (d *DrawDAG) Draw(screen *ebiten.Image) {
    // This is similar to the previous implementation (Game.Draw),
    // except g is replaced with d as the root component, and the
    // loop over g.drawList is replaced with:

    d.dag.topWalk(func(x Drawer) {
        // ... loop body that determines if x is hidden and what
        // draw options to apply ...
        x.Draw(screen, &state.opts)
    })
}

// Update updates the DAG with changes to draw ordering
// constraints.
func (d *DrawDAG) Update() error {
    // Assume each component calls Update on any subcomponents,
    // similar to this loop.
    for _, x := range d.Components {
        if u, ok := x.(Updater); ok {
            if err := u.Update(); err != nil {
                return err
            }
        }
    }

    // TODO: update d.dag 
    return nil
}

After Update-ing subcomponents, DrawDAG is ready to update d.dag. A simplistic approach would be to delete d.dag and build it from scratch. But some work can be saved if we only update for components whose bounding boxes have changed. If registerOne and unregisterOne are relatively quick, we can remove all the components that changed, and re-add them. These changes to DrawDAG might look like:

type DrawDAG struct {
    Components []interface{}

    dag
    
    // Cache of last-known bounding box for each component:
    boxCache map[Drawer]geom.Box
    
    // TODO: any other helper data structures
}

func (d *DrawDAG) Update() error {
    // update subcomponents loop here
    
    // Remove and re-add components that have moved.
    var readd []Drawer
	for dr, bb := range d.boxCache {
		nbb := dr.BoundingBox()
		if bb != nbb {
			d.unregisterOne(dr)
			readd = append(readd, dr)
		}
	}
	for _, db := range readd {
		d.registerOne(dr)
	}
    return nil
}

func (d *DrawDAG) registerOne(x Drawer) {
    d.dag.addVertex(x)
    d.boxCache[x] = x.BoundingBox()
    
    // TODO: find draw ordering constraints involving x
}

func (d *DrawDAG) unregisterOne(x Drawer) {
    d.dag.removeVertex(x)
    delete(d.boxCache, x)
}

Note that this does not deal with the possibility that draw ordering might need to change in cases where bounding boxes remain unchanged. This could be added using an interface for components to report whether they’ve changed shape in the current update.

Still, this is an improvement on rebuilding the DAG on every update - components that have changed have their constraints checked, and components that are fixed only change if they were or are connected to something that changed. In the worst case this could still be every component, but for a scene consisting mostly of fixed terrain, this is a big improvement.

Next, let’s deal with avoiding comparisons in registerOne by checking if there are overlaps in screen space. A blunt-force approach, that makes the theoretical worst-case even more worse, is to divide screen space into equally-sized square chunks, and for each chunk, track the set of components that overlap that chunk.

type DrawDAG struct {
    Components []interface{}
    ChunkSize  int  // tunable!

    dag
    boxCache   map[Drawer]geom.Box
    chunks     map[image.Point]drawerSet
    projection geom.Projection
}

func (d *DrawDAG) registerOne(x Drawer) {
    d.dag.addVertex(x)
    xbox := x.BoundingBox()
    d.boxCache[x] = xbox
    
    // Project xbox into screen space and find chunk coordinates
    xrect := xbox.BoundingRect(d.projection)
    min := xrect.Min.Div(d.ChunkSize)
    max := xrect.Max.Sub(image.Pt(1, 1)).Div(d.ChunkSize)
    
    // Look in each overlapping chunk, and build a set of  
    // candidates to check (union of all overlapping chunks).
    candidates := make(drawerSet)
    var p image.Point
    for p.Y = min.Y; p.Y <= max.Y; p.Y++ {
        for p.X = min.X; p.X <= max.X; p.X++ {
            chunk := d.chunks[p]
            if chunk == nil {
                d.chunks[p] = drawerSet{x: {}}
                continue
            }
            // Merge chunk into candidates
            for c := range chunk {
                candidates[c] = struct{}{}
            }
            // Add x to the chunk
            chunk[x] = struct{}{}
        }
    }
    // Compare x against each candidate y
    for y := range candidates {
        // Don't create self-cycles
        if x == y {
            continue
        }
        // Do the bounding rectangles actually overlap?
        yrect := y.BoundingBox().BoundingRect(d.projection)
        if !xrect.Overlaps(yrect) {
            // x and y both overlap some chunk, but not each other
            continue
        }
        switch {
        case drawOrderConstraint(x, y):
            d.dag.addEdge(x, y)
        case drawOrderConstraint(y, x):
            d.dag.addEdge(y, x)
        }
    }
}

func (d *DrawDAG) unregisterOne(x Drawer) {
    d.dag.removeVertex(x)
    
    // Remove x from d.chunks
    // Since x.BoundingBox() might have changed, use the value
    // cached in d.boxCache instead (saved in d.registerOne) to
    // find the chunks containing x.
    
    xrect := d.boxCache[x].BoundingRect(d.projection)
    min := xrect.Min.Div(d.ChunkSize)
    max := xrect.Max.Sub(image.Pt(1, 1)).Div(d.ChunkSize)
    var p image.Point
    for p.Y = min.Y; p.Y <= max.Y; p.Y++ {
		for p.X = min.X; p.X <= max.X; p.X++ {
			delete(d.chunks[p], x)
		}
	}
	
    delete(d.boxCache, x)
}

// drawOrderConstraint details omitted; compares boxes to see
// which is in front/behind/on top/below/etc, calls DrawBefore/DrawAfter
func drawOrderConstraint(x, y Drawer) bool {...}

If the scene consists of small components that are spread out, this approach is pretty good. Each chunk will only have a few components, and each component is small, so there are few chunks to gather and few components to compare.

If the scene consists of lots of large, perpetually moving components, all overlapping the same chunks, then all this is bad! - at least \(O(A|V| + |V|^2)\), where A is the average screen area of the components (as measured in chunks, but that’s a constant factor).

It’s a start!

September 24, 2021 07:17 AM

September 15, 2021

Josh

Making a Game in Go, part 4

Welcome to Part 4 of this series. In parts 1 through 3, I built up a small game game engine to the point where it was useful for many styles of 2D game. Components from different parts of the game tree can be drawn in different orders, thus accomplishing most of what is needed for implementing platformers and top-down adventures where the walls have “height”.

Unfortunately… yes, the engine is still incomplete. There is one major style of “2D” game that will be difficult to implement in the engine so far: the “isometric” game.

Third Dimension entered the chat

I put “2D” in scare quotes precisely because “isometric” isn’t a 2D style - not really. It is a 3D style that is (usually) possible to draw entirely as a sequence of flat images.

Note: “Isometric” is also in scare quotes for reasons of pedantry explained by the Wikipedia article.

Let’s blunder onwards, and add a Z axis to the engine. It already sort-of has one, it’s just called DrawOrder. Wherever we currently have a 3D point for storing position or size information, we now use a 3D point. And when we need a 2D point (e.g. for drawing on the screen, which is always 2D), we’ll project the 3D point onto the 2D plane by adding some amount to each of X and Y that is proportional to Z:

// Int3 is our 3D vector type. It uses integer components.
type Int3 struct { X, Y, Z int }

// ..., bunch of image.Point-like methods omitted ...

type Projection { ZX, ZY float64 }

// Project projects a point from 3 dimensions into 2.
func (π Projection) Project(p Int3) image.Point {
    return image.Pt(
        p.X + int(π.ZX * float64(p.Z)),
        p.Y + int(π.ZY * float64(p.Z)),
    )
}

You can…?

Yes, π is a letter (of the Greek alphabet) and is therefore a valid identifier in Go. I used π because it is easy to type on a Mac (Option-P) and π is a conventional algebraic symbol for projections (in the same way \(x, y, z\) are variables in algebra). It doesn’t always have to mean the number 3.14159…

Now, “clearly”, if we return the Z position from DrawOrder (assuming the Z axis increases as objects get “nearer”) everything will be draw in the correct order, right?

func (s *Sprite) DrawOrder() int {
    return s.Actor.Pos.Z
}

Actually, that’s not enough. If two components have equal Z, then they are likely one on top of another, and if they overlap at all the one on top would need to be drawn later (if that is the “camera angle” implied by the projection).

So, uh, ok, I guess we’ll change everything to return two values from DrawOrder, and use the second value to tiebreak the draw-order on equal Z?

type Drawer interface {
    Draw(...)
    DrawOrder() (int, int)
}

func (d drawList) Less(i, j int) bool {
    az, ay := d.list[i].DrawOrder()
    bz, by := d.list[j].DrawOrder()
    if az == bz {
        // Y axis pointing downwards
        return ay > by
    }
    // Z axis pointing towards "camera"
    return az < bz
}

This is fine…if all your objects have flat, axis-aligned sides.

A character is supposed to be behind a hexagonal prism, but is drawn in front of it An example of incorrect drawing order. The stick figure is intended to be obscured by the prism, because it is behind the right side, but because the figure's Z value is higher than the back of the prism, it is drawn after the prism.

Whoops.

Fixing draw order, badly

I hinted fairly strongly in the previous section that isometric games really aren’t 2D games, they are at their core 3D games. Therefore we might look to how 3D games solve the problem.

3D games typically have access to a Z buffer, that records depth information on a per-pixel basis. The Z buffer answers the question “how far away was the geometry that resulted in each pixel?”, and is used during rendering to ensure closer things remain on top of things further away. For each pixel being drawn, if the pixel currently in the screen buffer came from something further away, it can be drawn over (and update the Z buffer with the new depth value), but if it came from something nearer, leave it alone.

Resorting to a Z buffer is a bit of a problem, for two reasons:

For fun 🤪 I tried hand-rolling a Z buffer using ebiten’s shader functions. Each shader has up to 4 input images but only 1 output image, so the Z buffer shader had to be separated into two shaders:

Sadly a single buffer cannot be used simultaneously as a source and a target for an ebiten shader, and the second shader tries to do that with the Z buffer. So I had the second shader write into a temporary buffer, copying most of the Z buffer in the process, then swapped the old Z buffer for the temp before the next draw.

All this mucking around with shaders and depth maps is overkill, and also - unsurprisingly? - didn’t have great performance with my toy example. Framerate dropped to 20fps on the WebAssembly build, with less than 200 components. Maybe I could have optimised it, but as solutions go, it seems a bit like cracking a walnut with the Mesta 50.

Fixing draw order, a bit gooder

How did old games manage isometric drawing on slow hardware without Z buffers? By just ordering everything correctly! It’s just that the ordering can’t be reduced to assigning every component one or two numbers compared in a consistent way.

Take the hexagonal prism example (essentially the same as an “isometric” square with the front and back truncated). After sketching a few of the arrangements on paper, the answer for this shape is:

Since this decision is specific to the prism shape, it will be up to the prism to make the decision, rather than providing some numbers that drawList can compare. This thinking led to a new Drawer interface and updated comparison:

type Drawer interface {
    Draw(...)
    DrawAfter(Drawer) bool
}

func (d drawList) Less(i, j int) bool {
    return d.list[j].DrawAfter(d.list[i])
}

DrawAfter is intended to compare the current Drawer with another, and reports if it thinks it should draw after the one it is given. Here’s the example implementation in Prism, and some other interfaces invented out of necessity along the way:

type BoundingBoxer interface {
    // geom.Box is like image.Rectangle but 3D.
    // BoundingBox returns a 3D axis-aligned bounding
    // box for the component.
    BoundingBox() geom.Box
}

type ZPositioner interface {
    // For flat objects that don't have depth (i.e. thickness),
    // they can just report a Z position.
    ZPos() int
}

// DrawAfter reports if the prism should be drawn after x.
func (p *Prism) DrawAfter(x Drawer) bool {
    // Prism has a BoundingBox method.
    pbox := p.BoundingBox()
    
    // Figure out the draw order based on the type of x.
    switch x := x.(type) {
    case BoundingBoxer:
        xbox := x.BoundingBox()
        
        // If there's no overlap in X, then no need to 
        // draw this after that.
        if pbox.Min.X >= xbox.Max.X || pbox.Max.X <= xbox.Min.X {
            return false
        }
        if pbox.Max.Z <= xbox.Min.Z { // p is behind x
            return false
        }
        if pbox.Min.Z >= xbox.Max.Z { // p is in front of x
            return true
        }
        if pbox.Min.Y >= xbox.Max.Y { // p is below x
            return false
        }
        if pbox.Max.Y <= xbox.Min.Y { // p is above x
            return true
        }
        // The hexagon special.
        // The plane separating the front and back 
        // is 8 pixels in.
        if pbox.Min.Z+8 <= xbox.Min.Z { 
            // x is in front of the front half of p
            return false
        }
        if pbox.Min.Z+8 >= xbox.Max.Z { 
            // x is behind the front half of p
            return true
        }

    case ZPositioner:
        return pbox.Min.Z > int(x.ZPos()) // p is after x
    }
    return false
}

This is not enough! Some screenshots from various attempts at fixing this:

Hexagons drawing in the wrong order The base-level prisms drawing in random order.
Hexagons drawing in the wrong order The stick figure is atop the coloured prism, but the prism still obscures the figure.

Now, the perplexing thing about the latter screenshot (the stick figure atop the coloured prism) was that:

And here’s why! The ordering provided to sort doesn’t have enough information to sort correctly. The prism knows when it was supposed to be drawn before or after the figure based on its midline, but the figure didn’t know this because that is a detail internal to Prism. So in some cases the figure and prism would both report false from DrawAfter. sort.Stable then considered them to be equal, preserving the existing ordering.

This can also happen transitively: the order between another prism and the coloured prism is known by sort, so if the figure and the other prism were in another relation known to sort, then sort.Stable might not have to compare the figure with the coloured prism at all!

More things are needed to make this sort-based approach work:

Here is the two-sided Less test:

type Drawer interface {
    Draw(...)
    DrawAfter(Drawer) bool
    DrawBefore(Drawer) bool
}

func (d drawList) Less(i, j int) bool {
    return d.list[i].DrawBefore(d.list[j]) ||
        d.list[j].DrawAfter(d.list[i])
}

And the corresponding implementations in Prism (working!):

// DrawAfter reports if the prism should be drawn after x.
func (p *Prism) DrawAfter(x Drawer) bool {
    pbox := p.BoundingBox()
    switch x := x.(type) {
    case *Prism:
        // Fast path for other prisms
        if p.pos.Z == x.pos.Z {
            return p.pos.Y < x.pos.Y
        }
        return p.pos.Z > x.pos.Z

    case BoundingBoxer:
        xbox := x.BoundingBox()
        if pbox.Max.Z <= xbox.Min.Z { // p is behind x
            return false
        }
        if pbox.Min.Z >= xbox.Max.Z { // p is in front of x
            return true
        }
        if pbox.Min.Y >= xbox.Max.Y { // p is below x
            return false
        }
        if pbox.Max.Y <= xbox.Min.Y { // p is above x
            return true
        }
        // The hexagon special.
        if pbox.Min.Z+8 <= xbox.Min.Z { 
            // x is in front of the front half of p
            return false
        }
        if pbox.Min.Z+8 >= xbox.Max.Z { 
            // x is behind the front half of p
            return true
        }

    case ZPositioner:
        return pb.Min.Z > int(x.ZPos()) // p is after x
    }
    return false
}

// DrawBefore reports if the prism should be drawn before x.
func (p *Prism) DrawBefore(x Drawer) bool {
    pbox := p.BoundingBox()
    switch x := x.(type) {
    case *Prism:
        // Fast path for other prisms
        if p.pos.Z == x.pos.Z {
            return p.pos.Y > x.pos.Y
        }
        return p.pos.Z < x.pos.Z

    case BoundingBoxer:
        xbox := x.BoundingBox()
        if pbox.Min.Z >= xbox.Max.Z { // p is in front of x
            return false
        }
        if pbox.Max.Z <= xbox.Min.Z { // p is behind x
            return true
        }
        if pbox.Max.Y <= xbox.Min.Y { // p is above x
            return false
        }
        if pbox.Min.Y >= xbox.Max.Y { // p is below x
            return true
        }
        // The hexagon special
        if pbox.Min.Z+8 >= xbox.Max.Z { 
            // x is behind the front half of p
            return false
        }
        if pbox.Min.Z+8 <= xbox.Min.Z { 
            // x is in front of the front half of p
            return true
        }

    case ZPositioner:
        return pbox.Max.Z < int(x.ZPos()) // p is before x
    }
    return false
}

This is still a lot of trouble to go to, and it is incomplete. For simplicity the examples above bake in constants about the shape of the prism (8 pixels!) and the “camera angle” implied by the projection. The “real” code is more involved. Some of the repetitive logic could be refactored into, say, Less, to do “obvious” cases involving BoundingBox correctly, leaving only the special cases for each implementation of Drawer to handle.

But is there a “textbook” correct approach?

Fixing draw order properly?

Shaun Lebron provides a useful explanation of isometric draw ordering. To summarise Shaun’s post:

  1. Find all pairs of compnents that could overlap (after projecting them onto the screen space).
  2. Use separating planes to find the relative order between them. These become directed edges in a graph, where the components are the vertices.
  3. Use a topological sort of the graph to produce a draw order.

What is the algorithmic complexity of this approach? Here’s a naïve function which implements step 1:

// BoundingRect returns an image.Rectangle that bounds the box if it were
// projected.
func (b Box) BoundingRect(π Projection) image.Rectangle {
    // details omitted
}

type drawerPair [2]int

// FindOverlaps finds pairs of components that might overlap
// in screen space.
func (d drawList) FindOverlaps(π Projection) []drawerPair {
    var edges []drawerPair
    for i, u := range d {
        switch u.(type) {
        case BoundingBoxer:
            urect := u.BoundingBox().BoundingRect(π)
            for j, v := range d {
                if i == j {
                    continue
                }
                switch v.(type) {
                case BoundingBoxer:
                    vrect := v.BoundingBox().BoundingRect(π)
                    if vrect.Overlaps(urect) {
                        edges = append(edges, drawerPair{i, j})
                    }
                case ZPositioner:
                    // ZPositioners overlap everything.
                    edges = append(edges, drawerPair{i, j})
                }
            }
            
        case ZPositioner:
            // ZPositioners overlap everything.
            for j := range d {
                if i == j {
                    continue
                }
                edges = append(edges, drawerPair{i, j})
            }
        }
    }
    return edges
}

Slight differences in detecting overlap aside, the structure of this function looks like typical \(O(n^2)\) time complexity - for each component, it searches through the whole list for other components that could overlap. And that is exactly right. We might be able to reduce this with some fun data structures for efficiently finding potential overlaps, and exclude ZPositioner (it produces lots of edges, but it may be possible to deal with them separately).

But consider the best algorithms for topological sort, which work in time \(O(|V|+|E|)\) (i.e. time linear in number of vertices plus number of edges). Our plucky game developer might be implementing a game with tons of overlaps, leading to a large number of edges \(|E| \approx |V|^2\) - then \(O(|V|+|E|) = O(|V|^2)\) (quadratic) as well. The fussy sort.Stable approach, at \(O(n(\log n)^2)\), is starting to seem not so shabby!

September 15, 2021 11:30 AM

Making a Game in Go, part 3

In Part 1 of this series, I described an overly simple but not terribly useful basis for a game engine in Go. In Part 2, I explained one way to divide the work of drawing and updating components when they are arranged in a hierarchy, with the drawback that the ordering between subcomponents of different parent components cannot be changed.

In this Part 3, I will take the other “fork of the road” and write about extra data structures to overcome those limitations.

The downsides

Before implementing a bunch of data structures and algorithms it is worth reflecting on what is about to be lost by doing so.

The method of delegating work from each component to each of its direct subcomponents (as in the previous post) has its upsides:

But there are responses to each of these points, too:

Finally, since I’m still at the “engine” layer of the game code, it makes sense to do all the clever stuff here. Though hopefully it’s obvious to any game programmers reading this that I’m not doing anything novel, or particularly clever. (Doing it is its own reward!)

To make it so that we can draw things in an order that is not constrained by the logical organisation of the game tree, the responsibility for drawing can’t just be delegated to the subcomponents in turn. Drawing has to be managed in some central place.

The draw list

In previous posts, there were two separate interface types for drawing (Drawer) and providing draw ordering information (DrawOrderer). Let’s combine them. Not only do they tend to be implemented together, but I shall put them together if only for the sake of some conceptual simplifications later:

type Drawer interface {
    Draw(screen *ebiten.Image, opts *ebiten.DrawImageOpts)
    DrawOrder() int
}

Recall that the goal is to be able to draw things in order, no matter where they are in the game tree. We have a data structure for things that are in an order: a slice. (Or an array, a list, or whatever it is called in your favourite language. In Go, a slice.)

type drawList []Drawer

Secondly, we must be able to keep the items in a drawList sorted, so let’s implement sort.Interface:

func (d drawList) Less(i, j int) bool {
    return d[i].DrawOrder() < d[j].DrawOrder()
}

func (d drawList) Len() int {
    return len(d)
}

func (d drawList) Swap(i, j int) {
    d[i], d[j] = d[j], d[i]
}

Why not use sort.Slice, like before?

No particular reason, other than demonstrating two ways of doing it.

We can put the drawList into Game as a field (called drawList). Game.Draw can be simplified to just draw the draw list without any type assertions, and Game.Update can now keep it sorted in one line:

type Game struct {
    // Not all the components, just the top-level ones.
    Components []interface{}
    
    // All the components that can be drawn.
    drawList drawList
}

func (g *Game) Draw(screen *ebiten.Image) {
    for _, d := range g.drawList {
        d.Draw(screen, nil)
    }
}

func (g *Game) Update() error {
    // ... Updates happen here ...
    
    // Keep the draw list sorted
    // Use stable sort to prevent flickering between items
    // with equal draw order value.
    sort.Stable(g.drawList)
    return nil
}

Why aren’t you checking if the list is already sorted, like before?

Aside from being shorter code, the sort algorithms are probably reasonably good on data that is already sorted, and if the draw order is changing frequently, the check is mostly redundant.

The problems now are:

Let’s fix those.

Scanning

We know that the components will be arranged in a tree. And some components are likely to have different internal arrangements to others. Scene, from Part 2, is essentially just a flat slice of subcomponents, whereas a hypothetical Sprite might consist of exactly two subcomponents called SpriteSheet and Actor.

We also want Game to find out about all the components. Perhaps it needs a way to traverse the tree.

To abstract away the details of how subcomponents are stored, and just get them in a consistent way, here is another interface:

type Scanner interface {
    Scan() []interface{}
}

Scan is intended to return all the direct subcomponents of a component. I called it Scan because it “scans” the internals of the component, but some alternative names for the method might be Subcomponents or Children.

Two different example implementations might look like:

type Scene struct {
    Components []interface{}
}

func (s *Scene) Scan() []interface{} { 
    return s.Components
}

type Sprite struct {
    Sheet SpriteSheet
    Actor Actor
}

func (s *Sprite) Scan() []interface{} {
    return []interface{
        &s.Sheet,
        &s.Actor,
    }
}

How would Game make use of Scan? With a depth-first search, of course. In fact if we make Game itself implement Scanner, then the depth-first search doesn’t even have to be a method of Game. Here’s a function that calls some callback function for every component it can reach from some starting component recursively, using Scan:

// Walk walks through a tree of components by calling Scan
// to find subcomponents of each component. It visits components
// in depth-first order.
func Walk(component interface{}, visit func(interface{})) {
    visit(component)
    if sc, ok := component.(Scanner); ok {
        for _, c := range sc.Scan() {
            Walk(c, visit)
        }
    }
}

And thus we can build drawList:

func (g *Game) Scan() []interface{} { return g.Components }

// Load is used to load the game. Call this after setting up
// g.Components.
func (g *Game) Load() {
    // First make sure drawList is empty (in case Load is
    // called again).
    g.drawList = nil

    // Use Walk to find all the Drawers in the game tree,
    // and add them to the draw list.
    Walk(g, func(c interface{}) {
        if d, ok := c.(Drawer); ok {
            g.drawList = append(g.drawList, d)
        }
    })
}

Hiding and transforming

A feature implemented in Part 2 was that each component could be drawn using options derived from its parent, and its grandparent, and so on. Examples were:

The game engine shouldn’t really care how each component wants to store state, so again, we can abstract these ideas with interfaces:

type Hider interface {
    Hidden() bool
}

type Transformer interface {
    Transform() ebiten.DrawImageOpts
}

Here ebiten.DrawImageOpts is used as the container for transforms to apply, as before, but we could use some other type if we want to do more things than apply geometry or colour matrices.

These interfaces are separate from Drawer, despite being concerned with things that primarily affect drawing, because they are useful for parent components that might not do any drawing themselves. For example, a Scene, which just contains other components, doesn’t draw anything itself, but might return a geometry matrix that moves all the components within it (establishing its own coordinate system).

Why Hidden and not Visible?

It’s true that dealing with the logical negation of a condition increases the chances of negation confusion (!NotVisible()?) However, I chose to keep Hidden instead of Visible as Hidden is congruous with the one implementation of the interface I’ve made so far. The visible/hidden state can be stored, and the interface implemented, by embedding a type such as the following:

type Hides bool

func (h Hides) Hidden() bool { return bool(h) }

func (h *Hides) Hide() { *h = true }
func (h *Hides) Show() { *h = false }

type SomeComponent struct {
    Hides  // brings Hidden, Hide, and Show methods with it
    ...
}

Hidden works better than visible for this case because the default value of any variable or field, if uninitialised, is the zero value for the type, which for bool is false. That means that when constructing a component with a Hides field, Hides doesn’t need to be set to false - it comes that way naturally. If it were done the other way around, i.e. with a field called Visible, then it would have to be explicitly set to true all the time all over the place.

Why Hides and not Hidden for the type name?

Hidden is considered more “readable” than IsHidden because getter-style naming is discouraged. But a struct type cannot have both a field and a method with the same name, and that applies even if you are acquiring a method for your type by embedding another type. The easier thing to change is the type name. Embedding Hides makes the struct descriptive of one of its behaviours (i.e. “this component has the behaviour ‘hides’, as in, is capable of hiding”), even if the name is awkward when setting the field.

The Parent Trap

With Hider and Transformer, the Draw method of Game can now use that information to hide components and transform drawing for those that aren’t hidden. An immediate, yet incorrect, implementation is as follows:

// Wrong!
func (g *Game) Draw(screen *ebiten.Image) {
    for _, d := range g.drawList {
        // Hidden?
        if h, ok := d.(Hider); ok && h.Hidden() {
            continue
        }
        // Transformed?
        var opts ebiten.DrawImageOpts
        if tf, ok := d.(Transformer); ok {
            opts = tf.Transform()
        }
        // Draw!
        d.Draw(screen, &opts)
    }
}

This is wrong because it doesn’t combine the values returned from Hidden and Transform from the parent components, which is what we wanted. So how do we do that? In the Part 2 way of doing things, this was easy to implement because if a parent component was hidden or wanted to supply draw options, it changed how it drew its subcomponents!

In order to obtain the cumulative hidden and transform values, Draw must follow the chain of parents up the tree, so that it may call Hidden and Transform on them. There are two ways we could store the information:

  1. Have all the components store a reference to their parent, and supply it via some new interface (Parenter?)
  2. Implement another helper data structure inside Game.

Option 1 kind of sucks, because the majority of components don’t really need to know anything about their parents or ancestors. The information is stored implicitly by the structure of the tree. If this were implemented, the “parent pointer” either needs to be set manually (asking for trouble) or the hypothetical Parenter interface also needs to have another method Game can use to provide the information as it Walks the game tree. Or we repurpose Scan or something.

Since the information is primarily for the benefit of Game and nothing else, let’s go with option 2:

type Game struct {
   Components []interface{}
   
   drawList drawList
   parent   map[interface{}]interface{}
}

parent is intended to be a map of components to their parent components.

Huh? map[interface{}]...?

Yes! You can use interface types as map keys in Go. This is a thing that works!

The majority of game components are going to be pointers to struct types, and pointer values are comparable. This also means you can have pointers as map keys: map[*T]... This sort of thing is a bit iffy in some other languages because they desire to have map or dictionary types disregard “object identity” (i.e. memory location) in favour of comparing the values being pointed at. Go has no operator overloading, EqualTo() / Hash() override, or the ability to supply such functions to the map builtin type, so pointers-as-map-keys really does mean that Go will hash and compare the pointers themselves. This pattern is useful when we need a shadow data structure to secretly augment the data we’re given with extra data on a per-item basis.

Next, we need to populate parent. The depth-first Walk above doesn’t supply enough information to visit to record the parent of each component, so let’s change that so that the visit callback is passed each component and its parent:

// Walk walks through a tree of components by calling Scan
// to find subcomponents of each component. It visits components
// in depth-first order. For the first component visited, visit
// is passed nil as the parent.
func Walk(component interface{}, visit func(c, p interface{})) {
    walk(component, nil, visit)
}

// Actual implementation of Walk.
func walk(component, parent interface{}, visit func(c, p interface{})) {
    visit(component, parent)
    if sc, ok := component.(Scanner); ok {
        // Recursively walk all of component's subcomponents.
        for _, c := range sc.Scan() {
            // component is the parent of c
            walk(c, component, visit)
        }
    }
}

With that in place, Load can be updated to build parent:

// Load is used to load the game. Call this after setting up
// g.Components.
func (g *Game) Load() {
    g.drawList = nil
    g.parents = make(map[interface{}]interface{})

    Walk(g, func(c, p interface{}) {
        if d, ok := c.(Drawer); ok {
            g.drawList = append(g.drawList, d)
        }
        g.parent[c] = p
    })
}

Note: You can append a nil slice, but you can’t set values in a nil map.

Now Draw can use it to accumulate the values needed to draw correctly:

// Correct but inefficient
func (g *Game) Draw(screen *ebiten.Image) {
drawLoop:
    for _, d := range g.drawList {
        var opts ebiten.DrawImageOpts
        
        // Starting at d, walk up the tree parent-by-parent
        // and skip drawing if any of them are hidden
        for p := d; p != nil; p = g.parent[p] {
            if h, ok := p.(Hider); ok && h.Hidden() {
                continue drawLoop
            }
            if tf, ok := p.(Transformer); ok {
                o := tf.Transform()
                
                // Concat o onto opts
                opts.GeoM.Concat(o.GeoM)
                opts.ColorM.Concat(o.ColorM)
            }
        }
        
        d.Draw(screen, &opts)
    }
}

This is nice. Unfortunately, if the game tree is deep, this can become slow. If we are at a component of distance \(n\) from the root of the tree, then the inner loop has \(O(n)\) iterations, and each of the components along the way could themselves be in the draw list - the inner loop might be executed for them too. Therefore Draw has time complexity \(O(n^2)\). For most 2D games this isn’t likely to be a huge issue, but if the engine is going to be useful as a general library, we ought to ensure a faster solution.

Since whether or not a component is hidden, or what its transform is, is not likely to change in between calls to Hidden and Transform, we can cache the accumulated value for each component, computing them only once.

Here it is. Feel free to skip ahead:

func (g *Game) Draw(screen *ebiten.Image) {
    type state struct {
        hidden bool
        opts   ebiten.DrawImageOptions
    }
    cache := map[interface{}]state{
        // The Game g is not hidden, has no transform,
        // and is the topmost component. Filling this in
        // provides a terminal case for the inner loop.
        g: {hidden: false},
    }

	for _, d := range g.drawList {
        // Is d hidden itself? Shortcut.
        if h, ok := d.(Hider); ok && h.Hidden() {
            // in case we encounter any descendants of d
            cache[d] = state{hidden: true}
            continue // skip drawing
        }
        
        // Walk up g.parent to find the nearest cached state.
        // Record a stack of components we saw along the way.
        // This loop terminates because it will reach hit g
        // eventually.
        var st state
        stack := []interface{}{d}
        for p := g.parent[d]; ; p = g.parent[p] {
            if s, found := cache[p]; found {
                st = s
                break
            }
            stack = append(stack, p)
        }
        
        // Unwind the stack, computing state along the way.
        // Everything in the stack doesn't have a cached state,
        // so save time in future iterations by caching the
        // intermediate values.
        for len(stack) > 0 {
            l1 := len(stack) - 1
            p := stack[l1]
            stack = stack[:l1]
            if h, ok := p.(Hider); ok {
                st.hidden = st.hidden || h.Hidden()
            }
            if st.hidden {
                cache[p] = state{hidden: true}
                continue
            }
            // p is not hidden, so compute cumulative opts.
            // Note the reverse Concat (st.opts onto o,
            // then swap).
            if tf, ok := p.(Transformer); ok {
                o := tf.Transform()
                o.GeoM.Concat(st.opts.GeoM)
                o.ColorM.Concat(st.opts.ColorM)
                st.opts = o
            }
            cache[p] = st
        }
        
        // Skip drawing if hidden.
        if st.hidden {
            continue
        }
        d.Draw(screen, &st.opts)
    }
}

You can define types inside functions?

Yes.

Registering and unregistering

There is one last piece needed before pressing on. In the Part 2 paradigm, each component could change its subcomponents without telling anything else. It’s none of ya business!

In this new paradigm, any components that come into existence after Load won’t be drawn, because they won’t be in the draw list, unless we tell Game somehow.

We could call Load again, and figure out the draw list and the parents from scratch. This would be fine, because all Load is doing is building up a database of components, and that should be pretty snappy. But later on we will also want to load images, sounds, and other resources from disk, for example, so re-Load-ing could ultimately be quite slow.

Instead, we provide a method to call when components are added or removed. Behold, Register:

func (g *Game) Register(component, parent interface{}) {
    if d, ok := component.(Drawer); ok {
        g.drawList = append(g.drawList)
    }
    g.parent[component] = parent
}

The new component will be put into sorted order in the next Update, so there is no need to do a whole careful insertion dance.

But notice that Register has the same body as the function passed to Walk in Load, so let’s refactor Load:

func (g *Game) Load() {
    g.drawList = nil
    g.parents = make(map[interface{}]interface{})

    Walk(g, g.Register)
}

What the heck is the method g.Register doing without parentheses and arguments?

You can “curry” methods in Go. The expression g.Register is a function with the signature func(interface{}, interface{}) that saves the reference to g:

reg := g.Register
reg(c, p)  // same as calling g.Register(c, p)

You can also go the other way: if you want a function with the signature func(*Game, interface{}, interface{}), you can use the expression (*Game).Register:

reg := (*Game).Register
reg(g, c, p)  // same as calling g.Register(c, p)

But hold up a sec! That’s cute and all, but what if the new component being registered has subcomponents of its own - shouldn’t they be registered too? You raise a good point:

// Infinite recursion
func (g *Game) Register(component, parent interface{}) {
    walk(component, parent, g.Register)
}

Uh… please hold… To break the recursion we can separate the function that registers one component from the user-friendly method that registers a whole subtree:

// Register registers a component and all its descendants
// with the game.
func (g *Game) Register(component, parent interface{}) {
    // Note the lowercase "register"
    walk(component, parent, g.register)
}

// register registers one component with the game.
func (g *Game) register(component, parent interface{}) {
    if d, ok := component.(Drawer); ok {
        g.drawList = append(g.drawList)
    }
    g.parent[component] = parent
}

What about un-registering? Our first cut implementation isn’t brilliant:

// Subtle future whoops!
func (g *Game) Unregister(component interface{}) {
    Walk(c, g.unregister)
}

// Small quadratic whoops!
func (g *Game) unregister(component, _ interface{}) {
    var newList drawList
    for i, d := range g.drawList {
        if d != component {
            newList = append(newList, d)
        }
    }
    delete(g.parent, component)
}

There are two minor issues:

The second issue is left as an exercise for the reader. (Rename walk to preorderWalk, make a copy, call it postorderWalk, and then swap the order of looping over the result of Scan and the call to visit. Then use that in unregister).

The first issue we can solve with another map and a couple of other tricks. Let’s build the improvements into drawList.

type drawList struct {
    list    []Drawer        // index -> Drawer
    reverse map[Drawer]int  // Drawer -> index
}

reverse will be able to map from Drawer back into an index in list. So the idea is that unregister will be able to jump right to the index of the component to remove, and remove it:

func (g *Game) unregister(component, _ interface{}) {
    if d, ok := component.(Drawer); ok {
        i := g.drawList.reverse[d]
        // TODO: Somehow remove g.drawList.list[i] in constant time
        delete(g.drawList.reverse, d)
    }
    delete(g.parent, component)
}

More on that “TODO” soon.

When drawList is sorted, it really sorts drawList.list, but we also have to keep the reverse map up to date with the new indexes:

func (d drawList) Less(i, j int) bool {
    return d.list[i].DrawOrder() < d.list[j].DrawOrder()
}

func (d drawList) Len() int { return len(d.list) }

func (d drawList) Swap(i, j int) {
    d.reverse[d.list[i]], d.reverse[d.list[j]] = j, i
    d.list[i], d.list[j] = d.list[j], d.list[i]
}

Load must create the map in order to write stuff into it:

func (g *Game) Load() {
    g.drawList.list = nil
    g.drawList.reverse = make(map[Drawer]int)
    g.parent = make(map[interface{}]interface{})
    Walk(g, g.register) // or equivalently, g.Register(g, nil)
}

and in register we append to list and write the index we’re appending into to reverse:

func (g *Game) register(component, parent interface{}) {
    if d, ok := component.(Drawer); ok {
        g.drawList.reverse[d] = len(g.drawList.list)
        g.drawList.list = append(g.drawList.list, d)
    }
    g.parent[component] = parent
}

Finally, don’t forget that Draw now has to iterate over g.drawList.list.

Bring out yer dead!

Anyway, back to unregister and that TODO. There’s actually no reason we need to do a huge amount of surgery on drawList.list. Introducing tombstone:

type tombstone struct{}

func (tombstone) Draw(*ebiten.Image, *ebiten.DrawImageOpts) {}
func (tombstone) DrawOrder() int { return math.MaxInt }

Sorry… type tombstone struct{}? Struct with no fields? Also what’s with the methods having just types in the parentheses?

Yes, you can have a type that is an empty struct. Because it has no fields, there’s no reason to refer to the receiver by name in its methods. By the same logic, you don’t need to name any of the args if you don’t need them, similar to how unregister has one named arg (component) and one blank (the underscore, _).

The idea with tombstone is that when unregister-ing a component, we replace it with tombstone{} in the draw list:

func (g *Game) unregister(component, _ interface{}) {
    if d, ok := component.(Drawer); ok {
        i := g.drawList.reverse[d]
        g.drawList.list[i] = tombstone{}
        delete(g.drawList.reverse, d)
    }
    delete(g.parent, component)
}

tombstone doesn’t draw, so the component is gone (visually speaking). What cleans up the tombstones from the list? Well, eventually Update is called, and Update sorts the draw list. tombstone defines its DrawOrder as math.MaxInt, i.e. absolute last. So after sorting the draw list, Update can trim them off the end of the slice:

func (g *Game) Update() error {
    // ... Updates happen here ...
    
    // Keep the draw list sorted
    // Use stable sort to prevent flickering between items
    // with equal draw order value.
    sort.Stable(g.drawList)
    
    // Trim any tombstones on the end.
	for i := len(g.drawList.list) - 1; i >= 0; i-- {
		if g.drawList.list[i] != (tombstone{}) {
			break
		}
		g.drawList.list = g.drawList.list[:i]
	}
    return nil
}

But what if I have components that want to always draw last, and return a draw order of math.MaxInt?

If necessary, we can enforce tombstones are last regardless of DrawOrder with an override in drawList.Less:

func (d drawList) Less(i, j int) bool {
	if d.list[i] == (tombstone{}) {
		// tombstones are not less than anything,
		// even other tombstones
		return false
	}
	if d.list[j] == (tombstone{}) {
		// non-tombstones are less than tombstones
		return true
	}
	return d.list[i].DrawOrder() < d.list[j].DrawOrder()
}

Why trim the tombstones from the end, and not the front?

For (admittedly very marginal and theoretical) performance gain. After trimming from the end, the array underlying the slice will have capacity at the end, and the next append will reuse that space. (Okay but why not append to the front? Because that’s not how the built-in append function works.)

Hope you enjoyed Part 3. Join me for Part 4 soon, which I hope will be even longer!

September 15, 2021 01:29 AM

September 06, 2021

Josh

Making a Game in Go, part 2

In Part 1 of this series of posts, I sketched a simple game engine written in Go. The proposed engine was overly simplistic, but could conceivably be used as a starting point for simple 2D games.

In this post, I want to discuss a critical design decision that affects how easy it is to make more complicated 2D games.

Structure

Recall from the previous post that the main type for the overly-simple game engine looked like this:

type Game struct {
    Components []interface{}
}

And, when time came to update the game state or draw the components, Game delegated the relevant work to each component that had either of those behaviours.

The flat nature of the Components slice implies that all the components in the game sit at some equal level in a flat hierarchy, with one special component (Game) delegating work. It’s kind of like the false utopia of the theoretical “Valve Organizational Chart”:

Valve Organizational Charts (as envisioned by employees) From Valve Handbook For New Employees (p. 5), Valve Corporation, 2012, Valve Press, accessed 6 Sep 2021.

Whatever your opinion on company org-charts, game design often benefits from additional structure. Each component might itself consist of some other components. Compare this screenshot from Commander Keen 4, and a hypothetical hierarchy of components that might be driving the game under the hood:

Commander Keen 4 screenshot From Commander Keen 4: Secret of the Oracle, Id Software Inc., 1992, Apogee.

It seems clear that a game tree is a more natural way of describing a game than flattening all the components into a single list.

Fork in the road

There are two ways to adapt the game engine to handle more complicated game structures. These are:

  1. Don’t. Make every component responsible for calling Update and Draw on all its direct subcomponents. In turn, each subcomponent calls those methods on their direct subcomponents, and so on.
  2. Alternatively, each component and subcomponent (and so on) registers with Game, and Game does some book-keeping to track them all and the relationships between them. Then Game figures out when to call Update and Draw on all components.

The rest of this post will be about Approach #1. I will write about Approach #2 in the next post.

Commander Keen 4 looks like the kind of game that could be implemented easily with approach #1. It is a platformer which could be described as a “tilemap sandwich”: background tiles, midground tiles and sprites, and foreground tiles. This makes the top layer of the game tree “fixed”; there is never a need to reorder the layers.

Scenery

Approach #1 has a number of benefits for the engine programmer. In particular, the work is delegated from the top level Game object down through each subcomponent, so there is minimal book-keeping in the top-level object. Also, each component can easily influence its subcomponents.

Let’s implement a component that might be useful in such an engine. Here’s one called Scene, which is intended to be a bare-bones container of other components:

type Scene struct {
    Components []interface{}
}

func (s *Scene) Draw(screen *ebiten.Image) {
    for _, c := range s.Components {
        if d, ok := c.(Drawer); ok {
            d.Draw(screen)
        }
    }
}

func (s *Scene) Update() error {
    for _, c := range s.Components {
        if u, ok := c.(Updater); ok {
            if err := u.Update(); err != nil {
                return err
            }
        }
    }
    return nil
}

Note that *Scene implements both the Drawer and Updater interfaces itself, so when it is nested in Game or another Scene (e.g. the below), its methods get called as intended, and in turn delegates work to its subcomponents:

game := &Game{
    Components: []interface{}{
        &Scene{
            Components: []interface{}{
                &Scene{
                    Components: []interface{}{
                        ...
                    }
                }
            }
        }
    }
}

ebiten.RunGame(game)

But wait! Scene is almost exactly the same as Game! It’s doing the same things: loop over the subcomponents, and delegate work to those that have the applicable behaviour. It would even make sense to copy the draw-order sorting in Update from Game into Scene too, because a Scene could contain subcomponents that change draw order over time.

This suggests a refactor of Game:

type Game struct {
    Scene
}

By embedding Scene, Game now has the methods of Scene (Draw and Update), and calling these is equivalent to calling them on game.Scene. The only other thing from ebiten.Game is Layout, and for now, that isn’t useful for Scene to implement (it could be, though), so Game remains useful as a separate type.

Let’s make Scene more useful, though. Some things we might want to do during a game are:

This is easy to do in the Approach #1 paradigm. This could be implemented in Scene as follows:

type Scene {
    Components []interface{}
    Hidden bool
    Disabled bool
}

func (s *Scene) Draw(screen *ebiten.Image) {
    if s.Hidden {
        // Skip drawing
        return
    }
    // loop over Components and draw the Drawers
}

func (s *Scene) Update() error {
    if s.Disabled {
        // Skip updating
        return nil
    }
    // loop over Components and update the Updaters
}

Drawing stuff and relative positioning

To draw a sprite onto the screen in ebiten, one typically needs code like this:

var opts ebiten.DrawImageOpts

// The destination position is set by translating the geometry matrix
opts.GeoM.Translate(pos.X, pos.Y)

// The source image might be a sprite sheet containing a particular subimage
// needed at this moment
sx := frameSize.X * index
src := sourceImage.SubImage(image.Rect(sx, 0, sx+frameSize.X, frameSize.Y))

// Draw src onto screen at pos
screen.DrawImage(src, &opts)

Given the Scene implemented above, it would be inconvenient if, say, we wanted to translate everything in a Scene by the same offset - each component would need its position updated. This in turn means storing two different positions for each component: its draw position and its real position, and keeping them in sync somehow. This is a mess.

A similar but related problem would be to recolour all the components in a Scene, e.g. suppose we want to use a ColorM to adjust the colouring in a consistent way.

Relative positioning and recolouring and all sorts of fun is unblocked if we alter the Drawer interface:

type Drawer interface {
    Draw(screen *ebiten.Image, opts ebiten.DrawImageOpts)
}

This diverges from ebiten.Game. Game would be the logical place to interop between ebiten.Game and Drawer, by supply the initial opts value to Scene’s Draw method:

func (g *Game) Draw(screen *ebiten.Image) {  // implements ebiten.Game, not Drawer
    // Pass the zero value for opts
    g.Scene.Draw(scene, ebiten.DrawImageOpts{})
}

Each parent component such as Scene can modify opts before delegating drawing to its subcomponents:

type Point struct {
    X, Y float64
}

type Scene struct {
    Offset Point
    // ... other stuff ...
}

func (s *Scene) Draw(screen *ebiten.Image, opts ebiten.DrawImageOpts) {
    if s.Hidden {
        return
    }

    // Copy opts
    newOpts := opts
    
    // Reset GeoM to an identity matrix
    newOpts.GeoM.Reset()
    
    // Translate scenespace to worldspace (translate by s.Offset)
    newOpts.GeoM.Translate(s.Offset.X, s.Offset.Y)
    
    // Reapply the original opts.GeoM to translate into screenspace or whatever
    newOpts.GeoM.Concat(opts.GeoM)
    
    // Draw the subcomponents
    for _, c := range s.Components {
        if d, ok := c.(Drawer); ok {
            d.Draw(screen, newOpts)
        }
    }
}

And each component can use the opts provided from its parent component in basically the same way:

func (s *Sprite) Draw(screen *ebiten.Image, opts ebiten.DrawImageOpts) {
    // Copy opts
    newOpts := opts
    
    // Reset GeoM to an identity matrix
    newOpts.GeoM.Reset()

    // Translate from spritespace to worldspace
    newOpts.GeoM.Translate(s.pos.X, s.pos.Y)
    
    // Reapply opts.GeoM to translate from worldspace to screenspace via
    // whatever geometry matrix was supplied by the parent
    newOpts.GeoM.Concat(opts.GeoM)
    
    // Draw!
    src := ...
    screen.DrawImage(src, &newOpts)
}

Problems

Approach #1 gets a long way, especially for platformers and other tilemap sandwiches, because it is straightforward and the logical structure matches the draw order. There are a few well-defined layers, drawn in a fixed order, and each component in the hierarchy can affect its subcomponents directly because it is responsible for delegating work to them.

The limits of the approach are hit as soon as subcomponents in different parts of the game tree need to be drawn in different orders. Suppose we are implementing a top-down game with walls or other obstacles with “height”. They must partially obscure objects behind them, and are partially obscured by objects in front of them. (Spoilers: you are now making a 3D game.)

Awakeman walks around a column A sprite (Awakeman) walks around a column, and is alternately partially obscured by the column, and partially obscures the column.

Logically, all the “wall parts” might belong as subcomponents of a single “wall” component, especially if the parent component holds common properties of each part like “size” and “sprite sheet”.

But having all the wall parts be subcomponents of one wall would mean all the wall parts are drawn in one layer: the “wall layer”. The wall parts now can’t intermingle with other components in a dynamic way, because draw ordering happens for each layer, not across layers. If the draw ordering is fixed (i.e. the game consists of nothing but fixed walls) then there is hardly a problem, but this prohibits having a sprite that sometimes walks in front of walls and sometimes walks behind them, because the ordering between them cannot change.

This necessitates a compromise: the wall parts must be immediate subcomponents of all the other components they need to be sorted amongst. The parent Scene can then sort them as the draw ordering changes. Great!

Unfortunately this sucks, because now there is no single “wall”, just lots of horrible little pieces that are separate from one another, and if we need to change some common property of them, we must either:

  1. Find them all and change each one individually
  2. Do book-keeping to ensure each one has a pointer to some shared struct, and update that
  3. There is no 3.

Compromise #2 is the more sensible option, but it becomes gets harder if the game tree needs to be serialised and deserialised. If the pointer to the shared struct is serialised along with the wall part, then the deserialiser might decide to allocate each wall part its own copy of the “shared” struct! If the pointer is not serialised along with the wall part, then each wall part has to somehow be told about, or independently locate, the shared struct to use after being inflated.

The benefits of a hierarchy are lost. It seems some amount of book-keeping is actually necessary, so why not go back to the beginning and implement Approach #2? Let’s rip the bandaid off and make complex 2D games easier! Approach #2 will be written about in Part 3 of this series.

September 06, 2021 04:23 AM

August 29, 2021

Josh

Complexifying the code editing experience

Until now I’ve looked upon containers (Docker, etc) with a certain small amount of bemusement. Sure, they are useful at work. I just never really saw a point for them at home, and didn’t find the time to even begin playing around.

But! I’ve finally encountered a problem to which Docker seems like a solution. Based on some tinkering this weekend, I can tentatively declare Docker to be a great partial solution to the problem of running unsigned code on macOS Catalina.

“Uh, use a virtual machine for this?” Well, yes, actually that seems to be what is happening under the hood with Docker on Mac. The nice part is then being able to expose small parts of the Mac’s filesystem to specific containers, and network containers to one another with user-defined bridges, as opposed to making them go via a physical interface.

Here’s a silly example that I’m totally going to use for reals.

Suppose I wanted to use code-server running on a nice beefy machine sitting at home, in a secure way, from an iPad, somewhere on the internet. I want to do this because VS Code seems nice, but isn’t on the App Store, and this is the closest I’ve seen (second to screen sharing the real thing). Let’s also suppose I don’t want to use coder.com’s paid service or Visual Studio Codespaces or GitHub Codespaces, for no particular reason.

In my mind the ideal setup is: I tap a home screen icon and I’m in without any passwords or fuss, but anyone else snooping around is denied a connection. The FAQ has some ideas, but long story short, instead of using code-server’s inbuilt authentication mechanisms (password?) I’ll go straight for mutual TLS authentication, and a separate reverse proxy is a reasonable solution for that part.

Another long story short, let’s use ghostunnel for the mutual TLS. It’s specifically built for the simple case of mutual TLS, and proxying allowed connections to some other server. Sadly I couldn’t get the binary release to run on Catalina directly. Maybe they’ll fix it, or I could build it from source, or … oh look there’s a container image on Docker Hub. There’s one for code-server too - in for a penny, in for a pound?

Recipe

Not included in this recipe:

Notes on iPads, client TLS certificates, and WebSockets:

Steps

Download the container images:

$ docker pull squareup/ghostunnel
$ docker pull codercom/code-server

Create a bridge network specifically for connecting the two containers together (and nothing else):

$ docker network create code-net

Note the two containers will be able to reference one another by name.

Put the fullchain.pem and privkey.pem for the domain, plus the .crt for the self-signed CA, into $HOME/code-server/certs.

Run the containers:

$ docker run \
  --name code-server \
  --detach \
  --network code-net \
  --volume "$HOME/code:/home/coder/" \
  -u "$(id -u):$(id -g)" \
  codercom/code-server:latest \
    --auth none \
    --disable-updates
$ docker run \
  --name code-proxy \
  --detach \
  --network code-net \
  --publish 443:443 \
  --volume "$HOME/code-server/certs:/home/ghostunnel/" \
  squareup/ghostunnel:latest server \
    --listen :443 \
    --target code-server:8080 \
    --unsafe-target \
    --cert "/home/ghostunnel/fullchain.pem" \
    --key "/home/ghostunnel/privkey.pem" \
    --cacert "/home/ghostunnel/Josh_Root_Authority.crt" \
    --allow-all

The code-server container has access to the files in $HOME/code, as the user who created the container, thanks to the --volume and -u flags. I disable code-server passwords with --auth none and disable auto-updates with --disable-updates, because these are mildly annoying.

The code-proxy container, running ghostunnel, has access to the certs via another --volume mount, and is exposed on port 443. ghostunnel is usually pointing at localhost, but in this case it is not, hence --unsafe-target.

August 29, 2021 05:35 AM

August 28, 2021

Josh

Making a Game in Go, part 1

Oh, poor neglected blog!

I’m making a game.

Why Go?

I’m doing it this way because:

Headwinds

There are probably lots of reasons for me not use Go for making a game.

ebiten

ebiten is a library for making 2D games in Go. It takes care of the following:

But there is a conceptual gap between being able to draw stuff in a window, and using that to make an entire game - even a “simple” platformer or top-down adventure.

How to draw an owl. Step 1: draw some circles. Step 2: Draw the rest of the fucking owl.

So in this post I wanted to start writing about the thing I’m building now (an engine) that will provide a bunch of tools for building a thing on top of it later (a game).

Diagram showing layers of a game. From the top: game, game engine, graphics and input library, runtime, and operating system/web browser.

Engine

ebiten.RunGame requires we pass in something implementing ebiten.Game, which looks like this (comments removed, which you can read at the ebiten godoc):

type Game interface {
	Update() error
	Draw(screen *Image)
	Layout(outsideWidth, outsideHeight int) (screenWidth, screenHeight int)
}

Basically, ebiten calls these methods over and over. Update is supposed to read the input state and then update the game state by 1 “tick,” and Draw is where the game should do all the graphics (screen.DrawImage, for example). This is a reasonably straightforward application of a Go interface.

Up the other end of a game engine is the “game”, that is, whatever is special or unique about this particular game being made. A good engine library should be useful for making lots of different games and provide a good selection of common parts, but also be flexible enough to allow custom parts to be provided by the game maker.

The subproblems the author of a game engine needs to solve are therefore:

  1. How to represent the various parts of various games
  2. Organising the parts of the current game in a useful way
  3. Updating each part of the game that needs updating
  4. Drawing each part of the game that needs drawing (in the right order)

Representing and organising the parts of a game

It occurred to me that the different parts of a game (let’s call them components from now on) need to do different things. Some components need to accept user input and update state over time. Some components need to be shown on the screen.

One approach would be to require all the components to have both Draw and Update methods, and for each component to have a stub do-nothing implementation when it doesn’t need to do either drawing or updating.

Another approach, that makes sense in Go, is to look at each component to see if it supports a behaviour, before calling it. This can be done with type assertions, which are fairly fast. An incredibly tiny game engine (though one that doesn’t provide much value to the game maker) might therefore look like this:

package engine

import "github.com/hajimehoshi/ebiten/v2"

type Game struct {
    Components []interface{}
}

func (g *Game) Draw(screen *ebiten.Image) {
    // Find all the components that can be drawn, and draw them.
    for _, c := range g.Components {
        if d, ok := c.(Drawer); ok {
            d.Draw(screen)
        }
    }
}

func (g *Game) Update() error {
    // Find all the components that can be updated, and update them.
    for _, c := range g.Components {
        if u, ok := c.(Updater); ok {
            if err := u.Update(); err != nil {
                return err
            }
        }
    }
    return nil
}

// And here's what Drawer and Updater look like:

type Drawer interface {
    Draw(*ebiten.Image)
}

type Updater interface {
    Update() error
}

Need to change the order of things being drawn? Reorder the components in the g.Components slice.

Or, instead: the engine could make it easier on the game-maker by letting them opt-in to some mechanism to figure out the draw order based on some number provided by each component:


type DrawOrderer interface {
    DrawOrder() float64
}

func (g *Game) Update() error {
    // Find all the components that can be updated, and update them.
    ...
    
    // Check if any of the components are now out of order - if so, sort them.
    cz := -math.MaxFloat64 // fun fact: this is the minimum value of float64
    for _, c := range g.Components {
        if do, ok := c.(DrawOrderer); ok {
            if z := do.DrawOrder(); z < cz {
                g.sortByDrawOrder()
                return nil
            }
            cz = z
        }
    }
    return nil
}

func (g *Game) sortByDrawOrder() {
    // Use a stable sort to preserve the ordering of components with equal
    // DrawOrder values.
    sort.SliceStable(g.Components, func(i, j int) bool {
        a, aok := g.Components[i].(DrawOrderer)
        b, bok := g.Components[j].(DrawOrderer)
        if aok && bok {
            return a.DrawOrder() < b.DrawOrder()
        }
        return !aok && bok
    })
}

Problems

This approach is probably less efficient than it could be.

Firstly, however fast each interface type assertion is (i.e. c.(Drawer), c.(Updater), c.(DrawOrderer)), it will happen for every component on every call to Draw and Update. That could mean a lot of repetitious, unnecessary type assertions when they could all be done “up front”. Suppose Game keeps track of whether it has done this processing or not, and performs it if needed:

type Game struct {
    Components []interface{}
    
    processed bool
    drawers []Drawer
    updaters []Updater
}

func (g *Game) Update() error {
    if !g.processed {
        // Do type assertions once
        for _, c := range g.Components {
            if d, ok := c.(Drawer); ok {
                g.drawers = append(g.drawers, d)
            }
            if u, ok := c.(Updater); ok {
                g.updaters = append(g.updaters, u)
            }
        }
        g.processed = true
    }
    
    for _, u := range g.updaters {
        if err := u.Update(); err != nil {
            return err
        }
    }
    
    // ... Do draw-ordering check...
    return nil
}

A drawback to this is that instead of having to edit just one slice to change components in the game, as many as three would have to be updated. (Additional books leads to additional bookkeeping.)

Secondly, if the draw ordering changes a lot, that could mean a lot of sorting, which may mean a bit of memory churn depending on how the Go stable sort is implemented. Optimising this would probably require knowing a bit more about the game being made - for example, are changes to draw order being made smoothly, so there are at most a few “inversions” per frame?

To begin with, though, these aren’t necessarily problems for implementing a game. The game engine just needs to be fast enough, and as long as the number of components is small enough (millions might still be fine, even on slow computers - I haven’t benchmarked it), then the basic approach seeems acceptable.

August 28, 2021 09:38 AM

April 17, 2020

Josh

Week 6

The apartment

Still in Sydney. Still in the same place. Two bedrooms, but I use the second as office / games. A week or two ago we moved the second desk into the living room - more comfortable for Hannah than using the dining table I think, and space for the spare monitor. The apartment building next door is almost complete - the rooftop garden has plants and exercise equipment in it, which will be nice to gawk at.

Clothes

T-shirts and pyjama shorts. Except to leave the house, when I would put on jeans, and take a face mask and pocket hand sanitizer. After a brief cool patch with rain, it’s been warm again, so I ignore socks / slippers most of the time. Also Folding@Home is pumping the office full of heat.

Food

Home-made meals most of the time.

Breakfast was often muesli with oat m*lk, porridge, or sometimes eggs and avocado on toast.

Lunch tended to be either leftovers, things on toast, or occasionally freshly cooked food.

Dinner varied the most, with all sorts of delicious things: kimchi fritters, Thai curry meatballs, steak and mash, salmon and mash and broccolini, mixed noodles…

We only ordered delivery maybe once a week. It tended to be pizza on Fridays but was sometimes Indian or Thai.

Coffee

This week it was aeropress after showering, and a mid-morning syphon. A few weeks ago we used up the V60 filter papers but Hannah ordered more.

Other beverages

  1. Always Be Hydrating (ABH)
  2. Whisk(e)y, neat/ice cube/highball

TV

55 inches, still has that issue where the audio is screwed up sometimes when Chromecasting. Also I need to repair the stereo.

  1. I’m still catching up on Buffy…
  2. Slowly getting through season 2 of Altered Carbon
  3. Need to finish off Eizouken
  4. Hannah was keeping up with Terrace House
  5. We just finished Feel Good

Games

The garden

Indoors: Jamie’s rubber plant (as in ficus, not as in made of rubber), the fern I rescued from the mint outside, the sanseveria that grew from a cutting rescued from the office, Hannah’s cyclamens and succulents

Balcony: a Kentia palm, limes and lemons, a few frangipani, aloe, the philodendron Winton didn’t want making moves on the wall, an oak from an acorn I found in Canberra once, some sweet alice, buckwheat, grasses, cherry tomatoes, mint and peppermint, more sanseveria, an apple tree, a bonsai-ed pear seedling, a rosemary cutting, and finally, taking over everything: pumpkins from seeds. All the chilis have long died. I’ve missed a few.

Agoraphobia

Not really - I went out yesterday to get probiotics and do a quick grocery shop. Saw a bunch of families exercising and playing in the park. The supermarket had (individual rolls of) toilet paper in stock!!?

On the other hand, I’ve had no motivation to do morning walks. Best laid plans, etc.

Work from home

Hard to get fully productive - expected. Home office chair has become a bit uncomfortable. Should have nicked my chair from the office. The year-long team video chat is mildly irritating, but nice to see people and have ad-hoc chats. It’s much nicer responding to oncall incidents from my workstation rather than laptop.

Creativity

Shot for months, have hardly been inspired to create anything in a while.

Home labs

Did find some motivation to install Faucet and play around with SDN. Might write a post about that soon?

April 17, 2020 02:39 AM

January 22, 2020

Josh

Writer's Block

It’s January, 2020, and my (vague) New Year’s Resolution is to write more. But I am not sure that I have anything worth writing.

Gee, I must live a pretty dull life. Compared to an imaginary “interesting strawman”, I’m sure this is true. Partly I suspect that the perspectives of a well-off white guy in their 30s who works in tech are not unique or special. Surely there are many more interesting voices out there. Why listen to mine? One thing I do think I have going for me is that I aim to be much less of a narcissist than the Prime Minister.

Working in an operations role has increased my appreciation for the banal. It sure is stressful when the code or architecture is so complicated that it cannot be diagnosed (complexity!), when backups don’t work when doing a restore (surprise!), when the deploy causes a security incident (whoops!), or teams can’t compromise on a solution for their common problem (conflict!). Doing things in a boring way avoids incidents, and therefore avoids interesting stories, right?

I was once taught in a video-game storytelling class that the thing that drives a story is conflict. Maybe this is an incomplete understanding of stories, and the feeling that because everything is going so well I have nothing interesting to say is an example of a bias towards this traditional approach. Would “everything went really well” stories be of interest? There must be some reason for the popularity of “slow TV”, and of videos of skilled people just doing their jobs really well.

Either way, do I have some stories to tell? Yes, I do. I also have a Google problem.

There are certain things I’m really not allowed to say, certain details that would give a lot of colour to stories that I might conceivably tell. I just don’t. It’s worked for the last 6 years. I like being paid a salary, bonus, and equity, and the big G likes certain internal systems to continue working, and doesn’t like leakers.

The other Google problem I have is the energy I have at the end of each day, for projects like Shenzhen Go, or synthesising weird musical noises, where there is no worry of confidentiality issues. 2018 was draining, even without all the conferences. 2019, well, hmm. This year is already cutting my work out for me. These days I get home and want to chill, not do more work. hypercardadventures.com started to feel like work. Writing conference talks is pretty much work. Home lab management is work. Some computer games - a lot like work.

Studying quantum theory with hardly any physics background? Kind of refreshing!

Conferences are interesting, often refreshing and invigorating, and tend to be full of people I like being around, so I like attending them. Breaking with tradition, just last week linux.conf.au was on at the Gold Coast, but for once I didn’t go. I’m going to continue pretending it was entirely due to a bunch of important meetings at work, and had nothing to do with me being bitter over never once getting a talk accepted into the LCA main conference.

That aside, all the talk recordings I’ve watched from it so far have been well worth the time: Benno’s talk (What UNIX Cost Us), Dr Sean Brady’s keynote, and the lightning talks.

January 22, 2020 05:07 AM

December 08, 2019

Josh

Gadget review: MacBook Pro (16-inch, 2019)

I had decided that I wasn’t going to get the new 16-inch MacBook Pro, for several very good reasons.

I had decided. Really decided. Totally decided, good-and-hard, definitely wasn’t going to buy it.

Haha…unless?

Keyboard

The keyboard is good again. It’s comparable to typing at my iMac with its “magic” keyboard. Before buying I went to the Apple store to try it. At that moment I was merely whelmed by it, until I compared with a butterfly-switch keyboard!

The Touch Bar is fine. I had a previous MBP a few years ago with one, so I already knew the ins and outs, but since then I’d gotten used to having a row of function keys again.

I’m not a huge vim user, but the return of a physical Escape key is useful.

Finally, the matte surface on the Touch ID is a nice touch. 🥁

Screen

It’s huge, sharp, and colourful. Very nice. Having a large screen has these benefits:

Sound

What a sound system! It’s no substitute for a proper speaker system or good headphones, but it works. The main drawback for me is that most of the time I’m using headphones anyway.

Weight

It’s hefty but lighter than the 17” I had a decade ago, and the 15” I had 7 years ago. Recently I hauled a PowerBook G3 between home and work, and the 16” feels like nothing in comparison. It’s lighter than carrying two 13” laptops, which happens frequently enough that the extra weight isn’t much.

Bulk

It feels much larger than the 13” laptops I got used to over the last 5 years. I have a few backpacks, but sadly my favourites aren’t designed for anything larger than a 13”. I’m now hanging out for the next version of the Betabrand Under-the-Jack Pack.

Travelling with it is pretty good so far. At the airport, it fit a bit too neatly in the red x-ray bin and it wasn’t trivial to get a grip on the edges to pull it back out. On the plane, it did not fit within the main seat pocket in any orientation (a Virgin Australia 737-800). The net pocket had a bit more room though and the laptop successfully fits in portrait orientation.

Charging

The 96 watt charging brick is also weighty, but doesn’t seem huge compared to the typical 60 watt brick. The laptop also succeeds in charging from a 60 watt HP charging brick (that I have at work), but I suppose I wasn’t pushing the performance most of the day.

Handily, the laptop also (rapidly) charged my phones last night, which on this trip has meant fewer charging bricks needed for travel.

USB C is kind of a minefield of mismatching chargers and devices, but for me it seems to just be working?

Software

It ships with macOS Catalina. If you’re not in the Apple ecosystem already then honestly there may be other laptops which are better. Boot Camp still seems supported. Where’d I put that Windows license key?

Free year of Apple TV Plus?

Another nice touch - I’m not itching for yet more shows to watch, but they look interesting.

Glitches

Problems I’ve noticed so far:


Verdict

MacBook Pro (16-inch, 2019)
Pros Cons
The keyboard is good again A bit pricey
Hefty but sleek Random glitches and insomnia?
Really decent performance Apple being Apple with deprecating legacy APIs and stuff
Great sound and display
Rating: 8.7 out of 10

December 08, 2019 10:50 AM

November 10, 2019

Josh

Blog III

I’m rebooting my blog, again, kind of like how, from time to time, Hollywood reboots movie franchises, or Facebook reboots Mark Zuckerberg. Minus the late-stage capitalism. This blog is free.

Why?

Lots of reasons. You may have noticed the complete blogging stagnation, with zero posts here since 2017. I have only written four posts since the last blog “reboot” (2015, when I migrated away from WordPress). Or maybe you noticed it was fully malfunctioning recently. Haha. Hope none of you noticed!

Other than technical issues, the demise of Blog 2.0 in 2018 was mainly down to two reasons:

  1. I was too busy or burnt out to write, and
  2. When I did have something to write, the statically-generated site workflow had juuuuust enough speed bumps to stop me feeling bothered.

Meanwhile, over in the social media…

At least SoundCloud is still around… oh.

Blog III it is.

What’s changed?

Where are all the posts before 2012?

I started Blog 1 in 2008. The quality of the writing was…variable. (It still is.) Most of the posts since The Paper Tiger were a bit better, and also more popular. I think. I removed the analytics a while ago. Who knows?

If enough people complain, I might peer into the archives and put a few of the old ones back.

What next?

More posts - soon?

November 10, 2019 06:49 AM

August 07, 2018

Paris

OSCON 2018 Recap

Photo by O'Reilly Media: https://www.flickr.com/photos/oreillyconf/43498186701/

A few weeks ago I attended, and spoke at, my 10th OSCON conference. I regularly say that OSCON is my favourite big conference, and every time I attend I’m reminded why I love it, and how much I love it: OSCON is a fun, relaxed, and very approachable place where companies and people involved in open source as contributors, consumers, and users, interface, work with, and have fun with each other. It’s unique in perspective, content, and value. And it’s super engaging everywhere from the lunch hall to the hallway to the sessions and in between. You should go, if you get the opportunity (O’Reilly runs a wonderful diversity and inclusion program, which make me able to help you make it along!)

This year was OSCONs 20-year celebration event! 🎉 If you have a Safari subscription, you can check out the videos from the event here. There’s also a collection of keynotes and interviews from the event on the O’Reilly Media YouTube channel.

On the Monday, Tim, Jon, and I presented a 3 hour session on Open source game development with Godot. Godot is an amazingly polished, and entirely open source, game development engine; Godot is a project of the Software Freedom Conservancy, and is aggressively competitive against the big commercial engines, like Unity and Unreal. I largely led this tutorial, supported by Tim and Jon. We got great feedback from our attendees, and had a full house. I’ll post the material from the workshop in the coming week.

On Tuesday, Tim, Jon, and I presented a 3 hour session on Machine overlord and you: Building AI on iOS with open source tools. We covered everything from CoreML, to Vision, to Apple’s Turi Create Python libraries. Our attendees loved it, and gave us great feedback; it was a fun precursor to our new book, Practical AI with Swift (more on that soon!) You can find the material from this OSCON session right here.

On Tuesday night, I stepped way, way out of my comfort zone and presented a 5 minute Ignite talk on The realities of weightloss. This talk was based on a seed of an idea that Mars had, which I’d taken and run with in a slightly different direction (with her permission). It seemed to resonate with the audience, and I got a lot of thanks, and hugs, from people afterwards. ❤

The next day, Wednesday, saw us doing our traditional book signing (for the latest Learning Swift) in the O’Reilly Media booth of the expo. We had a huge line of people, and signed for about 45 minutes. It was great fun! The O’Reilly staff treat us like royalty, which always makes us feel very special.

On Thursday, in the second-last slot of OSCON 2018, Tim and I teamed up with Mars to deliver an entirely-live coded talk on Learning Swift with Playgrounds. Mars wrote all the examples, designed the flow, and really got thrown in the deep end—and she totally nailed it! Tim provided an excellent narration of proceedings, as Mars live-coded her way through the demos (with Xcode crashing, as is custom!) We got many fabulous reviews, with the talk getting a 4.9/5 ⭐ average. We were thrilled. You can find some notes here, and the fabulous Playground that Mars wrote here on GitHub.

Our friends, VM, Josh, and Paul, also delivered well-received, and awesome talks.

We really love working O’Reilly, particularly our amazing editor, Rachel Roumeliotis, who has risen the ranks of the company while we’ve been working with her (absolutely no connection to us working with her!) and is now a VP of Content Strategy.

We’re doing a bunch of great projects with O’Reilly over the coming year or two, including finishing up a new edition of our iOS Swift Game Development Cookbookas well as a new Unity Game Development Cookbook, a Head First Swift book, and a brand new title, Practical AI with Swift. More updates on all of these soon!

Our latest edition of Learning Swift is available, and getting a bunch of great reviews, and our Mobile Game Development with Unity remains a fabulous guide to building games with Unity. Check them out?

I’ll leave you with one of my favourite tweets of the event, which someone sent following our Learning Swift 3rd Edition book signing:I can’t wait for next year’s OSCON: July 15-18, again back in Portland!

August 07, 2018 11:08 AM

July 28, 2018

Paris

/dev/world/2018

The conference that I help run, /dev/world/2018, is selling tickets!

We have amazing keynotes from the following people:

And we have workshops!

And sessions!

We’ll also have a dinner keynote, during our famous quiz, from Paul Fenwick! It’s going to be amazing! Grab a ticket?

July 28, 2018 07:22 AM

July 13, 2018

Paris

OSCON 2018

I’m super, super, super excited to be back at OSCON, my favourite conference, in Portland. This year you can find me at the following bits of OSCON:

You should also check out the following sessions, from my friends:

July 13, 2018 10:20 PM

May 15, 2018

Paris

/dev/world/2018 CFP extended!

By popular demand, we’ve extended the /dev/world/2018 call for presenters by one week, to 22 May 2018! Get your talks in! You will be amazing!

May 15, 2018 01:14 AM

April 20, 2018

Paris

/dev/world/2018

The iOS, macOS, Swift, and general Apple development conference that I help run, /dev/world is looking for presenters! We’ve opened the CFP for our 11th event (we’ve been going for 11 years! That’s nuts!) and we’re very excited.

If you have a good idea for a talk, please send it our way! I might wear my space suit again.

April 20, 2018 01:23 AM

March 28, 2018

Paris

Latest Swift book: Learning Swift

Learning Swift (3rd edition), my latest book on Swift, covering Swift 4 and beyond, is available now. Check it out on Safari, or from your favourite retailer of books.

March 28, 2018 07:23 AM

March 22, 2018

Paris

Award! 😮

I’m utterly stunned to report that Night in the Woods, a game which we work on in a variety of capacities, has been awarded two incredibly prestigious IGF (Independent Game Festival) awards for 2018:

This is a truly stunning result for a really cool little game.

Oh, we’re also nominated for some BAFTA awards. No big deal.

March 22, 2018 07:39 AM

February 14, 2018

Paris

Tasmanian Leaders Program

From Thursday to Sunday I was lucky enough to be up on the relatively remote West Coast of Tasmania, in the Tasmanian-style resort town of Strahan, attending the first residential of the year-long Tasmanian Leaders Program (TLP).

TLP is a annual program (I’m part of TLP12, the twelfth intake for the program) that takes participants on residential retreats and linking sessions around Tasmania, exploring personal and professional development issues and activities. I’m told that it’s quite a competitive/exclusive/prestigious program, and I really wasn’t expecting to be offered a place.

I met 30 interesting and passionate Tasmanians, and had a great weekend doing all sorts of activities. I’ll post more about what we’re up to as the program progresses!

February 14, 2018 01:11 AM

January 16, 2018

Paris

Blockchain-to-Ponzi Safari Extension

I have made a Safari (macOS) extension that helpfully replaces some words in webpages. Download it here: ponzi scheme-to-ponzi-scheme v1.safariextz.

Please enjoy. Source release available on GitHub. Based on classic “Cloud to Butt” technology.

I take no responsibility for anything that may happen to your system from using this. It doesn’t phone home (other than whatever Apple might do with signed Safari extensions), and doesn’t do anything but some JS find-and-replace.

January 16, 2018 04:37 AM

January 09, 2018

Paris

Learn Unity game development

We’re excited to be teaching Unity game development live online next week, through O’Reilly Media’s Safari platform! It’s free for Safari members. Learn to build video games with one of the most popular engines around. January 17 and 18, 6PM to 9PM, AEDT.
We’re also running the same workshop again, at the end of February, if that date suits you better! Check it out.

January 09, 2018 12:38 AM

December 02, 2017

Josh

Macintosh Tiny

Back while I was preparing for /dev/world this year, I had split my attention in a few variations on a theme:

Since I ran myself out of time at /dev/world to talk about “Macintosh Tiny”, that’s what this entry is about.

The goal

The goal was to shove a Raspberry Pi, a small LCD panel, and maybe an amp and speaker, into a case that looks sort of like a miniature Macintosh Classic, and then run an emulator on it. Peripherals of the era, namely, floppy disk drives, hard disks, SCSI ports, serial ports, ADB ports, and so on, are not part of the project. While everything that could run on 5 volts could easily be battery powered, that was also not a consideration.

Photo of me, holding the Macintosh Tiny, at /dev/world 2017, in front of projected text “Macintosh Tiny”

Other than the Raspberry Pi 3, I found a couple of cheap 5-inch LCDs (800x480 resolution, unnecessary resistive touch feature). The HDMI and micro USB connectors for these panels sit on one of the long edges - it’s designed to mount the Raspberry Pi directly, consuming the GPIO pins and 5V from the Pi, and get HDMI over a small nub of a circuit board which has two HDMI connectors back to back.

However, my case idea called for the Raspberry Pi to go in the bottom of the case so the USB and Ethernet ports could be exposed (analogous to where the logic board and ports are situated on a real Macintosh). This meant one thing I was worried about early on in the process was how I was going to cram a whole bulky HDMI cable and power for the screen into the front of the case, especially if the display’s natural rotation had the connectors coming out the top (Narrator: it was), because then the “head” of the Tiny would have to be made unnaturally tall to hide the cable connectors. Turns out, money solves all known problems, and later on I ordered some 15cm-long flat-ribbon HDMI cables with right-angle connectors on both ends.

I started by thinking I’d 3D print something, so began messing around in OpenSCAD. I feel like I “get” the program-like, constructive solid geometry style of OpenSCAD. However, I’ve never 3D printed anything before in my life, nor have I successfully designed the mini Mac case, so started thinking about ways to shortcut the process.

The case: balsa wood

Macintosh Tiny, displaying the After Dark screensaver Flying Toasters.

Someone suggested balsa wood. So I went and got some. 100% Australian plantation-grown balsa wood, and a bottle of PVC glue, from Lincraft.

Benefits of using balsa:

Downsides are:

To start making a case out of balsa, I was inspired by the Macintosh construction: the computer internals are bolted to the front case, and the back shell then slides on to cover it all up. So for the first two attempts, I started with a sheet of balsa, put the display face-down on top, and then tried to assemble a case upwards.

Macintosh Plus service manual page 28

This approach didn’t work very well. For one thing, the 5 inch display is relatively heavy compared with the Raspberry Pi, so when the proto-Tiny was upright it was unbalanced and liked to topple onto its front again.

The discarded husk of Proto-Tiny #2

The third attempt at constructing a case was successful, probably because I started from the bottom instead of the front face, and used longer pieces of balsa that I cut from a square rod. This lowered the centre of gravity to avoid toppling the Tiny. It also looked more like a scaled down Macintosh at this point, because the slope of the top could be judged more easily.

At this stage I had the display locked into the balsa wood case, the Raspberry Pi mounted on the bottom, and the Pi could be powered via a USB cable coming out the back. The display was then powered via some breadboarding cables from the Pi. This mostly worked, but had some low power issues.

One problem with making a scaled down Macintosh and preserving the angles is the display: with my cheap panel, which didn’t have a great vertical viewing angle, the unit is only really usable at eye level. I fixed this after finishing the audio system by giving it some balsa wood “feet” at the front, making it look a little less like a Classic and more like a Colour Classic.

Macintosh Tiny, with

The power supply

Once I decided to have inbuilt sound, and thus an amplifier which used more than 5 volts, the power situation became more complex - I didn’t want to run off a regular USB power source any more. The solution was to take an input of e.g. 12 volts, and feed it into a combination of a 9V regulator for the amplifiers, and a step-down converter for the Pi and display, providing an ample 3 amps (badum-tish).

The audio

Original Macintoshes have an inbuilt speaker and line out. I didn’t much care for the line out but thought an inbuilt speaker would be a nice touch. Ultimately I ended up with stereo, mounting the speakers with glue onto some holder balsa which I then glued to the side panels. Given the emulator was outputting mono audio anyway, the second speaker is overkill, but a nice touch.

There are some major issues with the Raspberry Pi as an audio source:

I found that a 7809 regulator wasn’t enough to reject the power supply noise, and ended up making an additional C-L-C filter to remove power supply noise from the Pi and display. I wanted to remove noise down to at least 100Hz (possibly overkill), so using this old formula:

$$f = \frac{1}{2\pi\sqrt{LC}}$$

what I wanted was something like ~47µF capacitors (easy to obtain, even as tantalum caps) and 20mH of inductance. I figured the best way of producing that much inductance was to get a spool of copper wire, a toroidal ferrite core, and wind a coil myself. After wasting a few meters of wire in frustration, Hannah suggested winding it onto a pen, and then feeding the pen through the toroidal core instead of wrangling lots of loose wire. Because the ferrite and wire is kind of heavy, the centre of gravity is lowered even further depending on placement.

To get rid of the ground loop noise, I did some quick research on how ground loop isolators are implemented. The easiest seemd to be with coupling transformers, and Jaycar sold those too. Jaycar also sell pre-made isolators with 3.5mm connectors in a case, which are only a few extra dollars compared to the transformers alone.

Actually, Jaycar stocked all the electronics I ended up using for the audio system, including two cheap 1 watt amplifier kits. A single one of these and one speaker would have been fine, as would a stereo amp, but these boards are tiny. The only downside is demanding more than 5 volts, which meant the power supply was slightly more complicated.

The full-range speakers I shelled out for were pricier than a “regular” 8-ohm hobby speaker, but more compact (36mm on each edge) and pack a decent punch across the frequency spectrum.

Inside Macintosh Tiny.

December 02, 2017 01:00 AM

August 29, 2017

Josh

/dev/world 2017

10th anniversary of /dev/world!

Here’s the links from my talk, Inside Macintosh.

And here’s some source code for a game that runs on 68k Macs and emulators.

August 29, 2017 02:00 AM

August 02, 2017

Josh

GovHack 2017

Nice.

GovHack is wrapped up for 2017. It was finished on the weekend, but Monday and Tuesday were a waste - I have been too miserable and sick to blog about it, and only just got a burst of energy to break through the mehffort. Our entry, Death Who? (Colonial Edition), is a virtual card game based upon real lives recorded in Tasmanian historical records. I wanted to share what I’ve learned about making a super hacky multiplayer game backend from scratch in 46 hours, in case you want to try the same thing.

The past few years I have flown down to Hobart to team up with old friends. As usual, I stated up-front that I wanted no share of any prizes we might win. I’m literally in it for the fun of hanging out with my friends.

The mix was a bit different this year. Our team of 8 consisted of me, Hannah, Paris, Mars, Jon, Tim, Seb, and Shea. Our new team members Hannah, Mars, and Shea all brought their own different strengths this year; Hannah and Shea worked on a web-based component, which is unusual for our team. Previous regular Rex went and did a solo entry which you need to check out.

Similar to past years, I made a backend for the game in Go. Each time this has been a server of some kind, depending on what is needed. There are a few preliminaries that can be done while the team settles on a direction, but it’s often better to have the decisions settled on Friday night, get a good night’s sleep, and then get cracking on Saturday morning. This time, we did the latter.

Constraints

As such, the server doesn’t have to be Google-class production-grade stuff. It just has to work for 30 minutes. Nevertheless, it’s relatively easy to do the right things in Go. I think it’s still running even now…

Hello, GovHack

The designers of Go had web servers in mind, so adding one feels natural. I generally jump straight to a skeleton main.go in a server directory in the GitHub repo without thinking much more about it:

package main

import (
    "flag"
    "fmt"
    "log"
    "net/http"
)

var httpPort = flag.Int("http_port", 23480, "Port the webserver listens on")

func main() {
    flag.Parse()

    // Set up HTTP handlers
    http.HandleFunc("/helloz", func(w http.ResponseWriter, r *http.Request) {
        fmt.Fprint(w, "Hello, GovHack 2017!\n")
    })

    // Start listening on HTTP port; block.
    if err := http.ListenAndServe(fmt.Sprintf(":%d", *httpPort), nil); err != nil {
        log.Fatalf("Couldn't serve HTTP: %v", err)
    }
}

If you look carefully through our repo history, you’ll notice that flag.Parse call was missing until Sunday. I frequently forget the basics!

The beauty of running a web server is that it lets you (1) provide a way of checking that the server is still running, and (2) provide a way of inspecting the game state at any point without logging—just leave a browser tab open on localhost:23480/something and refresh when you want to take a peek. So let’s set up a handler for that:

http.HandleFunc("/statusz", func(w http.ResponseWriter, r *http.Request) {
    // TODO: write the game state to w
})

If you’re wondering about the z at then end of /hello and /status: I really can’t help putting it there. It’s a Google-ism.

State

It’s best to agree upon the basic structure of the state-space with the people making the client before going any further. In this case, we have a multiplayer card game with two types of cards. We whiteboarded some states:

Start setting up some types to track the state. I like to do this in a separate package, but there’s no compelling reason to be so neat in a jam/hackathon.

package game

// Statum is some fake latin I made up
type Statum int

const (
    StateLobby Statum = iota
    StateInGame
    StateGameOver
)

type State struct {
    State     Statum          `json:"state"`
    Players   map[int]*Player `json:"players"`
    WhoseTurn int             `json:"whose_turn"`
    Clock     int             `json:"clock"`
}

type Player struct {
    // ... snip ...  
    Score       int     `json:"score"`
}

While it’s no big deal in Go to handle sending/receiving different JSON types nested inside some kind of genericised “message” type by adding MarshalJSON/UnmarshalJSON methods, to make it easier for clients I recommend avoiding doing that. In this case some parts of the state only have meaning depending on other parts of the state (e.g. WhoseTurn and Clock only mean something when State == StateInGame). To make it even easier we are also sending the entire game state to the client—we don’t care about cheating (it’s a hackathon).

Since this is a multiplayer game, be sure to smother state mutations in mutexes. sync.RWMutex is great and lets you get better performance in some cases but a sync.Mutex would be fine (it’s a hackathon). It would be possible to use the new sync.Map here, but we have to guard more than just the map from concurrent access and I like concrete types, so embedding a mutex makes the most sense.

type State struct {
    //...snip...

    // Non-exported fields for bookkeeping
    mu     sync.RWMutex
    nextID int
}

func New() *State {
    return &State{
        Players: make(map[int]*Players),
    }
}

func (s *State) AddPlayer() int {
    s.Lock()
    defer s.Unlock()
    id := s.nextID
    s.Players[id] = new(Player)
    s.nextID++
    return id
}

func (s *State) RemovePlayer(id int) {
    s.Lock()
    defer s.Unlock()
    delete(s.Players, id)
}

Player is defined in a way that its “zero value” is a sensible default. State is almost but not quite as simple, hence the New (it contains a map which we’d like to just use, but nil maps don’t work that way). It starts in the lobby state and supports arbitrarily adding and removing players. You could use a slice for storing players but then you will either have to handle nil “holes” in the slice, or fiddly logic with reslicing. Just use a map (it’s a hackathon). I might use a slice with nils next time.

Serving a game

The next step needs you to settle on the communication between the game client and the server. We chose what seemed like the easy thing which was to send JSON messages over TCP. Typical “serious” game servers often implement a compact binary protocol over UDP. It’s straightforward to do JSON and TCP in Go, and you can see how I did it this time in server.go. The example TCP listener in the net package documentation is a nice starting point. However, some notes.

Firstly, an infinite loop will… infinitely loop, blocking its goroutine indefinitely. Since this binary is also running a web server, one of the two has to be executed in a new goroutine. (Best practice is to have the goroutine created only in the main func so it’s obvious what its lifetime is, but this is a hackathon.)

Secondly, unless the server is synchronous (in the sense that there are no messages sent from the server that aren’t in response to something from the client), you need 2 goroutines per connection: one for receiving and one for sending. One client can affect all the other clients, so this was needed. We planned for the server to just spam the clients with state objects as it pleases.

Thirdly, it is very important that goroutine leaks are avoided: they might be lightweight but they consume memory and CPU cycles, after all. Contexts are great for this, especially in larger server projects. Here they serve the purpose of keeping the sending and receiving goroutines organised. When the context is cancelled, the connection can be closed and both goroutines can end. Additionally, the context can hold some per-player state. For a while I was using the context to hold the player ID, but instead went for an explicit parameter. Instead of a cancellable context, it is pretty much equivalent to give it a “quit” channel that gets closed for cancellation, but I use contexts all the time at work and didn’t bother to think about it much (it’s a hackathon).

Notifying all the clients

The goroutine handling outbound data (the imaginatively-named handleOutbound) is notified by a channel closing when it is time to transmit the game state, but this bears a little closer examination since there’s a great time-saving upside to this: there is no need to implement a registry of things to send notifications to, Go can handle it.

Firstly, remember that all reads on a closed unbuffered channel finish straight away and get the zero value. The outbound handler is an infinite loop around a select waiting on that channel or on the context. Here’s the part in State:

type State struct {
    // ... snip ...
    changedNote chan struct{}
}

func (s *State) Changed() <-chan struct{} {
    s.RLock()
    defer s.RUnlock()
    return s.changedNote
}

func (s *State) notify() {
    close(s.changedNote)
    s.changedNote = make(chan struct{})
}

Every time Changed is called it returns a channel whose sole purpose in life is to be closed in the future by notify. When the state changes (and it should only be changed by methods that do the correct locking), notify is called, closing the current channel and replacing it with a new one. (Calls to notify need to be guarded by the mutex.) Anything that is interested in the state can then just call Changed, and proceed once the returned channel is closed.

However, it’s a hackathon - why not do something really cheap and use a timer to spam updates every second (or something?):

func (s *Server) handleOutbound(conn net.Conn) {
    for range time.Tick(time.Second) {
        s.state.Dump(conn)
    }
}

This is fine, as long as steps are taken to avoid the goroutine leak (hint: it should end when the context is done, which means selecting on both the ticker and <-ctx.Done()). But it didn’t occur to me to do this at the time. Using channel-closing as a snappy notification system for arbitrarily many clients is a technique I’ve used a lot, and feels very natural in Go.

One thing that’s important for development speed is to give the client developer (Jon) a simple message to send the server that does nothing, to ensure communication works from the client side without much effort. Here’s Action:

type Act int

const (
    ActNoOp      Act = iota
    ActStartGame
    ActPlayCard
    ActDiscard
    ActReturnToLobby
)

type Action struct {
    Act  Act `json:"act"`
    Card int `json:"card"`
}

The zero value for Action has Act = ActNoOp, so, sending the empty JSON object {} works as a no-op message. This also helps manually testing the server: you can netcat/telnet into it and manually enter {} (or real actions as JSON).

Unit testing

Test what it does, not how it does it.

It’s a hackathon: if you don’t have time, don’t bother with unit tests, and just test manually. However I can hardly live without at least one or two unit tests. By writing a unit test against your actual API you force yourself to understand some implications of the API design.

Go doesn’t come with a mocking framework. You don’t need one. Run and test the actual server:

func TestGame(t *testing.T) {
    s := server{}
    r := &response{}
    if err := s.listenAndServe("localhost:0"); err != nil {
        t.Fatalf("Couldn't start: %v", err)
    }
    defer s.Close()

    // Connect player 0
    conn0, err := net.Dial("tcp", s.Addr().String())
    if err != nil {
        t.Fatalf("Couldn't connect: %v", err)
    }
    defer conn0.Close()

    send0 := json.NewEncoder(conn0)
    recv0 := json.NewDecoder(conn0)

    // ... snip...

    // Play a game!
    for i, p := range actions {
        // Send an action as one of the players.
        // Check each player receives the state.
        // Check the state against the desired state.
    }
}

All that really has to be faked is the card deck: you don’t want a flaky test because your virtual players got dud hands. So the game state uses a deck that you give it satisfying a Deck interface, and it has two implementations: the real deck which can be Shuffled, and a fake RiggedDeck which is the same but calling Shuffle has no effect.

Adding the, y’know, game

Adding the game logic isn’t all that interesting: with the above in place, it would be possible to make it into almost any kind of multiplayer game (with tweaks). The biggest tweak would be reducing the outbound data to only partial state updates, but that adds unnecessary complexity (it’s a hackathon).

Implementing the rules of the game is a lot like careful state bookkeeping. Having clear delineation of states helps a lot. There are explicit and implicit actions, e.g. player 1 plays card 3, versus player 2 has disconnected. It is important that concurrent actions don’t corrupt one another - use mutexes and the race detector (go test -race ...). It’s also important to think about what states could be “black holes” (often related to implicit actions). For example, if someone disconnects during a game, then the game shouldn’t wait for them to play. Or another example: if a player successfully connecting requires the game to be in the lobby state, and all the players disconnect, then the state should reset to the lobby state so people can rejoin.

Fortunately it’s a hackathon, so it’s allowed to have bugs galore, but I don’t think there are many. 😜

The game is data-driven (a bunch of historical data is churned into game cards). Data wrangling was done by Seb and Tim. We agreed early on that the data should be a JSON-formatted array of objects, which is not hard for them to encode and the server to decode. Loading the data is straightforward (hello my old friend json.NewDecoder) but the magic is in creating the cards out of them. (A few loops though.)

Conclusion

It’s a lot of fun working with such talented people in a hackathon environment. Making a good game server involves a mix of planning, technique, experience, design, teamwork, and communication. I’m once again looking forward to GovHack next year!

August 02, 2017 02:00 AM

June 22, 2017

Chris

Hire me!

tl;dr: I’ve recently moved to the San Francisco Bay Area, received my US Work Authorization, so now I’m looking for somewhere  to work. I have a résumé and an e-mail address!

I’ve worked a lot in Free and Open Source Software communities over the last five years, both in Australia and overseas. While much of my focus has been on the Python community, I’ve also worked more broadly in the Open Source world. I’ve been doing this community work entirely as a volunteer, most of the time working in full-time software engineering jobs which haven’t related to my work in the Open Source world.

It’s pretty clear that I want to move into a job where I can use the skills I’ve been volunteering for the last few years, and put them to good use both for my company, and for the communities I serve.

What I’m interested in doing fits best into a developer advocacy or community management sort of role. Working full-time on helping people in tech be better at what they do would be just wonderful. That said, my background is in code, and working in software engineering with a like-minded company would also be pretty exciting (better still if I get to write a lot of Python).

Why would I be good at this? I’ve been working on building and interacting with communities of developers, especially in the Free and Open Source Software world, for the last five years.

You can find a complete list of what I’ve done in my résumé, but here’s a selection of what I think’s notable:

So, if you know of anything going at the moment, I’d love to hear about it. I’m reachable by e-mail (mail@chrisjrn.com) but you can also find me on Twitter (@chrisjrn), or if you really need to, LinkedIn.

June 22, 2017 07:42 PM

February 15, 2017

Chris

Two Weeks’ Notice

Last week, a rather heavy document envelope showed up in the mail.

Inside I found a heavy buff-coloured envelope, along with my passport — now containing a sticker featuring an impressive collection of words, numbers, and imagery of landmarks from the United States of America. I’m reliably informed that sticker is the valid US visa that I’ve spent the last few months applying for.

Having that visa issued has unblocked a fairly important step in my path to moving in with Josh (as well as eventually getting married, but that’s another story). I’m very very excited about making the move, though very sad to be leaving the city I’ve grown up in and come to love, for the time being.

Unrelatedly, I happened to have a trip planned to Montréal to attend ConFoo in March. Since I’ll already be in the area, I’m using that trip as my opportunity to move.

My last day in Hobart will be Thursday 2 March. Following that, I’ll be spending a day in Abu Dhabi (yes, there is a good reason for this), followed by a week in Montréal for ConFoo.

After that, I’ll be moving in with Josh in Petaluma, California on Saturday 11 March.

But until then, I definitely want to enjoy what remaining time I have in Hobart, and catch up with many many people.

Over the next two weeks I’ll be:

If you want to find some time to catch up over the next couple of weeks, before I disappear for quite some time, do let me know.

February 15, 2017 08:33 PM

January 01, 2017

Chris

My 2016 Highlights

2016 was, undeniably, a length of time containing 366 days and a leap second.

For me, there were a bunch of highlights that it would be amiss to let pass without recording on this blog, so here goes:

So those are some of the highlights of my year. It’s been entirely not bad, in the grand scheme of things. Hooray!

January 01, 2017 07:52 AM

July 06, 2016

Chris

linux.conf.au 2017 wants your talks!

lca2017-tweet-cfp-open

You might have noticed earlier this week that linux.conf.au 2017, which is happening in Hobart, Tasmania (and indeed, which I’m running!) has opened its call for proposals.

Hobart’s a wonderful place to visit in January – within a couple of hours drive, there’s wonderful undisturbed wilderness to go bushwalking in, historic sites from Tasmania’s colonial past, and countless wineries, distilleries, and other producers. Not to mention, the MONA Festival of Music and Arts will probably be taking place around the time of the conference. Coupled with temperate weather, and longer daylight hours than anywhere else in Australia, so there’s plenty of time to make the most of your visit.

linux.conf.au is – despite the name – one of the world’s best generalist Free and Open Source Software conferences. It’s been running annually since 1999, and this year, we’re inviting people to talk abut the Future of Open Source.

That’s a really big topic area, so here’s how our CFP announcement breaks it down:

THE FUTURE OF YOUR PROJECT
linux.conf.au is well-known for deeply technical talks, and lca2017 will be no exception. Our attendees want to be the first to know about new and upcoming developments in the tools they already use every day, and they want to know about new open source technology that they’ll be using daily in two years time.

OPENNESS FOR EVERYONE
Many of the techniques that have made Open Source so successful in the software and hardware world are now being applied to fields as disparate as science, data, government, and the law. We want to know how Open Thinking will help to shape your field in the future, and more importantly, we want to know how the rest of the world can help shape the future of Open Source.

THREATS FROM THE FUTURE
It’s easy to think that Open Source has won, but for every success we achieve, a new challenge pops up. Are we missing opportunities in desktop and mobile computing? Why is the world suddenly running away from open and federated communications? Why don’t the new generation of developers care about licensing? Let’s talk about how Software Freedom and Open Source can better meet the needs of our users and developers for years to come.

WHATEVER YOU WANT!
It’s hard for us to predict the future, but we know that you should be a part of it. If you think you have something to say about Free and Open Source Software, then we want to hear from you, even if it doesn’t fit any of the categories above.

My friend, and former linux.conf.au director, Donna Benjamin blogged about the CFP on medium and tweeted the following yesterday:

At @linuxconfau in Hobart, I’d like to hear how people are USING free & open source software, and what they do to help tend the commons.

Our CFP closes on Friday 5 August – and we’re not planning on extending that deadline – so put your thinking caps on. If you have an idea for the conference, feel free to e-mail me for advice, or you can always ask for help on IRC – we’re in #linux.conf.au on freenode – or you can find us on Facebook or Twitter.

What does the future of Open Source look like? Tell us by submitting a talk, tutorial, or miniconf proposal now! We can’t wait to hear what you have to say.

July 06, 2016 01:21 AM

May 12, 2016

Hovo

The big bike trip – Day 18

Once again we are on the run, today was a brilliant ride up the coast. Nice speed limit and winding roads with good (dry) weather. After picking up some food in a local town we pulled up short of our desired campsite due to running out of daylight. This was the first time we have […]

May 12, 2016 11:12 PM

The big bike trip – Day 17

After been kicked off the boat at what the heck time is this o’clock we sat down at a cafe to fill our stomachs before venturing into the heart of Melbourne for camping supplies. Got what we were after and promptly high taled it out of Melbourne central before anything could halm us. For most […]

May 12, 2016 10:52 PM

The big bike trip – Day 16

Today we left the warmth of Longford and headed out to Beaconsfield. Here we checked out the mining museum, there are plenty to see if your into history. The museum is filled with history of the mining site but also has lots of interactive displays with industrial equipment and other information about life in the […]

May 12, 2016 10:32 PM

The big bike trip – Day 15

Today we packed up our gear from the rocky hard but very flat campground that the parks allowed us to camp on. I really wanted to go for a walk up to the lookout over wineglass bay, so we did! We wanted to get closer to Devonport but not stay in Launceston. After searching for […]

May 12, 2016 01:21 AM

May 09, 2016

Hovo

The big bike trip – Day 14

Greeted the morning and setup my GoPro for a time lapse of the sunrise over the Bay, here are some teaser photos I took from my phone until I proccess the images (no computer with me). After packing up camp we headed over to freycinet with the intent on camping the night here. Camping in […]

May 09, 2016 11:09 PM

April 26, 2016

Chris

Introducing Registrasion!

Time for me to fill you all in on some work I’ve been doing in preparation for linux.conf.au 2017. I’ve been looking into how we can better run the conference website, and reduce the workload of our volunteers into the leadup to the conference.

linux.conf.au has, for the last 10 conferences, used a home-grown conference management system called Zookeepr. I got administration experience in Zookeepr after being involved in running PyCon Australia for a couple of years, and continued to help manage registrations for the years following. While Zookeepr is a venerable piece of software, my 4 years of experience with it has helped me become familiar with a bunch of its shortcomings. Most of these shortcomings are in the area of registration handling.

A problem with conference management software is that the people who come to develop on it are often highly transient — they’re conference organisers. They show up, they make their modifications, and then they get as far away from developing it as possible. Zookeepr’s been affected by this, and it’s meant that difficulties with workarounds are usually overlooked when fixing things.

So I decided to look elsewhere.

Back in 2012, the Python Software Foundation funded a conference management suite called Symposion.

Symposion solves a bunch of problems that Zookeepr solves, and more importantly, it doesn’t suffer from the lack of continuous contributions that Zookeepr has: It’s an actively-maintained app, built on Django, and it has a community of developers supporting it in the form of the Pinax project. In the Python world, it’s used for a very large number of conferences, from PyCon US (a big conference, getting some 1000 talk submissions yearly), down to local regional conferences like PyOhio. It’s well known, and improvements to the system aren’t contingent on conference organisers maintaining interest in the system after they stop running conferences.

Unfortunately, for various reasons, Symposion doesn’t handle conference registration.

So after OSDC2015 in Hobart successfully ran their conference website with Symposion, I decided to plug the gap. In January this year, I jotted down all of the things that I thought was good about Zookeepr’s registration system, and thought about how I could go about objectively improving upon it.

I threw together a data model, and wrote a test suite, and liked what I saw. I asked the Python Software Foundation for a grant to let me do some concerted work on the project for a month or so, and they accepted.

The result is Registrasion (that’s Registration for Symposion (sorry)). I’ve just put out a 0.1 release, which I believe is suitable for running a conference if you’re happy to pull data out of the system with SQL queries, and take payments with bank transfers.

Registrasion was designed with a few key goals in mind, all of which came from observing how Zookeepr struggled around some frequent edge cases that, incidentally, come up late in the process of running a conference. Those late-occurring edge cases are invariably the ones that don’t get fixed, because volunteer conference staff all need to go and run their conference.

In particular, I focused on:

Many of these goals solidified after talking to past conference organisers, who’d all used Zookeepr.

I’m quite proud of a few things in Registrasion. The first is that Registrasion makes it really easy for attendees to add extra things to their registration as they decide they need to. We also take care of automatically giving out freebies that attendees forgot to select during initial registration. In PyCon AU’s case, that’s a lot of manual work we can avert.

Another is a really flexible way in managing what parts of the inventory are available to our users, and at what time. We can show and hide items based on voucher codes, or based on whether they have other products selected. This averts a whole pile of manual work that a past linux.conf.au reported, and I’m glad that our year won’t have to

Finally, I’ve made sure that Registrasion has a lot of documentation. It was a key goal to make sure that new conference organisers can understand vaguely how the system fits together. Python’s tools, and Read The Docs, has made this very very easy.

There’s a pile more work to be done, but there’s also plenty of time before lca2017 opens its registration (in October, probably?). But so far, it’s been super-fun to dive back into Django development, given it’s something I haven’t played with in a few years, and to solve a problem that I’ve been dwelling on for a couple of years now.

Hopefully, in Registrasion, we’ve got a piece of software that can serve the community well, will find use outside of LCA, but will still serve LCA’s needs well for years to come.

If you’re interested, please come along and contribute! I’d love to have you on board!

April 26, 2016 11:41 PM

March 01, 2016

Chris

Python in the Caribbean? More of this!

I don’t often make a point of blogging about the conferences I end up at, but sometimes there are exceptions to be made.

A couple of weekends ago, a happy set of coincidences meant that I was able to attend the first PyCaribbean, in Santo Domingo, capital city of the Dominican Republic. I was lucky enough to give a couple of talks there, too.

This was a superbly well-organised conference. Leonardo and Vivian were truly excellent hosts, and it showed that they were passionate about welcoming the world to their city. They made sure breakfast and lunch at the venue were well catered. We weren’t left wanting in the evenings either, thanks to organised outings to some great local bars and restaurants over each of the evenings.

Better still, the organisers were properly attentive to issues that came up: when the westerners (including me) went up to Leo asking where the coffee was at breakfast (“we don’t drink much of that here”), the situation was resolved within hours. This attitude of resolving mismatches in the expectations of locals vs visitors was truly exceptional, and regional conference organisers can learn a lot from it.

The programme was, in my opinion, better than by rights any first-run conference should be. Most of the speakers were from countries further afield than the Caribbean (though I don’t believe anyone travelled further than me), and the keynotes were all of a standard that I’d expect from much more established conferences. Given that the audience was mostly from the DR – or Central America, at a stretch – the organisers showed that they truly understood the importance of bringing the world’s Python community to their local community. This is a value that it took us at PyCon Australia several years to grok, and PyCaribbean was doing it during their first year.

A wonderful side-effect of this focus on quality is, the programme was also of a standard high enough that someone could visit from nearby parts of the US and still enjoy a programme of a standard matching some of the best US regional Python conferences.

A bit about the city and venue: Even though the DR has a reputation as a touristy island, Santo Domingo is by no means a tourist town. It’s a working city in a developing nation: the harbour laps up very close to the waterfront roads (no beaches here), the traffic patterns help make crossing the road an extreme sport (skilled jaywalking ftw), and toilet paper and soap at the venue was mostly a BYO affair (sigh). Through learning and planning ahead, most of this culture shock subsided beyond my first day at the event, but it’s very clear that PyCaribbean was no beachside junket.

In Santo Domingo, the language barrier was a lot more confronting than I’d expected, too. Whilst I lucked out on getting a cabbie at the airport who could speak a tiny bit of English, and a receptionist with fluent English at the hotel, that was about the extent of being able to communicate. Especially funny was showing up at the venue, and not being allowed in, until I realised that the problem was not being allowed to wear shorts inside government buildings (it took a while to realise that was what the pointing at my legs meant).

You need at least some Spanish to function in Santo Domingo, and whilst I wasn’t the only speaker who was caught out by this, I’m still extremely grateful for the organisers for helping bridge the language barrier when we were all out and about during the evening events. This made the conference all the more enjoyable.

Will I be back for another PyCaribbean? Absolutely. This was one of the best regional Python conferences I’ve ever been to. The organisers had a solid vision for the event, far earlier than most conferences I’ve been to; the local community was grateful, eager to learn, and were rewarded by talks of a very high standard for a regional conferences; finally, everyone who flew into Santo Domingo got what felt like a truly authentic introduction to Dominican Culture, thanks to the solid efforts of the organisers.

Should you go to the next PyCaribbean? Yes. Should your company sponsor it? Yes. It’s a truly legitimate Python conference that in a couple of years time will be amongst the best in the world.

In PyCaribbean, the Python community’s gained a wonderful conference, and the Caribbean has gained a link with the global Python community, and one that it can be truly proud of at that. If you’re anywhere near the area, PyCaribbean is worthy of serious consideration.

March 01, 2016 07:50 PM

February 12, 2016

Chris

Talks from linux.conf.au 2016

I spoke at linux.conf.au 2016 in Geelong! Once during the main conference, and once during the conference close.

Welcoming Everyone

My main conference talk, Welcoming Everyone: Five Years of Outreach and Inclusion Programmes at PyCon Australia, a five-year retrospective of how we’ve done outreach and financial assistance at PyCon Australia. It’s important that we share knowledge about how we run programmes that increase the diversity of our communities, and PyCon AU’s example shows how to build and grow such a program.

lca2017 handover talk

During the conference close, I gave our handover talk for linux.conf.au 2017, sharing what we think Hobart has to offer for the conference, and our vision for the conference. If you want to find out, in 6 minutes, what we’re planning on doing next year, this video is a good way to do just that.

February 12, 2016 10:26 AM

February 06, 2016

Chris

linux.conf.au 2017 is coming to Hobart

Yesterday at linux.conf.au 2016 in Geelong, I had the privilege of being able to introduce our plans for linux.conf.au 2017, which my team and I are bringing to Hobart next year. We’ll be sharing more with you over the coming weeks and months, but until then, here’s some stuff you might like to know:

The Dates

16–20 January 2017.

The Venue

We’re hosting at the Wrest Point Convention Centre. I was involved in the organisation of PyCon Australia 2012 and 2013, which used Wrest Point, and I’m very confident that they deeply understand the needs of our community. Working out of a Convention Centre will reduce the amount of work we need to do as a team to organise the main part of the conference, and will let us focus on delivering an even better social programme for you.

We’ll have preferred rates at the adjoining hotels, which we’ll make available to attendees closer to the conference. We will also have the University of Tasmania apartments available, if you’d rather stay at somewhere more affordable. The apartments are modern, have great common spaces, and were super-popular back when lca2009 was in Hobart.

The Theme

Our theme for linux.conf.au 2017 is The Future of Open Source. LCA has a long history as a place where people come to learn from people who actually build the world of Free and Open Source Software. We want to encourage presenters to share with us where we think their projects are heading over the coming years. These thoughts could be deeply technical: presenting emerging Open Source technology, or features of existing projects that are about to become part of every sysadmin’s toolbox.

Thinking about the future, though, also means thinking about where our community is going. Open Source has become massively successful in much of the world, but is this success making us become complacent in other areas? Are we working to meet the needs of end-users? How can we make sure we don’t completely miss the boat on Mobile platforms? LCA gets the best minds in Free Software to gather every year. Next year, we’ll be using that opportunity to help see where our world is heading.

 

So, that’s where our team has got so far. Hopefully you’re as excited to attend our conference as we are to put it on. We’ll be telling you more about it real soon now. In the meantime, why not visit lca2017.org and find out more about the city, or sign up to the linux.conf.au announcements list, so that you can find out more about the conference as we announce it!

lca2017 handver.001

February 06, 2016 03:45 AM

January 08, 2016

Chris

Three weeks until LCA2016

In February, I’m presenting my first-ever solo presentation at linux.conf.au, my favourite Free and Open Source Software Conference. This year, the conference is in Geelong (just out of Melbourne). I’ve been attending linux.conf.au since 2008 in Melbourne, and am running the conference next year in Hobart.

I’m presenting Welcoming Everyone: Five Years of Outreach and Inclusion Programmes at PyCon Australia, a five-year retrospective on how we’ve handled running financial assistance and related programmes at PyCon Australia.

Doling out financial assistance money to people often looks like it should be an easy thing to do right, but targetting and assessing grants so that the right people are interested, want to attend, and receive assistance is quite a difficult task. This talk shares our successes, our mistakes, and what we’ve learned along the way.

Registration for linux.conf.au 2016 is still open, so if you’re not yet planning on attending, there’s still time to get a ticket!

January 08, 2016 10:10 AM

January 06, 2016

Chris

I’m looking for a job!

tl;dr: I’m looking for somewhere new to work. I have a résumé and an e-mail address!

UPDATE: Right now, I’m based in the San Francisco Bay area, so I’ve re-posted this article and updated it to be current.

I haven’t scared you off yet? Great! Let’s try being a bit more specific.

I’ve worked a lot in Free and Open Source Software communities over the last five years, both in Australia and overseas. While much of my focus has been on the Python community, I’ve also worked more broadly in the Open Source world. I’ve been doing this community work entirely as a volunteer, most of the time working in full-time software engineering jobs which haven’t related to my work in the Open Source world.

I’ve spent the last few years swapping context between building and working with communities I love, and working in a field where these strong ties weren’t useful. This hasn’t been sustainable, so late last year I resigned my job to refresh myself, and considered what my future might look like.

It’s pretty clear that I want to move into a job where I can use the skills I’ve been volunteering for the last few years, and put them to good use both for my company, and for the communities I serve.

What I’m interested in doing fits best into a developer advocacy or community management sort of role. Working full-time on helping people in tech be better at what they do would be just wonderful. That said, my background is in code, and working in software engineering with a like-minded company would also be pretty exciting.

Why would I be good at this? I’ve been working on building and interacting with communities of developers, especially in the Free and Open Source Software world, for the last five years.

You can find a complete list of what I’ve done in my résumé, but here’s a selection of what I think’s notable:

So, if you know of anything going at the moment, I’d love to hear about it. I’m reachable by e-mail (mail@chrisjrn.com) but you can also find me on Twitter (@chrisjrn), or if you really need to, LinkedIn.

January 06, 2016 11:03 PM

December 11, 2015

Josh

Exit, WordPress

I moved this blog out of WordPress. It’s now a static site generated with Hugo. Here’s what I did.

The old setup

Previously, this blog was hosted on DreamHost (both the domain registration and hosting). Due to the remarkable quirk of me being a cheapskate while I was at uni, I bought the domain myself but one of Paris or Jon (I can’t remember who now) did the hosting, because they had hosting. DreamHost was the domain registrar and provided the box that the A record pointed to.

DreamHost makes this easy…too easy. To host content for a domain on DreamHost, if you have purchased hosting in some form, all you have to do is enter the domain name, and be the first person to do that. Then they can set it all up. They get the options all the way down to and including the DNS settings, but not to renew or cancel the domain registration (unless they registered the domain too). If someone else has a hosting account (say, the person who registered the domain) and they want to take over hosting, one of two things has to happen:

  1. The person who is currently hosting has to remove the hosting in their account, or,
  2. The person who registered the domain files a ticket with DreamHost support to get the hosting cut over to their account.

So under the old setup, I registered the domain, and one of my friends kindly and graciously provided the hosting, which is the more expensive part, and for that I’m really grateful.

The hosting itself was a typical WordPress setup. The server ran Linux, the web server was Apache with PHP 5, and MySQL was the database backend.

Benefits of this old setup include:

Problems with the old setup

Problem #1: Comment spam. A mere 4 months after my first blog post, I wrote a blog post about spammers.

Until I migrated off WordPress yesterday, I used Akismet to do automated spam filtering. This requires setting up a WordPress account and getting an API key, then you put the API key into the Akismet WordPress plugin and you’re set. Every now and again you review some spam comments but the volume of spam is greatly less.

But nobody really commented much on my blog. For that reason, and also because there exist people I don’t to hear from, I disabled the comment form on posts and pages. Sadly this wasn’t enough. For some reason I don’t care to understand (because the old way is dead now), comments would still appear in the moderation queue.

Problem #2: Security vulnerabilities. Old PHP had ‘em. Old WordPress had ‘em. WordPress plugins get ‘em. The database password was crap. The attack surface of the old WordPress blog is pretty big, but the value of the target was small. (My blog isn’t that interesting.) This is kind of a deal with any dynamically-generated content, compared with static sites.

I know that there were vulnerabilities and they were abused. I had shell access to the server, and a few times found various PHP files that DreamHost automatically blocked either by setting the file perms to 0000, or moving them into “.INFECTED” files. Just how badly pwnd my old blog was in the end, I’ll never be sure. But it was pwnd.

Security means security updates. It was a chore signing in to click the “Update everything” button. It’s more of a chore doing the recommended file and database backup before WordPress updates. It’s not a large burden, but it’s a burden, and my feelings on automating and getting rid of toil like this blossomed as a result of working for Google now.

Problem #3: The hosting situation. Because I’m a Googler now, I don’t want to be a cheapskate. I have the privilege of having a good income. I’m sure my friends get good feelings from being generous. Again, thank you guys. It was greatly appreciated. However! I can host things myself now.

The new setup

The new setup works like this.

The benefits of this approach:

The drawbacks:

Erm. That’s about it for drawbacks, actually.

Migration

Migration was a bit of a pain, but I prevailed.

There exists a WordPress to Hugo Exporter. It is a WordPress plugin. You push the button and then you download a zip file containing static content and all your pages and posts helpfully converted to Markdown for you. I used this.

What I was unable to do was run it on my live blog. I tried and it failed. When you push the Export button, it scans the site, building an archive in /tmp on the server. The content for my old blog was over 1 GB, but /tmp didn’t have that much space, so it crashed and failed.

I solved this problem by:

  1. Running up Debian 8 in a VM at home, giving it stacks of disk and RAM;
  2. Installed the standard LAMP stack from the Debian repos;
  3. Packed all the WordPress files from my live site, and a full database dump, into a tarball that I downloaded;
  4. Unpacked the tarball in my Debian VM;
  5. Reconfigured WordPress in the VM enough to get it working;
  6. Ran the exporter locally.

The exported files worked pretty well in Hugo, but I wanted to make it really sing. So began the editing process.

Most importantly was the look and feel. There is a Twenty Fourteen theme for Hugo, which is an adaptation of the WordPress theme of the same name. It’s the theme I used on my old blog, and it’s kind of nice, so I kept it for the new blog.

It was easy enough to implement the theme (git clone the theme into the themes directory). Some adjustments later (such as the summary view), and it was pretty good.

Most of the editing effort was reorganising the content. I wanted to migrate off the wp-content/uploads structure that was unhelpfully preserved by the exporter. So I went through all the posts one by one and found the bits that were actually used, and moved them into one of two places:

  1. For “galleries” of photos that I dumped at the end of blog posts, I uploaded them to Google Photos and pasted the share-link.
  2. For photos interspersed with text in blog posts, I copied them into /static/$postnumber and then rewrote the autogenerated <figure> tags with the figure shortcodes provided by the theme.

Rewriting <figure> to shortcodes and fixing the paths got really boring, really fast. So I gave up and wrote a short Go program to did it for me.

Much tweaking later (deleting autogenerated HTML weirdness, replacing formatting with Markdown equivalents, tidying filenames, fixing brokenness in the theme layouts…), I was happy with the output from Hugo (what you see on this site now!) so I:

Everything worked!

Time for dinner!

December 11, 2015 01:00 AM

October 16, 2015

Chris

On burnout, resigning, and coming back to life

Fun story: I quit my job last week.

Somewhat ironically, the first time I’m really writing on this blog about what has been my day job for the last 3-ish years is writing about leaving it.

I don’t have too much to say about my reasons for leaving, but identifying that I’d been suffering severe burnout for a few months was the tipping point for it. Over the last few months my output in most everything I’ve done has visibly dropped – not just in work, or my volunteer efforts (for which numerous other people depend on me), but also in the things I enjoy doing in my spare time.

My last upload to Flickr, prior to this week, was in June last year. Beyond things necessary to get talks done, I haven’t written a line of code in my spare time all year. The last useful thing I wrote on this blog was in January 2014. Those things should have been pretty good indicators, but I missed them.

When deadlines started approaching, I put less pressing things off to the side. I thought at the time that I was merely re-prioritising things in favour or more pressing ones, rather than completely dropping the ball on them. I mean,  that’s basically how it’s always worked in the past.

More on that: I’ve long used conference trips as a way to pace myself through my work; timing trips more-or-less equally throughout the year, so that just as I was starting to get bored and demotivated, I’d have a chance to recover for a bit. This worked pretty well for a few years.

(Indeed, getting away as often as I have over the last few years has let me forge lasting friendships far across the world, and to get really useful things done locally, particularly for PyCon AU. I’m grateful to have had the opportunity to do that.)

So the pattern of feeling down just before a trip was there, just as it always was, for my trip to OSCON and PyCon AU in July this year.

The difference: for whatever reason, I came back feeling not much better than when I left I didn’t pick up the tasks I’d put aside, so they slipped even more.

Something had to give. I chose work. There’s not much more to say for the moment, other than that the time was more-or-less of my own choosing, and I left my job on amicable terms.

Now, what next?

First and foremost, I’m getting myself into a position where I’m mentally ready to run LCA2017 next year. This is probably the biggest undertaking of my life, and I need to be ready for it. I’m making steps to getting the organisation of that back on track.

I have roles with PyCon Australia again next year. Happily, my main role – raising sponsorship money – is now a team role, and I’ll be far less hands-on this time around.

If you’ve been depending on me to get something done over the last few months, and it hasn’t happened, I’m sorry. I’ve been terrible for letting things slip, even worse, I haven’t been open enough about my reasons for it. I really hope to improve this in the future. My backlog is slowly, but surely, getting cleared out.

Beyond that, I’m taking a couple of months off to sort myself out, and to make a concerted effort in figuring out what’s next.

I’m travelling for fun! Right now, I’m sitting somewhere in Far North Queensland, visiting my parents who are here for some reason (I’ve not seen Mum since February).

Over the next few weeks, I’ve got a few conferences I have committed to speaking at (OSDC in Hobart in two weeks’ time; PyCon Canada and Fossetcon in Florida in November), and so will be spending time travelling to attend those, but also taking a bunch of time off around them to relax.

One of the projects I’ve been putting aside for motivational reasons is a book I’m co-authoring on Android development, which I’m sure will show up (a bit more finished) in the future.

As for what I’ll be spending most of my time doing? I’m really not sure. What I’d like to be doing is the subject of another post. I’ll probably write it next week. If you want to cold-call me with opportunities in the hope that they’re relevant, linkedin is as good a place as any for now (lol), but I’m also around on twitter or e-mail.

October 16, 2015 06:20 AM

August 10, 2015

Chris

PyCon Australia 2015!

I was at PyCon Australia 2015 in Brisbane last week, and I presented a couple of talks!

This was the second year of PyCon Australia in Brisbane, it was pretty excellent. I’m looking forward to next year’s, which will be in Melbourne!

August 10, 2015 10:19 AM

April 23, 2015

Josh

Nines of nines

In the operations business we like to talk about nines of things, especially regarding service levels.

If

then generally,

right?

This works for any whole number n: e.g. 5 nines is $$\begin{align}1 - 10^{-5} &= 1 - 0.00001 \\ &= 0.99999.\end{align}$$

There’s a problem with this simple generalisation, and that is, when people say “three and a half nines” the number they actually mean doesn’t fit the pattern. “Three and a half nines” means 0.9995, but

We could resolve this difficulty by saying “3.3ish nines” when we mean 0.9995, or by meaning ~0.9996838 when we say “three and a half nines.” But there’s at least one function that fits the half-nines points as well!

Let’s start with the function above: $$f(n) = 1 - 10^{-n}.$$ For every odd integer, it just has to be lower by a small, correspondingly decreasing amount. We can do this by increasing the exponent of 10 by $$\begin{align}k &= 0.5 + \log_{10}(0.5) \\ &\approx 0.19897.\end{align}$$

One function for introducing a perturbation for halfodd integers is $$p(n) = \sin^2(\pi n).$$ When n is a whole integer, \(p(n) = 0\), and when \(n\) is half an odd integer, \(p(n) = 1\). Multiply this function by some constant and you’re in business.

Thus, define a new function \(g(n)\) for all \(n\):

$$g(n) := 1 - 10^{-n + k p(n)}$$

i.e.

$$g(n) = 1 - 10^{-n + (0.5 + \log_{10}(0.5))\sin^2(\pi n)}$$

which, when plotted, looks like this:

a negative exponential curve with a negative exponential wiggle. And it has the desired property that at every integer and half-integer it has a value with the traditional number of nines and trailing five (or not).

April 23, 2015 02:00 AM

January 16, 2015

Chris

To the Future

hobart.lca2017.org

That is all.

January 16, 2015 07:17 PM