Brainstorming with factoring

In the last post I described how I sometimes describe a problem with a matrix, and then look at the matrix transpose to see if it gives me new ideas. Another technique I use is to look for a factoring.

In algebra, factoring transforms a polynomial like 5x² + 8x - 21 into (x + 3)·(5x - 7). To solve 5x² + 8x - 21 = 0, we can first factor into (x + 3)·(5x - 7) = 0. Then we say that x + 3 = 0 or 5x - 7 = 0. Factoring turns a problem into several easier problems.

	x	3
5x	5x²	15x
-7	-7x	-21

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

	Uncompressed	Gzip	Bzip
Unencrypted	File	Gzip(File)	Bzip(File)
Encrypted	Encrypt(File)	Encrypt(Gzip(File))	Encrypt(Bzip(File))

Using the Decorator pattern (or mixins), I've turned six different types of files into four components: plain, gzip, bzip, encrypt. This doesn't seem like much savings, but if I add more variations, the savings will add up. Factoring turns O(M*N) components into O(M+N) components.

Another example comes up when people ask me things like “how do you write linear interpolation in C#?” There are a lot of potential tutorials I could write:

	C++	Python	Java	C#	Javascript	Rust	Idris	…
Interpolation
Neighbors
Pathfinding
Distances
River maps
Isometric
Voronoi
Transforms
…

If there are M topics and N languages, I could write M*N tutorials. However, that's a lot of work. Instead, I write a tutorial about interpolation, someone else writes a tutorial about C#, and then the reader combines knowledge of C# with knowledge about interpolation to write the C# version of interpolation.

Like transpose, factoring only helps sometimes, but when it applies, it can be quite useful.

Read More

Brainstorming with transpose

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:

	A	B	C	D	E
1	A1	B1	C1	D1	E1
2	A2	B2	C2	D2	E2
3	A3	B3	C3	D3	E3
4	A4	B4	C4	D4	E4
5	A5	B5	C5	D5	E5

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

	Attack	Defend	Special
Fighter	sword	armor	slam
Mage	fireball	reflect	freeze
Thief	dagger	dodge	disarm

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:

	Fighter	Mage	Thief
Attack	sword	fireball	dagger
Defend	armor	reflect	dodge
Special	slam	freeze	disarm

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.

	Generate Code
Constant
Operator
Loop
Branch
Function
Type

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.

	Generate Code	Data flow	Constant folding	Loop fusion	…
Constant
Operator
Loop
Branch
Function
Type

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:

	Constant	Operator	Loop	Branch	Function	Type
Generate code
Data flow
Constant folding
SSA
Loop fusion

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:

	Nick	Feng	Sayid	Alice
cars	X			X
politics		X	X
math			X	X
travel	X	X

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.

Read More

White Paper Games launch 'The Occupation.

HAPPY LAUNCH DAY to our Alumni and all at White Paper Games! 

“The Occupation is a first-person, fixed-time, investigative thriller set in North West England on 24th October 1987. You play as a journalist in a detailed, systems-driven world where people react to your actions and time is your biggest enemy.”

For more info:

Huge CONGRATULATIONS.

Read More

Improving hexagon map storage diagram

Last week, I decided to improve the map storage section of the hexagon guide. This section had a diagram that suggested the use of a 2D array, but then it presented formulas that didn't look like what was shown. Reader feedback made me realize this section was confusing. I was mixing two separate steps here.

1. Store the map in a 2D array.


2. Slide the rows to the left to save space.

Hexagon map storage: grid, and also slide left

The diagram showed step 1 but not step 2. The formula under the visualization showed step 2. Mismatch!

I think it's worth having two separate diagrams here. I couldn't figure out where to place the second diagram in the page layout, so I decided to instead make the one diagram animate between the two different approaches.

Hexagon map storage: slide and resize rows

One of the advantages of writing text over making videos is that I can treat it as a "living document" that improves over time. The improvements are less frequent the longer the document has been around, but I am still updating the pages I wrote in the 1990s, and I intend to continue improving the new ones too.

Read More

Improving island shaping for map generation

One of my goals for 2019 is to improve my existing pages. This week I improved the island map section of my noise-based map generation page.

Island map generation: you figure it out

I had offered lots of options: additive vs multiplicative, Euclidean vs Manhattan distance, and three mysterious parameters named a, b, c. It was simple for me to offer lots of options. The problem with lots of options is that there's a large “possibility space” to explore. You may or may not find something you like.

Based on feedback from readers, I decided to rewrite this section. I stepped back and thought about why we're adding and multiplying. What is the goal? How does it work?

1. Push the edges of the map down into water. I need to decrease elevations near the edges.


2. Push the middle of the map up onto land. I need to increase elevations near the middle.

The main idea is to start with noise-based elevation and reshape it into what we want. The noise-based elevation fits into a box , and we reshape the box into something like . The contents of the box, whatever terrain had been generated, will get pushed up and down when the box is changed.

I rewrote the entire section of the page to explain this idea, and I ended up removing the interactive diagram.

Island map generation: explain the main ideas

Related: Why Minimal Guidance During Instruction Does Not Work says that experts can use the interactive exploration to navigate the possibility space because they have already built up the intuition to know where to go. Novices on the other hand learn better with guidance.

Read More

Visit by Head of Games Design at TT-Games - Arthur Parsons

We are very lucky to welcome Arthur Parsons to our Games Design studio at UCLan this week.
Arthur is Head of Games Design at TT_Games and as such, it's so amazing that he takes time to visit our course and speak directly and openly with our students.
Arthur gave a great presentation about the criteria involved in designing and making a Lego game and offering a broad insight into the workings of the industry in terms of producing and marketing a game.
It's great to have the chance to speak with experienced industry experts such as Arthur.
His warmth and enthusiasm always motivate our students so much and encourage them to work hard and develop their passion for games design.

 

Read More

Visit to Uclan Games Design by Joe Nelson

UCLan Games Design students were delighted to welcome an important visitor from the games industry to their studio this week.

Namely, a fantastic opportunity to hear from Joe Nelson, Game Director at Ninja Theory on the 5-time BAFTA-winning "Hellblade: Senua’s Sacrifice". Joe studied Game Design at UCLAN in Preston so we are particularly proud of his achievements.

Joe Nelson is a game director at Ninja Theory, having been design lead on Senua’s Sacrifice" and previously working on both level and system designs.

His presentation described how to develop a plan for your game design to maintain a feasible story and authentic feel throughout the project. Joe's talk was a unique and fascinating insight into the depths of research and design planning that go into a game such as HellBlade.

It was great to welcome Joe back to the course in his capacity as a Games Director.

Read More