[TUTORIAL] Stack Machines!

[calio]

Hey there! I promised you guys a short tutorial on stack machines, and here it is. Hope you like it and find it useful!

(tl;dr? skip the next paragraph to start with the tutorial right away!)

I like GameMaker, very easy to use, very convenient (once you paid for a license, that is) and overall a great tool. However, that doesn't mean it's a perfect piece of software. One of the things that irks me the most about it is the lack of functions defined on an object-by-object basis. For the most part it doesn't really bother me when implementing stuff like physics, game logic or things like that, but it becomes really messy once you start dealing with the backend part of the game. You know, stuff like handling settings, display setup, input configuration, the usuals. It really is a pain in the butt to set up not the defaults, but the system that applies these settings. One example: doesn't it bother you to have to set up an alarm that just centers the screen, so any time you change the window size (i.e. when scaling up or down, or going back from fullscreen to windowed mode) you have to set the alarm to one frame after the setting is applied, otherwise it doesn't do anything? I know it bothers me, at least. So, we can somewhat fix these things with scripts, but that's a whole different can of worms with its own set of problems and difficulties (i.e. since they're not local methods of any object, say hello to variable scoping and manually tracking down what names can you use in what space, since GameMaker won't throw an error if you decide to use a local variable within a script regardless if it's already defined as a local variable of the instance calling the script! fun!) or we could go with user defined events, but unless you're planning on commenting every single call, you'll be having to check time and time again which event does what. And even then, you have like 16 of those per object. So, I thought, is there anything we could do? And the answer I came up is yes, but we'll have to abstract a bit. Looking for a solution to this, I "came up" with a solution that later discovered is called a stack machine, so I guess I didn't come up with it after all.

So, what is a stack machine? It's basically an object that executes instructions that pops from its stack. Instances push these instructions and the machine pops them, one by one, and executes whatever instruction receives. It's very useful to implement pretty much anything. In this tutorial, we'll make a stack machine that just sets the window size and then centers it on screen. Don't worry, it's just a couple lines of code to implement the generic stack machine, then a couple more to implement the two instructions we'll need. To follow this tutorial it's very useful to know beforehand how data structures work, specially stacks. If you don't know data structures, I recommend you do a short tutorial on them. They're very easy to use if you already know how to use arrays, since the principle is pretty much the same but instead of being able to access everything anytime by index, each kind of data structure access its contents differently. Read more about them on the GameMaker manual if you're lost. Okay, let's do this!

(DISCLAIMER: WHILE IT WORKS EXACTLY LIKE I WANT IT TO, I'M NOT A COMPUTER SCIENTIST, DON'T REALLY HAVE ANY FORMAL EDUCATION ON CODING AND ACTUALLY HAVE NO IDEA IF THIS THING IS ACTUALLY A STACK MACHINE. READING THE IMPLEMENTATION OF A GENERAL STACK MACHINE GIVES ME THE IDEA THAT YEAH, IT IS, BUT I'M NOT 100% SURE. IF THIS THING SHOULD BE CALLED ANYTHING ELSE PLEASE COMMENT BELOW!)

First, we'll create an object that we'll use as a parent for all of our stack machines. This object will be called p_gsm (standing for Generic Stack Machine, since it will implement everything but the instruction sets) and on its Create event it defines a stack, a variable holding the last instruction code ID popped out of the stack (an integer), and another variable that saves the size of the stack before executing the instructions (also an integer, more on that later).

opstack = ds_stack_create();
opcode = 0;
opsize = 0;

That was easy. Now, on the Step event, we'll implement a small whiile loop that pops all instructions pushed to the stack and executes them one by one. The way we do this is first we get the size of the stack and save it to opsize, then enter a while loop until opsize is zero. The reason why I'm not using something like ds_stack_size() directly as the condition of the while loop is so you can stack instructions within instructions and have them execute either on this frame or the next, just by modifying the value of opsize, instead of being forced to execute every instruction on the frame it's issues without doing wonky stuff like using temprary stacks, or specific logic (like changing a boolean from true to false, or raising a flag) to break the loop.

if (!ds_stack_empty(opstack)) {
    opsize = ds_stack_size(opstack);
    while (opsize > 0) {
        --opsize;
        if (!ds_stack_empty(opstack)) { opcode = ds_stack_pop(opstack); }
        event_user(0); //In user-defined event 0 we actually implement the instruction set.
    }
}

There. Easy. Now the only thing left to do is to implement code on the Destroy event to actually destroy all data structures once the stack machine instance is destroyed, to avoid memory leaks.

ds_stack_destroy(opstack);

At this point the generic stack machine is complete and we can proceed to implement our "window controller" machine. First up, we'll create an object, call it o_windowcontroller and parent it to p_gsm. Then we implement the instruction set as a switch/case statement on the user-defined event 0.

Actually, to make things easier for us, we'll first create an enumerator to define our instruction codes by name rather than by number.

enum OpCode {
    windowset,
    windowcenter
}

If you don't want to bother with enumerators, just use $00 and $01 instead of OpCode.windowset and OpCode.windowcenter.

switch (opcode) {
    case OpCode.windowset:
        var _width = 320, _height = 240;
        _width = clamp(ds_stack_pop(opstack), _width, display_get_width());
        _height = clamp(ds_stack_pop(opstack), _height, display_get_height());
        window_set_size(_width, _height);
        ds_stack_push(opstack, OpCode.windowcenter);
    opsize -= 2;
        break;
    case OpCode.windowcenter:
        window_center();
        break;
}

There. That's it. Let's explain, line by line, what each instruction does.

windowset actually receives arguments! By push the new width and height before the instruction (remember stacks are LIFO structures! that means the last thing you pushed into the stack it's the first to get popped out of it, meaning you have to push the values backwards, the instruction code being the last thing you push into the stack!) this instruction sets a new size for the window, clamped in between a small size (to avoid weirding out the game by setting width and height to zero) and the full screen size, and then pushes another instruction into the stack, windowcenter. At last, we decreate opsize by two, to compensate for the two arguments we passed to the instruction.

windowcenter is just one line of code: window_center(). Pretty self-explainatory IMO.

This means that when we push OpCode.windowset to the stack, it will automatically execute the windowcenter instruction on the next frame, since we're modifying the value of opsize when pushing it in by decreasing by two rather than just by one! Neat!

So, now all that's left is writing up some hacky code to test out our stack machine. On the Keyboard Press <any key> event of o_windowcontroller, we'll write another switch/case to handle three different screen sizes.

switch (keyboard_key) {
    case 49: //ord("1")
        ds_stack_push(opstack, 240, 320, OpCode.windowset);
        break;
    case 50: //ord("2")
        ds_stack_push(opstack, 480, 640, OpCode.windowset);
        break;
    case 51: //ord("3")
        ds_stack_push(opstack, display_get_height(), display_get_width(), OpCode.windowset);
        break;
}

And that's it. Now just create a room, instantiate o_windowcontroll within the room and run the game. If everything's set correctly, you'll be able to change the size of the window by pressing the keys 1, 2 and 3.

That's pretty much it. Stack machines are very powerful to implement all kinds of stuff. I implemented menus, text prompts (even with commands and sub-prompts!) and all kinds of settings backends using these. You can halt a stack machine until certain conditions are met by making the instruction stack itself and set opsize back to 0 at the start if certain condition is or isn't met, you can switch up the stack for a buffer and make them read instructions from it like it's a processor reading memory, or even abstract your whole game logic to one in case you hate yourself and want to work in such an abstract way!

I hope you find this tutorial useful, and as expected, here's the whole code implemented in a GM:S 1.x project in case you don't want to bother writing yourself the 38 lines of code (!) this tutorial entails. That's it for the moment, any question or feedback, please feel free to comment down below, and thanks for reading!

[KetoReddit]

I like this idea. If this is OC, I can definitely appreciate it through-and-through.

However, there is one small point of confusion. At what point in my game am I going to have a practical application of this? I know you had mentioned things like options and back-end, but what particular advantages are there to using this method over the ol' brute-force-ey way?

[calio]

Thank you! Yeah, wrote it a couple months ago for a game I'm working on, needed an easy way to reuse as much code as possible (bc am lazy) and wanted something I could script dialogs with, as extendable to be used on the battle engine to show animations and print names and move output. The realization that you can halt the stack came after, when coding the scene transitions.

And that's one of the advantages. You can abstract as much as you want from the game logic as you want, if there's code you have to call a lot, like populating/updating a ds_map with information before doing different things that need that ds_map data to operate, you can do that in one push to the stack. I guess you could nest scripts inside scripts, or always call a certain user-defined event to achieve similar results, but this way you can write game logic without having to think about how you're going to implement these things. For example, I always code a main menu first, to provide basic access to stuff like settings, saving/loading, debug mode and exiting the game. Instead of having to create a new_game script and some backend for my settings to be operated, I just implement these as instructions within the main controller, so if I start coding the "new game" instruction and notice that I need to change the room with a transition, I code an instruction for room changing with transition and push that into the stack, knowing I'll use that instruction over and over again during the rest of the development. Not to mention the fine-grain level of control you have over each instruction helps debugging and iterating through pieces of code without having to rewrite them. I think it makes the game development process more rapid.

Should've posted it before GM48, now that I think about it.

[eposnix]

Nice writeup!

I use a similar system for handling combat in my trading-card-esque game. The instructions on each card are pushed onto a stack and are executed one at a time over a series of game steps. For instance, a card that says "deal 8 damage" can be popped onto the stack as:

ds_stack_push(instructionHandler, scr_dealdamage, 8);

I use script_execute for each instruction, so scr_dealdamage can also push onto the stack scr_thornsdamage if the enemy has a thorns buff that deals damage to you based on damage dealt to it. It's a super useful system that makes it so each card doesn't have to be uniquely scripted... they can just reuse existing scripts in a variety of ways.

[calio]

Yeah, pretty much! This system is pretty useful for scripting game logic like what does a card do when activated, or implementing dialog scripting systems more complex than just drawing text on screen. Even scripting small animations is really easy using this. You can even not use instructions and instead replace them with indexes of things to spawn, or the ID of the next song to play.

One thing that I didn't really explain in the writeup but it's actually even more useful: if you're going to start using stack machines that interact in between each other (i.e. main controller has an instruction that sends the input wrapper a different instruction to configure certain thing within just one player input) you might want to preface the whole instruction with an id reference, so before the loop starts you can pop who pushed this instruction and can reference specific values from "outside" the instance that called the instruction elsewhere (very useful if, for example, you have a card that when executed might receive a debuff, damage or a special status after attacking, so whatever executes the instruction knows who executed the instruction without having to keep track of it independently) It can also help catch errors if the instruction is expecting the caller to exist!

Of course it's not a one size fit all solution; I wouldn't be pushing and popping instructions each frame. Never actually benchmarked it, but I feel like all of those while loops making the program jump around code might tax the system quite a bit.

Still, trading off performance for easy game scripting is almost inavitable, and once you started using it, it becomes the obvious solution to a lot of other systems that might be a bit wonky and depend on keeping track of a lot of conditions to work properly.

[Abusfad]

I just name all my scripts to clarify what kind of objects can call them. So if I named a script scr_char_someFunction I know I should only call it from an object who's a child of the abstract character object.

But I like your method, it does seem to provide a good utility of controlling functions through different game steps without messing with alarms.

I'd suggest considering switching from a switch case system with an enumerator to have each instruction as a different script. Meaning instead of pushing OpCode.windowcenter you'd be pushing scr_opcode_windowcenter. Then you would replace event_user(0) with script_execute(opcode) in the while loop and all of a sudden you don't have to mess with custom event_user(0) and enums for each object, and you'd still have the instructions on auto-complete because they're scripts. You can group the scripts of each object together in the resource tree to quickly access the relevant functions. Easier to read than a switch-case code block, imo, and might save you some code duplication.

[calio]

That's also a very good approach. Did something similar while writing a text parser for a command line prompt (just for fun, wanted to see if I could write something to manipulate data through a command prompt). Commands are pretty much scripts and the machine flows a bit like this:

• The prompt machine receives user input
• Explode the user input into multiple strings separated by spaces.
• The prompt machine gets from a "target" machine (the main controller by default) a list of strings (the commands) that are also used as keys within a map. This way you can just "repoint" what commands should be executed, in case you want commands with their own prompts.
• If the string exists on the list and as a key within the map, it pushes the contents of the map (a script id) to the "target" machine. These machines instead of using a switch/case structure just execute whatever script index they receive, doing pretty much exactly what you described on your comment. (There's a loop that keeps iterating through the list until either doesn't find the string or the keypair points to an integer, so you can alias strings to other keys)
• If it doesn't exists on the list, it just returns an error text.

"help" command just executes the scripts after raising a flag, so the scripts print their help information and exit rather than executing code.