Introducing 3omns

It is my great honor to announce the first alpha release of 3omns, a new reimplementation of an old game idea. This implementation picks up where I left off with Bomns3 (which I abandoned after running into one too many Vala compiler bugs). Like the name Bomns itself, don’t expect the titular numbering scheme to make sense, here.

With this alpha release, the state of 3omns could best be described as mostly functional. There are some features I’m already particularly proud of: the two big ones are bot AI and network play, both of which I’ll discuss in more depth below. There are many things left un- or half-implemented: you have to re-run the binary to start a new game, there’s no way to configure which keys control which player (and nothing beyond keyboard input) — I could go on and on. This release is meant to show off my progress thus far and to establish a direction for future work. Plus, 3omns is already fun, if I say so myself. For more details about implemented and planned features, see 3omns on github. Below, I’ll discuss some noteworthy aspects of the game’s development thus far.

If you’re on Ubuntu Trusty, you can get 3omns from the 3omns PPA. Otherwise, you should get a source tarball from github.

Architecture & AI

3omns is written in a combination of C11 and Lua. The C code handles some low-level tasks like rendering and socket manipulation, and defines a library of data structures such as levels and entities used by the Lua code. The Lua code defines 100% of the game logic. Using Lua takes a lot of the annoying grunt work out of writing game code: things like temporary arrays or one-off data structures are more concise in Lua than in C. If I ever have a more serious game idea (3omns is more of a programming exercise), I’d be tempted to use an all-Lua game engine and entirely skip worrying about low-level details myself.

There’s one killer feature Lua has that helps immensely with the bot AI: coroutines. The bots basically run as their own programs, and coroutines are (among other things) a way to have multiple programs running concurrently without resorting to OS threads, which are far too heavyweight here. Without coroutines, I’d have to implement a big state machine I could call into from a loop, where each call performs only a small amount of processing so the engine gets a chance to keep the game moving along. The number of states (or the amount of stored data to keep track of) balloons quickly with anything even remotely complex, and it gets unmanageable. (To be fair, what I just described is exactly how the C code calls into Lua, but letting the Lua interpreter keep track of all the state makes the game code much easier to write.)

Instead, the AI code is simple and linear, written as a normal collection of functions, with calls to suspend their execution at strategic locations. Since Lua also supports tail-call elimination, I can get away without running the AI in a loop at all: instead of having each state return when it finishes to some logic that figures out what state to call into next, I simply call the next state directly from the one finishing.

Using a hybrid C/Lua approach has some drawbacks, though. Namely, complexity: it’s over a thousand lines of C code to define the Lua interface to all the game objects I need. The entities are particularly complex, because I want to have Lua define how they interact, but render them and receive network updates for them in C. My approach so far has been to duplicate a small amount of state for the entities in both C and Lua, and keep that state synced whenever it changes, so that both places have immediate access to the properties they need without having to ask for it. This makes things run quickly, but adds complexity to the code as you might imagine. This is the area of 3omns’s architecture I’m least satisfied with, especially since it grew a bit organically as I added networking code, and I might revisit it in the near future.

Network Syncing

I’ve never written network syncing code for a game before, so this was a bit challenging at first. I ended up with something that works well enough for simple games like 3omns: the clients are as thin as can be, receiving the game state from the server and sending back only new input. This means clients experience lag as one full round-trip from the server — they do no “prediction” on their own of what the game state will look like as a result of their input. Doing it this way is dead simple, and means there’s ample room for improvement if I want to spend more time on the problem. (I refer to this as the Quake 1 networking model, because I remember being infuriated by how much lag there was between pressing even movement keys and seeing the results in that game.)

Any model of syncing requires the game to come up with a serialized representation of its own state to send from server to client. 3omns doesn’t involve much state — I just send RLE-compressed map data and ask each entity for its serialized data. Because entities have state in both C and Lua (and not all of it is shared), this requires a bit of trickery: I first grab the state I know about in C, then call into Lua to have it return whatever data it needs to pass to clients. On the receiving end, I first set up the C state, then call into Lua to have the entity reconstruct itself from whatever the server’s Lua code sent. Again, this is complexity added by splitting up entities between C and Lua, and I’d like to simplify this in the future.

All of the socket code is implemented in C. For this alpha, the protocol involves bare UDP with a simple “magic number” header to make sure both endpoints are speaking the same version of 3omns. This is why 3omns only works on LANs for now (and there’s no guarantee even of that): there’s no reliability or packet ordering, so updates can be dropped, delivered out of sequence, or duplicated. Despite reading a few blog posts recently about how in this modern age everyone should just use TCP instead of implementing reliability on top of UDP, I still think that UDP is the correct choice for a rapid-fire action game like 3omns where there’s very little state transfer but updates need to be reflected quickly (i.e. congestion control bad). For the next release, I plan on adding the necessary reliability so 3omns will work across the internet.

There is one trick I found that can make implementing a protocol a little easier, if it involves a fixed length header: using sendmsg and recvmsg instead of your standard sendto and recvfrom. The *msg variants take multiple buffers to send from or receive into, so instead of having to copy data from the caller into or out of a single buffer that includes the protocol header data, you can keep the buffers separate and let the kernel do the work for you.

Other Notes

I also took the time to finally learn how to effectively use the Autotools for this release. I can’t say I really enjoy using Autoconf, but I will say that understanding it better goes a long way toward easing the pain. I’ve tried a number of other build systems, and the way I’ve come to feel about Autoconf is a bit like Democracy: it’s the worst build manager, except all the others. I tried to keep things simple with 3omns’s configure.ac, but I did end up adding some configurability for some extra install directories, plus it conditionally generates the manpage — at around a hundred lines for everything, I don’t think I did too badly. For anyone else looking to better understand the Autotools, I highly recommend the Autotools book by John Calcote. It’s not a perfect book, but it’s light years ahead of the uninspired smattering of made-up and out-of-date tutorials available online.

I also wanted to automate the PPA’s debian packages build process. You can see my preliminary results on the debian branch. There’s enough there for a whole ‘nother blog post, so I won’t get into the details yet.

That’s probably enough about 3omns for now. I’ve still got a long way to go before I can take it out of alpha. Better get cracking!