{"id":94,"date":"2010-04-16T11:46:32","date_gmt":"2010-04-16T18:46:32","guid":{"rendered":"http:\/\/zalbee.intricus.net\/immerge\/blog\/?p=94"},"modified":"2025-05-23T22:49:05","modified_gmt":"2025-05-24T02:49:05","slug":"solving-continuity-levels-with-dijkstras-shortest-path","status":"publish","type":"post","link":"https:\/\/zalbee.intricus.net\/immerge\/blog\/94","title":{"rendered":"Solving Continuity Levels with Dijkstra’s Shortest Path"},"content":{"rendered":"

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).<\/em><\/p>\n

Continuity<\/a> 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<\/a> (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.<\/p>\n

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.<\/p>\n

I also took this opportunity to get familiar with Python<\/a>, 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.<\/p>\n

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<\/a> 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<\/a> that could automate this :). Lastly, I skipped solving the 8-puzzle, since it’s not necessary.<\/p>\n

<\/p>\n

The Basics<\/h2>\n

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\u00a0exactly<\/em>. 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). \u00a0Top 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.<\/p>\n

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).<\/p>\n

\"\"

Matching sides are labelled with letters.<\/p><\/div>\n

In this level, there are 7 types of sides with these openings:<\/p>\n

Number of openings\u00a0\u00a0(points)\u00a0per side:<\/div>\n
Left\/right sides:<\/div>\n
\n