Solving Boulder Dash

Boulder Dash is an old favorite of mine. So much was done right in it by the original developers (Peter Liepa and Chris Gray) and the game is still fun even 30 years later. Then, the whole concept behind governing non-player movements in the game is very much like a cellular automaton (think: Conway's Game Of Life) and the fact that most of the levels are randomly generated with manual content added, which is something that we see even today (it was one of the main feature of Oblivion) makes it just incredible for me.

I will try to document my journey in trying to find the best solution for Boulder Dash like puzzles. And this is important: I say "like" because there is no way to find the best solution for Boulder Dash itself (my apologies to anyone ending up here looking for an universal solver). I will explain why in details when we get to that part of the game, but suffice to say that I will need to make some assumptions in order to auto-generate and solve caves:

1. I will concentrate on Boulder Dash I. I might implement some of the Boulder Dash II objects, but they are not as thoroughly documented as the ones in the first game.
2. Pushing boulders will always be immediate, as opposed to having a 1/8 chance of succeeding like in the original games.
3. Amoebas will grow at a fixed pace, which will be relayed as information to the player. The best way to decide on the frequency and relay that information is debatable, but doing it once every X moves is probably the easiest solution for me and for an eventual solver.

It might be good to mention that I will not code a complete game of Boulder Dash here. Anyone looking for example of the game and code should look at Elmer's Production invaluable BoulderDash home Page or Code inComplete's Javascript version of Boulder Dash. In fact, I will likely "borrow" the pseudo-codes on Elmer's page to implement most of the objects.

So, with this out of the way, lets start Solving Boulder Dash!