Brainstorm: how to look at tasks from a different angle

Brainstorming with transposition

Sometimes I get stuck and have to look for ways to think about the task from a different angle. There are tasks that can be displayed in the form of a matrix or table. Their structure looks something like this:


The cells I'm working with are arranged in columns and rows. Let's take an example from a simple game:


Lines are character classes: warrior, mage, thief.

Columns are types of actions: attack, defense, special action.

The matrix contains all the code for processing each of the types of actions for each type of character.

What does the code look like? Typically, such structures are organized into such modules:

1. Fighter will contain a code for handling sword strikes, reducing damage with armor and a special powerful blow.
2. Mage will contain a code for handling fireballs, reflection of damage and a special attack by freezing.
3. Thief will contain a code to handle dagger attacks, avoid dodge damage and a special disarming attack.

It is sometimes useful to transpose the matrix. We can arrange it on another axis:

1. Attack will contain the code for handling swings, fireballs and dagger attacks.
2. Defend will contain a code for handling damage reduction, reflection of damage and escape from damage.
3. Special will contain a powerful strike, freeze and disarm code.

I was taught that one style is "good" and the other is "bad." But it’s not obvious to me why everything should be that way. The reason is the assumption that we will often add new classes of characters (nouns), and rarely add new types of actions (verbs). This way I can add code using the new module without touching all available ones. In your game, everything can be different. Looking at the transposed matrix, I am aware of the existence of the assumption and can cast doubt on it. Then I will think about the type of flexibility I need, and only then I will choose the code structure.

Let's look at another example.

Interpretations of programming languages ​​have various types of nodes corresponding to primitives: constants, operators, loops, branching, functions, types, etc. We need to generate code for them all.


Excellent! You can create one class for each node type, and they can all inherit from the base class Node. But we rely on the assumption that we will add rows and less often columns. What happens in the optimizing compiler? We are adding new optimization passes. And each of them is a new column.


If I want to add a new optimization pass, then I will need to add a new method to each class, and all the optimization pass code will be distributed into different modules. I want to avoid such a situation! Therefore, in some systems, another layer is added on top of this. Using the visitor pattern, I can store all the code for merging loops in one module, rather than breaking it into multiple files.

If you look at the transposed matrix, we will open another approach:


Now, instead of classes with methods, I can use tagged union and pattern matching (they are not supported in all programming languages). Due to this, the entire code of each optimization pass will be stored together and can do without the indirectness of the visitor pattern.

It is often useful to look at the problem from the point of view of the matrix. If you apply it to an object-oriented structure that everyone thinks about, it can lead me to something else, for example, to the pattern “entity-component-system”, relational databases, or reactive programming.

And this applies not only to the code. Here is an example of applying this idea to products. Suppose there are people with different interests:


If I were developing a social networking site, I could allow people to follow other people's news . Nick can sign up for Alice, because they are both interested in cars, and on Fenya, because they are both interested in traveling. But Nick will also receive Alice's posts on mathematics and Fenya's posts on politics. If I were considering a transposed matrix, I could allow people to subscribe to topics . Nick could join a group of car lovers, as well as a group of travelers. Facebook and Reddit began around the same time, but they are transposed matrices of each other. Facebook allows you to follow people; Reddit allows you to subscribe to topics.

When I come to a standstill or when I want to consider alternatives, I look at the problem and look for different ordering axes in it. Sometimes looking at a problem from a different angle can provide a better solution.

Decomposition Brainstorming

I use another technique called decomposition.

In algebra, the decomposition operation transforms a polynomial of the form 5x² + 8x - 21 into (x + 3) · (5x - 7). To solve the equation 5x² + 8x - 21 = 0, we can first factor it into (x + 3) · (5x - 7) = 0. Then we can say that x + 3 = 0 or 5x - 7 = 0. Expansion turns a difficult task into a few easier tasks.


Let's look at an example: I have six classes: File, EncryptedFile, GzipFile, EncryptedGzipFile, BzipFile, EncryptedBzipFile. I can decompose them into a matrix:


Using the “decorator” pattern (or impurities), I turned six different types of files into four components: plain, gzip, bzip, encrypt. This does not seem to save much, but if I add more variations, the savings will increase. Decomposition turns O (M * N) components into O (M + N) components.

Another example: sometimes people ask me questions like “how to write linear interpolation in C #?” . I can write many potential tutorials:


If there are M topics and N languages, then I can write M * N tutorials. However, this is a lot of work. Instead, I will write a tutorial on interpolation , someone else will write a tutorial about C #, and then the reader will combine the knowledge of C # with the knowledge of interpolation, and write their version of interpolation in C #.

Like transposition, decomposition does not always help, but if applicable, it can be quite useful.

Backward brainstorming

In the previous two parts, I talked about how I sometimes approach the task, trying to arrange it into a matrix. Sometimes this does not help and then I try to look at the task in the opposite direction. Let's take a look at procedural map generation, for example. Often I start with a noise function, then add octaves, adjust parameters, and add layers. I do this because I need cards that have certain properties.


