Space Station 13: ChemiCompiler Helper

Gaming
, , ,
1

Space Station 13 is a top-down tile based action role-playing multiplayer video game running on the freeware BYOND game engine, originally released in 2003
– Wikipedia


My brother, Eli plays this game, Space Station 13. Well, actually, he plays a fork of it that runs a server called Goonstation. The point is that you are doled out a role on the eponymous space station, and it is up to you to play that role, to the best of your ability, while faced with all kinds of antics and shenanigans.

Space Station 13 tracks all kinds of crazy levels of detail, Dwarf Fortress style, and Goonstation adds even more complex pseudo-realism on top of that.

Eli has shown me different aspects of play on Goonstation before, and has even asked for my help once or twice in the past to understand how the door-hacking system works, or how the networking between different computers on the station is done (also for hacking, Eli is a bit of a mischief maker no matter what role he plays).

But something he showed me a couple days ago really caught my attention. Goonstation has a really complex chemistry system. The formulas are somewhat realistic and thought out, and the number of compounds you can create is pretty insane. Being good at chemistry in Goonstation is a pretty big deal, since it means that you can create poisons, medicines, bombs, holy water, and even drugs like “triple meth” (I didn’t ask).

Being somewhat realistic, the formulations of these compounds get complex and tedious pretty quick, what with the mixing, isolating, heating, cooling, measuring, and keeping track of products, by products, and multitudes of beakers, all while crazed doctors try to trap you in whirring treadmill deathraps, hacked up robo-security tries to hunt you down, and guys dressed in clown suits keep pushing you over slippery tiles to make you fall down.

So, the devs of Goonstation created a machine called the ChemiCompiler. Basically just an automated pipette, beaker heater, and pill dispenser, it can take up to 10 beakers at a time and be programmed to do very complex chemical tasks.

Yes, you heard right! Programmed. But, and here’s the rub: you have to program the ChemiCompiler in a special adaptation of Brainfuck called “ChemFuck”. I’m convinced this is to keep the chemistry system balanced given how strong it is to be good at chemistry.

For those not familiar, brainfuck is a dumb, dumb, dumb programming language. It treats all memory as an infinite row of “cells”. Each cell starts at zero and may only store integers. A brainfuck machine also keeps track of a “pointer” which points to one of the cells at a time, and is also the default target for most brainfuck commands.

Here are all of the canonical brainfuck commands:
> - move the pointer one cell ‘forward’ in memory
< - move the pointer one cell ‘backward’ in memory
+ - increment the value of the cell under the pointer
- - decrement the value of the cell under the pointer
[ - loop start, if the value under the pointer is zero, move past the matching loop end
] - loop end, if the value under the pointer is not zero, move back to the loop start
, - in typical brainfuck, this reads in one cell of input and stores it at the pointer
. - print out the value in the current cell as an ASCII character

So, in order to print out an ASCII ‘A’, one would need to execute something like ++++++[>++++++++++<-]>+++++. This program stores 6 into cell 0, then enters a while loop where we increment cell 1 ten times, move back to cell 0, and decrement it. This gets us up to 60 in cell 1, so we increment cell 1 5 more times and print it.

