Tag Archives: Gaming

Solving Mushroom Man 113 with Dynamic Programming

Here’s something that might sound strange. Today, while playing the retro puzzle game “Mushroom Man” — a great throwback to “Chip’s Challenge” — I noticed how similar one of the levels was to solving a programming contest question. In level 113 “Don’t Drink the Water,” there is a large number of water tiles and only a limited amount of oxygen available to cross those tiles. At one point, I found myself on a spot where all paths left me exactly 1 oxygen short. Eventually, I needed to work backwards, counting the tiles to look for a solution. The shape of the level — a 10×10 grid with the goal in the corner — reminded me a lot of a dynamic programming solution where you would fill in a 2D integer array.

Dynamic Programming?

The origin of the term dynamic programming has very little to do with writing code. It was first coined by Richard Bellman in the 1950s, a time when computer programming was an esoteric activity practiced by so few people as to not even merit a name. Back then programming meant “planning,” and “dynamic programming” was conceived to optimally plan multistage processes.

– https://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf

Dynamic programming is about breaking a large problem into sub-problems, and using those sub-solutions to find the large solution. While you could write a DP solution recursively, it’s usually much more efficient to start with the smallest problem, and iteratively build up to the large one. A lot of the classic examples, such as the longest subsequence problem, can be solved by building a 2-dimensional table. For that reason, I like to think of DP algorithms as table-building. Read more »

Reversola – Reverse Engineering Sola Rola

Banner

Introduction

I was browsing the Kongregate forums one day, when a post caught my eye. It was a list of broken games on the site that still had achievements to earn, and the clever ways that people had found to progress in those games far enough to earn the achievements. Sola Rola: The Gravity Maze was one of the few that hadn’t been solved. This game was interesting because not only was it broken on Kongregate, it was also broken on every single other Flash game portal out there, including the game’s own sponsor Gimme5Games and the website of its creator, EvilFree Productions.

This was a simple physics-based game where you rotate the environment, similar to Loco Roco, but with its own cheeky characters having to navigate a maze. Around September 24, 2010, something changed that broke the game. No matter which website or computer you accessed it from, the game would show the sponsor logo and then a blank white screen. For two years, seemingly no one could figure it out, so in September of 2012, I set out to investigate it myself. Two weeks later, with the help of the Kongregate community, we were able to recreate the original levels to get a working version of the game for people to play and — if they are into this sort of thing — earn the achievements.

Why it Doesn’t Work

A few people already found out why the game doesn’t load. When the game starts, it tries to load two XML files: translate.xml, containing language strings, and levelList.xml, containing the level list. The problem is these files were ONLY located on the Gimme5Games server and the files are now nowhere to be found. This explains why the game was broken no matter which portal hosted the game (SWF file). After an hour of fruitless searching through internet archives, and several efforts to contact the developer, it was clear the original files would not be found. Another approach had to be taken.

In April of 2012, askon, a Kongregate user, posted the source code decompiled from the game’s SWF file, and a way to fool the game into starting with an empty XML file. All that was missing were the contents of that file — the level data! Fortunately, someone had recorded every single level of the game on Youtube, so we had hope to reconstruct the levels, if we only we knew the structure of the XML files. That is where I would come in. More on that later.

Getting the Game to Start

Network diagram

The hosts file entry bypasses the DNS lookup and redirects requests to our server.

When the game starts, it requests the XML files using ordinary HTTP requests to “http://www.gimme5games.com/solarola/translate.xml” and “http://www.gimme5games.com/solarola/levels/levelList.xml”. Since those are gone forever, we need the game to look for those files on a different server — one that we control. One obvious way would be to modify the compiled SWF file itself, however that wouldn’t allow us to earn achievements on the Kongregate site. Instead, we will redirect the request at the DNS lookup step. The easiest way to do this is to modify the “hosts” file of the local machine. Now, instead of asking a remote DNS server for the IP address of gimme5games.com, our PC will simply use the entry in our hosts file.

Read more »

2011 WTF Games of the Year

I have updated my annual list with 3 games!

This year’s winners are a pair of deceptively simple but frustratingly difficult games, QWOP and GIRP. Plus I added an extra one to 2010 for fun. Click below to see these reviews and more:

zAlbee’s WTF Game of the Year

2010 WTF Game of the Year

I have named the 2010 WTF game of the year. It includes cars and zombies.

Robot Wants Fishy – complete map

Complete Map (warning: huge picture 662 KB) for Robot wants Fishy, including all item locations.

Solving Continuity Levels with Dijkstra’s Shortest Path

Continuity (game screen)

(This article was originally posted here.)

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.

Read more »