Making a PICO-8 TAS

Speedrunners turn the process of beating a single-player video game into a competitive activity, trying to finish games as quickly as humanly possible. This has become increasingly mainstream (though still niche) in the past few years with the rise in popularity of events like Games Done Quick. However, there’s another, smaller community interested in beating games quickly but from a different perspective: how quickly can a game be beaten if humans are taken out of the equation? This is the question set out to be answered by a TAS, or Tool-Assisted Speedrun (sometimes generalized to Tool-Assisted Superplay).

The goal is to create a sequence of inputs which complete the game as quickly as possible, by any means necessary. In practice, this means things like advancing the game frame-by-frame and replaying small sections repeatedly to get them perfect. People make TASes mostly for entertainment value, and to satisfy the curiosity of how far a game can be pushed. The result is a video of gameplay that looks completely superhuman.

One of the best examples of a TAS video is this one of Zelda II:

It turns out that in this game, if the player holds left and right at the same time (something not possible on an ordinary controller), Link can gain a ridiculous amount of speed and complete the game incredibly fast.

In this post I’m going to talk about my process of making a TAS for CELESTE Classic (referred to here as Celeste), made by Matt Thorson and Noel Berry, one of my favourite games. This game was run at Summer Games Done Quick 2016:

The main mechanic of the game is the dash, which lets the girl shoot through the air in any of the 8 directions. When she dashes her hair turns blue until she touches the ground again, indicating that she can’t dash. Later in the game she gets an upgrade that lets her dash twice. The category of the game that interests me is called 100%, which is where the player must collect all 18 strawberries hidden throughout the game. This is in contrast to any%, where the player completes the game with any number of berries (optimal, to our current knowledge, is 1 berry).

I originally released a 2:26 TAS of the game in Fall of 2015. I redid the TAS because there’s been a lot of new discoveries about the game, and also because there’s been some changes to PICO-8 itself that make the production much easier, more pleasant, and more technically interesting.

Here’s the final result (I recommend watching the SGDQ video first, to compare):

For reference, the real-time leaderboard for 100% is at speedrun.com

PICO-8

Celeste is a game for the PICO-8, a fantasy video game console created by Lexaloffle. It emphasizes embracing restrictions to create interesting games, such as a very limited colour palette, and very small storage. One of the things that made adding speedrun tools difficult initially was that games are limited to 8192 Lua tokens of code. When Celeste was first released, it used up nearly all of the available code space, meaning adding extra mechanisms to control the game was effectively impossible. Since the release of Celeste, the way PICO-8 counts tokens has changed (as of v0.1.4), giving us around 2000 more tokens to work with, which is plenty to add on some tools.

Another recent addition to PICO-8 is GPIO (General Purpose Input/Output) pins. This is a 128-byte chunk of shared memory usable for IO within PICO-8. How it’s exposed is dependent on platform (at the time of writing, it’s not exposed on the native client at all), but in the web player, it maps to a global JavaScript array called pico8_gpio. In this case the term “pins” is somewhat fanciful, but they’re also exposed (partially) on things like the PocketCHIP. This means we can write code that runs on a webpage alongside the PICO-8 web player that can communicate with it. The GPIO is really cool, since it opens up huge possibilities for what a PICO-8 cartridge can do! For example, Sean S. LeBlanc used it to make a PICO-8 Twitter client.

The combination of the increased code space and the GPIO pins means we can hook up the PICO-8 web player to talk to JavaScript and then build the rest of the TAS tooling from within JS.

The original TAS was made possible by picolove, a PICO-8 emulator written by impbox. I made some crude modifications to it that let it read in a sequence of inputs from a text file and play them back. That’s how the entire TAS was made, by me entering button inputs into a text file (which you can see here), then booting up the game and seeing if they worked. It was about as tedious as it sounds, which is why this time I wanted something much more sophisticated.

Controlling PICO-8

The first order of business for setting up tooling to control a running session of Celeste was to create a system for allowing JavaScript and PICO-8 to communicate over the GPIO pins.

The setup is this: There’s a 128-byte region of memory (at addresses 0x5f80 to 0x5fff) within PICO-8 which is mapped to a global JavaScript array, pico8_gpio (PICO-8 can access this memory using the built-in peek and poke functions). Both PICO-8 and JavaScript can read and write to this section, and PICO-8 can poll reading it at 30fps.

