There are a lot of variables and objects in a game's internal state.
And more importantly, there are a lot of relationships and connections between these variables and
objects.
In order to have the game run effectively without slowing down, calculations done between
these variables need to be done efficiently.
It is common to sacrifice some memory usage and overall code compactness in order to have
it run faster or be easier to understand.
However, using this extra, redundant data to help code run more effectively comes with
some drawbacks.
Mainly, that it becomes more difficult to retain a consistant, defined state.
Since code efficiency is what's at stake here, error checking is minimal.
Therefore, the code needs to be extra careful that it can't enter an invalid state that
would cause catastrophic errors and glitches.
In this video, we'll look at a couple design patterns that revolve around data redundancy
and then look at some example case studies and see exactly how things can go wrong.
Let's first look at a very simple example of data redundancy.
Suppose you just needed to keep track of a list of items.
It doesn't matter what they are, or even what order they are in.
The only thing you need to know is whether an item is in the list or not, and you should
be able to figure out how many items are in the list.
Say, a list of video game consoles you own.
You would write down each console you own right this moment.
If you ever sold one or gave one away, you would remove it from the list.
And if you ever bought a new one, you would add it to the list.
Easy, right?
If you ever want to know how many consoles you own, you just have to count how many items
are on the list.
One, two, three, four, five, six, seven.
Okay, but what if instead of seven items in a list, you had seven hundred, or seven million?
It would be quite the task to count every item in the list each time you wanted to know
how many there were.
So, to be more time efficient, you could also keep track of how many items are in the list
in conjunction with the list itself.
This is the data redundancy I'm talking about.
You don't necessarily need to keep track of how many items are in the list--it's an intrinsic
property of the list itself.
While it does take up resources to include this metadata in the data structure, the trade
off is well worth it in terms of time needed to query the property of the structure.
But there's additional work you have to do if you provide a shortcut like this.
You have to make sure the new property is valid at all times.
Since we are essentially taking an intrinsic property of this list and copying its value
into a separate field, the value has to be updated accordingly if the base property of
the list changes.
What that means for us is that we have to update our length property each time something
is added or removed from the list.
If we don't, then we risk being out of sync with the data structure.
Therefore, if something is added to the list, we add one to the length, and if something
is removed, we subtract one.
Otherwise, the length property will not match the actual length of the list.
This could cause some serious issues, especially around the edge cases where the list is empty,
or where the list is full (if it has a maximum size).
And as you could probably guess where this was going, this is exactly the sort of problem
that can occur in the item lists in the first generation Pokémon games.
This applies to both the player's item bag as well as the PC's item storage.
Let's look at the exact structure these item lists use in the game.
The very first byte in the list structure holds how many item stacks are currently in
the list.
Then each item in the list is specified one after the other.
Each item element consists of two bytes: one byte for the item's unique ID, and another
byte for the number of items in that stack.
The player's item bag allocated room for 20 item stacks, taking up 40 bytes, while the
PC's item storage has room for 50 item stacks, taking up 100 bytes.
Then, there was a single byte at the end of the list used for marking the end of the list.
Just as a reminder, the data redundancy here has to do with the size of the list, or put
in a different way, finding the end of the list.
The end of the list can be found by either querying the first byte of the structure,
or by just scanning through all the items in the list itself before hitting the terminator
byte.
Actually, let's look at exactly how this terminator works, because it will be useful to know to
understand how the item list can become desynched.
Each item is given a unique ID, starting from 1 and going up to 97 as well as 196 through
250.
And then the quantity for each item stack can be anywhere from 1 to 99.
The terminator is just a special item in the list with the ID of 255, the greatest number
you can represent with 8 bits.
Unlike all the other items, this item, which gets displayed as 'CANCEL' in the item list,
has no quantity associated with it.
This is why the list structure has this odd byte at the end.
When the list is full, the terminator fills this last byte, and it doesn't require a quantity,
saving one byte of memory.
When the list is not full, anything in this region of memory that comes after the terminator
is ignored.
Let's see how the game handles adding and removing items from the list.
To add an item to the list, the size of the list is compared to the maximum possible size--20
for the bag and 50 for the PC.
If the size is exactly equal to this maximum size, the list is determined to be full and
the addition is aborted.
If it is not equal--not just less than, but not equal--then the item is added to the list.
The new item's unique ID is stored in the list at the index corresponding to the list's
current size, which is normally where the terminator is currently.
It's quantity is written in the byte after, and then a new terminator is written in the
byte after that.
Then, the size of the list is incremented by one.
This implementation of this function is adequate.
If the list starts in a valid state--that is, the number of items is between 0 and 20
(or 50) and the quantity for each item stack is between 1 and 99--it will always be in
a valid state after this function.
If the list starts in an invalid state, some unintended behavior could occur.
Suppose the redundant count property was lower than the actual number of items in the list.
When adding the new item, an existing item in the list will get overwritten.
And then every item after it will be lost since a new terminator gets appended to the
list data right after this newly added list entry.
After this though, the list is in a valid state again.
But suppose the redundant count property was higher than the actual number of items in
the list.
The data for the new item would get written to memory, but since this is after the list
terminator, it's not part of the valid part of the list.
Although as you'll see later, this item would still be accessible--you would just have to
scroll past the 'CANCEL' option in the menu.
But these conditions should never happen in the first place, so it's fine, right?
To remove an item from the list, the function responsible needs to be supplied with the
index of the item to remove.
So an index of 0 removes the first item, an index of 1 removes the second item, and so
on.
This index is never checked against any bounds, since it is assumed that it will always be
within the bounds of the size of the list.
The item at this index in the list is identified, along with the item directly after it.
Then the byte at the position of the second item is copied to the location of the first.
Both of these pointers to memory locations are incremented by one and this continues
for the rest of the list.
This effectively shifts all of the items up one position in the list, so that there are
no empty gaps in the data structure.
The item data continues to be shifted back two bytes until the terminator is shifted
over, at which the list size is decremented by one and the function completes.
This implementation of this function is completely adequate as well.
If the list starts in a valid state, it will always be in a valid state after this function.
There is one unintended behavior that is possible when the list starts in an invalid state which
is when there is an item with a quantity of 255.
When shifting the items back a slot, each byte is checked for the terminator, instead
of just the item ID.
So if an item has a quantity of 255, that 255 will be treated as the terminator itself.
This results in the item stack in question being duplicated, and all the items after
it in the list not moving.
This also means the size of the list becomes desynched.
The redundant size byte is still decremented by one, but the size of the list never actually
changed, since one item was removed and one item was duplicated.
But these conditions should never happen in the first place, so it's fine, right?
Well of course, there is a way to glitch an item to have a quantity of 255.
Encountering MissingNo.
sets the highest bit of the quantity of the item in the sixth slot of the bag.
Which happens by the way because the Pokédex registers each Pokémon that you've seen as
a single bit in a large table.
MissingNo.'s dex number of zero gets interpretted as 256, and this table is indexed out of bounds.
The bit that actually ends up being set corresponds to the highest bit of the item quantity of
the sixth item in the bag.
This has the result of adding 128 to the already existing quantity of that item.
So by encountering MissingNo.
once, then tossing enough of the item to get a quantity of 127, then encountering MissingNo.
again, the quantity will become 255.
With this glitched item, you can toss the same item stack over and over since it duplicates
itself.
This ultimately desynches the redundant size property and causes it to continue to decrease
even though the list isn't getting any smaller.
Eventually, this value becomes zero and wraps around to 255 with one more item removal.
With the redundant list size property being 255, you can now access the item list as if
it had 128 items, even though only 20 items worth of space is allocated to memory.
See, the list terminator in this case is only used in practice for drawing the word 'CANCEL'
in the item menu, and to aid with removing items from the list.
The redundant list size property is used for everything else, including acting as the bound
to check against for the cursor in the menu.
So in this state, the cursor can continue to be brought down past the intended limit
for the item list.
All of these glitch items are various other game variables being interpretted as items,
and they can be manipulated in any way that items in the bag can be manipulated, such
as swapping them around and tossing them.
As you can see, you have to be very careful when using redundant data like this to control
how a data structure works, especially in a situation where you aren't going to have
any kind of error checking.
You have to be sure that every action taken on the structure updates all metadata properly
so that everything is in sync at all times.
This isn't to say that things can't go wrong when you don't create metadata shortcuts,
but that maintaining these properties can lead to errors that just can't exist without
them.
This is even more of the case when different metadata are used for different kinds of tasks.
Like in this example, where the terminator is used to reduce the size of the list, but
the redundant size property is used to expand it.
This leads to cases where items can be added without an issue, but can't be removed without
messing things up.
Let's look at another redundant data pattern that can cause a lot of issues when values
get desynched.
Again let's start super simple.
Suppose you have two data structures--whatever they may be--and they need to be linked in
some way.
Maybe this is a parent-child relationship where this object belongs to the other, or
maybe these are two similar objects that need to be paired off for some reason.
The simplest way of creating this link would be to store a pointer to one of the objects
inside the data structure of the other.
That is, the memory address that denotes where this object's data is stored in memory is
itself stored inside the data of the second object's data.
With this information, you can follow the pointer to access the data of the other object
if you are working with it first.
Now, if these objects belonged to a larger super-structure where you had access to them,
this one-way link would be sufficient for denoting this relationship.
If you were working with this object instead, you can't just follow the pointer backwards.
You would have to go to the super-structure and work your way to the first object, then
compare the value of its linking pointer and see if it matches the object in question's
memory address.
Sure, this would be pretty inefficient, especially if there were many other objects that could
also possibly relate to this one, but it wouldn't be impossible to figure out.
Therefore, in order to streamline this process, it is very common to actually include the
converse pointer from the second object back to the first.
This way you can hop back and forth from one object to the other without any complications.
When you do this though, one of these pointers becomes redundant, just like with the length
of the list in the previous example.
Now in order to modify this relationship, two pointers have to be updated instead of
just one, and they have to be done carefully at the same time.
For example, to change this relationship from between objects B and D here to B and C; first,
the pointer from B to D should be updated to go from B to C.
Then, the pointer from C needs to be created to point from C back to B.
And finally, the pointers from D to B and A to C need to be removed completely.
What used to be one or two operations is now three or four operations instead.
If any of these operations are done incorrectly, you can end up with a one-way relationship
where one object doesn't know about the other, a double relationship where two objects know
about the same object, or a disjoint relationship where the true link between objects is completely
mixed up.
There's an infamous glitch in Super Mario 64 that is a byproduct of this sort of error.
It's not quite as straight-forward as the super simple example we just saw, but it boils
down to the same principle.
First lets look at how objects are handled in the game's code.
A pointer to each currently loaded object can be found in a doubly linked list.
This includes enemies, certain platforms, items, effects, and even Mario himself.
When objects load in, they get added to this list--either appended to the end or inserted
in the middle depending on the order the objects should be processed.
And the opposite when objects unload, they get removed from the list.
However, there's a bit more going on during these two actions.
These structs that actually make up the list, object nodes as they are called, are always
present, even if the object corresponding to that node is not loaded.
And even these unloaded objects are still present in memory, just not being used anymore.
These nodes are marked as being available for newly loading objects--their data will
replace the existing data of the old object.
When an object is loaded, one of the available nodes is given the new object's data, and
it is inserted into the list where it belongs.
And when an object unloads, the node is marked as available for a new object, and it is moved
to the end of the list of currently loaded objects.
This means there is always a dividing line between objects that are currently loaded
and objects that no longer exist in the stage.
But it is important to know that the underlying data of the object is still there, since it
never actually gets deleted until a new object loads into that node.
The next thing to look at is how the game deals with Mario holding certain objects,
like boxes and Bob-ombs.
When an object is grabbed, it doesn't actually stick to Mario's hands.
Instead, it is just hidden from view and from interacting with anything in the stage.
And separately, Mario's model is updated to show the object in question, but this is just
a graphical change.
It's only when the object is thrown or dropped that the real object is unhidden and warps
to Mario's position.
So why exactly does it work this way?
Mario and the object he's holding have a relation just as discussed earlier.
While Mario keeps track of what object he is holding, each object keeps track of whether
it is being held separately.
Now in practice, there is a global struct responsible for identifying which object Mario
is currently holding.
But we can represent this more abstractly as an arrow pointing from the Mario object
to the held object.
And also in practice, objects only have a few states that signify if they are being
held or not.
But since there is only one possible option for what can be holding them--Mario--we can
represent this more abstractly as an arrow pointing from the held object to Mario.
This two-way relationship is what we are interested in.
Normally, when Mario grabs and object, this two-way link is created together, and when
the object is thrown, the two relations are removed together.
However, there are ways to have only one of these relations created or removed, resulting
in an inconsistant game state where Mario is holding an item that doesn't know it's
being held or where an item behaves as if it is being held when it isn't.
Let's look at the first case.
It turns out that the two parts of this relationship aren't created simultaneously when an object
is grabbed.
First, Mario grabs the object and the first relation is created.
But it's not for a few more frames that the converse relation is created--it takes a little
bit for the object to realize it has been grabbed.
This slight discrepency isn't really that much of an issue normally, but if the object
unloads during this small window, the relationship will break.
Mario still behaves as if he grabbed the object, but the object doesn't exist in the world
any more because it unloaded.
Now remember, that when and object unloads, its data isn't actually erased right away,
but only when another object loads into the same memory location.
For example, suppose Mario grabs this box right when it unloads.
It may look like he successfully grabbed the box, but the box has actually unloaded, and
this is just an old, dormant version of it.
The moment another object loads into that memory location, Mario will be holding it
instead.
Now, you'll notice that the coin here that loaded in is still present over here.
This is why this glitch is refered to as cloning, since it looks like there are two copies of
the object--it's a bit of a misnomer though because there is really only one copy of the
object, just being rendered in two places at once.
When the coin loaded in, it was never notified that Mario is holding it.
So it behaves as it would normally, justing sitting in the stage.
It's only until the object is thrown that it updates accordingly.
The other glitch to talk about will be about breaking the link in the opposite direction.
When Mario uses a teleport in a stage, he will be forced to not hold an object.
Now normally, the teleport won't even work if Mario is holding something, but there is
another glitch that let's Mario hold an object while being in an animation state other than
those that correspond with holding an object.
This is refered to as holding the object hands-free, since it's no longer attached to Mario's hands.
In this animation state however, the teleport will work, even if Mario is holding the object
hands-free.
After the teleport, the relation from Mario to the object in question will be removed,
but not the reverse relation.", This results in the object just being hidden
forever, since it still behaves as if it were being held, even though Mario isn't holding
anything anymore.
In this example, the box will never reappear even though it normally comes back after some
time.
This is because the box is programmed to never disappear if it is being held.
And if the box thinks it's being held always now, it will never unload and never respawn.
By the way, Mario can still establish new relations with other grabbable objects just
fine.
In fact, by grabbing another object, it can be said that two objects are being held by
Mario at one time.
I said that objects become completely hidden when they are grabbed, but there is one exception,
and that is the Bob-omb.
The reason for this is so that the smoke that comes out of the top of the Bob-omb renders
next to the one that is in Mario's hands, since it is the actual Bob-omb object, and
not the rendered copy in Mario's hands that can make smoke.
What this means is that if you try this hands-free teleport glitch with a Bob-omb, when you reload
the Bob-omb by revisiting the teleport you entered, it will start smoking as if Mario
were holding it.
And if you grab another object when you do this, Mario will be holding that object and
the Bob-omb's smoke will still show up.
He quickly drops it though because the two objects are colliding with each other.
And because of the Bob-omb's exception, it is the only object that can be regrabbed out
of this state, since it isn't completely hidden like any other object.
In order to figure out everything you saw here, I referenced a Pokemon Red disassembly
and Super Mario 64 decompilation which you can find links to in the description.
Also, thank you to JoshDuMan and Pannenkoek for their help and documentation regarding
Super Mario 64--that game is a beast to delve into.
And of course, thank you for watching!