ChemFuck adds 3 additional registers, sx, tx, ax, or source, target, and amount respectively, and some specialized commands that read from/write to those registers, and perform side effects in the specialized hardware:

} - move the value of the cell under the pointer to sx
{ - move the value of sx into the cell under the pointer
) - move the value of the cell under the pointer to tx
( - move the value of tx into the cell under the pointer
' - move the value of the cell under the pointer to ax
^ - move the value of ax into the cell under the pointer
@ - transfer ax units of reagent from beaker index sx to beaker index tx
$ - heat/cool beaker index sx to ((273 - tx) + ax) degrees Kelvin
, - Chemfuck re-purposes this command to measure the volume stored in beaker index sx and store the value in ax
# - isolate ax units of reagent index under the pointer from beaker index sx to beaker index tx, this is particular to the way the game stores the contents of beakers. If a beaker has both water and mercury in it, those are stored as two separate amounts which must be accessed by index for isolating

Now, my brother is not a programmer, and even if he was, nobody wants to program in ChemFuck. So, I’ve devised a small project that will let my brother list out the steps he wants his process to take, and this web interface will spit out semi-optimized chemfuck for him to copy-paste into the game.

I’ve already built a little chemfuck simulator so I don’t have to boot up the game to test the outputs:

This is some of the most fun programming I’ve had in a long time!

2 Likes
2

@draloff, I wanted to say I really loved reading this. We can only give one heart, and this makes me wish I was on social media to share it. :slight_smile:

1 Like
3

@maiki Glad to hear it! I’m having a lot of fun whipping things up, luckily ChemFuck is a pretty simple language so I didn’t have to spend a lot of time wallowing in parsing or anything like that, so it was a pretty direct translation from command to the implementation. Also since we have the source code for Goonstation, it was easy to use the reference implementation when I wasn’t sure what the behavior should be.

One thing I’ve discovered is that I’m going to need to enable some additional commands in “debug mode” to fake things like the chemistry simulation. i.e. if you have a beaker with 20 units of Copper Nitrate and heat it up to 453 K it becomes some amount of Nitrogen Dioxide and some amount of … something else. So the simulator needs a way for the user to, in debug mode, “assert” that the chemical reaction happens, and adjust the label and amounts of reagents in the beaker.

So I’m thinking about adding a queue of more complex “meta operations”, and a debug-mode-only “meta” command ! that pulls off the head of the queue and executes it.

That way, if somebody adds an assertion/relabeling command in the web interface, when they go to debug it we can just push the metaop into the VM before we start the program, and insert ! in the appropriate place when compiling the form to ChemFuck… although loops are going to be a problem if we’re pushing things in before the program starts. Maybe have to keep track of the loop nesting at the VM level, and pull the metaops into a loop-level queue and keep re-inserting queue items at the loop end.

Warning: Frame-by-frame imagining of how that would go below

metaops: [ relabel , print "Hi" , relabel , print "hot stuff", print "starting" ]
nestingLevel: 0
loopops: {}
Code:   ! +++ [ ! ! > +++ [ ! ! - ] < - ]+++
      ^
Memory: | 0 | 0 | 
          ^
Printing: ""

Setting up a situation with a nested loop, the last item in the metaops queue is the first to be executed

metaops: [ relabel , print "Hi" , relabel , print "hot stuff" ]
nestingLevel: 0
loopops: {}
Code:   ! +++ [ ! ! > +++ [ ! ! - ] < - ]+++
        ^
Memory: | 0 | 0 | 
          ^
Printing: "starting"

This op gets tossed because it’s at the top level

metaops: [ relabel , print "Hi" , relabel , print "hot stuff" ]
nestingLevel: 0
loopops: {}
Code:   ! +++ [ ! ! > +++ [ ! ! - ] < - ]+++
              ^
Memory: | 3 | 0 | 
          ^
Printing: ""

Setting up the loop counter for 3 iterations

metaops: [ relabel , print "Hi" ]
nestingLevel: 1
loopops: { 1: [ relabel, print "hot stuff" ]}
Code:   ! +++ [ ! ! > +++ [ ! ! - ] < - ]+++
                  ^
Memory: | 3 | 0 | 
          ^
Printing: "hot stuff"

Skipping ahead a bit, we’ve executed the next two metaops and re-queued them at the loop level here

metaops: [ relabel , print "Hi" ]
nestingLevel: 1
loopops: { 1: [ relabel, print "hot stuff" ]}
Code:   ! +++ [ ! ! > +++ [ ! ! - ] < - ]+++
                          ^
Memory: | 3 | 3 | 
              ^
Printing: ""

Setting up the inner loop for another three iterations

metaops: []
nestingLevel: 2
loopops: { 1: [ relabel, print "hot stuff"], 2: [ relabel, print "Hi" ]}
Code:   ! +++ [ ! ! > +++ [ ! ! - ] < - ]+++
                              ^
Memory: | 3 | 3 | 
              ^
Printing: "Hi"

Again, requeueing at the nesting level

metaops: []
nestingLevel: 2
loopops: { 1: [ relabel, print "hot stuff"], 2: [ relabel, print "Hi" ]}
Code:   ! +++ [ ! ! > +++ [ ! ! - ] < - ]+++
                                ^
Memory: | 3 | 2 | 
              ^
Printing: ""

Decrementing the loop counter

metaops: []
nestingLevel: 2
loopops: { 1: [ relabel, print "hot stuff"], 2: [ print "Hi" , relabel ]}
Code:   ! +++ [ ! ! > +++ [ ! ! - ] < - ]++
                            ^
Memory: | 3 | 2 | 
              ^
Printing: "Hi"

Skipping ahead, note how after executing print "Hi" it’s now at the back of the loop-level queue

metaops: []
nestingLevel: 2
loopops: { 1: [ relabel, print "hot stuff"], 2: [ relabel, print "Hi" ]}
Code:   ! +++ [ ! ! > +++ [ ! ! - ] < - ]+++
                              ^
Memory: | 3 | 2 | 
              ^
Printing: ""

And execution of the next op

metaops: []
nestingLevel: 1
loopops: { 1: [ relabel, print "hot stuff"], 2: [ relabel, print "Hi" ]}
Code:   ! +++ [ ! ! > +++ [ ! ! - ] < - ]+++
                                      ^
Memory: | 2 | 0 | 
          ^
Printing: ""

Kind of continuing on like that until we exit the inner loop and decrement the outer loop counter

metaops: []
nestingLevel: 1
loopops: { 1: [ print "hot stuff", relabel ], 2: [ relabel, print "Hi" ]}
Code:   ! +++ [ ! ! > +++ [ ! ! - ] < - ]+++
                ^
Memory: | 2 | 0 | 
          ^
Printing: "hot stuff"

Executing the higher level ops queue now, print "hot stuff" is now at the back of the queue

metaops: []
nestingLevel: 1
loopops: { 1: [  relabel, print "hot stuff" ], 2: [ relabel, print "Hi" ]}
Code:   ! +++ [ ! ! > +++ [ ! ! - ] < - ]+++
                          ^
Memory: | 2 | 3 | 
              ^
Printing: ""

Continuing execution, and we go on like that until…

metaops: []
nestingLevel: 1
loopops: { 1: [  relabel, print "hot stuff" ], 2: [ relabel, print "Hi" ]}
Code:   ! +++ [ ! ! > +++ [ ! ! - ] < - ]+++
                                        ^
Memory: | 0 | 0 | 
          ^
Printing: ""

Here we are at the end of both loops

metaops: []
nestingLevel: 0
loopops: { }
Code:   ! +++ [ ! ! > +++ [ ! ! - ] < - ]+++
                                           ^
Memory: | 3 | 0 | 
          ^
Printing: ""

and we’re free to trash all of the loop-level ops now that we’re back at the top level

1 Like
4

Future goal is to devise a ChemForth that uses the ChemFuck machine as a simple stack machine, and then maybe get rid of the metaops because the it can be compiled to pure ChemFuck

5

Okay, smallish update.

Took a little time to modularize the VM a bit. Breaking things out into submodules really helped with the sanity of the project, so I’m glad that worked out. Working on a common interface between modules, each module has a reset method to ka-blank out the state when a new program is loaded. Thinking also of giving each module a way to hand off a printer interface to them so that each module can try to print to the printbuffer (which the real, in-machine game also has)

ChemForth has been a surprisingly fun endeavor, if quite difficult. ChemFuck is not so good with basically any way that involves two brainfuck values interacting in any way. Basically everything operation is driven with while loops and involves a whole lot of pushing values onto the stack as flags that something else did or did not happen, to drive a different loop which may or may not execute.

Luckily there’s quite a few examples of different projects that do Forth->brainfuck, or even C->brainfuck, so I’ve had some inspiration to work from.

For example, here’s how we push large numbers on the stack. Naively, in order to get the value of a cell up to any given number, you need to repeat the + operation as many times as you need to get up there. Ex. 5 = +++++, 10 = ++++++++++.

But that really stop scaling around 30. Around then, it’s shorter to just do a loop that increments by 10, +++[>++++++++++<-]+++ is 33, for example.

So I wrote a function that outputs nested loops that gets you up to the number you need:

function incToValue(value: number): Instruction[] {
        const base = 10;
        const r = value % base;
        const q = (value - r) / base;
        if (q <= 1) {
            return repeat(Instruction.INC, value);
        } else {
            return [
                Instruction.INC_P,
                ...incToValue(q),
                Instruction.LOOP_START,
                Instruction.DEC_P,
                ...repeat(Instruction.INC, base),
                Instruction.INC_P,
                Instruction.DEC,
                Instruction.LOOP_END,
                Instruction.DEC_P,
                ...repeat(Instruction.INC, r)
            ];
        }
    }

INC_P and DEC_P map to > and < respectively, INC and DEC to + and -, and LOOP_START and LOOP_END are [ and ]. incToValue operates recursively, building nested loops. Here’s incToValue(162400): >>>>++++++++++++++++[<++++++++++>-]<++[<++++++++++>-]<++++[<++++++++++>-]<[<++++++++++>-]<. Relatively compact!

If-then-else is harder, conceptually.

>+<[[-]>-< then_branch >]>[-< else_branch >]<
>+            ; push 1 (y)
<[            ; if x
  [-]         ; dec x to zero
  >-          ; dec y
  < then_branch ; then branch from x
  >             ; go to y
]
>[               ; if y
  -              ; dec y
  < else_branch ; else branch from x
  >             ; goto y
]
<               ; back to x

Even this has some limitations. It can really mess up the execution if the then_branch pushes more than one value onto the stack, since the else branch executes based on the value of y, the temporary value technically above the value of the stack.

Technically, I’m making things way more difficult on myself than I really need to. ChemFuck has 3 registers to use as well as the stack, in reality I could be leveraging those to my advantage, but the appeal of getting basic brainfuck functionality in, and then only leveraging ChemFuck facilities is very strong.

More basic operators are being difficult. ChemFuck values can’t be negative, which means that subtraction is weird. and and or are much more difficult than I thought they would be, which is bad. I’ve kind of implemented them as weird nested if statements for now… but the inefficiency of that approach is real.

For example, here’s a program that pushes two 5s onto the stack and then tries to determine if the two values are equal. In forth, this would be 5 5 =.
>+++++>+++++<[>>+>+<<<-]>>>[<<<+>>>-]<<[>>+>+<<<-]>>>[<<<+>>>-]<<[>>+<<-]>[<+>-]>[<+>-]<[<->-]<>+<[[-]>-<>]>[-<+>]<>+<[[-]>-<>]>[-<+>]<<<[<->-]<>+<[[-]>-<>]>[-<+>]<>+<[[-]>-<>]>[-<+>]<<>+<[[-]>-<>[-]<>>]>[-<>[[-]<+]>]<>+<[[-]>-<>]>[-<+>]<
This implementation calls over twice, which means that we copy each 5 back onto the stack. But in brainfuck, a copy is destructive, because it involves using the original value as a loop index as you increment another cell. So in order to actually copy, you increment two cells, and then destructively copy the last cell back into the first.

So if the stack is 5, then some intermediate states of the copy would look like 5 -> 2 3 3 -> 0 5 5 -> 3 5 2 -> 5 5.

So each call to over actually triggers two or three copies, depending on how you count.

Not to mention that the ChemForth compiler is lacking even a modicum of peephole optimizations. In the string above, there are plenty of places where you see a >< or <>, which could just be eliminated entirely without effect.

Honestly, I wonder if it wouldn’t be more effective to compile Forth to some intermediate representation that can do constant folding and do a lot of the logic in Typescript instead, and just writes the bare minimum of computations that can’t be figured out at compile time to brainfuck.

1 Like
6

Correction: In brainfuck, not just copies are destructive. Basically any read of a value is destructive. Preserving a value means copying it as you destroy it (and perhaps copying it back into the original place).

Luckily this is not too-too different from how Forth behaves. calling a word that operates on one or more values already on the stack consumes those values unless the word explicitly dup’s them before operating on them.

In a lot of ways, dealing with brainfuck is like dealing with TTL. You have to invent everything from scratch in this weird low-level thought process that doesn’t cleanly map at all to the higher level constructs you actually want to work in.

I’ve been thinking about basically emulating negative numbers, either by cutting the integer space in half and counting up from a sufficiently large value as negative numbers, or by actually pushing two values onto the stack for every number as (a - b) pairs. Both are computationally a lot more expensive, the first because reading or writing a large value is non-trivial (pushing a (0 - 10) pair onto the stack is literally 3200 times faster than pushing a value > 32,000), the second because every operation will need to reckon with these pairs in some way, and literally doubling the number of copies necessary to shuffle values around. I think with the fact that reading or writing values is O(n) (or possibly worse in the write case! Big numbers are made with nested loops, and the care and keeping of those loops introduces more temporary values on the stack, and the evaluation of a lot more instructions that don’t directly contribute to incrementing the cell at hand will stack up especially in the inner-most loops. The read case going to generally be O(n) for sure, because we don’t know how big the value is until we try to read from it, the read loop basically collapses to [-] in analysis) the pairs option is probably the better choice.

1 Like
7

Building an intermediate representation that does constant folding and keeping track of cells to optimize reads and writes is starting to look a whole lot more attractive.

8

To be fair, it is called brainfuck. :slight_smile:

1 Like
9

That’s true. Every time I go, “Man, this is unreasonably challenging, maybe I’m just bad or not seeing something obvious” I remember that I’m trying to implement a general purpose language on top of a language designed to be bad and hard.

2 Likes
10

I respect their design decisions SO MUCH.

1 Like