This post covers how Maze Burrow's "undo" mechanic works under the hood. This is a technical post, and some familiarity with the C# programming language may be required to understand it.

Preface

First, let's cover what the undo mechanic is. In Maze Burrow, you must solve puzzles by moving patterned blocks into matching tiles. If a move causes you to get stuck, or you simply change your mind, you can undo that move:

Maze Burrow is a simple game with grid-based movement. We shouldn't need to do much more than store each object's position, right?

Well, not quite. While Maze Burrow is indeed a relatively simple game, the level design increases in complexity, and new objects that are introduced as the game progresses makes this non-trivial.

Let's go over an example of such an object that you can encounter at the end of World 1: moles!



Moles throw rocks that can be used to defeat them. If the player undoes their move after a mole is defeated, what should happen? If we stored just the object's position, the player would be able to undo all their moves up to this point while the mole is still gone! On top of not behaving as expected, a player would be able to exploit this mechanic to get an unnaturally low move count in many levels.

One of my goals with the undo mechanic was to acknowledge all the drawbacks of undoing a move, which means the player has to redo any progress they lost from it. In this instance, undoing the move should cause the mole to be back where it was in tip-top shape:



If the mole is back after an undo, then we can also expect that if a rock was inside a pipe block after moving a block, the rock should then be back inside when undoing. We can see how these little interactions add up to make this fairly complex, which is where my implementation comes in.

Implementation

[Obsolete("Don't use this; use bar!!!")]
public bool foo;

The ObsoleteAttribute tells the programmer that the foo field should no longer be used.

[AttributeUsage(AttributeTargets.Field | AttributeTargets.Property, AllowMultiple = false, Inherited = true)]
public sealed class RecordableAttribute : Attribute
{
    public RecordableFlags RecordedFlags { get; private set; } = RecordableFlags.None;
    public RecordableAttribute(RecordableFlags recordableFlags)
    {
        RecordedFlags = recordableFlags;
    }
}

For whichever field we want to record, we attach the RecordableAttribute to it. For example, if we want to record an object's position, simply add the attribute:

[Recordable(RecordableFlags.None)]
public Vector2 Position { get; set; } = Vector2.Zero;

RecordableFlags tells us how to record the object, such as whether to clone it or not.

Great, so now everything we want recorded is Recordable, but how exactly can we use this attribute? At a high level, we need to record the values of every field and property that's Recordable and set them back to those values when undoing. To do this, we can create structures to hold all the data. These structures, say RecordedObjData, can contain the following:

• An object field, which is the object to record. For instance, a mole or block.
• A Dictionary<string, object> which is populated with the data of all the recordable fields and properties of the object. The keys are the names of the fields/properties, and the values are their respective values.

Another structure can be used to hold more information that we'll need. In Maze Burrow's case, a list of RecordedObjData and an object list for the level. The object list is necessary so we can preserve what was present before undoing; for instance, a mole after being defeated.

You may be thinking this can contain a lot of data, and it certainly will! If we have 50 objects in a level with recordable attributes, the data will add up quickly. Ideally, we want to reduce the number of allocations as much as possible to avoid .NET garbage collections.

Fortunately, when we look back at the type of game Maze Burrow is, it's only necessary to record everything once the player makes a move, which means pushing or pulling a block. That alone heavily reduces how much data we need to record and process.

However, we're not in the clear yet; we still need to record all the objects. To do this we'll utilize Reflection, which, among many other things, allows inspecting an object at runtime; this includes getting and setting members such as fields and properties!

I'll outline the process:

1. Get the Type of the object, along with all their fields and properties. This gives us FieldInfo[] and PropertyInfo[] arrays for the object.
2. Filter out all fields and properties that don't have Recordable attributes on them. This reduces how many we need to iterate through. To get the Recordable attributes we call GetCustomAttribute<RecordableAttribute>() on the FieldInfo/PropertyInfo.
3. While iterating the FieldInfo/PropertyInfo arrays, check the RecordableFlags on their Recordable attributes to see how the object handles it.
4. Get the value of the field/property with GetValue and do the appropriate actions for the above (Ex. if THAT object needs to be recorded, then record it - this is recursive).
5. Add this value to the list if it should be added based on the RecordableFlags.

