In this post, we will be looking at another data type, the “stack.” A stack is an ordered collection of elements that operates on the elements in a “last in, first out” (LIFO) order.
What does LIFO really mean? Think about a stack of plates in a cafeteria lunch line. A diner takes the plate off the top of the stack, which is the last plate that was added to the stack. So basically, the last plate added to the stack, will be the first one taken off the stack.
Stacks in computer science follow the same LIFO order as our real-world example.
Operations on a Stack
Some of the essential standard operations that many programming languages include for stacks include:
- push: Place an element onto the top of the stack
- pop: Remove and return the top element of the stack
Many languages also include several extra operations, such as:
- peek: Look at the item at the top of the stack, but do not remove it
- empty: Check to see if the stack is empty
- size: Return the number of elements in the stack
- clear: Remove all items from the stack
Possible Applications in RPGs
RPGs usually include a lot of multi-level menus. Turn-based battles rely on menus for choosing player actions. For example, consider a game like Final Fantasy 6. In battle, each player has a list of possible actions, which would be the top level of the turn “menu.” If the player casts a spell, he will choose the Magic option, which then brings up a list of spells. Once the player chooses a spell, the next step in this so-called “menu” is to move the cursor to the intended target. At any time, the player can change his mind and back out to the previous menu level.
This basic idea also shows up with other menus in games. For instance, let’s say you want to change a character’s equipment. First, you go to the overall character menu screen. Then you choose the character’s equipment menu. Depending on the game, you might choose a separate menu for the type of equipment. Games like The Elder Scrolls series let you view separate menus for weapons, armor, and accessories, for example. Once you’ve made your choices (or changed your mind), you can then “retrace” your steps through the menu back to the game screen, or even a previous menu screen.
Stacks would be a logical data structure choice to keep track of the order of the menu screens. You would work backwards from the last screen you accessed, all the way back to the bottom of the stack.
Undoing Previous Actions
Some game genres, particularly board and card games, often include a way to undo previous moves. Puzzle-platformer game Braid includes time rewind as a prominent feature, but some strategy-RPGs do as well. Playstation 3 game Tears to Tiara II allows users to rewind previous turns. Other games, such as some of the Fire Emblem games, Iron Danger, and Vestaria Saga II, also include a turn rewind mechanic.
A stack is a great way to implement such a feature. The last action you take would go on top of the stack, and then to undo actions, you could pop off the most recent actions from the top.
Stacks are yet another useful data structure that you can use in your own RPGs. Can you think of any other possible examples where stacks might be used in a game you like?
As a reminder, I am putting together an RPG course. If you’d like to provide some feedback about what you’d like to learn, and get updated when it’s ready, please fill out this form. And don’t forget to check the page on developing RPGs for more learning.