💾 Archived View for blog.snowfrost.garden › 1 captured on 2022-07-16 at 13:28:53. Gemini links have been rewritten to link to archived content

View Raw

More Information

⬅️ Previous capture (2021-11-30)

➡️ Next capture (2023-01-29)

-=-=-=-=-=-=-

Porting *Space Station 13* with Transpilation

Table of Contents

I've been working on *Donk Project* for the past three months or so. It was one of those projects that I couldn't help but try out, to see how far I could get.

Introduction

The Game

1: https://spacestation13.com/

[IMG]

The core of the game, however, stays largely the same: the eponymous Space Station 13, a research vessel operated by the pan-galactic corporate hegemon NanoTrasen, is staffed by the players. The players take on various roles. Janitors, scientists, cooks, bartenders, cargo technicians, security guards, and the various heads of departments, all the way up to the Captain of the station, all have duties to fulfill in order to ensure the operation of the station.

Every shift, a new shuttle full of crew arrive to the station. Most roles are self-explanatory, but research, supply, and engineering, as well as other departments, have specific goals to investigate materials, perform research, design viruses and analyze genetics. If nothing goes wrong, and it's time for the crew to leave, the return shuttle arrives, and the crew hops off the station, ending the shift.

Every shift, something goes wrong.

[IMG]

It could be something relatively benign. Science is screwing around and not doing important research. There's no chef, and the morale of a hungry crew continues to plummet. The engine isn't outputting enough, so some of the departments lose power. Maybe the station is just a gross mess and the janitors are nowhere to be found.

[IMG]

Then, there are the *antagonists*. Every shift, some crew members may be clandestine agents working for NanoTrasen's sworn enemy, the cabal of hyper-corporations called the Syndicate. They may need to steal something valuable, or kill someone important.

But that's really the tip of the iceberg. The extra-terrestial and supernatural always have their eyes on Space Station 13.

A meteor shower bombards the station, necessitating massive repairs. The miners get killed under mysterious circumstances on the local planet. There may be changelings, shapeshifting worms piloting a person's body from the inside, with the object of killing and taking on the appearance of other crew members without detection.

[IMG]

There could be vampires, pan-dimensional beings that feed on crew and gain terrifying powers in return. It could be a squadron of nuclear operatives hellbent on wiping the station off the face of the galaxy. It could be a small mouse that bursts into a cancerous blob that slowly begins taking over the station, room by room, breeding horrifying creatures that attack the crew.

[IMG]

Or the singularity engine breaks loose of its containment shielding and starts devouring the station, growing more and more powerful with all the matter it consumes, until there's no one left to take the return shuttle.

In short, a lot can happen on Space Station 13, and it's up to the intrepid crew to pull together, survive, and stay alive until the shift is over.

Introducing BYOND

SS13 is built on a small, independent software platform called *BYOND*. BYOND, and its tools, are free to use, and are designed to make game programming--networked game programming especially--accessible to users who are not necessarily tech savvy, although at this point in the platform's lifetime, teams of programmers have managed to build sophisticated libraries and games on it, and a mature ecosystem around it.

The BYOND platform is 24 years old. I'll emphasize that: it was first released in 1996. It is regularly updated, to this day. Game makers register their game with BYOND's API, and the interface for browsing and connecting to games (called *Dream Seeker*) will then show that game within its directory. SS13, the largest draw on BYOND, has anywhere from 500-1500 players on it on average. A handful of other games hit triple digits.

As a point of comparison, at the time of writing, the top 25 multiplayer games currently being played on Steam all have at least an order of magnitude more than that, with the top four (CS:GO, Dota, Among Us and PUBG) having over 100,000 concurrent players. A handful of games, at their all-time peak, have had millions of concurrent players.

This is not meant to be disparaging. Rather, SS13 has a serious cult following; a quietly popular game that is just as enjoyable to watch as it is to play. Streamers on YouTube and Twitch can receive hundreds of thousands of cumulative views of their SS13 play-throughs.

In order to achieve its goal of making game programming accessible, BYOND comes bundled with everything needed to write a game from scratch: an engine, a multiplayer server hub, and a no-frills IDE called Dream Maker that includes a tile-based map editor and graphics tool.

Background

The BYOND API

The BYOND API, as I'm describing it, includes the high-level mechanics and abstractions exposed to users as the building blocks for their games, and we are going to start there.

