Introduction

We begin with an education example that is easy to understand.  The same method applies to games as well.

Suppose you are designing a curriculum with subjects A, B, C, D, E, and F.  Each subject has 5 levels, level 0 (intro), then 1, 2, 3, and 4.  Suppose also that A is a prerequisite for B, B is a prerequisite for C and so on.  Also, the levels within a subject should be taken in order.  Finally, when A0 is completed, B0 can be taken, then C0.  When A4 is completed, B4 can be taken, and so on.  In what order would the subjects be taught?

One possibility is A0, B0, C0, D0, E0, F0, then A1, B1, C1, D1, and so on.  Another is A0, A1, A2, A3, A4, then B0, B1, B2, and so on.  The first has an advantage over the second in that with the second, a student might have forgotten much of A by the time they get to F.  Not only that, if level 4 requires more “maturity” than level 0, it would be better to have mostly 0s up front and slowly add 1s, then 2s, and so on.  An advantage of the second over the first is that with the first, even though F0 technically can be taken after A0 through E0, we might have a situation where F requires more maturity than A.  So we would want mostly As up front, then Bs, and finally Fs toward the end.

While these are conflicting goals, I’m sure the reader can guess a good compromise is possible: a strategy giving us As near the beginning, Fs near the end, 0s near the beginning, 4s near the end, and the mix is such that maturity is allowed to grow slowly and some As are far enough along that the subject is not forgotten completely.  An additional goal is the strategy shouldn’t be too hard to compute (and it should generalize to more than 6 subjects and 5 levels).

We apply the strategy not only to the original education problem, but to game levels and order of appearance of game enemies, pickups, puzzles, and so on.

Computing the Order, a First Draft

The author would enjoy having a closed-form mathematical expression so that given the nth subject at the ith level, the order in which it is taught is some function f(n,i).  While a simple expression for f might exist, the author has not found it.  The second-best situation is to have an algorithm for computing the sequence, either by hand or computer.  For larger instances of the problem a computer is necessary.  We start with imperfect strategies suitable for hand computation, and then give a more complex strategy requiring a computer but giving better results.

The simpler algorithm can be described as follows: Start with the As.  Use a pencil (or something erasable, like chalk or dry erase markers) to fill in a linear grid.  The first square is A. The second square is A.  Skip one square and the fourth square is A. Skip two squares and the seventh square is A.  Skip 3 squares and the 11^th square is A.  And so on.  The grid (assuming horizontal lines) looks like:

AA_A__A___A…

Now, in a linear grid parallel to this (or the next line of graph paper), pencil in the Bs, one in the first square, one in the second, one in the fourth, and so on, aligned with the As.  Thus, the grid looks like:

AA_A__A___A
BB_B__B___B

Make a parallel grid of Cs as well, then Ds, Es, and finally Fs.  We now have 6 lines, each with a few letters and a lot of spaces:

AA_A__A___A
BB_B__B___B
CC_C__C___C
DD_D__D___D
EE_E__E___E
FF_F__F___F

Now, start moving the second line (the Bs) into the first (the As).   The first B is in the first grid space, and there is already an A there, so try the second space.  There is an A there as well, so try the third.  It is empty so the first line starts out “A A B A _ _ A _ _ _ A”.  This B has been merged into the A line so erase it.

Now take the second B, in the second grid space of the second line.  Again, merge it with the A.  The first space it can go is the fifth grid square of the first line.  So, the first line now starts out “A A B A B _ A _ _ _ A”. 

Continue: for each B in the second line, move it to the first line.  If there is an empty space in the first line above the B, just move it in.  Otherwise, go forward (never backward) till you find an empty space for it.

After moving all the Bs to the first line, start working on the Cs in the same way.  Each C goes in the first empty space of the first line that is at least as far along as it was in the third line.  Do it again for D, then E, then F.

When done, the final result (with level numbers added) will look like:

A0 A1 B0 A2 B1 B2 A3 B3 C0 C1 A4 B4 C2 C3 C4 D0 D1 D2 D3 D4 E0 E1 E2 E3 E4 F0 F1 F2 F3 F4

It’s not perfect, since a lot of Es and Fs are bunched toward the end, but it is a reasonable, computable sequence and the strategy can be applied to any number of subjects and any number of levels.

Note, it’s possible that some “holes” will remain in the grid.  Just ignore them and consider the subjects “adjacent”.