It is quite possible to start with experiments with parameters, but the parameter space is quite large, and it is not known whether I will find the parameters that are most suitable for my requirements. Therefore, having experimented a little, I stop and start thinking in the reverse order: if I can describe what I need, then this can help in finding the parameters.

It was this motivation that made me study algebra. If we have an equation of the form 5x² + 8x - 21 = 0 , then what will be x ? When I did not know algebra, I would solve this equation, trying to substitute different values ​​of x, first choosing them randomly, and then adjusting them when I feel that I’ve got close to the solution. Algebra gives us a tool to go in a different direction. Instead of guessing the answers, she gives me an apparatus (decomposition, or quadratic equations, or the Newtonian method of iterative search for roots), which I can more consciously use to search for x values (-3 or 7/5).

I feel like I often get into this kind of programming situation. While working on the generation of procedural maps, after experimenting with the parameters for some time, I stopped and compiled a list of what should be in the game worlds of one project :

1. Players must start the game far from the coast.
2. When leveling up, players must climb uphill.
3. Players should not be able to reach the edge of the map.
4. As the level grows, players must join in groups.
5. There should be simple monsters on the coasts without much variation.
6. On the plains there should be a wide variety of monsters of medium difficulty.
7. In mountainous areas there must be complex boss monsters.
8. There must be some kind of landmark that allows players to remain at the same level of difficulty, and another landmark that allows you to rise or fall in the level of difficulty.

The compilation of this list led to the creation of the following restrictions:

1. Game worlds should be islands with many coasts and a small peak in the center.
2. Altitude should correspond to the complexity of monsters.
3. At low and high altitudes, there should be less variability of biomes than at medium altitudes.
4. Roads should remain at the same level of difficulty.
5. Rivers should flow from large to small heights, and provide players with the ability to move up / down.

These limitations led me to design a map generator. And he led to the generation of a much better set of cards than those that I received by adjusting the parameters, as I usually do. And the resulting article interested many people in creating maps based on Voronoi diagrams.

Unit tests are another example. It is suggested that I should come up with a list of examples to test. For example, for grids of hexagons, I might think that I need to check a condition add(Hex(1, 2), Hex(3, 4)) == Hex(4, 6). Then I remember that you need to check the zeros: add(Hex(0, 1), Hex(7, 9)) == Hex(7, 10). Then I can think of is that it is necessary to check and negative values: add(Hex(-3, 4) + Hex(7, -8)) == Hex(4, -4). Well, great, I have a few unit tests.

But if you think a little further, then in factI check add(Hex(A, B), Hex(C, D)) == Hex(A+C, B+D). I came up with the three examples shown above based on this general rule. I am going in the opposite direction from this rule in order to come to unit tests. If I can directly encode this rule into a test system, then the system itself will be able to work in reverse order to create examples for testing. This is called property-based testing. (See also: metamorphic testing )

Another example: constraint solvers. In such systems, the user describes what he wants to see in the output, and the system finds a way to satisfy these constraints. Quote from the Procedural Content Generation Book, chapter 8 :

Using the constructive methods from Chapter 3, as well as the fractal and noise methods from Chapter 4, we can create various types of output data by tuning the algorithms until we are satisfied with their output data. But if we know what properties the generated content should have, it will be more convenient to directly indicate what we want the general algorithm to find content that meets our criteria.

This book describes programming of answer sets (ASP), in which we describe the structure of what we work with (tiles are floor and walls, tiles border each other), the structure of the solutions we are looking for (a dungeon is a group connected tiles with the beginning and the end) and the properties of the solutions (side passages should contain no more than 5 rooms, there should be 1-2 loops in the maze, three assistants must be defeated before reaching the boss). After that, the system creates possible solutions and allows you to decide what to do with them.

Recently, a constraint solver was developed, which caused great interest due to its cool name and curious demo: Wave Function Collapse. [About this solver there is an article on Habr.]If you give him example images to tell him what restrictions are imposed on neighboring tiles, he will create new examples that match the given patterns. His work is described in WaveFunctionCollapse is Constraint Solving in the Wild :

WFC implements a greedy search method without going back. This article explores WFC as an example of constraint-based decision methods.

I have already achieved a lot with the help of constraint solvers. As with algebra, before I learn how to use them effectively, I need to learn a lot.

Another example: the spaceship I created . The player can drag engines anywhere, and the system will determine which engines need to be activated when you click on W, A, S, D, Q, E. For example, in this ship:


If you want to fly forward, then include two rear engines. If you want to turn left, then turn on the right rear and left front engines. I tried looking for a solution, forcing the system to iterate over a lot of parameters :


The system worked, but not perfect. Later I realized that this is another example of where the solution in the opposite direction could help. It turned out that the movement of spacecraft can be described by a linear system of restrictions . If I understood this, I could use a ready-made library that accurately solves the constraints, and not my trial and error method, which returns an approximation.

And another example: the G9.js project, in which you can drag the output of a certain function on the screen , and it determines how to change the input data to match the desired output data. G9.js demos look great! Be sure to uncomment the “uncomment the following line” line in the Rings demo.

It is sometimes useful to think of a task in the reverse order. It often turns out that this gives me better solutions than with direct reasoning.