Here I'd like to add a personal disclaimer: **I have not spent any serious amount of time writing in the DM language**. This means that aside from existing codebases, my only other sources of information on the API and language are the *Designer's Guide[2]* and the Dreammaker Reference[3] documentation available publicly. I may have over- or under-estimated the abilities of the language, and what's strictly necessary to transpile it.

2: http://www.byond.com/docs/guide/guide.pdf

3: https://secure.byond.com/docs/ref/

Game worlds in BYOND are made up of two-dimensional levels. Every level has its own drawing order, and each cell in the level (a.k.a. *tiles*) may have one `/area`, one `/turf`, and multiple objects and moving entities, known respectively as `/obj` and `/mob` types. Every entity in the game world is represented as a type in a hierarchical object system. For example, both `/obj` and `/mob`.

Variables and fields are flexible container-types, and will accept assignment of most other objects or primitives.

All procs are declared as belonging to some object's type. Objects have the ability to call procs attached to other objects, as well as have procs from other objects called within their context. In other words, the `src` (the entity owning the proc) is not necessarily the `usr` (the entity which invoked the proc), and this distinction is typically defined by the in-game distance and visibility of the entities in question.

For example, if one has a magic cloak in game, one would only want it to work if it were being worn by someone. The API provides a pseudo-inventory, `usr.contents`, so we can restrict invocation of the relevant proc like so: 

/obj/magic_cloak/verb/disappear()
  set src = usr.contents
  usr.invisibility = 1

Now `disappear` can only be called if the cloak is in the caller's inventory.

The documentation makes a distinction between *procs* and *verbs* but syntactically they are equivalent, as far as I can tell, and the *Designer's Guide* has verbiage to that effect.

The canonical DM "Hello, World" in the *Guide* looks like this: 

/mob/proc/Login()
  world << "Hello world!"

Indentation is whitespace-significant, as in Python. A separate syntax for declarations, using stair-stepping, is supported: 

mob
  Login()
    world << "Hello world!"

The former style is preferred.

Entities, even user-written ones, are all somewhere on the object tree, and may subclass each other. For example, `/obj` is the tail node of its branch, and one may define both `/obj/animal` and `/obj/animal/cat`, with all of the 90s-OOP-craze inheritance it implies.

The language is meant to be accessible but powerful, and where it does not support server-side features, a DLL interface is provided, which current programmers take full advantage of.

Introducing Donk Project

The Curse

The *Curse* has been described variously. In the simplest terms, the Curse is the mysterious force that prevents the success of a remake of SS13 into a modern codebase with a supportive community. The Curse has seemingly taken a half dozen projects down this road. The 2016 article *Space Station 13 Remakes[4]* documents 14 projects that could be considered direct or close spiritual successors to SS13. Out of those, only SS14 is still active, as far as I can tell.

4: https://medium.com/@treeform/space-station-13-remakes-9b985e2269da

At the moment, there are two claimants to the title of Curse-Breaker: *SS14[5]* and *Unitystation[6]*.

5: https://store.steampowered.com/app/1255460/Space_Station_14/

6: https://store.steampowered.com/app/801140/Unitystation/

[IMG]

SS14 is written in C#, and asserts itself as a "completely different project with it’s *[sic]* own design decisions, goals" and "runs on an entirely different engine". It is working to rethink the fundamentals of SS13, from how people are identified visually, to the combat system, to rewriting how entire departments operate.

SS14 is currently very robust, with a translation of the pixel animation format to a smoother, more modern feel, highlighted items, and secondary menus. Since server administration and performance is a critical aspect of running a game such as this, SS14 also provides web-based server monitoring and telemetry.

At the time of this writing, SS14 has an estimated release date of Fall 2020.

[IMG]

Unitystation, as its name might imply, is a port of SS13 to the popular Unity engine. According to their Steam page:

Unitystation is about 1/4th of the way through its development goals in
reaching a version 1.0, which will include most features found in a standard
game of Space Station 13 on BYOND.

One can take this to imply that Unitystation's goals are a more direct interpretation of SS13's gameplay: hoping to provide an experience of similar fidelity, but with modern graphics, UI, and so on.

At the time of this writing, Unitystation has an estimated release date of Winter 2021.

Any attempts which try to implement the engine--and then SS13's complex and intricate mechanics on top of it--is likely to be a complex, uphill battle. And in a world where Unity and other sophisticated engines provide the power to recreate the game's mechanics, it's then up to the developers to bring the effort needed to write a game that's been under continual refinement for over 15 years, with less focus on the engine that's coming rather than the engine that exists.

