Solving Continuity Levels with Dijkstra’s Shortest Path

This post is probably off-topic for this blog, but it is the only blog I use, so enjoy. (By the way, WordPress editor still greatly annoys me and so does this theme’s style. I’m going to have to fix the CSS eventually).

Continuity is a new Flash game that I was playing recently. It combines platforming and puzzle in a novel way – your character must jump from platform to platform collecting keys to open a door, but must do so inside mini-levels (squares). The macro-game is essentially an 8-puzzle (8 pieces in a 3×3 square grid), where you shift the puzzle pieces using the one empty space, such that your character can succeed in the mini-levels.

This game is perfectly solvable through logic and working backwards, though for some of the harder levels you need to keep a long memory of steps. In short, I became bored and impatient of solving the puzzles in my head, and decided after ~30 levels, it’d be more interesting to automate it by writing a solver.

I also took this opportunity to get familiar with Python, a language well known for its fast prototyping and easy learning curve. I have only worked in Python once, during a 4-month internship 4 years ago, but otherwise, my main skills are in C and Java. However the syntax required to write good algorithms and data structures in these “classic” languages can get quite long and annoying. So I coded up a Python script to solve the final two levels.

The rest of this post details how to develop the solution. The solution is relatively simple because we can just treat each exit in a square as a point in a directed graph, where each edge in the graph A->B specifies that point B is reachable from point A, and then apply a search algorithm through the graph. I chose Dijkstra’s shortest path algorithm, which runs fast and finds the best (shortest) solution. However, my program did require a lot of manual data entering to specify the paths/exits in each puzzle piece, so it wasn’t fully automatic. Perhaps Python has some magic that could automate this :). Lastly, I skipped solving the 8-puzzle, since it’s not necessary.

The Basics

First some notation. I will number the squares (from 1-n). In this game, your character can only move between two squares if the sides match exactly. So, for each square, I will classify its sides with a letter. Two sides that can connect to each other will have the same letter, but different case (e.g. side X connects to side x).  Top and left sides will use capital letters; bottom and right sides use lower case. We will label each opening in an side A as A1, A2, A3, etc… in order from top to bottom or left to right.

I will use Level 31 in Continuity as an example. I have labelled this level in the below image. The labels just make it easier for a human to follow (and to input).

In this level, there are 7 types of sides with these openings:

In Python:

numOpenings = {'a':2, 'b':2, 'c':2, 'z':2, 'y':2, 'x':0, 'w':1}

The following are the sides that each square possesses. Also noted the special points and their related openings:

Square	Sides	Notes
1:	A, b, Z, z
2:	B, b, Y, y	<Keys: b2>
3:	B, a, W, w
4:	C, a, Z, y
5:	A, a, W, z	<Start: A1, a1, W1>
6:	A, b, Z, z	<Finish: Z2>
7:	B, c, Y, x
8:	C, b, Z, w	Keys: b1, (Z1 or Z2)

In my code, I simply use strings to store the sides per square, since they are easy to deal with:

sqEdges = ["AbZz", "BbYy", "BaWw", "CaZy", "AaWz", "AbZz", "BcYx", "CbZw"]

Setting up the Graph Data

Construct a directed graph of connected points. There is a connection (edge) from p1 -> p2 if you can get from p1 to p2. That does not imply you can get from p2 -> p1 because of game physics (jumping and gravity), so this is a directed graph.

First, inter-square connections (between different squares).

It is simple to see that any 2 squares can be placed adjacent to each other in whichever way desirable. We just assume that any such move is equally easy to do, with weight 1. (Because it really is easy!)

All matching sides can be connected to each other, with the exception of top and bottom sides, where the connection is one-way (top to bottom). So we can infer all inter-square connections from the square->sides table above, using a loop:

Secondly, find the intra-square connections (within same square).

Unfortunately, the only way to do this is inspect each square to see if it is possible to reach the opening via jumping inside the square alone. This was easily the longest (and most error-prone) part of the process. I won’t even list them all here because the list is so long.

Finally, connections from special points to openings.

Ah, these are the keys and doors in the game. Yes, there is still a game here ;-).

Most of the time, extra points are not necessary. Most keys or doors can only be reached by one opening, so just use that point. For starting point, just pick the closest opening. If a key or door can be reached by more than one opening, we will create an extra point with connections. For example, in this level, ‘key2’ is the only extra point:

and the others we can just alias to existing points:

Solving the Path!

Now we need to find a path that collects all keys and reaches the goal (door). The order of which keys to collect does not matter. Let’s just pick an arbitrary order of key collecting. Then find a path from <Start> to <key1> … <keyN> to <Finish>. Call these the checkpoints.

One solution is to run some search algorithm from each checkpoint to the next, then concatenate the paths together. We could use common search algorithms (DFS, BFS) to traverse though the nodes until we find the goal. DFS backtracks when it reaches a dead end, while BFS searches all paths in parallel, one step at a time.

