Ariadne - a 1st person maze on a 16x2 LCD display

README.markdown

A tribute to Ariadne (the maze generator from Inception). See video and instructable.

ariadne.pde

/* Ariadne - 1st person maze on a 16x2 LCD display 
 You can use any Hitachi HD44780 compatible LCD:
 rs on pin 2, rw on 3, enable on 4, data 5-8 (pins explained at
 http://www.arduino.cc/en/Tutorial/LiquidCrystal).
 There's also a 10K ohm potentiometer on analog input 1 (outer legs to +5v and gnd),
 a push-button on pin 10 (with a 10k ohm pull-up resistor bitween the pin and gnd),
 and a Piezo speaker on pin 9 (PWM).
 
 Enjoy,
 @TheRealDod, Nov 25, 2010
 */
#include <LiquidCrystal.h>
LiquidCrystal lcd(2, 3, 4, 5, 6, 7, 8);

char line_buff[16+1]; // 16 chars and a \0

// Steering wheel potentiometer
const int POTPIN = 1;

const int BUTTONPIN = 10;
const int BUTTONPRESSED = HIGH; // depends on whether button is normally-open/closed
int last_button_state;

// Piezo speaker
const int SPEAKERPIN = 9;

const int RANDSEEDPIN = 0; // an analog pin that isn't connected to anything

#define BITMASK(x) (1<<(x))
const byte LEFT=0;
const byte BOTTOM=1;
const byte PLAYER=2;

char *intro_message[2] = {
  "Ariadne: A tiny",
  "1st person maze"};

char *win_message[2] = {
  "Freedom! Click",
  "to continue..."};

// glyphs
char BLANK = ' '; // no need to waste a glyph on that :)
char EXIT = '*';

const int NGLYPHS = 8;
// note that glyph 0 can't be used in
// lcd.print() of null-terminated strings
byte glyphs[NGLYPHS][8] = {
  // 0: reserved
  { 
    B00000,
    B00000,
    B00000,
    B00000,
    B00000,
    B00000,
    B00000,
    B00000}
  // 1: BITMASK(LEFT)
  ,{
    B10000,
    B10000,
    B10000,
    B10000,
    B10000,
    B10000,
    B10000,
    B10000}
  // 2: BITMASK(BOTTOM)
  ,{
    B00000,
    B00000,
    B00000,
    B00000,
    B00000,
    B00000,
    B00000,
    B11111}
  // 3: BITMASK(LEFT)|BITMASK(BOTTOM)
  ,{
    B10000,
    B10000,
    B10000,
    B10000,
    B10000,
    B10000,
    B10000,
    B11111}
  // 4: BITMASK(PLAYER)
  ,{
    B00000,
    B00000,
    B00010,
    B00111,
    B00010,
    B00101,
    B00000,
    B00000}
  // 5: BITMASK(PLAYER)|BITMASK(LEFT)
  ,{
    B10000,
    B10000,
    B10010,
    B10111,
    B10010,
    B10101,
    B10000,
    B10000}
  // 6: BITMASK(PLAYER)|BITMASK(BOTTOM)
  ,{
    B00000,
    B00000,
    B00010,
    B00111,
    B00010,
    B00101,
    B00000,
    B11111}
  // 7: BITMASK(PLAYER)|BITMASK(LEFT)|BITMASK(BOTTOM)
  ,{
    B10000,
    B10000,
    B10010,
    B10111,
    B10010,
    B10101,
    B10000,
    B11111}
};

const byte NORTH = 0;
const byte EAST = 1;
const byte SOUTH = 2;
const byte WEST = 3;
char *compass[2][4] = {
  { 
    " N "," E "," S "," W "}
  ,{
    "W^E","N<S","EvW","S>N"}
};

const int MAZEROWS = 12;
const int MAZECOLS = 12;
const int DISPLAYROWS = 2;
const int DISPLAYCOLS = 9;
const int PLAYERDISPLAYROW = 1;
const int PLAYERDISPLAYCOL = 5;