Ultimately, the Curse is not real. Software development is hard, rewriting complex programs from scratch is hard--independent community projects like this often suffering from second-system syndrome in the rewrite--and keeping communities organized and regularly motivated is hard.

Overview

<img style="border:none;" src="header.png"></img>

In our case, when we support some language feature, we gain a small bit of support for all of the pieces of SS13 which use that feature. As we support more language features, and reach parity with behavior of the BYOND API, we lose the need to worry about the complexity of the game we're porting. This is a lofty goal, but in this writer's estimation, the process of rewriting BYOND, and a transpiler, is vastly less onerous than the alternative.

That is why I do not forsee Donk ever having any kind of relevance in the future of SS13 ports; it is simply something to wrench on until I get bored.

To this end, I've created several components that make up Donk Project.

`donk/dm2pb` builds off the community's Language Server support and generates a protobuf representation of a DM codebase's AST.

`donk/transpiler` is a transpiler written in Go. At the moment it contains a very simple, mostly-stateless emitter. Eventually it will need to support scoping and call stacks, and may eventually need to perform its own compilation pass.

`donk/core` provides the primitives used in building the BYOND API, and `donk/api` is the surface area containing stub calls to all the Dreammaker APIs.

Basic parsing grammars for icon files (`.dmi`) and map files (`.dmm`) have been written, which allow us to pull in maps, images and image metadata as necessary. These pieces are `donk/image` and `donk/api/mapping`, respectively.

The client and server implementations have the codename *Pollux*, but can be simply referred to as Donk Client and Donk Server, respectively. Pollux also contains the entity management and network implementation between the client and server.

The Transpiler

Despite being one of the more complex pieces of machinery built so far, there's not much to say about the transpiler. Once the AST of the program, or my current serialization of it, is complete, emitting the proper C++ source is a matter of first generating the skeleton of the object tree, and then filling in the contents with the transpiled method calls and variable declarations. Right now this is all very ugly, and has no real notion of a stack or scope, so local variable declarations don't work, for example.

However, it is easy enough to look up whether a variable is declared on an object, and just make sure references to it are linked back to the `src`.

Why C++?

Why not? There's decades worth of solid libraries in the ecosystem, as well as a new generation of modern, C++17-and-above-supporting libraries. Modern C++ includes a variety of standard library features useful for implementing an API like this, such as `<variant>`, `<any>`, `<functional>`, and `<fileystem>`.

More critically, C++ should be thought of as just one expression of Donk Project. With the transpiler available, there's nothing stopping an entrepreneurial programmer from creating a new set of templates to emit output in a different language. In fact, I plan to prototype a similar project in Java soon, since I have some other fragments of game engines I may be able to plug in more quickly.

The Core

All paths in Donk are represented with a `donk::path_t`, and fully-qualifies everything. For example, `/mob` is always `/datum/atom/movable/mob` in Donk. The filesystem paths created in the API and generated code reflects this.

All objects in Donk are part of the object hierarchy, and the root of the hierarchy is `donk::iota_t`. Iotas are a representation of a single entity in Donk, and they are designed to allow addressing variables and procs with no other information about the in-game type.

Within the entity component system, iotas themselves are not iterated over, due to the need for components to be copy-constructable. Instead, we keep track of the three pertinent fields: the entity's path, its fields, and its attached functions.

Fields are of type `donk::var_t` and can be one of several things: an `int`, `float`, or `std::string`, a reference to a game asset (`donk::resource_t`), of a list of other vars.

Fields are stored in a `donk::var_table_t`, procs are stored in a `donk::proc_table_t`. There's nothing too special about these, save for the fact that they are trivially copy-constructible and are easily serializable. There was an attempt to use operator overloading to allow for syntactic sugar and simpler transpilation, but it is more often the case that access of iotas is via pointers, necessitating either `(*iota)["field"]` or `iota->operator[]("field")`.

UUIDs, used for keeping track of entities across the network, are simply `unsigned int`s.

The API

The API is made up of the native types in Dreammaker. These native types are all direct subclasses of `donk::iota_t`. Subclasses and overriding type functions are not classes, but a `donk::var_table_t` containing the overriden variables, and a collection of free functions corresponding to the method.

The Icon and Map Parsers

