Adventures in Assembly

This post is part of my final project for one of my university courses, Assembly Language Programming. It'll be a bit more technical, but read on if you want to know a bit about how I used knowledge learned over the length of the course and NASM to create a choose your own adventure story format. There are a few small life updates at the end of the post for anyone who may not be technically inclined.

Text-based choose your own adventure stories are something that I've always had an interest in. Off and on for nearly the past decade, I've been working on one such game called Gordorio - it's been through many, many iterations, several restarts, and ultimately I run into issues that make me put it on the backburner until I pick up motivation a few months later. One of the most common issues that I run into is finding a simple and concise way to store the data for the story. Most importantly, this data consists of the text that the user will read and the options they'll have to choose between for each passage.

I've wanted to have a format that I could store this information in easily, while keeping everything easy to maintain and link together. I've gone numerous attempts to create such a format in the past, but I've always run into the issue of the implementation being too flexible and causing inconsistencies down the line, or it's difficult and unwieldy to create any complex story.

For the scope of this project, I decided to create a format that would allow me to create the base story - I want to create a format that could support the bare minimum data required, while also being extensible and easy to add additional functionality to later down the line.

Structure of a Story

To be able to implement this sort of structure, first it's important to look at what the structure of a choose your own adventure story usually is. Below I've made a simple tree that represents that structure of a simple story. Starting at the first section, you can follow it down each level of bullet points for your own story.

• You step into the classroom, fluorescent lights shining overhead, and look around. You're a few minutes late, but it looks like your professor is just now getting started. There's an open seat at the front of the classroom, and one towards the back. Where do you sit?
  • Walking up to the front of the classroom, you can feel the other students watching. Just a few minutes late isn't too bad, but you feel a bit silly walking up in front of everyone while the professor is talking. You sit down and pull out your laptop, ready to take notes.
  • You walk quickly to the back and sit quietly in the open seat. Looking forward, everyone seems to have their notebooks and laptops open already, so you work to get everything out and ready for notes. As you rummage through your backpack, you notice that you've forgotten any pens or pencils. Should you ask your neighbor or just skip notes for today?
    • Begrudgingly, your classmate hands you a mechanical pencil on the condition that you give it back at the end of class. Of course, you forget about the informal agreement and your trusting classmate is shorter one pencil at the end of the day.
    • You decide to skip your notes for today. As soon as you walk out of the classroom, you've happily forgotten everything that was talked about.

Making it Machine-readable

