[Bug Fix] Circular References and Serialization

circularReferences5

There was a problem that I recently encountered while writing a plugin for RPGMaker MV, and thinking about it a little further, is something that authors of serialization libraries may need to consider if they haven’t already.

Background

In RPGMaker MV, save files are managed by serializing all of the game data to a JSON string, and then storing that as a blob somewhere such as a local file, your browser’s local storage, or somewhere in the cloud.

The issue I ran into was related to saving a game: when I opened my save menu in-game and tried to save my progress, it would simply play an error sound and nothing happened.

Which was strange: I wrote a plugin that implemented a way to manage inventories, and everything worked in-game. However, once I tried to save, it simply wouldn’t save.

What was happening?

Identifying the Issue

RPG Maker MV prints out a stacktrace whenever it runs into an exception. In the case of saving, if it fails to save, it would still print out an exception, but it handles the exception so that the game doesn’t crash.

The error message was

Object too deep

Which is not very useful.

When I followed the stack trace, I noticed notice that it was recursively calling itself while attempting to serialize my objects to create the save data.

circularReferences2

What I found out was that “circular object references” are not handled properly during the JSON serialization process.

What is Serialization?

Basically, serialization is the process of converting an object into a stream of bytes. It is used as a way of communicating with other applications or media that may not understand how to work with your data.

For example, a simple text file is unable to store a Javascript object that is currently in memory; instead, you have to convert it into a format that the file knows how to handle, such as a string.

There are many different serialization methods. One standard serialization format is Javascript Object Notation, or JSON.

So in the case of saving game progress in RPGMaker MV, the engine provides you with a method that will turn your objects into a JSON string, and then another method that will turn a JSON string back into your object.

What is a Circular Object Reference?

Let’s say you had two objects A and B.

A is the parent of B, and A holds a reference to B as its child.
B is the child of A, and B holds a reference to A as its parent.

Here’s some Javascript that describes what I mean

var a = {}
var b = {}
a.child = b;
b.parent = a;

This is a circular object reference: A refers to B through the `child` property, and B refers to A through the `parent` property. Here is an illustration of what the above code looks like:

circularReferences3

This type of structure allows you to ask the following questions, and receive an answer immediately:

A – who is your child?
B – who is your parent?

In general, you can have any number of objects whose references form a cycle at some point. If you had three objects A, B, and C, you might have

A points to B, and
B points to C, and
C points to A

If you were to follow the relationships, you’ll find yourself stuck in a loop.

Circular References and Serialization

That loop is exactly the problem that serialization faces.

In order to fully capture all of an object’s properties, a serialization routine might simply recursively iterate all of the object’s properties and convert each property into a string.

Now, what happens when you attempt to recursively iterate through a cycle? Let’s take a look at the example of the A and B parent-child relationship.

  1. When you attempt to serialize A, you want to keep this parent-child relationship intact. So you would go ahead and say that the child of A is B.
  2. Now, you must serialize B. Again, you want to keep this parent-child relationship intact, so you would go and say that the parent of B is A.

At this point, we have serialized A and B. Can we say that we are finished?

Not exactly. When you say that the parent of B is A, how would you serialize that?

If we were to use the same “iterate all properties recursively and serialize it” logic, you would need to serialize A again, because it is a property of B.

We are back to step #1, and there’s no way out with our current approach.

Can’t We Just Remove the Cycle?

So the problem with serialization, when it comes to circular references, is the possibility that you would run yourself into a loop and never be able to escape.

One solution, of course, is to never have circular references. Easy enough: if there’s a problem with something, get rid of it.

However, there may be situations where it would be “nice” to have this kind of structure in your code.

A real-world example: If you wanted to know who is B’s parent, you could go to every human in the world and ask “is this your child?”

Perhaps one of them will say yes. You’d be lucky if one of the first hundred people you asked said yes.

However, it would be much more efficient to start by asking the child who its parent is, and then perhaps go and verify it with the parent in question. In the worst case, the child might have gotten the parent wrong, and you’d still have to go and ask every human in the world, but it’s something that I would likely try as my first solution.

Breaking Out of the Cycle

Remember the two steps I outlined when serializing A:

  1. Serialize A, and then serialize its child B.
  2. Serialize B, and then serialize its parent A

If we continue without performing any checks to see if we’re in a cycle or not, the computer will just loop forever. However, if there was a way to actually break out of the cycle, then we should be fine.

One thing that you will notice is that A has already been serialized before, so couldn’t we just somehow tell the serializer to point to the same A from before?

circularReferences4

Maybe we can just have a special identifier that says “use this other object that we saw earlier”.

If so, then our cycle problem should be solved, because if we avoid serializing the same object again, then we avoid the cycle problem.

Solution for RPG Maker MV

For RPG Maker MV’s JSON serialization, we have a solution presented by Hudell: Orange Circular JSON, which is based on the Circular JSON library by WebReflection.

This plugin allows developers to simply install it into their project, and it will improve the way JSON serialization is performed so that it will check for cycles, thus solving the circular reference problem.

Summary

Circular object references are valid structures in programming. If you need to serialize your objects, which may contain circular references, you would have to handle it in your serialization routines.

The actual implementation would be up to you depending on what you are doing, but the general idea in this solution is to simply introduce a particular identifier which you may assign to each object so that you can refer to them later on.

Happy coding!

You may also like...

12 Responses

  1. TheChilliPL says:

    How to add custom data to object, because I want to save data from my plugin…

    • Hime says:

      You can assign the data to any object that already gets saved (because those objects are deep cloned), or make sure that the save/load methods are updated to handle your custom data as well.

Leave a Reply

Your email address will not be published. Required fields are marked *