If there's one lesson I've learned from this, it is this: PNG chunks, despite being part of the spec, are far less used than one would believe. Support for them is spotty or non-existent in the current land of single-header libraries for image processing, and even the reference implementation, `libpng`, doesn't really deign to plot out an end-to-end example of reading and writing chunks. Just put the image information in a parseable format outside of the image; that way you can separate them as needed for your asset pipeline.

Anyway, icon and map parsing are straightforward. The grammars I'm using are fed into peglib[7]. For the icon metadata:

7: https://github.com/yhirose/cpp-peglib

DMI_DATA     <- DMI_HEADER DMI_METADATA STATE_DECLS DMI_FOOTER
DMI_HEADER   <- '# BEGIN DMI'
DMI_FOOTER   <- '# END DMI'
DMI_METADATA <- 'version = 4.0' WIDTH HEIGHT
WIDTH        <- 'width' '=' ( NUMBER )
HEIGHT       <- 'height' '=' ( NUMBER )
STATE_DECLS  <- (STATE_DECL)*
STATE_DECL   <- 'state' '=' '"' STATE_NAME '"' SETTINGS
SETTINGS     <- (SETTING)*
SETTING      <- SETTING_NAME '=' NUMBER / ( FLOAT (',' FLOAT)* )
SETTING_NAME <- 'dirs' / 'frames' / 'rewind' / 'delay'
STATE_NAME   <- < [a-zA-Z0-9] [a-zA-Z0-9-_]* >
FLOAT        <- < [0-9]*.?[0-9]+ >
NUMBER       <- < [0-9]+ >