/* 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
};


#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])

byte maze[MAZEROWS][MAZECOLS];
int groups[MAZEROWS][MAZECOLS];

int player_row;
int player_col;

void setup()
{
  last_button_state = !BUTTONPRESSED;

  //Serial.begin(9600);
  randomSeed(analogRead(RANDSEEDPIN));
  for (int i=0; i<NGLYPHS; i++) {
    lcd.createChar(i,glyphs[i]);
  }
  pinMode(SPEAKERPIN,OUTPUT);
  digitalWrite(SPEAKERPIN,0); // to be on the safe side
  lcd.begin(16,2);
  //lcd.print("Generating maze");
  //debugMaze();
  showMessage(intro_message);
  makeMaze();
  while (!getButtonPress()) { delay(100); }
  lcd.clear();
}

void loop() {
  byte heading=getHeading();
  if (getButtonPress()) {
    moveForward(heading);
  }
  if (!(player_row || player_col)) { // Yay! We won!
    showMessage(win_message);
    makeMaze();
    while (!getButtonPress()) { delay(100); }
    lcd.clear();
  }

  drawMaze(heading);
  delay(50);
}

byte getHeading() {
  return analogRead(POTPIN)/256;
}

int getButtonPress() {
  int button_state = digitalRead(BUTTONPIN);
  int button_change = button_state!=last_button_state;
  last_button_state = button_state;
  return button_change && (button_state==BUTTONPRESSED);
}

void moveForward(byte heading) {
  if (maze[player_row][player_col]&BITMASK(heading)) {
    tone(SPEAKERPIN,880,150); // wall-banging sound
  } 
  else {
    player_row += MAP2SOUTH(heading,-1,0);
    player_col += MAP2EAST(heading,-1,0);

  }
}

void makeMaze() {
  // initialize
  for (int r=0; r<MAZEROWS; r++) {
    for (int c=0; c<MAZECOLS; c++) {
      maze[r][c] = 15; // walls in all directions
      groups[r][c] = r*MAZECOLS+c; // each cell is in a different group
    }
  }
  // break walls
  int walls_to_break = MAZEROWS*MAZECOLS-1;
  while (walls_to_break--) {
    breakWall();
  }
  // put player at bottom right
  player_row = MAZEROWS-1;
  player_col = MAZECOLS-1;
}

void drawMaze(byte heading) {
  line_buff[DISPLAYCOLS]='\0';
  for (int r=0; r<DISPLAYROWS; r++) {
    for (int c=0; c<DISPLAYCOLS; c++) {
      int deltarow=r-PLAYERDISPLAYROW;
      int deltacol=c-PLAYERDISPLAYCOL;
      int absrow=player_row+MAP2SOUTH(heading,deltarow,deltacol);
      int abscol=player_col+MAP2EAST(heading,deltarow,deltacol);
      line_buff[c]=rowColChar(heading,absrow,abscol);
    }
    lcd.setCursor(0,r);
    lcd.print(line_buff);
    lcd.print(compass[r][heading]);
  }
  lcd.setCursor(13,0);
  lcd.print("R  "); // blanks would clear previous garbage
  lcd.setCursor(14,0);
  lcd.print(player_row);
  lcd.setCursor(13,1);
  lcd.print("C  "); // blanks would clear previous garbage
  lcd.setCursor(14,1);
  lcd.print(player_col);
}

//===== aux functions

//---- display a 2 line message

void showMessage(char *msg[]) {
   lcd.clear();
   for (int r=0; r<2; r++) {
    lcd.setCursor(0,r);
    lcd.print(msg[r]);
  }
}

//---- for makeMaze()

void breakWall() {
  int breaking_west,row1,col1,row2,col2,joinfrom,jointo;
  while (1) {
    breaking_west=random(2); // decide whether it's a western or a southern wall
    if (breaking_west) {
      row1 = row2 = random(MAZEROWS);
      col1 = 1+random(MAZECOLS-1); // can't break west from 1st col
      col2 = col1-1;
      if (!(maze[row1][col1]&BITMASK(WEST))) {
        continue;
      } // no wall to break
      joinfrom = groups[row1][col1]; 
      jointo = groups[row2][col2];
      if (joinfrom==jointo) {
        continue;
      } // no reason to break this wall
      maze[row1][col1] &= ~BITMASK(WEST);
      maze[row2][col2] &= ~BITMASK(EAST);
    } 
    else { // breaking south
      row1 = random(MAZEROWS-1); // can't break south from last row
      row2 = row1+1;
      col1 = col2 = random(MAZECOLS);
      if (!(maze[row1][col1]&BITMASK(SOUTH))) {
        continue;
      } // no wall to break
      joinfrom = groups[row1][col1]; 
      jointo = groups[row2][col2];
      if (joinfrom==jointo) {
        continue;
      } // no reason to break this wall
      maze[row1][col1] &= ~BITMASK(SOUTH);
      maze[row2][col2] &= ~BITMASK(NORTH);
    }
    // join the groups
    for (int r=0; r<MAZEROWS; r++) {
      for (int c=0; c<MAZECOLS; c++) {
        if (groups[r][c]==joinfrom) {
          groups[r][c] = jointo;
        }
      }
    }
    break;
  }
}

//---- for drawMaze()

// rowColChar deals with all special cases, or calls cellChar otherwise 
char rowColChar(byte heading, int row, int col) {
  if (row==-1 && col==0) { // the exit
    return EXIT;
  } 
  if (row<-1 || row>MAZEROWS || col<-1 || col>MAZECOLS) { // limbo: unconstructed mazespace ;)
    return BLANK;
  } 
  if ((row==-1 || row==MAZEROWS) && (col==-1 || col==MAZECOLS)) { // corners are limbo too
    return BLANK;
  } 
  if (row==-1) { // northern wall
    return cellChar(heading,BITMASK(SOUTH),0);  
  } 
  if (col==MAZECOLS) {  // eastern wall
    return cellChar(heading,BITMASK(WEST),0);  
  }
  if (row==MAZEROWS) { // southern wall
    return cellChar(heading,BITMASK(NORTH),0);  
  } 
  if (col==-1) {  // western wall
    return cellChar(heading,BITMASK(EAST),0);  
  }
  // A real cell (at least in this reality)
  return cellChar(heading,maze[row][col],row==player_row&&col==player_col); // a real maze cell
}

char cellChar(byte heading, byte walls, byte is_player) {
  byte result=is_player ? BITMASK(PLAYER) : 0;
  if (walls & BITMASK((WEST+heading)%4)) {
    result |= BITMASK(LEFT);
  }
  if (walls & BITMASK((SOUTH+heading)%4)) {
    result |= BITMASK(BOTTOM);
  }
  if (result) {
    return result;
  }
  return BLANK;
}

//---- cheat mode ;)

void debugMaze() {
  for (int r=0; r<MAZEROWS; r++) {
    for (int c=0; c<MAZECOLS; c++) {
      if (maze[r][c]&BITMASK(WEST)) {
        Serial.print("|");
      } 
      else {
        Serial.print(" ");
      }
      if (maze[r][c]&BITMASK(SOUTH)) {
        Serial.print("_");
      } 
      else {
        Serial.print(" ");
      }
    }
    Serial.println('|');
  }
}

ariadne_bb.png