The inputs in my recent
Kwirk TAS were produced by a
Lua script. The script programmatically navigates the menus, manipulates RNG, and plays the solutions to the puzzles. Instead of hardcoding frame offsets, the script empirically discovers the earliest frame at which each input is accepted, for every input, each time it is run. When there are
two ways to get through a menu, the script tries both of them, and keeps the faster one. Doing all this requires sophisticated control over the emulator that is difficult to achieve using
BizHawk callbacks alone. To make it easier, the script includes a chunk of support code for managing savestates as immutable data, using ordinary Lua statements, loops, and function calls, not callbacks. The programming style enabled by this support code is what I want to talk about in this thread. If you've ever felt limited by
while true do emu.frameadvance() end, this is for you.
User movie #638643807847186809
The link above is the
Kwirk Lua script as a userfile. It's the same script as was used for
[6203] GB Kwirk "Heading Out?, all floors" by Sand in 25:15.19, with additional comments and edits for clarity. In my Git repository at https:
//www.bamsoftware.com/git/kwirk.git, it's tas.lua at commit ef235541. The important parts for this discussion (generic savestate manipulation code, not specific to
Kwirk) are from
BASE_SAVESTATE to
earliest_effective_frame.
Before I talk about how the support code works, I'll show some excerpts from the script to show what it looks like to program in this style. The first one below is from the beginning of the run, where we dismiss the title screen and enter the menus. The script waits for the title screen code to run (by waiting for the address
TITLE_SCREEN_ADDR to be executed), then finds the earliest possible frame to press the Start button (using an auxiliary function,
earliest_effective_frame, that I'll say more about later), and finally selects "Heading Out?" mode from the first menu.
Language: lua
local savestate = BASE_SAVESTATE
-- Run until the title screen (skipping over the BIOS animation).
savestate = run_until_exec(savestate, nil, TITLE_SCREEN_ADDR)
-- Find the earliest frame at which we can press Start to get past the
-- title screen.
savestate = earliest_effective_frame(savestate, function (s)
return savestate_joypad_set(s, {Start = true})
end, function (s)
return run_until_exec(s, 32, MENU_ADDR)
end)
savestate = select_menu_item(savestate, 1) -- Heading Out?
The next excerpt is part of the
post_run_reconfigure function, which is responsible for doing the menuing between segments. The function reads the current values of settings from memory, tries two ways of navigating the menus to change the settings, and returns a savestate representing the one that's faster:
Language: lua
local cur_skill = savestate_read_u8(savestate, SKILL_ADDR)
local cur_num_floors = savestate_read_u8(savestate, NUM_FLOORS_ADDR)
-- The display variable uses the encoding 0 = DISPLAY_BIRDSEYE,
-- 1 = DISPLAY_DIAGONAL which is the opposite of our convention (which
-- uses the order in which the options appear in the menu).
local cur_display = assert(({[0] = 1, [1] = 0})[savestate_read_u8(savestate, DISPLAY_ADDR)])
-- Try the End menu.
local menu_savestate = savestate
if cur_display ~= display or cur_num_floors ~= num_floors or cur_skill ~= skill then
menu_savestate = select_menu_item(menu_savestate, 1) -- End
if cur_skill ~= skill then
menu_savestate = select_menu_item(menu_savestate, 2) -- Select skill
menu_savestate = select_menu_item(menu_savestate, skill)
else
menu_savestate = select_menu_item(menu_savestate, 1) -- Select course
end
menu_savestate = select_num_floors(menu_savestate, num_floors)
menu_savestate = select_menu_item(menu_savestate, display)
end
-- Try the B Button.
local b_savestate = savestate
if cur_display ~= display or cur_num_floors ~= num_floors or cur_skill ~= skill then
b_savestate = cancel_menu(b_savestate)
if cur_num_floors ~= num_floors or cur_skill ~= skill then
b_savestate = cancel_menu(b_savestate)
if cur_skill ~= skill then
b_savestate = cancel_menu(b_savestate)
b_savestate = select_menu_item(b_savestate, skill)
end
b_savestate = select_num_floors(b_savestate, num_floors)
end
b_savestate = select_menu_item(b_savestate, display)
end
if savestate_frame_count(menu_savestate) <= savestate_frame_count(b_savestate) then
savestate = menu_savestate
else
savestate = b_savestate
end
return savestate
"Savestates" in these excerpts are actually custom savestate objects, built around BizHawk's native savestates. They are ordinary data that you can assign to a variable or pass into a function. Once created, a savestate is immutable: you cannot change the emulator state is represents, but you can derive new, different savestates from it. Functions like
select_menu_item that take a savestate as input produce a new savestate as output, with the input savestate remaining unchanged. You can assign a returned savestate value over an existing variable if you don't need the old value (as happens in the first excerpt above); or you can assign it to a new variable to get two variables that represent different emulator states (as with
menu_savestate and
b_savestate in the second excerpt).
Notice there's no explicit "rewind" operation in the second excerpt, even though, after deriving
menu_savestate from the passed-in
savestate, we need to go back to the beginning of the menu to begin deriving
b_savestate. The focus is on computing over data, not driving the emulator. The emulator
is, in fact, going to be jumping around various savestates and emulating frames as you run these function calls, but you don't write the code that way. The support functions take care of controlling the emulator to implement the savestate data operations you request.
There are two difficulties with writing Lua code in BizHawk that the support code is trying to address:
- The emulator itself—its emulated CPU registers and RAM, the state of joypad inputs, and more—is effectively a big mutable global variable, with all the problems that come with that. Instead of writing functions that change their behavior depending on the current state of the emulator, we'd prefer to have functions depend only on their parameters. This means representing the emulator state as data, and abstracting away the low-level details of controlling the emulator.
- Programming with callbacks is awkward. We frequently want to let the emulator run until some event occurs, such as a change in RAM or the passing of a certain number of frames. The only built-in way for a BizHawk Lua script to do this is to relinquish control, let the emulator run, and wait to be called back. It gets more complicated if you want to wait for event A, then event B, then event C in sequence, or wait for multiple events at the same time. (JavaScript programmers know about callback hell.) We'd prefer to write code that looks like ordinary synchronous Lua code, using ordinary statements and control structures.
We deal with the first difficulty by defining an abstract "savestate" data type and requiring that all changes to the emulator state be mediated through it. The code inside the
do ... end block is the code that is trusted to control the emulator directly (calling functions like
memorysavestate.loadcorestate and
joypad.set), and to do operations that depend on the current emulator state (like
memorysavestate.savecorestate and
emu.framecount). All other code must work through the safe primitives that are exported (not marked as
local) by this block. (If you know Rust, the
do ... end block is analogous to an
unsafe block, providing a safe interface around low-level details that require careful management.)
We deal with the second difficulty using
Lua coroutines. I've remarked on the inconvenience of programming with callbacks: you have to register a callback, let your script exit so the emulator can run, and then when the event happens and the callback is called, you have to reconstruct what you were doing before you gave up control. This is a kind of problem that coroutines were meant to solve. Instead of letting your script exit, you can register a callback and then call
coroutine.yield, which lets the emulator run but also remembers the execution state of the script. In the callback function, you call
coroutine.resume, which jumps back to where you were waiting for the event.
Here's a small example of converting code from the callback style to the coroutine style. This is how you would wait for the address
ADDR to be executed in a callback, using
console.log to represent the code that should be run after the event happens. The
event.unregisterbyid in the callback is because BizHawk's event registrations are multi-shot, and we only want to be called back once.
Language: Lua
local event_id
event_id = event.on_bus_exec(function ()
event.unregisterbyid(event_id)
console.log("exec", ADDR)
end, ADDR)
And here's an equivalent example that uses coroutines in the way I described:
Language: Lua
local co = coroutine.running()
local event_id
event_id = event.on_bus_exec(function ()
event.unregisterbyid(event_id)
coroutine.resume(co)
end, ADDR)
coroutine.yield()
-- Execution continues here after callback calls coroutine.resume.
console.log("exec", ADDR)
It may not look like much of an improvement at first. But notice that, crucially, the
console.log happens at the same level as
coroutine.yield—not inside the callback. This makes a big difference when the code that needs to be executed after the event occurs is more complex—and especially when that code goes on to wait for further events. It's analogous to
converting callback-oriented code to use promises and async in JavaScript. You'll see this pattern used in the support code's functions
run_until_event_raw and
frame_align.
You can, of course, encapsulate the coroutine operations in a function. Then waiting for multiple events in sequence becomes a simple sequence of statements:
Language: Lua
local function wait_for_exec(addr)
local co = coroutine.running()
local event_id
event_id = event.on_bus_exec(function ()
event.unregisterbyid(event_id)
coroutine.resume(co)
end)
coroutine.yield()
end
wait_for_exec(ADDR1)
console.log("exec", ADDR1)
wait_for_exec(ADDR2)
console.log("exec", ADDR2)
Whereas doing the same in the callback style would require nested callbacks.
In the callback style, the emulator is in control: the emulator runs, and calls into your Lua script when certain events happen. In the coroutine style, your code is in control: your code runs, and calls into the emulator when it needs the emulator to compute a new savestate. Of course, behind the scenes, everything is still all built on the emulator issuing callbacks to the Lua engine, but you get to write your program in a natural way. Think of the emulator as a hardware peripheral, a co-processor optimized for computing over savestates. Driving the emulator is not the goal in itself; rather the emulator is a tool that helps you incrementally compute the game-winning savestate you want.
Now I'll comment on a few parts of the support code to help explain what it's doing.
Language: Lua
-- The metatable for all savestate objects. The important metamethod is
-- __gc, which tells BizHawk to reclaim the resources of savestates
-- that are no longer referenced.
local savestate_mt = {
__gc = function(savestate)
delete_emu_savestate(savestate.id)
end,
__tostring = function(savestate)
return string.format("savestate{%s}", savestate.id)
end,
}
-- Create a new savestate object from the current state of the
-- emulator. It is the caller's responsibility to ensure that the
-- emulator state is frame-aligned.
local function new_savestate()
-- A savestate object consists of the identifier of an
-- emulator-native savestate, and the joypad state.
local savestate = {
id = save_emu_savestate(),
buttons = joypad.get(),
}
-- Keep the keys from joypad.get, but set all the values to false.
for k in pairs(savestate.buttons) do
savestate.buttons[k] = false
end
setmetatable(savestate, savestate_mt)
return savestate
end
A "savestate" object is a table with
id and
buttons keys. This is all I needed for
Kwirk; other games may need more.
id is the ID of a native BizHawk savestate (which I've called an
emu_savestate to distinguish it from our savestate objects).
buttons makes the state of input part of the savestate, because
BizHawk savestates do not store what buttons are currently pressed. The joypad state would otherwise be another global variable. We set a
__gc metamethod on savestate objects to free the savestate object's associated BizHawk-native savestate when the object is no longer referenced.
Language: Lua
-- Assume that at the point at which this script is run, it's a safe
-- time to make a savestate (i.e., we're frame-aligned).
BASE_SAVESTATE = new_savestate()
The only way to get a savestate object is to do an operation on an already existing savestate object. Where does the first savestate object come from?
BASE_SAVESTATE is set to the state of the emulator at the point when the script is loaded.
Language: Lua
-- Run the emulator until the event registered by the register_event
-- function happens, or frame_limit frames elapse, whichever happens
-- first. If the register_event event happens first, return true; if
-- frame_limit is exceeded first, return false. frame_limit may be an
-- integer, or nil to mean "no limit". register_event should be a
-- callback registration function such as event.on_bus_exec,
-- event.onframeend, etc. The ... variable arguments are passed to
-- register_event.
local function run_until_event_raw(frame_limit, register_event, ...)
if frame_limit ~= nil and frame_limit <= 0 then
return false
end
local co = coroutine.running()
-- We register two event callbacks: one for the event the
-- caller is interested in (event_id), and one to count frames
-- and enforce frame_limit (limit_id). We register both
-- callbacks, then yield to let the emulator run until one of
-- the two callbacks calls coroutine.resume. The event_id
-- callback resumes with the value true; the limit_id callback
-- resumes with the value false. After being resumed, we
-- dispose of the callback that was not called. We register
-- event_id before limit_id so that, if both callbacks happen
-- for the same event, the caller's event takes precedence.
local event_id = register_event(function ()
if co ~= nil then
assert(coroutine.resume(co, true))
end
end, ...)
local frame_count = 0
local limit_id = event.onframeend(function ()
frame_count = frame_count + 1
if frame_limit ~= nil and frame_count >= frame_limit then
if co ~= nil then
assert(coroutine.resume(co, false))
end
end
end)
local event_occurred = coroutine.yield()
assert(event.unregisterbyid(event_id))
assert(event.unregisterbyid(limit_id))
-- We want only one of the two callbacks above to run
-- coroutine.resume. At this point, one of them has done so --
-- but just unregistering both callback IDs does not guarantee
-- that the other will not also run coroutine.resume. That is
-- because both callbacks may be looking for the very same
-- event; i.e. register_event is event.onframeend and
-- frame_limit is 1). BizHawk runs all callbacks that were
-- registered at the time the event occurred, even if, in the
-- course of working through the list of callbacks, a later one
-- gets unregistered by an earlier one. We set co to nil as a
-- signal to both callbacks that if they run, they should not
-- call coroutine.resume.
co = nil
return event_occurred
end
-- Starting from the given savestate, return a new savestate that is
-- the result of running until the event registered by register_event
-- happens; or return nil if frame_limit frames elapse without the
-- event happening. frame_limit may be nil for no limit. register_event
-- should be a callback registration function such as
-- event.on_bus_exec, event.onframeend, etc. The ... variable arguments
-- are passed to register_event.
function run_until_event(savestate, frame_limit, register_event, ...)
restore_savestate(savestate)
local event_occurred = run_until_event_raw(frame_limit, register_event, ...)
if event_occurred then
-- The event may not have occurred at a frame boundary,
-- so align the emulator state before creating the new
-- savestate.
frame_align()
return new_savestate()
else
return nil
end
end
The function
run_until_event_raw encapsulates the basic register/
coroutine.yield/
coroutine.resume pattern I've described, for arbitrary events. It gives you the option of specifying a maximum number of frames to wait for the event to happen before giving up. The internal, "raw" version of the function operates on the emulator directly: it starts at the current state of the emulator, and mutates the state before returning. The public function
run_until_event wraps
run_until_event_raw in a safe interface that takes a savestate object as input and returns another savestate object as output.
run_until_event calls
restore_savestate (another trusted function) to reset the emulator to the input savestate object before calling
run_until_event_raw; and then calls
new_savestate to create a savestate object from the emulator state.
Language: Lua
-- Find the earliest frame at which running an action function on a savestate
-- produces a savestate that satisfies a test predicate.
--
-- The action function takes a savestate as input and returns a savestate as
-- output. The test function takes a savestate as input and returns a Boolean
-- output (nil|false or otherwise). This function runs the action function on
-- the given savestate, then runs the test predicate on the resulting
-- savestate. If the test function's return value is not nil and not false, it
-- returns two values: the return value of action and the return value of test.
-- If the test function returns nil or false, it goes back to the original
-- savestate, advances one frame, and tries the action and test again. The
-- process continues, advancing one frame at a time, until the test predicate
-- succeeds.
--
-- It is common to call this function with a test predicate whose return value
-- is either a savestate or nil. In that case, you can regard the two return
-- values as "savestate after action performed" and "savestate after test
-- passed".
local function earliest_effective_frame(savestate, action, test)
local action = action or function (savestate) return savestate end
local frames = savestate_frame_count(savestate)
while true do
local action_performed = action(savestate)
local test_result = test(action_performed)
if test_result then
return action_performed, test_result
end
-- No luck with this frame. Try doing the action one frame later.
savestate = run_one_frame(savestate)
local new_frames = savestate_frame_count(savestate)
assert(new_frames == frames + 1, string.format("frames=%d new_frames=%d", frames, new_frames))
frames = new_frames
end
end
earliest_effective_frame is the most important auxiliary function used throughout the script. Starting from a provided
savestate, it finds the earliest frame at which performing an action (such as pressing a button) eventually has some effect (such as a memory location being written to or an address being executed). The
while true loop advances one frame at a time, running the
action function on a savestate for that frame, then running
test on the savestate that
action returns. The loop terminates when
test returns a true value. The function returns the results of calling both
action and
test (because sometimes you want one or the other). In the
Kwirk TAS, the
test function is usually one of the functions defined in terms of
run_until_event, such as
run_until_exec or
run_until_u8_becomes. These functions return either a future savestate, or
nil if the event doesn't happen within the frame limit. The effect of using such a
test function in combination with
earliest_effective_frame is that we peek a short time into the future after performing every action, to see if the action
will have an effect. This is a versatile operation that helps with a lot of TASing tasks. In the title screen code excerpt above, you'll see
earliest_effective_frame called with an
action function that presses the Start button, and a
test function that peeks up to 32 frames ahead to see if
MENU_ADDR gets executed.
The savestate manipulation support code in tas.lua is what I needed for
Kwirk. The same or a similar technique could work for lots of other games and TASing tasks, so I encourage you to try it with your own projects. But you may have to make some adjustments, depending on what you're doing. For example, my TAS only needed joypad buttons; if you're doing a console with an analog stick, you'll need to add the analog stick state to the savestate object. The current version of the support code wouldn't work well for press-and-hold inputs (
Kwirk only needs one-frame presses). In order to hold buttons in a convenient way, you may have to enrich the savestate object to support some kind of "sticky" inputs that don't become unpressed when the frame is advanced, perhaps by adding code in the frame counter callback of
run_until_event_raw that renews the inputs every frame.
What about the common
while true do emu.frameadvance() end pattern, which is
endorsed in the BizHawk docs and
used in example scripts? It turns out it's equivalent to a special case of what I have shown here.
emu.frameadvance just
calls coroutine.yield after setting a flag indicating that the script wants to be resumed at the next frame. Scripts that yield in that way are
resumed by a function that
calls coroutine.resume. So calling
emu.frameadvance is effectively the same as calling
run_until_event with
event.onframestart, relying on special-purpose code inside BizHawk. The advantage of doing it yourself is that you can do it with any event, not just
event.onframestart.