And the TGM file format (forgot to mention there's the first-party map format, DMM, and TGM, which is more diff-friendly in version control. For now, TGM is the only supported format): 

MAP           <- HEADER KEY_DECLS ROW_DECLS
HEADER        <- '//MAP CONVERTED BY dmm2tgm.py'
                 ' THIS HEADER COMMENT PREVENTS RECONVERSION,'
                 ' DO NOT REMOVE'
KEY_DECLS     <- KEY_DECL*
ROW_DECLS     <- ROW_DECL*
KEY_DECL      <- '"' KEY_NAME '"' '=' '(' PRESET (',' PRESET)*  ')'
PRESET        <- PATH ( '{' ATTR (';' ATTR)* '}' ) / PATH
ATTR          <- ATTR_NAME '=' ATTR_VAL
ATTR_NAME     <- < [a-zA-Z0-9] [a-zA-Z0-9-_]* > 
ATTR_VAL      <- NUMBER / '"' ATTR_STR_DATA '"'
ATTR_STR_DATA <- < [a-zA-Z0-9] [a-zA-Z0-9-_]* >
KEY_NAME      <- < [a-zA-Z0-9] [a-zA-Z0-9]* > 
PATH          <- < '/' PATH_PART ('/' PATH_PART)* >
PATH_PART     <- < [a-zA-Z0-9] [a-zA-Z0-9-_]* > 
ROW_DECL      <- TRIPLET '=' '{' '"' KEY_NAME* '"' '}'
TRIPLET       <- '(' NUMBER ',' NUMBER ',' NUMBER ')'
NUMBER        <- < [0-9]+ >

I welcome corrections.

Pollux

Pollux uses SFML[8] for its graphics and networking support. It encodes update frames in a protocol buffer and serializes them across the wire. If there are dependencies between objects their vars' value is changed to their UUID, and the UUIDs are re-linked to their real objects client-side.

8: https://sfml-dev.org

TGUI[9] (**not to be confused with `tgui`, the most current UI framework for BYOND games**) is the current UI framework, making it easy to prototype as well as render onto a managed surface alongside the UI elements.

9: https://tgui.eu/

The Interpreter

Right now the interpreter is little more than a thin skin over the ECS library used for server-side and client-side tracking. That library is `entt`[10], which I am excited to finally have a reason to explore. It makes it easy to group, sort, and iterate over entities in the ECS.

10: https://github.com/skypjack/entt

We start with a slightly more complex "Hello World" in Dreammaker: we will add icons, a call to a core function, and a map. We will make a one-room dungeon with a snake, a spellbook, and players which spawn in as warriors. Let's examine the spellbook object in DM: 

obj/spellbook
  icon = 'fantasy_tileset.dmi'
  icon_state = "spellbook"

  proc/polymorph()
    name = "lizard"
    icon = 'fantasy_tileset.dmi'
    icon_state = "lizard"
    view() << "[usr] casts polymorph!"

  verb/read_polymorph()
    usr.verbs += /obj/spellbook/proc/polymorph

Each namespace contains a registration function which registers procs and variables with an entity. The spellbook's looks like this: 

void Register(donk::iota_t& i) {
  i.RegisterProc("polymorph", 
      datum::atom::movable::obj::spellbook::polymorph);
  i.RegisterProc("read_polymorph",
      datum::atom::movable::obj::spellbook::read_polymorph);  

  donk::var_t xxx__icon = donk::resource_t("fantasy_tileset.dmi");
  i.RegisterVar("icon", xxx__icon);
  donk::var_t xxx__icon_state = std::string("spellbook");
  i.RegisterVar("icon_state", xxx_icon_state);
}

And the two procs `polymorph` and `read_polymorph` look like this: 

void polymorph(donk::proc_ctxt_t& ctxt, donk::proc_args_t& args) {
  (*ctxt.src())["name"] = "lizard";
  (*ctxt.src())["icon"] = donk::resource_t("fantasy_tileset.dmi");
  (*ctxt.src())["icon_state"] = "lizard";
  ctxt.core("view")("Broadcast",
    std::stringstream() << "" << (*ctxt.usr()) << " casts polymorph!");
}

void read_polymorph(donk::proc_ctxt_t& ctxt, donk::proc_args_t& args) {
  (*ctxt.usr())["verbs"] +=
      "/datum/atom/movable/obj/spellbook/proc/polymorph";
}

You can see a pattern; all functions have the same signature: `void(donk::proc_ctxt_t, donk::proc_args_t)`. This way we can handle DM's flexibility in assigning return values without having a return site. It also makes it very easy to test functions in isolation.

The core functions are all bound to `/` for convenience and follow the same conventions. For example, this is the (current, naive) implementation of `/proc/locate`: 

void locate(donk::proc_ctxt_t& ctxt, donk::proc_args_t& args) {
  auto x = args[0]->get_integer();
  auto y = args[1]->get_integer();
  auto z = args[2]->get_integer();
  auto map_tile = ctxt.map()->index(x, y, z);
  (*ctxt.result()).data_.emplace<
      std::shared_ptr<donk::iota_t>>(map_tile->turf());
}

We look up the map tile information from the interpreter, and makes the results accessible with `ctxt.result()`. Once the interpreter receives the result, it returns it to the function which requested it.

The generated code is not meant to be pretty just yet; rather it is meant to be as explicit as possible in order to facilitate possible human refactoring.

Putting It All Together

After all of this, we can make the final comparison between our project running on BYOND's client:

[IMG]

And Donk:

[IMG]

We can spin up a second client and check chat broadcasts between the two of them:

[IMG]

11: https://opengameart.org/content/32x32-fantasy-tileset

Prior Art

To the best of our knowledge, there are two extant projects which take the transpiler approach: *Somnium[12]* and *JStation13*.

12: http://somnium13.github.io/

Somnium attempts a straightforward translation of the object outline of SS13 into C#, possibly with the intent of integrating it into Unity. This is really sophisticated work; not only does it have a complete transpilation of the SS13 codebase it uses, it includes its own interpreter and API, seemingly entirely written and fully implemented.

In retrospect, this project deserves a closer look; reading over it in preparation for this writing highlighted an issue that needs to be addressed in Donk's transpiler. It uses C#'s attributes to set proc properties and provide a lightweight language for representing the various distance, range, and view functions necessary.

Finally, it appears that some amount of decompilation has been performed; the global functions implemented by BYOND are implemented here in what seems to be automatically generated code. Many pieces of implementation seem to have been independently commented out or commented upon during the work to make it compile, so it's not clear it can even run as expected without additional work.

JStation13 appears to be a student project supported by the *Rensselaer Center for Open Source* during 2017. I cannot find any extant copy of the codebase that indicates significant progress on the task. Despite in some places being referred to as "Java Station", it seems to have been a web application with a C++ backend.

What's Next

The next steps for the project are client input support and improvements to the interpreter to allow proper argument passing, then actually passing update frames across the network during the game loop.

Then it's time to get back to the transpiler and build it out to support more sophisticated code constructs. Rather than try and get all of SS13 building on Donk, all at once, work will be focused on ensuring correct implementation behavior with increasingly more complex DM code, with a focus on supporting the core implementation and the most-depended-upon classes of SS13's dependency chain.

Anyway, that's it. I'm Warriorstar#2017 on Discord if you want to reach out.