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:
Go forward a units of length.
Turn left (by some angle not specified).
Go forward b units.
Turn towards the starting point.
Go forward all the way to the starting point, and no further (c units).
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:
Go forward a units.
Turn left by 90 degrees.
Go forward b units.
Turn towards the starting point.
Go forward all the way to the starting point, and no further (c units).
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.
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”.
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):
Go forward 1 unit.
Turn left 90 degrees.
“Go forward i units”, i.e. turn left 90 degrees (again) then go forward 1 unit.
Turn towards the starting point.
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.)
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! 😄”
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:
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
}
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):
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]
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
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:
Buy a senator and get them to pass legislation banning Bitcoin.
Advertise against Bitcoin. Lots of adversiting.
Buy and sell Bitcoin in a manipulative way that destabilies the markets and
causes a crash, and then continuing to do that, to keep the value down.
Buy the exchanges, and operate them dishonestly (don’t let people cash out).
Buy TSMC, fire Bitmain as a customer, and issue a new policy prohibiting the
manufacturing of mining ASICs.
Buy TSMC, build an ungodly amount of hashing power for myself, and use it to
mine blocks with no transactions in them.
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:
Run a Bitcoin node, mine blocks, or trade in Bitcoin. Doing these things is
considered a “vote in support” of Bitcoin.
Don’t do any of those things.
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:
Bitcoins are worthless.
Therefore, relaying Bitcoin transactions would be a waste of energy.
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?
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:
The Yarn Spinner language itself - concretely this can be thought of as the
combination of a
lexer grammar
and a
parser grammar that can be converted into whatever other language is needed
(that ANTLR supports).
The Yarn Spinner compiler (containing the generated parser in C# from above).
Given a .yarn file, the compiler produces a
protobuf containing the
compiled program, and a string table in CSV format containing all the lines of
dialogue.
The dialogue runner. Given the output from the compiler, the dialogue runner
runs the program and delivers the dialogue to the game.
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:
IRL access to key members of the Yarn Spinner team if I have any questions. 😄
Yarn Spinner is open source with a permissive license (MIT). Not only can I
read the original implementation to understand how it works, my implementation
is free to outright copy pieces of it or be a derivative work without worry
(provided the license conditions are satisfied).
The bytecode is a protobuf format. Generating proto stubs in Go is about as
easy as any other language supported by protocol buffers. This takes care of
program decoding.
The number of opcodes (17) is small, especially compared with ISAs of non-
virtual CPUs like x86. Between the opcodes, the variations on opcodes,
and the standard library of functions, there is not a burdensome amount of
work.
The string table format is CSV. The
encoding/csv standard library package
can do the heavy lifting there.
Implementing the Yarn Spinner
format functions
(these appear in the string table), particularly plural and ordinal,
might not be straightforward, but there are
probably a few Go packages floating around that provide the Unicode CLDR data,
such as golang.org/x/text.
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:
Run the compiled Yarn Spinner program.
Tell the game to show a line (of dialogue). The program itself doesn’t know
the contents of a line, merely the ID of the line in the string table and
the values of any text substitutions.
Tell the game to show a set of options (themselves lines in the string table).
Accept the player’s choice of option (an integer).
Tell the game to run game-defined commands (strings).
Notify the game of any other possibly interesting events, like the beginning
and end of nodes, that certain lines might be delivered soon so that the game
can load associated assets in the background, or the end of the dialogue.
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.
Imitating the original Yarn Spinner API is desirable for two reasons:
Providing a similar API leverages the design work that has gone into the
existing API.
Providing a similar API makes using it easier for anyone who has used the
original.
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.
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.
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:
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:
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
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.
This comment
indicating the instability of the API.
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...
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:
Finding components by name or identifier
Finding a component by a path
Finding all the child components of a component
Finding all the descendant components of a component
Finding all the components having a particular type or behaviour
Combinations of the above
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:
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.
In thefirstfourposts 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:
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.
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:
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 DrawDogDrawDAG 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).
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.
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:
With flat 2D drawing, the source images would need to be paired with extra
depth information. Each pixel would have a corresponding number in a depth
map, that when added to the Z of the component, can be compared and written
into the Z buffer. Creating depth maps might be burdensome on pixel artists.
ebiten doesn’t seem to provide a way to use the Z buffer that already exists
in the underlying graphics pipeline…quite possibly because it is trying to
be a simple 2D library.
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:
The first shader reads from the Z buffer, the depth map, and the source image,
and writes the pixels from the source image to the screen buffer when the
depth map indicates the pixel is nearer then the corresponding point in the Z
buffer.
The second shader reads from the Z buffer and the depth map, and writes to the
Z buffer when the pixel is nearer.
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:
If another component is on top (its Y is less than the prism’s top Y)
then draw the prism first and the other component later.
If another component is in front of the prism’s front half (i.e. its farther Z
is greater than the prism’s middle), then draw prism first, other later.
Otherwise draw the prism later and the other first.
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:
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:
Now, the perplexing thing about the latter screenshot (the stick figure atop
the coloured prism) was that:
The comparison between the coloured prism and the stick figure was
demonstrably, provably, and testably correct - DrawAfter reported the right
answer when comparing the prism with the figure, and
The draw order was correct when the stick figure jumped onto the prism
from in front of the prism, but not from behind the left or right sides.
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:
Less needs to ask both components what order they think they should be in.
It’s not enough to ask both components whether they must be drawn
after the other, because both could report false, placing them in a false
equivalence. They must also report whether they must be drawn before the
other.
As much information about ordering is needed, even between components that
don’t overlap at all, to prevent transitivity issues.
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.
Find all pairs of compnents that could overlap (after projecting them onto
the screen space).
Use separating planes to find the relative order between them. These become
directed edges in a graph, where the components are the vertices.
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!
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:
The delegation of responsibility is clear, which makes it easier to debug.
(Component foo not being drawn? Does its parent ever call Draw on it?)
The whole tree of components can be deserialised, for example, using
gob, without, say, having to build up
helper data structures in a post-processing step, or by overriding the
serialiser/deserialiser behaviour (implementing GobEncode/GobDecode).
Implementing extra data structures involves the work of “extra bookkeeping” -
it’s not enough for each component to know about its subcomponents. The
additional structures have to be kept up to date.
But there are responses to each of these points, too:
Why should each component have to know how to delegate responsibility to its
subcomponents? That seems like something that could be written once and shared
across all of them.
Post-processing is going to happen anyway, e.g. to load game assets like image
and sound files.
Some extra data structures are going to be needed for implementing other
features, like scripting.
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:
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:
drawList is currently empty (assuming the user of Game is in another
package). There is no way to keep drawList up to date with the contents of
Components, or their descendants.
The options passed to each component’s Draw method don’t reflect that of
their parent components. For example, hiding a parent component doesn’t hide
any of its descendants.
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:
A parent component should be able to move or scale all its child components.
Hiding a parent component should automatically hide all the child components.
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:
Have all the components store a reference to their parent, and supply it
via some new interface (Parenter?)
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.
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:
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:
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:
unregister is doing linear-time work in looping over the draw list, and
producing an almost-identical list of almost the same size. Repeatedly calling
unregister (say, by unregistering one top-level component, causing all the
descendants to unregister) could result in quadratic time complexity.
Unregister is using Walk, which calls the callback first, before walking
the subcomponents. This is a preorder tree traversal. For reasons I will get
into in a later post, we want a postorder traversal, so that we unregister
the children before unregistering the parent. For the purposes of this post,
however, there is no problem unregistering parents before children.
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:
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!
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”:
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:
Level 1 (Border Village)
Background
Forest
House
Background tile
Background tile
…
Midground tilemap
Ground tile
Ground tile
…
Sprites
Mimrock
Billy Blaze (Keen)
Bounder
Circling stars
Poison Slug
Lifewater droplet
Lifewater droplet
…
Foreground tilemap
Tile
Tile
…
Scorecard
Score
Digit
Digit
…
Lives count
Helmet icon
Digit
Digit
Ammo count
Blaster icon
Digit
Digit
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:
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.
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:
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:
Hide everything in a Scene, e.g. hide level 1 and show level 2
Stop updates to everything in a Scene, e.g. pause the game
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.)
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:
Find them all and change each one individually
Do book-keeping to ensure each one has a pointer to some shared struct,
and update that
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.
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:
port-forwarding 443 to the machine that will be running the containers,
pointing a domain name to the machine,
obtaining Let’s Encrypt certs for the domain,
installing and using github.com/square/certstrap to create a self-signed root CA plus the client certificates.
Notes on iPads, client TLS certificates, and WebSockets:
AirDrop-ing a .p12 file (created with a non-empty password) to the iPad worked for me. Don’t forget you still have to go into Settings > General > Profile to install it.
While you’re there, enable the NSURLSession WebSocket experimental feature (Settings > Safari > Advanced > Experimental Features > NSURLSession WebSocket), because of https://bugs.webkit.org/show_bug.cgi?id=158345.
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.
I’ve done it before. Awakeman episodes 27 and 40 were written in Go.
Go can target Windows, Linux, Mac, the web (WebAssembly), and even iOS and
Android.
I have some ideas about engine programming in Go that might not be interesting
to anyone else, but entertain me nonetheless.
Headwinds
There are probably lots of reasons for me not use Go for making a game.
Limited resources for doing it, because everybody else is using Unity or
Unreal or Godot or löve or …
Something something garbage collector
Something something generics
Something something C++
I’m an inexperienced game developer, with less than a handful of games made,
and no formal education in game making, so what would I know!
ebiten
ebiten is a library for making 2D games in Go. It takes
care of the following:
Graphics across the varied platforms
Input handling, including game controllers
Telling your code to layout, update, and draw
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.
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).
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:
How to represent the various parts of various games
Organising the parts of the current game in a useful way
Updating each part of the game that needs updating
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.
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
Always Be Hydrating (ABH)
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.
I’m still catching up on Buffy…
Slowly getting through season 2 of Altered Carbon
Need to finish off Eizouken
Hannah was keeping up with Terrace House
We just finished Feel Good
Games
Daily fix: Animal Crossing New Horizons. Finally encountered a “scorpion island” and made BANK
Mobile / gatcha: Arknights
With friends: Sea of Thieves
Deep dives: …not much otherwise… solo slooping in Sea of Thieves? Might start on ACO, or finish Black Mesa?
Top of wishlist: Half-Life Alyx. I have no VR headset so…
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?
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.
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.
I had decided that I wasn’t going to get the new 16-inch MacBook Pro, for several very good reasons.
I have plenty of laptops already, including a perfectly serviceable MacBook Air. The keyboard is…fine.
The price seemed a bit steep - especially in Australian dollars!
If I want compute power, I could SSH home, or perhaps spin up some cloud VMs for a few dollars. Why carry it around?
I’m slightly grumpy with Apple, most recently for screw ups to do with macOS Catalina. The death of 32-bit and notarization requirements are two things. But it also seems to be a bit unstable?
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 hugevim 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:
I can have Tweetbot, Slack, and some misc other windows all on screen at once.
Logic is decently usable.
It’s great for watching videos when away from home and I forgot the HDMI adapter.
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:
The night before my current trip, I shut the lid and left it charging. The following morning I went to put some more things in my backpack, and found it had decided to stay on and heat up overnight. Insomniac, much? “Wake for network” is now extremely turned off.
About half an hour ago it kernel panicked. Why? No idea. I was just trying to git push!
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
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:
I was too busy or burnt out to write, and
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…
I have a Twitter account. It gets used mostly for retweeting things or the occasional attempt at being funny. It’s not a blog platform, and they don’t ban Nazis.
Many months ago, I closed down my Facebook account. Good riddance. I don’t trust them, and neither should you.
I still have an Instagram account though! I sometimes use it to share pictures of whatever I’m about to eat. I suppose they get to keep part of my soul forever.
Tumblr is…Tumblr. Fine and dandy, but I hardly ever go there.
I never really started on Medium, and given how annoying they are attempting to get me to log in to view people’s posts, I won’t be.
Recording video isn’t my jam, so (other problems aside) YouTube doesn’t suit me.
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.
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 onOpen 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.
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?
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.
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!
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.
Back while I was preparing for /dev/world this year, I had split my attention in a few variations on a theme:
Fixing original Macintosh hardware (the Macintosh Plus);
Emulating Macintoshes on modern machines;
Constructing a Raspberry Pi case that looks sort of like a scaled-down Mac.
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.
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
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:
It’s lightweight;
Soft and easy to work with, using a regular blade and cutting mat;
Not very expensive;
Nails go in very easily;
No need to wait for a 3D printer to print;
Various glues stick easily, including PVC and hot glue, and
Comes in a variety of cross-sections (flat, square, circular).
Downsides are:
Due to how easy it is to work with, it can be easy to break;
It’s a reasonable insulator of heat, which isn’t great for electronics;
It burns easily, and
I cannot saw straight to save myself.
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.
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 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.
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:
The Pi uses “PWM out” for the digital-analog conversion, which generally sounds kind of bad. Not much I can do about this issue, but it’s good enough for an emulated old computer.
The Pi likes to detect the HDMI screen as an audio output. This behaviour can at least be tamed with the /boot/config.txt.
The Pi cannot drive low-impedance speakers directly for very long, and even if you force it to, it sounds crap (ask me how I know). The sound chip shuts down when overloaded (good). You can’t turn the volume back up with alsamixer when this happens.
If you use standard earbuds, the sound from a Pi is generally OK, but if you use an amplifier on the same power supply there are two huge sources of noise which overwhelm the signal: power supply noise, and ground loop noise.
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.
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.
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
Serve a game based on some government-provided data.
Work with multiple players.
SLO: It has to work for demonstration purposes (what might be called “best effort” SLO, but I have a whole other rant about that).
No need to worry about bandwidth, CPU, memory, disk usage, or any of that as long as it works for demo purposes.
Players can cheat and hack the server as much as they like - demo purposes, see above.
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:
Lobby: the players are joining the game, the game hasn’t “started”
When someone pushes the “start” button, transition to…
In game: the game is underway
Players take turns. Once one player plays, go to the next player.
Once all players have had a turn, begin the next round.
Once all rounds have been played, transition to…
Game over: the winner is proclaimed.
The game can be returned to the lobby state by pushing a button.
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!
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).
Something with a strong developer relations element. I enjoy working with other developers, and I love having the opportunity to get them excited about things that I’m excited about. As a conference organiser, I’m very aware of the line between terrible marketing shilling, and genuine advocacy by and for developers: I want to help whoever I work for end up on the right side of that line.
Either in San Francisco, North of San Francisco, or Remote-Friendly. I live in Petaluma, a lovely town about 50 minutes north of San Francisco, with my wonderful partner, Josh. We’re pretty happy up here, but I’m happy to regularly commute as far as San Francisco. I’ll consider opportunities in other cities, but they’d need to primarily be remote.
Relevant to Open Source. The Open Source world is where my experience is, it’s where I know people, and it’s the world where I can be most credible. This doesn’t mean I need to be working on open source itself, but I’d love to be able to show up at OSCON or linux.conf.au and be excited to have my company’s name on my badge.
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:
Co-organised two editions of PyCon Australia, and led the linux.conf.au 2017 team. I’ve led PyCon AU, from inception, to bidding, to the successful execution for two years in a row. As the public face of PyCon AU, I made sure that the conference had the right people interested in speaking, and that we had many from Australian Python community interested in attending. I took what I learned at PyCon AU and applied it to run linux.conf.au 2017, where our CFP attracted its largest ever response (beating the previous record by more than 30%).
Developed Registrasion, an open source conference ticket system. I designed and developed a ticket sales system that allowed for automation of the most significant time sinks that linux.conf.au and PyCon Australia registration staff had experienced in previous years. Registrasion was Open Sourced, and several other conferences are considering adopting it.
Given talks at countless open source and developer events, both in Australia, and overseas. I’ve presented at OSCON, PyCons in five countries, and myriad other conferences. I’ve presented on a whole lot of technical topics, and I’ve recently started talking more about the community-level projects I’ve been involved with.
Designed, ran, and grew PyCon Australia’s outreach and inclusion programmes. Each year, PyCon Australia has offered upwards of $10,000 (around 10% of conference budget) in grants to people who otherwise wouldn’t be able to attend the conference: this is not just speakers, but people whose presence would improve the conference just by being there. I’ve led a team to assess applications for these grants, and lead our outreach efforts to make sure we find the right people to receive these grants.
Served as a council member for Linux Australia. Linux Australia is the peak body for Open Source communities in Australia, as well as underwriting the region’s more popular Open Source and Developer conferences. In particular, I led a project to design governance policies to help make sure the conferences we underwrite are properly budgeted and planned.
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:
Attending, and presenting a talk at WD42 — my talk will be one of my pieces for ConFoo, and is entirely new material. Get along!
Having a farewell do, *probably* on Tuesday 28 February (but that’s not confirmed yet). I’ll post details about where and when that’ll be in the near future (once I’ve made plans)
Madly packing and making sure that that I use up as close to 100% of my luggage allowance as possible
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.
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:
At linux.conf.au 2016 in Geelong in February, I announced linux.conf.au 2017 in Hobart. Over the last year, the conference team and I ran a wildly successful CFP, found 4 amazing keynotes, and lined up what looks like it should be an excellent conference. The only* thing left to do is actually run the thing.
At PyCon in Montréal in 2014, I ran a BoF session for regional PyCon organisers. Two people from the Dominican Republic showed up and asked for our help in starting a PyCon in the Caribbean. In February 2016, I got to go to that conference, and it was incredible!
On that note, I got to continue building on a deeply wonderful relationship with the amazing Josh Simmons that we started in 2015. Over the course of 2016, we got to spend time with each other on no fewer than 6 occasions, both in North America, and here in Australia. We met (and got along quite well with) each others’ friends and families. We spent time living together, and have made big steps towards living together permanently this year. Frankly, I could do a whole post on this and I’m not sure why I haven’t.
On a slightly related note, I spent 92,000-odd miles in the air this year. Much of that was spent ducking over to the US to spend time with Josh; some of the rest was with Josh, and some of it was alone. I got to see some wonderful places I’ve never seen before, like the Grand Canyon and Hoover Dam, an actual northern hemisphere winter with snow and everything, and driving up the Californian coast from Los Angeles.
… and one night in May, on the Steel Bridge in Portland, Josh and I decided that we should get married.
So those are some of the highlights of my year. It’s been entirely not bad, in the grand scheme of things. Hooray!
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.
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.
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.
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 […]
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 […]
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 […]
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 […]
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 […]
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:
Eliminating manual work for registration managers (Zookeepr has a lot of that)
More flexibility in how we automatically offer certain items to end-users (selling flexible accommodation dates was a difficulty one conference year had)
Handling money properly, so that it’s possible to easily reconcile inventory and what’s in the invoicing system
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!
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.
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.
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!
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.
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!
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.
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.
Something with a strong developer relations element. I enjoy working with other developers, and I love having the opportunity to get them excited about things that I’m excited about. As a conference organiser, I’m very aware of the line between terrible marketing shilling, and genuine advocacy by and for developers: I want to help whoever I work for end up on the right side of that line.
Remote-Friendly. I’ve got conference travel lined up already for the first half of 2016, mostly to the US, but I need to primarily be in Australia so I can run linux.conf.au 2017. I’m happy to work from wherever I happen to be, but having the support of my employer to do so is really important.
Relevant to Open Source. The Open Source world is where my experience is, it’s where I know people, and it’s the world where I can be most credible. This doesn’t mean I need to be working on open source itself, but I’d love to be able to show up at OSCON or linux.conf.au and be excited to have my company’s name on my badge.
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:
Co-organised two editions of PyCon Australia and made a successful bid for linux.conf.au 2017. I’ve led PyCon AU, from inception, to bidding, to the successful execution for two years in a row. As the public face of PyCon AU, I made sure that the conference had the right people interested in speaking, and that we had many from Australian Python community interested in attending. PyCon AU attracted presenters from six countries, and attracted more than 300 people to my geographically isolated city in the middle of winter. I’m taking what I’ve learned, and am doing this again for linux.conf.au 2017.
Given talks at countless open source and developer events, both in Australia, and overseas. I’ve presented at OSCON, PyCons in four countries (soon to be five), and myriad other conferences. I’ve presented on a whole lot of technical topics, and I’ve recently started talking more about the community-level projects I’ve been involved with.
Designed, ran, and grew PyCon Australia’s outreach and inclusion programmes. Each year, PyCon Australia has offered upwards of $10,000 (around 10% of conference budget) in grants to people who otherwise wouldn’t be able to attend the conference: this is not just speakers, but people whose presence would improve the conference just by being there. I’ve led a team to assess applications for these grants, and lead our outreach efforts to make sure we find the right people to receive these grants.
Served as a council member for Linux Australia. Linux Australia is the peak body for Open Source communities in Australia, as well as underwriting the region’s more popular Open Source and Developer conferences. In particular, I led a project to design governance policies to help make sure the conferences we underwrite are properly budgeted and planned.
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:
The person who is currently hosting has to remove the hosting in their account, or,
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:
Standard! So freaking standard that helpful articles just oozes out of the internets.
WordPress is a dynamic blogging platform, so you can get pretty complicated with content generated out of the database.
WordPress has themes, and auto resizes photos, and and and…
WordPress supports plugins. I have various bits of math floating around and having a plugin that renders LaTeX in actual symbols is really nice!
Comments. I no longer consider this a benefit, but it was nice for the first 5 years.
WordPress has mobile apps that you can use to edit your blog. I only did this a couple of times but it was a cute touch.
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.
Domain registrar: DreamHost (still).
Hosting option: Redirect (HTTP 301 redirect) joshdeprez.com to www.joshdeprez.com, on my own DreamHost account.
Custom DNS option: www (in the joshdeprez.com zone) is a CNAME for c.storage.googleapis.com. So the files are hosted by Google Cloud Storage.
The source code for the site is written in Markdown, which Hugo converts into HTML according to various Go HTML templates and layout files.
The benefits of this approach:
It’s my own DreamHost account, and Google Cloud account.
It’s static, so the content is highly cacheable and can be served from Google’s CDN.
It’s static, so there’s no database or PHP.
It’s static, so there’s no comments at all. I could use a plugin like Disqus later on if I decide I really want comments (I really do not want comments).
It’s static, so entire classes of web vulnerabilities don’t happen.
It’s static, so I compose content offline, use git to version control the whole thing, and upload when I’m happy with it.
The drawbacks:
The 301 redirect to www is an annoying but necessary part of using a CNAME to use transparent hosting on a different domain. Why can’t I point the A record at Google Cloud Storage? Because GCS uses DNS load balancing, and the IP address (the A record target) would change depending on location, load, the phase of the moon, etc.
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:
Running up Debian 8 in a VM at home, giving it stacks of disk and RAM;
Installed the standard LAMP stack from the Debian repos;
Packed all the WordPress files from my live site, and a full database dump, into a tarball that I downloaded;
Unpacked the tarball in my Debian VM;
Reconfigured WordPress in the VM enough to get it working;
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:
For “galleries” of photos that I dumped at the end of blog posts, I uploaded them to Google Photos and pasted the share-link.
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:
filed a DreamHost ticket to move hosting to my account,
gsutil -m rsync-ed the site up to the GCS bucket,
set the hosting options with the redirect and custom CNAME,
SSH’d into the old host and deleted all the old site files and dropped the database (local backup just in case!) and…
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.
I was at PyCon Australia 2015 in Brisbane last week, and I presented a couple of talks!
Python’s New Type Hints In Action… In JavaScript looked at the tarpit surrounding PEP 484, by introducing Pythonistas to TypeScript, an implementation of the same type system but for JavaScript. There’s a video on youtube and notes on github.
Test-Driven Repair looked at the issue of adding tests to code that hadn’t really considered it. I proposed some ideas about how to go about adding tests and refactoring your code to make future testing easy. There was a lot of good discussion after this talk, and this one represents an improvement over the version I presented at OSCON a week earlier. Once again, there’s a video on YouTube and notes on Github.
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!
In the operations business we like to talk about nines of things, especially regarding service levels.
If
“one nine of availability” = available 0.9 of the time,
“two nines of availability” = available 0.99 of the time,
and so on…
then generally,
“\(n\) nines of availability” = available \((1 - 10^{-n})\) of the time,
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
\(1 - 10^{-3.5} \approx 0.9996838\), and going the other way,
\(0.9995 \approx 1 - 10^{-3.30103}\).
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\):
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).