To illustrate, here is the case of 10 subjects and 10 levels:

A0 A1 B0 A2 B1 B2 A3 B3 C0 C1 A4 B4 C2 C3 C4 A5 B5 C5 D0 D1 D2 A6 B6 C6 D3 D4 D5 D6 A7 B7 C7 D7 E0 E1 E2 E3 A8 B8 C8 D8 E4 E5 E6 E7 E8 A9 B9 C9 D9 E9 F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 G0 G1 G2 G3 G4 G5 G6 G7 G8 G9 H0 H1 H2 H3 H4 H5 H6 H7 H8 H9 I0 I1 I2 I3 I4 I5 I6 I7 I8 I9 J0 J1 J2 J3 J4 J5 J6 J7 J8 J9

Again, we have the issue of a lot of Fs, Gs, Hs, Is, and Js together.  Is there a solution?

Refining the Strategy

Initially, the letters were put down in a simple pattern: skip 0, skip 1, skip 2, and so on.  If the sizes of the skips increase faster, the earlier subjects will spread further toward the end.  Specifically, if we have 10 subjects and 10 levels, we would like the last A to be close to around the 90^th grid cell or so (100 cells total, but B through J at the final level must be after the last A).   

Mathematicians may notice that the grid cell occupied by the level n of subject A (with n starting at 0) is n*(n+1)/2 + 1, so the level 0 A goes at 0(1)/2 + 1 or the first cell, level 1 A goes at 1(2)/2 + 1 or the second cell, level 2 A goes at 2(3)/2 + 1 or the 4^th cell, and so on. Thus, the final level 9 A goes at 9(10)/2 + 1 or the 46^th cell, only about half as far as it should go.   We can keep using a quadratic expression, which will make the As start close together and be spaced wider as we go along.  The simplest modification is to drop that denominator of 2: put the level n A at n(n+1) + 1.  Thus, the As will go at positions numbered 1, 3, 7, 13, 21, 31, 43, 57, 73, and 91.  That’s close to the “90” goal.  Then do the same with Bs, etc. and follow the same merging strategy as before.  In practice, there will be more holes left using this scheme, but that does not matter: we collapse the holes.

When we do it this way, we find with 6 subjects and 5 levels, we get

A0 B0 A1 B1 C0 C1 A2 B2 C2 D0 D1 D2 A3 B3 C3 D3 E0 E1 E2 E3 A4 B4 C4 D4 E4 F0 F1 F2 F3 F4

which is an improvement.  With 10 subjects and 10 levels, the sequence becomes:

A0 B0 A1 B1 C0 C1 A2 B2 C2 D0 D1 D2 A3 B3 C3 D3 E0 E1 E2 E3 A4 B4 C4 D4 E4 F0 F1 F2 F3 F4 A5 B5 C5 D5 E5 F5 G0 G1 G2 G3 G4 G5 A6 B6 C6 D6 E6 F6 G6 H0 H1 H2 H3 H4 H5 H6 A7 B7 C7 D7 E7 F7 G7 H7 I0 I1 I2 I3 I4 I5 I6 I7 A8 B8 C8 D8 E8 F8 G8 H8 I8 J0 J1 J2 J3 J4 J5 J6 J7 J8 A9 B9 C9 D9 E9 F9 G9 H9 I9 J9

This is an improvement over what we had before, though there are still a few long sequences of the same subject.

Adding Randomness

We fix the final issue by adding randomness to the mix.  It would be nice at each merging stage to simply select randomly, at each point, which line gets merged with the first line.  However, that would put some subjects out of prerequisite order.  There is a way, but it becomes more difficult to do by hand and a computer becomes almost necessary.  (the previous way is doable by hand, and if you reorder some of the last by hand, that may be good enough for many applications.)

A solution is to make the sequence somewhat random, subject to the prerequisite constraints.  First we build a Directed Acyclic Graph (DAG) whose nodes are subject-level pairs, and we connect a directed edge between two nodes when one is a prerequisite of the other. 

For the DAG we use the following structure:

Then the nodes are just integers.  The incoming dictionary gives, for each target node, the list of source nodes with an edge going from the source to the target.  The outgoing dictionary gives, for each source node, the list of target nodes with an edge going out of the source to the target.

We say that a node X is a prerequisite of node Y if either X and Y have the same subject but X’s level is less than Y’s level, or X and Y have the same level but X’s subject is a prerequisite for Y’s subject.