Okay that's it, we are done. Simply use this data to set all fields and properties back when undoing, and we have our undo solution.

Optimizing

Not so fast. After implementing it like this, I found out that it was generating a whopping 600 KB of memory on a SMALL level! This caused the garbage collector to run like crazy, and even though it's manageable in a game like Maze Burrow, it's unlikely to scale well as the game gets larger. Not to mention, players with lower-end hardware might run into serious performance issues. How can we do better?

Optimization #1...?

The first thing is to understand what's going on under the hood. First, every time we call GetValue on a field or property, we're getting back an object, not the original type of the field/property. If the object we're getting back is a value type, such as an int or double, then that value is "boxed", which means it's placed into a newly allocated object on the heap. This extra allocation adds up for lots of objects and increases the memory pressure on the garbage collector!

However, we can't prevent that can we? Each field/property needs to be recorded after all. In this particular situation, there's little we can do to improve it, but at least we know this is where some of the memory is coming from. Let's look at other areas.

Optimization #2 - Caching

Remember how we were filtering out all fields and properties without Recordable attributes? Every time we call GetFields() or GetProperties(), while the individual FieldInfo/PropertyInfo objects are internally cached by the .NET runtime, the arrays they return are newly allocated.

On top of that, to get the attributes we need to call GetCustomAttribute<RecordableAttribute>(), which internally returns the first NEWLY ALLOCATED Attribute of a NEWLY allocated array!

The fields and properties of an object in Maze Burrow don't change at runtime, so that should give us a clue for how to approach this: cache, cache, and more cache!

That's right, we're going to be caching everything here: the filtered FieldInfo[] and PropertyInfo[] arrays, as well as the RecordableFlags on each Recordable attribute on every single one of them!

Most of it can be summed up in these three data structures:

• private static readonly Dictionary<MemberInfo, RecordableFlags> RecordableCache  = new Dictionary<MemberInfo, RecordableFlags>(512);
• private static readonly Dictionary<Type, FieldInfo[]> TypeFields = new Dictionary<Type, FieldInfo[]>(256);
• private static readonly Dictionary<Type, PropertyInfo[]> TypeProperties = new Dictionary<Type, PropertyInfo[]>(256);

MemberInfo is the base class of FieldInfo and PropertyInfo, so you can put them in the RecordableCache with no issues. The capacity for each data type is specified to avoid resizing the internal structures holding the data every now and then, which generates more garbage and has some overhead; this is yet another optimization, albeit smaller.

If we encounter a Type for the first time, after doing all the filtering, we cache what we need in here. Then we can retrieve everything we need next time at no additional runtime cost and without allocating a lot of memory! Here's the one for FieldInfo:

private static FieldInfo[] GetFieldsForType(Type type)
{
    if (TypeFields.TryGetValue(type, out FieldInfo[] fields) == false)
    {
        fields = type.GetFields(RecordBindingFlags);
        fields = CondenseFieldArray(fields);
        TypeFields.Add(type, fields);
    }
    return fields;
}

After these optimizations, the average memory allocation dropped from 600KB all the way down to 24-32 KB, and the solution remains highly scalable. And what's more is we have control over it: we can record every known type in the game at startup and have very little overhead while playing, and if we need to, we can also clear out some of the cache that we know is not going to be needed for certain parts of the game.

Conclusion

Is this the most optimal solution? I wouldn't say it is, but it works extremely well and is scalable without affecting game performance. I could've manually recorded every field/property in specialized structures for each object to improve performance and decrease memory usage. However, that has the drawback of increasing development time since it requires more involved changes. The important thing is to do what works for your game and not fret about doing everything perfectly, since no such thing exists.

I hope you've enjoyed this technical overview of Maze Burrow's undo system, and I hope you learned something from it; I sure did while working on it. You can find the full code here. If you have any questions, feel free to ask in the comments below or through my Twitter, where I regularly post updates to Maze Burrow's progress.

Thanks for reading, and keep at it, game devs!

- Kimimaru