Since I was going to need to do some pretty complex communication in order to build the tool I wanted, I made a library to make getting JS to talk to PICO-8 easier: communic8.

I’ll outline the protocol I came up with for communic8 here, and I should preface this by saying I have no experience in networking or binary protocols :)

Communication is broken up into discrete messages composed of bytes. The first byte in the GPIO space is always reserved as a header, and indicates:

• Whether the message written is ready for consumption (the consumer unsets this upon reading),
• who wrote the current message, JavaScript or PICO-8, and
• whether PICO-8 currently has a lock on the pins.

The remaining 127 bytes are available, and are filled with messages with this format:

• a header byte with value 1,
• two bytes representing the number of bytes to come,
• an ID byte, so the response can be linked to the request, and finally
• the content of the message.

One observation: since we read from this buffer sequentially, we don’t have to worry about message order, which lets us simplify the implementation quite a bit.

Next, a gotcha. Since JavaScript is single threaded, we don’t also have to worry about locking the region of memory while JS is writing to it. There’s no way PICO-8 can jump in and start reading or writing before the JS gives up control. However! The reverse is not true! The PICO-8 webplayer has a scheduler that can interrupt it in the middle of a frame if it’s taking too long. This means that it’s possible, if we take too long, that PICO-8 will write to some of the GPIO pins and then get interrupted before finishing, so PICO-8 has to set a locking bit whenever it writes to the pins. It sounds unlikely to actually happen, but it bit me and took me most of a day to figure out. When you’re set into an assumption (in this case I didn’t realize that PICO-8 could get interrupted like that) that’s wrong, debugging gets very hard!

Messages are separated by an arbitrary number of padding 0’s, since due to the nature of the GPIO communication we must write in multiples of 128 bytes at a time, so for example, if a message is only 10 bytes, there’s 117 bytes of empty space we need to put something in. This format is flexible enough to allow for multiple small messages to be packed into a single frame, and for large messages to be split up over multiple frames, both of which are important.

How the content of the messages themselves are formatted isn’t as interesting, but if you want to see more, you can check out the library on GitHub. If you make anything cool with it, please let me know, I’d love to see (and if you need help getting it going, also please hit me up).

A TAS environment

The tool I made ended up looking like this:

The right and left arrows move the game one frame forwards or backwards, and the green and yellow boxes represent a controller.

The game waits until it receives a command to move forward before advancing a frame (which includes what the controller state should be for that frame).

The code conceptually looks something like this:

function next_frame(controller_state)
  add(queued_frames, controller_state)
end

function _update()
  ...
  if #queued_frames > 0 then
    current_controller = dequeue(queued_frames)
    advance_frame()
  end
end

Going backwards is a little trickier. The way it works is that my modified version of Celeste supports a message that dumps the entire game state at the current moment.

The tool then keeps track of all the states for every frame of each level, so when we hit the back-a-frame button, the tool sends a different message into PICO-8 with the state for that frame, and PICO-8 loads it back in. This setup makes it really easy to go over a particular section of a level until it’s right.

There’s a bit more that goes on, but this is basically all we need to effectively TAS levels.

This is the first thing I did once I had this working:

1600m TAS: 2016 pic.twitter.com/Ffeqxuisjl

— Justin (@justinjaffray) August 21, 2016

This trick is extremely precise, in fact, I have a standing offer for the Celeste players that I’ll give any of them who can do it real-time a dollar. It involves getting pixel-perfect positioning to get a frame-perfect boost up onto the spikes to get a little bit of extra height, followed by a tight jump, and then an immediate move to the left to get a frame-perfect walljump and then a frame-perfect dash upwards shortly after to be at the correct height and speed to land on the spikes above. I had suspected it was possible for a long time, so being able to finally advance frame-by-frame to make it work was really exciting.

As an aside, if you know what that level looks like normally, you might notice that there’s some objects removed. That’s because at this point in time I was having problems with dumping states that were too large (and having more entities increased the size of the states) so I removed them to test this, since they didn’t matter here.

Replaying the TAS

After I finished TASing all the levels (which took about 2 weeks), I needed to get them back into a vanilla version of the game and write some (hopefully minimal) code to replay them.

