Brainstorming with transpose

From Red Blob Games's Blog

Sometimes I get stuck and look for a way to think about a problem a different way. There are some problems that you can view in the form of a matrix/table. The structure looks like this:

There are rows and columns, and I'm trying to work on the cells. Let's try an example from a simple game:

The rows are the character classes: Fighter, Mage, Thief.

The columns are the types of actions: Attack, Defend, Special.

The matrix contains all the code to handle each of these types of actions for each of the types of characters.

What does the code look like? The usual thing to do is to organize this into three modules:

1. Fighter will contain code to handle sword attacks, damage reduction from armor, and slam special attacks.
2. Mage will contain code to handle fireballs, damage reflect, and freeze special attacks.
3. Thief will contain code to handle dagger attacks, damage avoidance from dodge, and disarm special attacks.

Sometimes it's useful to transpose the matrix. I can organize along the other axis:

1. Attack will contain code to handle sword attacks, fireball attacks, and dagger attacks.
2. Defend will contain code to handle damage reduction, damage reflect, and damage avoidance.
3. Special will contain code to handle slam, freeze, and disarm.

I was taught that the one style is "good" and the other style is "bad". But it's not obvious why this should be so. The reason is that there is an assumption that we will often add more character classes (nouns) but rarely add more types of actions (verbs). That way I can add more code with a new module, without touching all the existing ones. It may or may not be true for this game. By looking at the transpose, it makes me aware of the assumption, and I can question it. I'll then think about what kind of flexibility I want, then decide on the code structure.

Let's consider another example.

In programming language implementations, there are different types of nodes corresponding to the primitives: constants, operators, loops, branches, functions, types, etc. I need to generate code for each of these.

Great! I can have one class for each type of node, and they can all derive from a superclass Node. But this is based on the assumption that I will often add more rows and rarely add more columns. What happens in an optimizing compiler? We add more optimization passes. Each one is another column.

If I want to add a new optimization pass, I would need to add a new method to each class, and all the code for an optimization pass is spread out all over the place. This is the situation I was trying to avoid! So some systems will add another layer on top of this. Using "visitors" I can keep all the loop fusion code in one module instead of splitting it up among lots of files.

If I look at the transpose of the matrix, it reveals another approach:

Now instead of classes with methods, I can use tagged unions with pattern matching (not all languages support this). This keeps all the code for each optimization pass together without requiring the indirection of visitors.

It's often useful to look a a problem in terms of a matrix. Applied to the object-oriented structure that everyone thinks about, it might lead me to use something different, such as an entity-component-systems, relational databases, or reactive programming.

It's not just for code. Here's an example of applying the idea to products. Let's suppose there are people with various interests:

If I were designing a social web site, I might let people follow other people. Nick might follow Alice because they're both interested in cars and Feng because they're both interested in travel. But Nick would also get Alice's math posts and Feng's politics posts. If I consider the transpose of this matrix, I might let people follow topics. Nick might join a cars group and also a travel group. Facebook and Reddit started around the same time, but they're transposes of each other. Facebook lets you follow people; Reddit lets you follow topics.

When I get stuck, or when I'm wanting to consider alternatives, I look at the problem to see if there are multiple axes of organization. Sometimes approaching the problem from a different direction can yield a better approach.

Labels: ideas , structure