A better way is to run a global shortest path algorithm, that finds shortest path from one point to every other point, such as Dijkstra’s algorithm. This algorithm is nice, because it only needs to check each node once, not doing any actual traversal. A bonus: We can select whichever order of collecting keys that gives the shortest total path. We can also give weights to the edges (e.g. I used cost = 1 to travel inside a square, but cost=10 to go between squares).

This does not take into account how many moves are required in the macro puzzle to shuffle the squares around to make the desired connection. Assigning a weight to each inter-square connection equal to number of “shuffles” might work, except this number depends on the previous arrangement of squares. Thus we would have to track the state of the macro puzzle with each step in a DFS or BFS search, and the weight would only be valid for that state; we’d have to recompute at each new state. Not only that, but DFS/BFS are not well-suited for weighted search. It wouldn’t work at all using the Dijkstra’s shortest path method, since that relies on global costs of each path that are known beforehand to be unchanging.

In any case, that is enough, because shifting two squares next to each other is extremely easy.

Coding

Here is the best part about Python. It is extremely easy to go from pseudo-code of a Dijkstra’s algorithm to Python code, thanks to its built in list and dictionary types and short syntax.

I used some object-oriented features (to encapsulate squares, each which hold a list of its points, each point holds an adjacency list of connected points), or you can go C-style and use global list variables like you would arrays. In fact, I ended up with a mix of both styles.

The Final Solution

Level 31

Here are the results for Level 31. I grabbed a permutation function off the Internet that was only 7 lines (wow!), and so found all the solutions for each different order of collecting the 3 keys. This was the shortest one:

###############
Solving for Permutation 6 of key collecting order:
-------------------
Finding shortest path from Sq 5-A1 (left top) to Sq 8-b1 (right top).
Sq 5-A1 (left top)
Sq 4-a1 (right top)
Sq 4-y1 (bottom left)
Sq 2-Y1 (top left)
Sq 2-B1 (left top)
Sq 8-b1 (right top)
Distance is 32
Finding shortest path from Sq 8-b1 (right top) to Sq 2-b2 (right bottom).
Sq 8-b1 (right top)
Sq 3-B1 (left top)
Sq 3-B2 (left bottom)
Sq 2-b2 (right bottom)
Distance is 21
Finding shortest path from Sq 2-b2 (right bottom) to key2.
Sq 2-b2 (right bottom)
Sq 7-B2 (left bottom)
Sq 8-b2 (right bottom)
Sq 8-w1 (bottom )
Sq 3-W1 (top )
Sq 3-a2 (right bottom)
Sq 1-A2 (left bottom)
Sq 1-z1 (bottom left)
Sq 8-Z1 (top left)
key2
Distance is 54
Finding shortest path from key2 to Sq 6-Z2 (top right).
key2
Sq 8-w1 (bottom )
Sq 3-W1 (top )
Sq 3-a2 (right bottom)
Sq 1-A2 (left bottom)
Sq 5-a2 (right bottom)
Sq 5-z2 (bottom right)
Sq 6-Z2 (top right)
Distance is 43
Total Distance is 150

Level 31 again, for cross-reference.

Level 32

As a bonus, here is the best solution for Level 32 using the same technique. Being the last level, the difficulty is higher, and you can see because of the very few common sides between squares. Four of the sides do not even have a corresponding match (A, F, h, i). But it could be worse — at least all the bottom sides have some square to fall into! For this level, the shortest path for the best permutation of key collecting had distance 143 and the worst was 283. So that’s about half. Bet your Youtube video walkthrough didn’t have that information ;-).

###############

Solving for Permutation 3 of key collecting order:
-------------------
Finding shortest path from Sq5 Central Area to Sq 2-V3 (top right).
Sq5 Central Area
Sq 5-d2 (right bottom)
Sq 4-D2 (left bottom)
Sq 1-d2 (right bottom)
Sq 1-v3 (bottom right)
Sq 2-V3 (top right)
Distance is 32
Finding shortest path from Sq 2-V3 (top right) to Sq 7-w1 (bottom ).
Sq 2-V3 (top right)
Sq 2-x3 (bottom right)
Sq 6-X3 (top right)
Sq 6-c1 (right top)
Sq 3-C1 (left top)
Sq 3-W1 (top )
Sq 7-w1 (bottom )
Distance is 33
Finding shortest path from Sq 7-w1 (bottom ) to Sq 2-B1 (left top).
Sq 7-w1 (bottom )
Sq 3-W1 (top )
Sq 3-g1 (right top)
Sq 7-G1 (left top)
Sq 7-U1 (top left)
Sq 6-u1 (bottom left)
Sq 1-U1 (top left)
Sq 1-A1 (left top)
Sq 1-A2 (left bottom)
Sq 1-v1 (bottom left)
Sq 2-V1 (top left)
Sq 2-B1 (left top)
Distance is 56
Finding shortest path from Sq 2-B1 (left top) to Sq 2-b1 (right top).
Sq 2-B1 (left top)
Sq 2-x1 (bottom left)
Sq 8-X1 (top left)
Sq 8-B1 (left top)
Sq 2-b1 (right top)
Distance is 22
Total Distance is 143