To build the graph:  

This algorithm will output a list of subject-level pairs such that any such pair is preceded by all its prerequisites, and where possible, the order is randomized.  This is essentially “scheduling using a directed acyclic graph (DAG) and a randomized topological sort” if you wish to google for more information.

For example, I ran this algorithm (in Unity C#) on 10 subjects A through J, 10 levels per subject, and got the following order:

A0 A1 B0 C0 A2 D0 B1 C1 B2 C2 E0 D1 D2 A3 B3 E1 C3 F0 A4 F1 D3 G0 G1 B4 E2 A5 C4 H0 F2 A6 E3 B5 H1 I0 G2 H2 B6 J0 F3 G3 H3 D4 I1 C5 C6 J1 I2 D5 A7 E4 F4 G4 E5 D6 A8 B7 J2 C7 F5 D7 H4 G5 I3 E6 H5 E7 F6 B8 F7 G6 I4 G7 I5 A9 C8 D8 J3 E8 B9 F8 C9 H6 D9 E9 I6 G8 J4 H7 J5 I7 H8 J6 J7 F9 G9 I8 J8 H9 I9 J9

See https://gist.github.com/DeplorableMountaineer/fc384cba79934433a42cc9332c1e8c72 for sample C# code.   This is a MonoBehaviour to be added as a component to a Unity (tested in 2020.2) game object.  It runs in the “OnValidate” event so it will update as you adjust the subject names and number of levels in the Inspector panel. Be careful---use ridiculously large numbers and Unity will crash!

Applications

The obvious application is the one used as an example: a curriculum with many subjects and levels for each subject. 

Another application is game levels.  There may be game levels of type A, B, C, and so on, where B is a little more advanced than A, and so on.  For each type, you start with 0, then 1, then 2, and so on, each getting harder.  So, in what order do you want to have the player play the levels by default? A0 B0 C0….A1 B1 C1…, is a bit repetitive, and A0 A1 A2… B0 B1 B2… is very repetitive.  The random scheme (such as the one just given which yields A0 A1 B0 C0 A2 D0 B1 C1…) is more interesting.

Still another application is placement of things like enemies, pickups, and puzzles.  There could be enemy type A, enemy type B, and so on, of strength 0, 1, 2, and so on.  You would introduce the lower-level enemies first, and higher-level enemies as the game progresses.  This strategy gives us a way to decide on the order the player encounters the enemies.  For example, the random strategy might give:

Minion_00 Minion_01 Minion_02 Minion_03 MinionCaptain_01 Minion_04 Minion_05 MinionCaptain_03 Minion_06 Warrior_02 Minion_07 Minion_08 Minion_09 MinionCaptain_05 Minion_10 Warrior_05 Boss_04 MinionCaptain_07 Minion_11 Overlord_05 Minion_12 MinionCaptain_09 Warrior_08 MinionCaptain_11 Minion_13 MinionCaptain_13 Minion_14 Warrior_11 Minion_15 Minion_16 Boss_09 Minion_17 Minion_18 Warrior_14 MinionCaptain_15 Overlord_10 Minion_19 MinionCaptain_17 Boss_14 Warrior_17 MinionCaptain_19 Overlord_15 Boss_19 Overlord_19 FinalBoss

where some were hand-deleted (as you can see by the level numbers) because there are fewer bosses and even fewer overlords, for example.  Also a single final boss was added.  Note the levels here might not be differences in enemy ability, but simply the nth such enemy to occur (or they could represent how many of that enemy occurs, or perhaps some function of the number of enemies).  An exercise for the reader is to modify the code to allow specifying the number of levels for each enemy class.  (For another exercise, modify the “IsPrerequisite” function from the GitHub Gist above to see how that affects the ordering).

The same is true for pickups of type A, B, C, etc. of size 0, 1, 2, etc.  (size is number of bullets or amount of health or something).  Finally, you can have puzzles of type A, B, C, etc., of difficulty 0, 1, 2, etc.  This way, the player learns as they go when solving puzzles, with a new one thrown in from time to time.

Final Note

It should be no surprise that an educational curriculum planning tool would have game design applications.  There is quite a bit of overlap between game design and course design.  In fact, many universities have departments and programs for combining education with game design.  Check out the description of the MIT Game lab at http://gamelab.mit.edu/ where we see the mission is both education and game creation.  Other universities have similar programs.