Ariadne - a 1st Person Maze on a 16x2 LCD

This game is a homage to Ariadne, the maze-generator from Inception :)
If you haven't seen the movie yet - watch this video again after you do (you can also watch it now - it's not a spoiler, it's just funnier for inception-vets).

The nice thing about it is that it's a 1st-person game, so when you rotate your character, it stays in place, and the maze rotates around it. This means that you don't only see a narrow strip of reality - you can choose between 4 of them. If you can keep a mental image of all of them, you can cover quite a lot of maze without moving. It's not as hard as it seems. It's quite intuitive.

It's a game I actually enjoy playing. Not too easy and not too hard to solve.
It's easy to build too. Most of it is software.

Step 1: Hardware

What you need is:

An Arduino
A Hitachi HD44780 compatible LCD.
A pushbutton on pin 10 (also connected to gnd via a 10K Ohm pull-up resistor).
A potentiometer on analog pin 1 (outer legs go to +5v and gnd).
A piezo speaker between pin 9 (PWM) and gnd.

See breadboard diagram.

Since the only LCD I have is an Electronic Brick, I wasn't sure how to wire a "real" LCD. I had an educated guess, but it was still only a guess. In the end, I've managed to find a way to "unbrick" the LCD and check the wiring in practice (see photo).

Step 2: Software

The code is here.
Most of it is quite straight-forward. The only bits worth mentioning are the maze generation algorithm and the way we deal with drawing a rotated maze.

Maze generation
I'm using Kruskal's algorithm, and I'm not even trying any of the fancy stuff Wikipedia suggests in order to optimize it. It's fast enough as it is.

It's pretty simple:

Start with all walls intact, and give each cell a unique group identifier (you can use the number col+row*width, or strings like "R0C0". Doesn't matter as long as they're unique).
Find a wall between two cells that have a different group identifiers.
Remove that wall.
Join the two groups: all cells that have the group identifier of the first cell, will now have the group identifier of the other cell.
Steps 2-4 should be run n-1 times (where n is number of cells).

At the end of the process, all cells are connected, and there are no loops in the maze.

The picture below shows how the walls and group identifiers look after a few rounds, and at the end of the process.

There's also a JavaScript version here. You can experiment with it even if you don't have an Arduino, and it might be useful for some JS game you might come up with.

The main difference between the JS and the Arduino versions is in JS we only store for each cell whether it has a left wall and whether it has a bottom one. On the Arduino we store all 4 walls (although there's a redunduncy here), since we also need to draw the cells rotated, and it's easier if we have access to all the walls of a cell.

Drawing a rotated maze
We define the 4 absolute directions as 0-4:

const byte NORTH = 0;
const byte EAST = 1;
const byte SOUTH = 2;
const byte WEST = 3;

There's a rotation matrix that helps us map from relative Up/Right/Left/Down to absolute N/E/S/W for a specific heading (heading is the absolute direction our character is looking at):

/* rotation map: for each heading, a mapping from [delta] rows/cols to [delta] south/east
{down->south,right->east,down->east,right->south} */
int rotation_map[4][4] = {
   {1,1,0,0} // north: down is south, right is east
   ,{0,0,-1,1} // east: down is west, right is south
   ,{-1,-1,0,0} // south: down is north, right is west
   ,{0,0,1,-1} // west: down is east, right is north
};

Here are the macros that do the actual mapping:
#define MAP2SOUTH(heading,row,col) ((row)*rotation_map[heading][0]+(col)*rotation_map[heading][3])
#define MAP2EAST(heading,row,col) ((row)*rotation_map[heading][2]+(col)*rotation_map[heading][1])

MAP2SOUTH returns the absolute row corresponding to a row,col on the display, and MAP2EAST returns the absolute column.

The rest is self explanatory (leave a comment if anything isn't).

Enjoy,
@TheRealDod

Introduction: Ariadne - a 1st Person Maze on a 16x2 LCD

Step 1: Hardware

Step 2: Software