We can put this into a bit more of a machine-readable format by giving each passage (what I've begun to call "segments") its own identifier. We can keep track of the relationships between segments using the identifiers, and lay out the above story in a table like so:

We'll also want to add a keyword to each segment so the user can select how they want to progress after they've read a passage.

Notably, the 0th segment doesn't have an ID or a keyword - we're going to be treating segment 0 as the start of the story, so the user won't need to enter any keywords to access it, nor will it follow any other segments.

We can take this tabular data and convert it into a simple binary format - for my use, I've gone ahead and used NASM to compile a simple text-based file into a binary one. I found this approach much easier and approachable simply because it keeps the source file easy to read, while making the binary file easy to update. I've decided to use long ints for the IDs, and C strings for all text data.

dq 0 ; ID
dq -1 ; Inject after
db '', 0
db "You step into the classroom, fluorescent lights shining overhead, and look around. You're a few minutes late, but it looks like your professor is just now getting started. There's an open seat at the front of the classroom, and one towards the back. Where do you sit?", 0

dq 1 ; ID
dq 0 ; Inject after
db 'front', 0
db "Walking up to the front of the classroom, you can feel the other students watching. Just a few minutes late isn't too bad, but you feel a bit silly walking up in front of everyone while the professor is talking. You sit down and pull out your laptop, ready to take notes.", 0

dq 2 ; ID
dq 0 ; Inject after
db 'back', 0
db "You walk quickly to the back and sit quietly in the open seat. Looking forward, everyone seems to have their notebooks and laptops open already, so you work to get everything out and ready for notes. As you rummage through your backpack, you notice that you've forgotten any pens or pencils. Should you ask your neighbor or just skip notes for today?", 0

dq 3 ; ID
dq 2 ; Inject after
db 'ask', 0
db 'Begrudgingly, your classmate hands you a mechanical pencil on the condition that you give it back at the end of class. Of course, you forget about the informal agreement and your trusting classmate is shorter one pencil at the end of the day.', 0

dq 4 ; ID
dq 2 ; Inject after
db 'skip', 0
db "You decide to skip your notes for today. As soon as you walk out of the classroom, you've happily forgotten everything that was talked about.", 0

Once we've compiled this (simply nasm input.asm), we can easily read it in with whatever implementation we'd like to.

Parsing and Storage

Parsing has been made fairly simple for us since I made sure to use a consistent width for numbers, and using C strings allows us to easily pull out strings. Using a loop, we can just iterate over the input file until we've read all of the segments in. I created the reference implementation for this format in C, and as such here's a small data structure that I created to store the data for each segment.

struct segment {
  long id;
  long after;
  char* keyword;
  char* text;
};

This mirrors our earlier table, and gives us easy access to all the data that we want on a segment. Now, we just need a container to hold all our segments. I opted for a binary search tree, as it would allow relatively efficient lookup of each segment. I created another data structure that would allow me to build the BST as segments were read in, and later on I could look up each segment by ID.

struct sortedSegment {
  segment* loaded;
  sortedSegment* lt;
  sortedSegment* gt;
};

This structure allows us to easily look up any segment by its ID, but it does have a few drawbacks:

• If we lose track of the root node, entire sections of the story can become inaccessible.
• Finding the segments that can follow any given segment requires iterating over every node in the BST.
• Lookup by ID can be potentially slow - in the reference implementation the BST isn't balanced at all, and can grow very tall as a result.

All of these issues can be resolve with just a few simple steps. To do so, first we'll update our sortedSegment structure just a bit.

struct sortedSegment {
  segment* loaded;
  sortedSegment* lt;
  sortedSegment* gt;
  // A count of the number of segments that branch off of this one.
  size_t branchCount;
  // An array of pointers to any segments that branch off of this segment
  sortedSegment** branches;
};

These new properties will allow us to more easily list and jump to subsequent segments in the story. To get them populated, we only need to iterate over the original BST once. For each node in the tree, we'll look up the segment that its injectAfter property points to, and add it to the branches array after incrementing branchCount.

Once we've completed this process, we've effectively created another tree within the original binary search tree. This new tree exactly mirrors the original tree we had set out to represent a choose your own adventure story.

Playing the Story

Now that we have the story all parsed and set up in a structure that's easy for us to navigate, all we need to do is step through the story with the user's choices. There are a few simple steps that represent the game loop here:

1. Print out the current segments text
2. Get the user's choice for how they'd like to progress
3. Verify that the user selected a valid keyword for any of the following segments
4. Jump to the user's chosen segment

Once all is said and done, the output of a story playthrough might look something like this (lines starting with > are user input).

You step into the classroom, fluorescent lights shining overhead, and look around. You're a few minutes late, but it looks like your professor is just now getting started. There's an open seat at the front of the classroom, and one towards the back. Where do you sit?
> back

You walk quickly to the back and sit quietly in the open seat. Looking forward, everyone seems to have their notebooks and laptops open already, so you work to get everything out and ready for notes. As you rummage through your backpack, you notice that you've forgotten any pens or pencils. Should you ask your neighbor or just skip notes for today?
> skip

You decide to skip your notes for today. As soon as you walk out of the classroom, you've happily forgotten everything that was talked about.

With that, we've completed the creation of a simple choose your own adventure story.

What Could Be Better?

Notably, this format isn't extremely flexible. If I were to extend it in the future, there are a few things I'd like to add.

• Allow segments to specify multiple other segments that they'd follow. This could allow for much more complex story flow.
• Implement a format for setting and accessing variables. This would be useful to keep track of things like player inventory, as well as if players had visited part of the story yet.
• Expanding on the last point, a form of simple logic that could make automated choices based on those variables could be super powerful. Anything from battles, health counters, and any number of things could be done.

Extensions like these are part of why I wanted to keep the basic format so simple. Some of these could be implemented with relatively little effort right now! That being said, there are a few things that I do really like about the current format:

• To add more segments, you don't need to modify any existing segments - each segments manages its own position in the story.
• If you want to join two stories together, you can just concatenate the files together. Since everything is built off IDs, the stories should integrate together smoothly. I really like this because it opens the door for people to make third party additions to other people's stories without needing to distribute patched binaries.

For anyone who may be curious, the reference implementation along with some basic documentation is available over on GitHub at https://github.com/katlyn/asm-adventure. I'm looking forward to potentially using this format in my future projects, and I think it'll be a useful tool as I continue to work on choose your own adventure stories going forward.

Of course, a special thanks is in order for my professor, Dr. Lawlor, and the friends who helped me with this project. I really enjoyed working on this and had a lot of fun working over smaller implementation details.

For any of my readers who read this blog to keep up with what I'm doing, here are a few small life updates.

• I've completed two more semesters of university since my last post - I'm not currently a full time student, but I'm still making progress towards getting a degree.
• I was elected president of the UAF Cyber Security Club for the 2022-2023 school year. It's been fun to create lectures for the club, as well as to organize meetups and presentations.
• I've finally set up my own Matrix homeserver. If you're into that sort of thing, you can reach me at @katlyn:is-hardly.online - that being said, I'll still be available through the old channels as well.
• I've acquired an IBM Selectric III correcting typewriter. I think it's a lot of fun to use, and there's something that I find really nice about typing things out on physical paper. The correcting bit of it is also a really nice plus, as well as being able to mess around with the various font golf balls that are available.

As a thanks to anyone who's gotten this far, here's an unsolicited creator recommendation: I highly recommend watching some Clickspring videos if you're wanting some laid-back entertainment. They're an excellent machinist, and their skeleton clock build is worth every minute of watching. If you want a quicker overview of the build, they put together a shorter overview edit as well.