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

Intro: 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:

1. 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).
2. Find a wall between two cells that have a different group identifiers.
3. Remove that wall.
4. 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.
5. 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

Comments

[Sembot]

Hai

Is this what you want,I uncheck ' I Made it ' (hand) and than i post a image

Can you explain the letters R11 and C11 I don't now what it means , sorry

Kind regards

[thedod]

Hi. Had some time to look at the code, and I have a theory:

In line 184 where it says lcd.begin(16,2), it should probably say lcd.begin(20,4) instead.

If I'm right, you'll get a working game, but only 16x2 characters will be utilized.

Please let me know if whether it works (perhaps add a photo).

If it does, I can go over the code and figure out what else to change so that you can view a larger part of the maze.

[thedod]

Thanks. I now understand that the photo is not of a 16x2 display, and that you weren't asking a rhetorical question ?. I somehow "decided" that you had a working game. Sorry about that.

This sure looks wrong (compared to the attached image): the compass is above the R and C indicators, Normally R and C are between 0 and 9 (a single digit), it seems like even the fonts have a black picture in the corner (probably fonts are a different size on this display).

Anyaway, let me see if by looking at specs alone I can figure out what to change in the code (might take from a few days to a few weeks, depending on work etc.). Maybe I'll sed you some test pde files (that show test patterns on the LCD etc.).
Maybe it will be easy enough to work this way. If not - I'll need to order a display like yours and give it a go.

Thanks for finding me a new challenge ?

[aspíndola núñez]

Great post, its my first introduction into the arduino world and thanks to you now I know much more than I did yesterday!!!

[Sembot]

Hai,

I have made de Maze game and its works well , thanks for sharing the code

Cane a make it for a LCD with 20×4 , what must a change in the code , please can you help
And place the text on the side

Kind regards
[e-mail]

[thedod]

> I have made de Maze game and its works well

This is so cool. Could you please take a photo and do an "I made it" comment? Thanks

> LCD with 20×4

Like this one? I can try and take a look how different the specs are but in order to be sure, I'll need to actually have one. Maybe next time I'm on an electronics shopping spree :)

[Sembot]

Thanks for repeat on my letter

This is what i all have done

I made a LCD above mine arduino with lots of sensors , Mic , Pot , LDR , TNC , and a switch , so I can use it with other prog eventual

Sorry if my englisch is not oke ( dutch)

Kind regards

[thedod]

This is great. Here's my post about it.

If possible, please click the "I made it" button and upload an image or 2 there (maybe an angle that shows the potentiometer and button).

I've only discovered the "I made it" button a few days ago and I'm not sure in what way "I made it" comments are different than regular ones, where they get displayed, etc. The only thing I know is that they need to have at least one photo.

So if you can, please give "I made it" button a test spin, and let's see what it does :) (don't feel like you have to do it. Entirely up to you)

All the best,

The Dod.