100 Levels of Log-ic: ASCII Maps, a Generator and a Solver
Hairy Beaver's levels are drawn in text. A solver proves each one can be finished and sets its par, and a generator builds most of them by chaining obstacles together and keeping only what the solver can beat.
Hairy Beaver has 100 levels. I drew about thirty of them by hand. A program built the rest, and another program checked all of them.
A level is a few lines of text
This is level one, First Chomp, exactly as it appears in the source:
................
................
................
................
................
.B...4....H.....
######..########
######..########
B is the beaver, H is home, # is ground and 4 is a tree four cells tall. There's a two-cell gap in the ground. Chew the tree, it falls right, it's a bridge.
The whole vocabulary fits in a paragraph. ~ is still water, > and < are water with a current, * is bramble, a run of = is a loose log, S is a rain cloud, ^ is blades, O is a rock, F is a friend, and W, N and V are a wolf, a hunter and a crow. A { or } above a tree makes it lean.
Drawing levels as text means a new puzzle idea takes a minute to try, and a level can be read in a code review.
The rules don't know about the screen
All of the game's rules live in one file with no graphics code in it: what happens when a tree falls, when a log floats, when a see-saw tips. The play screen asks that model what happened and animates the answer.
That separation is what makes everything else here possible, because a command-line program can load the same rules and play the game with nobody watching.
The solver
The solver is a breadth-first search. From the starting position it tries every action the beaver has (walk, chomp, bite a log, grab and push or pull, wait a beat for moving water) and keeps going until he's home.
It does two jobs. It proves the level can be finished, and the length of its shortest solution becomes the level's par. Your maple leaves are measured against that number.
It has one known blind spot. On levels with currents, the solver assumes perfect timing, so its answer is optimistic. Those levels get played by a human as well.
The generator
The hand-built levels each teach one idea, in order. The generator takes over from there. It works by stringing together obstacle segments, small recipes like:
bridge: a tree, then a pit a little narrower than the tree is tallramp: a cliff with a tree standing the right distance from itriver,blades,domino,catapult,icebreak,burrow…
There are about twenty of them, each with a weight for how often it's picked. A candidate level is a random chain of segments. Most candidates are bad, and the generator's real job is throwing them away: anything the solver can't finish is discarded, and the survivors are ranked by how much work the solution takes. The ranking is why the later levels get longer and harder without anyone hand-ordering them.
Each segment also carries a few hint lines, so a generated level opens with advice that fits what's in it. "Hairy beavers don't swim. Logs do."
The same trick records the trailer
The game takes debug launch arguments: a level number and a script of inputs, like -level 4 -script RRLLCL for right, right, left, left, chomp, left. It was built for testing.
It also means the gameplay video at the top of this post was never played by hand. A shell script boots a simulator, launches each level with a script of inputs, records the screen, and joins the clips. When the art changes, the video gets re-recorded with one command.
What the hand-built levels are for
A generator can make a puzzle. It can't make a joke, and it can't decide that level 26 should be the first time you see ice. The hand-built levels carry the teaching order and the personality, with names like Stairway to Beaven, Raft Punk and Leave It to Beaver. The generated ones give the game its length, and the solver keeps both honest.
Next: a game with no image files.