There’s a problem, though. If it were the case that every time the same sequence of inputs were used, the exact same thing happened (meaning the game was deterministic), we’d be done now, however, that is not the case with Celeste.

Celeste makes significant use of randomness. A couple things in the game that are random include

• the height of all the snowflakes and clouds on the screen,
• the speed of each snowflake on the screen,
• and the orientation, speed, and position of any given dust particle.

None of these affect the game in a significant way, though. There are two things affected by randomness that are significant:

1. Height of balloons

Every balloon in the game bobs up and down:

They move on a sine wave that loops every 100 frames, and when the level begins, every balloon is placed onto a random position on that sine wave. The hitboxes for the balloons move with their appearance, so this can affect the way a level plays out significantly.

2. Positions of berries coming out of chests

In levels with a key and chest, when the player grabs the key, the chest shakes for a few frames, then disappears to reveal the berry:

What’s creating this shaking effect? It turns out that it works by moving the chest to a random choice of three pixels every frame. The chest’s position is not reset before releasing the berry, and as a result, a berry can pop out at any of three different locations. Granted, they’re not very far apart, but there are a couple of tricks in the TAS which require dashing on the frame before grabbing a berry, which means this has to be perfect.

I’m going to be honest - in the previous TAS, I fudged this a little. I just hardcoded the locations of all the balloons and chests so they were exactly where I needed them. This is also what I did for the version of the game running inside of the TAS tool. Since the new TAS was going to be running on actual PICO-8, and not picolove, I decided I needed to do better. It was brought to my attention that PICO-8 provides a way to seed the randomness (speedrunners generally refer to all forms of randomness in a game as RNG, or Random Number Generation) via the function srand.

Essentially, if we call srand(<some number>) at the very beginning of the game, the sequence of random values that come after will all be deterministic. I just needed to find the perfect value for srand that would make the game run to completion.

I thought this would be straightforward, but I was wrong.

Since we’re striving for very close to perfect play, we cut things very very close. That is, dashing on the first frame of getting a balloon, not dipping any lower than needed. As such, I didn’t realize how precise all the locations of the balloons were. I tried around 400 seeds and didn’t make it past level 13 (out of 30) before I decided I was going to need to change the inputs slightly to get things to work properly. The expected number of seeds increases exponentially with the number of levels, so waiting around for the perfect seed probably wasn’t going to be reasonable. Further, since so many things consume RNG, (every frame, each dust particle on the screen calls rnd, which gives a random number), picking a seed analytically was going to be more or less impossible. I didn’t want to sacrifice time in the name of getting the right seed, so luckily, there’s a trick we can do.

Seeding the RNG by calling srand means that the sequence of calls to rnd the game makes will be deterministic. So once the game is seeded, the only way we can change the RNG for an event is by causing more or fewer calls to rnd to happen prior to that event. If the RNG we’re getting at a particular point is bad, if we are able to cause some extra rnd calls to happen prior, we can essentially “re-roll” the situation. The question is then, is there a way to do that without affecting gameplay? The answer is yes!

If the player tries to dash when her hair is blue, this happens (and a sad little sound effect plays):

That little puff of white smoke is what we care about. When the puffs of smoke appear on screen, they call rnd for a bunch of things, like their horizontal speed, their position, and their orientation. Since we’re forcing the game to call rnd, we’re changing the result of some future rnd calls. In addition, this has absolutely no effect on the girl’s movements. Thus, any time we have bad RNG for a level, we can “puff” a few times in a level (or few levels) prior to “re-roll” it, as opposed to just trying a different seed, which will affect all the levels prior to that one as well.

So after picking a satisfactory seed (I used 29, if you were wondering) and inserting puffs in the right positions, we get a completed run! I didn’t actually know what the time was going to be until the run completed, and I was extremely pleased that I managed to save 20 seconds over the previous TAS.

So now I’m done with this game, I’ve put a lot of time into exploring it and pushing it, but I’m ready to call it quits (at least until the new one comes out…).

Thanks to everyone who gave me feedback this post, and this whole thing wouldn’t have been nearly as cool as it is without all the help from all the Celeste players (baldjared, SecksWrecks, Meep, heehee, and aspinach).