Brainstorming: how to look at tasks from a different angle

Brainstorming using transposition

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


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


Lines are classes of characters: warrior, mage, thief.
')
Columns are types of actions: attack, defense, special action.

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

What does the code look like? Usually such structures are ordered into such modules:

1. Fighter will contain code to handle sword strikes, damage reduction with armor and a special powerful strike.
2. Mage will contain fireball handling code, damage reflections, and a special freeze attack.
3. Thief will contain code to handle dagger attacks, avoid evasion damage, and a special disarming attack.

Sometimes it is useful to transpose the matrix. We can arrange it on a different axis. :

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

I was taught that one style is “good” and the other “bad.” But it is not obvious to me why everything should be like this. The reason is the assumption that we will more often add new classes of characters (nouns), and rarely add new types of actions (verbs). This way I can add code with the help of the new module, without touching all the existing ones. In your game, everything can be different. Looking at the transposed matrix, I am aware of the existence of an assumption and I can call it into question. Then I will think about the kind of flexibility I need, and only then I will choose the structure of the code.

Let's take another example.

In interpretations of programming languages ​​there are various types of nodes that correspond to primitives: constants, operators, cycles, branching, functions, types, etc. We need to generate code for all of them.


Fine! You can create one class for each type of node, and they can all inherit from the base class Node . But we are based on the assumption that we will add more rows and less often columns. What happens in the optimizing compiler? We add 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 the entire optimization pass code will be posted to different modules. I want to avoid this situation! Therefore, in some systems, another layer is added on top of this. With the help of the “visitor” pattern (visitor), I can store all the loop merge code in one module, and not split it into multiple files.

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


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 will be able to 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, then it can lead me to something else, for example, to an entity-component-system pattern, relational data bases, or reactive programming.

And this concerns not only the code. Here is an example of applying this idea to products. Suppose that 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 subscribe to Alice because they are both interested in cars, and 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 considered a transposed matrix, I could allow people to subscribe to topics . Nick could join a group of car enthusiasts, as well as a group of travelers. Facebook and Reddit started their existence at about the same time, but they are transposed matrices of each other. Facebook allows you to subscribe to people; Reddit allows you to subscribe to topics.

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

Brainstorming with decomposition

I use another technique called “decomposition”.

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


Let's take a 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 file types into four components: plain, gzip, bzip, encrypt. This does not seem to allow us to save much, but if I add more variations, the savings will increase. Decomposition converts O (M * N) components to 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 themes and N languages, then I can write M * N tutorials. However, this is a lot of work. Instead, I will write an interpolation tutorial, someone else will write a C # tutorial, and then the reader will combine C # knowledge with interpolation knowledge, and write his own interpolation version in C #.

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

Brainstorming in the opposite direction

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


It is quite possible to begin with experiments with parameters, but the parameter space is quite large, and it is not known whether I will find the parameters that best fit my requirements. Therefore, after experimenting a little, I stop and start thinking in reverse order: if I can describe what I need, it can help in finding the parameters.

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

I feel that I often get into this situation in programming. When working on the generation of procedural maps, I experimented with the parameters for some time, I stopped and made a list of what should be in the game worlds of one project :

1. Players must start the game far from shore.
2. When leveling up players must rise from the mountain.
3. Players should not be able to reach the edge of the card.
4. With increasing levels of players must be combined into groups.
5. On the coasts should be simple monsters without much variability.
6. There should be a large variety of medium difficulty monsters on the plains.
7. In mountainous terrain must be difficult monsters, bosses.
8. There must be some kind of guideline that allows players to remain on the same level of difficulty, and another guideline that allows you to rise or fall in the level of difficulty.

Compiling this list led to the following restrictions:

1. Game worlds should be islands with many coasts and a small peak in the center.
2. The altitude must match the complexity of the monsters.
3. At low and high altitudes there should be less variability of biomes than at medium altitudes.
4. Roads must remain on the same level of difficulty.
5. Rivers must flow from high to low altitude and allow players to move up / down.

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

Another example is unit tests. It is assumed that I should come up with a list of examples for verification. For example, for hexagonal meshes, I might think that I need to check the condition add(Hex(1, 2), Hex(3, 4)) == Hex(4, 6) . Then I can remember that you need to check the zeros: add(Hex(0, 1), Hex(7, 9)) == Hex(7, 10) . Then I can remember that you need to check and negative values: add(Hex(-3, 4) + Hex(7, -8)) == Hex(4, -4) . Well, great, I have several unit tests.

But if I think a little further, then in fact I 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 backwards from this rule in order to arrive at unit tests. If I can directly code this rule into a test system, then the system itself can work in reverse order to create examples for testing. This is called "property-based testing". (See also: metamorphic testing )

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

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

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

Recently, a constraint solver was developed, which aroused 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 sample images to tell you what restrictions are placed on neighboring tiles, he will create new examples that match the specified patterns. His work is described in the article WaveFunctionCollapse is Constraint Solving in the Wild :

WFC implements a greedy search method without going back. In this article, the WFC is explored as an example of decision methods, subject to constraints.

I have already achieved a lot with the help of restrictions. As in the case of algebra, before I learn to use them effectively, I need to learn a lot.

Another example: the spacecraft 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 turn on the two rear engines. If you want to turn left, then turn on the right rear and left front engines. I tried to look for a solution, forcing the system to go through many parameters :


The system worked, but not perfectly. Later, I realized that this is another example of where the solution could help in the opposite direction. 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 exactly resolves the constraints, and not my own trial and error method, which returns an approximation.

And one more example: the G9.js project, in which you can drag the output data of a certain function around the screen, and it determines how to modify the input data to fit the desired output data. G9.js demos look great! Be sure to uncomment the "uncomment the following line" line in the Rings demo.

Sometimes it is useful to think about the task in reverse order. It often turns out that this gives me better solutions than with reasoning in the forward direction.