/*
 *  Copyright (C) 2008-2014 Florent Bedoiseau (electronique.fb@free.fr)
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */
// Modification : 17/02/2014

int VIDE=0;
int MUR=1;
int PAS=2;

class Node {
  int _x;
  int _y;
  int _dir;
  
  Node (int x, int y, int dir)  { 
    _x = x;
    _y = y;
    _dir = dir;
  }

  int getX () { return _x; }
  int getY () { return _y; }
  int getDir () { return _dir; }
};


class Maze {
  Maze (int h, int w, int p) {
    _h = h;
    _w = w;
    _sx = 1;
    _sy = 1;
    _dirs = 0;
    _p = p;
    
    if (_w < 5) _w = 5;
    if (_h < 5) _h = 5;

    _m = new int [_h][_w];
    _nodes = new ArrayList();
  }

  
void show () {
  
  color red = color (0xFF, 0x00, 0x00);
  for (int j = 0; j < _h; ++j) {
    for (int k = 0; k < _w; ++k) {
      color col = red;
      int val = _m[j][k];
      if (val == VIDE || val == MUR) col = color (0x00, 0x00, 0xFF);
      else if (val == PAS) col = color (0xFF, 0xFF, 0xFF);
      
      rectMode(CORNER); 
      fill(col);
      rect(k*4, j*4, 4, 4);
    }
  }
  
  fill(red);
  rect(_sx*4, _sy*4, 4, 4);
  }

  void checkNode (Node aNode) {
      int x = aNode.getX();
      int y = aNode.getY();

      switch (aNode.getDir()) {
      case 1: if (TestN (x, y-1)) addNode (x, y-1); break; // N
      case 2: if (TestE (x+1, y)) addNode (x+1, y); break; // E
      case 3: if (TestS (x, y+1)) addNode (x, y+1); break; // S
      case 4: if (TestW (x-1, y)) addNode (x-1, y); break; // W
      default: break;
      }
  }
  
  boolean TestN (int x, int y) {
    if (_m[y][x] != VIDE) return false;
    if (_m[y-1][x] == PAS) return false;
    if (_m[y][x-1] == PAS) return false;
    if (_m[y][x+1] == PAS) return false;
    return true;
  }

  boolean TestE (int x, int y) {
    if (_m[y][x] != VIDE) return false;
    if (_m[y][x+1] == PAS) return false;
    if (_m[y-1][x] == PAS) return false;
    if (_m[y+1][x] == PAS) return false;
    return true;
}
  
  boolean TestS (int x, int y) {
    if (_m[y][x] != VIDE) return false;
    if (_m[y][x-1] == PAS) return false;
    if (_m[y][x+1] == PAS) return false;
    if (_m[y+1][x] == PAS) return false;
    return true;
  }
  
  boolean TestW (int x, int y){
    if (_m[y][x] != VIDE) return false;
    if (_m[y][x-1] == PAS) return false;
    if (_m[y-1][x] == PAS) return false;
    if (_m[y+1][x] == PAS) return false;
    return true;
  }

  void reset () {
    for (int y = 0; y < _h; ++y) {
      for (int x = 0; x < _w; ++x) {
        _m[y][x]= VIDE;
      }
    }

    for (int y= 0; y < _h; ++y) {
      _m[y][0] = MUR;
      _m[y][_w-1] = MUR;
    }

    for (int x= 0; x < _w; ++x) {
      _m[0][x] = MUR;
      _m[_h-1][x] = MUR;
    }

    _dirs = int (random (0, 24));
  }

  void addNode (int x, int y) {
    // Compute new directions
    if (_p > 1) {
      if (int(random (0, _p)) == 0) { 
  _dirs = int(random (0, 24)); // Select moves order 
      }
    }
    else {
      _dirs = int (random (0, 24)); // Select moves order 
    }
    
    for (int idx = 0; idx < 4; ++idx) {
      int d = dirset[_dirs][idx];
      _nodes.add (new Node (x, y, d));  // Adds 4 Nodes 
    }

    _m[y][x] = PAS; // OK we walked on it
  }

  void compute (int sx, int sy) {
    reset ();

    if (sx >= 1 && sx < 100) _sx = sx; // (rand () % (_w - 2)) + 1;
    if (sy >= 1 && sy < 100) _sy = sy; // (rand () % (_h - 2)) + 1;

    addNode (_sx, _sy); // inserting first node
    while (true) {
      int n = _nodes.size();
      if (n == 0) return; // The end
      
      Node node = (Node) _nodes.get(n - 1); // Taking last one
      _nodes.remove (n - 1);
      checkNode (node);
    }
  }
  
  int [][]_m;
  int _h, _w;
  int _sx, _sy;
  int _dirs;
  int _p; // Change direction probablility : 1->each step, 4-> 1/4 step
  ArrayList _nodes;
};



int [][] dirset = {
    { 1, 2, 3, 4},
    { 1, 2, 4, 3},
    { 1, 3, 2, 4},
    { 1, 3, 4, 2},
    { 1, 4, 2, 3},
    { 1, 4, 3, 2},
    
    { 2, 1, 3, 4},
    { 2, 1, 4, 3},
    { 2, 3, 1, 4},
    { 2, 3, 4, 1},
    { 2, 4, 1, 3},
    { 2, 4, 3, 1},

    { 3, 1, 2, 4},
    { 3, 1, 4, 2},
    { 3, 2, 1, 4},
    { 3, 2, 4, 1},
    { 3, 4, 1, 2},
    { 3, 4, 2, 1},
    
    { 4, 1, 2, 3},
    { 4, 1, 3, 2},
    { 4, 2, 1 ,3},
    { 4, 2, 3, 1},
    { 4, 3, 1, 2},
    { 4, 3, 2, 1}
};

boolean change = true;
Maze maze;
void setup () {
  size (320,240);
  background(0);
  noFill();
  noStroke ();
}

void draw () {
  if (change) {
    change = false;
    maze = new Maze (60, 80, int (random(1, 6)));
    maze.compute (1, 1);
    maze.show ();
  }
}

void mouseClicked() {
  change = true;
}