主题：迷宫生成及寻路算法练习（递归回溯/深度优先算法）
作者：ZC@FJNU 2021.10
版权声明：本程序为原创代码，用于College of Arts in FJNU高校课堂教学。
本程序遵守开源协议，欢迎二次开发，分发时务必保留上述信息。
This program is created for college education (College of Arts in FJNU, auther Zheng Cheng)
We open the source code to anyone who is interested, just enjoy playing.🙂
If you edit and share, the above information must be retained when distribution.

玩法说明：
迷宫生成：

程序开头可以设置迷宫大小。(见下方变量COLS和ROWS）
推荐15×20的简单迷宫适合自己玩，50×80复杂迷宫适合做寻路观察。
运行即开始生成迷宫（默认为每帧砸一面墙），按<回车键>可加快迷宫生成速度
迷宫生成完成后，即可开始玩。
用<鼠标>或者<方向键>控制蓝色方块移动，到达终点（白色）即胜利
按<r>键重新生成随机迷宫
迷宫寻路：
按<空格键>显示/隐藏迷宫解法路径（解法是唯一的）
按<鼠标左键>可以重新定位迷宫的终点（即出口）；
按<鼠标右键>可以重新定位迷宫的起点（即入口）；
每次重新设定后，电脑会重新寻路，这个过程可以慢放欣赏（后面详述）
按<d>键可以看所有格子的方向（过程参照，没啥用）
参考：https://www.jianshu.com/p/f643b0a0b887
https://www.cnblogs.com/teternity/p/MazeAlgorithm.html

迷宫生成关键算法3个函数：
moveNext():如何从当前格子移到下一个格子
updateBreakableWalls():计算格子有哪几面墙能砸
jumpToAVisitedGridAndMoveNext():跳到一个已访问过的随机格子并砸墙
算法思路：
第一步，从起点开始随机砸墙，遵循3个原则：
a,最外面一圈墙壁不能砸；
b,已经砸过的墙不能再砸；
c,隔壁是已访问过的格子的墙不砸（否则会形成环状回路，让迷宫解法不唯一）
第二步，如果无墙可砸（走到死胡同），那么随机跳到一个格子继续砸墙，该格子应该是：
a,已访问过的（这样能保证和起点连通、可达，避免出现一片封闭的独立迷宫）；
b,有墙可砸的（满足步骤1中的3个原则）；
第三步，如果满足步骤2的格子也不存在了，说明所有格子都已连通且可达，迷宫生成完毕。

迷宫寻路算法DFS：
这个算法比想象的还简单，网络参考代码都是渣渣。只需要一个dfs函数不断做递归就行了。
简单说，就是从起点开始，对每个格子都做一次上下左右四方向上的探索：
只要某个方向没墙，并且下一个格子没探索过，那就对下一个格子做一次dfs。
每个格子探索前将自己推进栈，四个方向探索完再将自己推出栈。
这样就能保证所有路径都遍历一遍，深度搜索完成，最后回到起点。
奇妙就妙在，在遍历的过程中，一定会遇到终点，此时要毫不犹豫中止遍历一路返回。
这时候因为匆忙中止而来不及推出栈的所有格子，就是起点到终点的唯一路径解了。
最后，为了让dfs过程更慢更清晰展现，我分别作了dfs和dfsThread两个函数，功能是一模一样的。

/*********************************************
 主题：迷宫生成及寻路算法练习 （递归回溯/深度优先算法）
 作者：ZC@FJNU   2021.10
 版权声明：本程序为原创代码，用于College of Arts in FJNU高校课堂教学。
          本程序遵守开源协议，欢迎二次开发，分发时务必保留上述信息。
 This program is created for college education (College of Arts in FJNU, auther Zheng Cheng)
 We open the source code to anyone who is interested, just enjoy playing.:)
 If you edit and share, the above information must be retained when distribution.
 
 玩法说明：
  1，迷宫生成：
  * 程序开头可以设置迷宫大小。(见下方变量COLS和ROWS）
    推荐15x20的简单迷宫适合自己玩，50x80复杂迷宫适合做寻路观察。
  * 运行即开始生成迷宫（默认为每帧砸一面墙），按<回车键>可加快迷宫生成速度
  * 迷宫生成完成后，即可开始玩。
    用<鼠标>或者<方向键>控制蓝色方块移动，到达终点（白色）即胜利
  * 按<r>键重新生成随机迷宫
  2，迷宫寻路：
  * 按<空格键>显示/隐藏迷宫解法路径（解法是唯一的）
  * 按<鼠标左键>可以重新定位迷宫的终点（即出口）；
    按<鼠标右键>可以重新定位迷宫的起点（即入口）；
    每次重新设定后，电脑会重新寻路，这个过程可以慢放欣赏（后面详述）
  * 按<d>键可以看所有格子的方向（过程参照，没啥用）
  参考：https://www.jianshu.com/p/f643b0a0b887
       https://www.cnblogs.com/teternity/p/MazeAlgorithm.html

 迷宫生成关键算法3个函数：
  moveNext():如何从当前格子移到下一个格子
  updateBreakableWalls():计算格子有哪几面墙能砸
  jumpToAVisitedGridAndMoveNext():跳到一个已访问过的随机格子并砸墙
  算法思路：
  1，从起点开始随机砸墙，遵循3个原则：
     a,最外面一圈墙壁不能砸；
     b,已经砸过的墙不能再砸；
     c,隔壁是已访问过的格子的墙不砸（否则会形成环状回路，让迷宫解法不唯一）
  2，如果无墙可砸（走到死胡同），那么随机跳到一个格子继续砸墙，该格子应该是：
     a,已访问过的（这样能保证和起点连通、可达，避免出现一片封闭的独立迷宫）；
     b,有墙可砸的（满足步骤1中的3个原则）；
  3，如果满足步骤2的格子也不存在了，说明所有格子都已连通且可达，迷宫生成完毕。

 迷宫寻路算法DFS：
  这个算法比想象的还简单，网络参考代码都是渣渣。只需要一个dfs函数不断做递归就行了。
  简单说，就是从起点开始，对每个格子都做一次上下左右四方向上的探索：
  只要某个方向没墙，并且下一个格子没探索过，那就对下一个格子做一次dfs。
  每个格子探索前将自己推进栈，四个方向探索完再将自己推出栈。
  这样就能保证所有路径都遍历一遍，深度搜索完成，最后回到起点。
  奇妙就妙在，在遍历的过程中，一定会遇到终点，此时要毫不犹豫中止遍历一路返回。
  这时候因为匆忙中止而来不及推出栈的所有格子，就是起点到终点的唯一路径解了。
  最后，为了让dfs过程更慢更清晰展现，我分别作了dfs和dfsThread两个函数，功能是一模一样的。
***********************************************/
final boolean FAST_SEARCH_PATH = true;// 寻路算法快慢显示切换
//（true：用函数一次性寻路，快；false：用线程逐帧寻路，慢）

// 简单迷宫（适合自己玩）
final int ROWS     = 20;  // 迷宫行数
final int COLS     = 30;  // 迷宫列数
// 复杂迷宫（适合观察电脑寻路）
//final int ROWS     = 50;  // 迷宫行数
//final int COLS     = 80;  // 迷宫列数

final float BORDER_L = 50; // 左边距
final float BORDER_R = 50; // 右边距
final float BORDER_U = 50; // 上边距
final float BORDER_D = 50; // 下边距
float gW; // 每个格子宽度
float gH; // 每个格子高度
int startX = 0;// 迷宫起点
int startY = 0;
int endX = COLS-1;// 迷宫终点
int endY = ROWS-1;

// 4种方向+2种状态
final int GO_START  = 0;
final int GO_END    = 1;
final int GO_UP     = 2;
final int GO_DOWN   = 3;
final int GO_LEFT   = 4;
final int GO_RIGHT  = 5;

Grids[][] grid = new Grids[COLS][ROWS]; // 格子类
Global g = new Global();   // 全局函数

//====================== setup 和 draw =============================//

void setup() {
  size(1200,800);
  gW = (width-BORDER_L-BORDER_R)/COLS;// 格子宽度
  gH = (height-BORDER_U-BORDER_D)/ROWS; // 格子高度
  //rectMode(CENTER);
  //imageMode(CENTER);
  //textAlign(CENTER,CENTER);
  
  // 对象初始化
  for (int i=0;i<COLS;i++)
    for (int j=0;j<ROWS;j++)
      grid[i][j] = new Grids(i,j);
  
  // 迷宫生成起点设置为已访问
  grid[startX][startY].visited = true;
}

void draw() {
  if (g.generationComplete) feedThread = true;
  // 更新状态
  g.update();
    
  // 画
  background(0);
  pushMatrix();
  translate(BORDER_L,BORDER_U);
  // 画数字
  stroke(150);
  fill(255);
  textSize(constrain(gH*3/4,2,30));
  textAlign(RIGHT,CENTER);
  for (int i=0;i<ROWS;i++) text(i, -4, i*gH+gH/2);
  textSize(constrain(gW*3/4,2,30));
  textAlign(CENTER,BOTTOM);
  for (int i=0;i<COLS;i++) text(i, i*gW+gW/2, 0);

  // 画迷宫
  stroke(255);
  for (int i=0;i<COLS;i++) {
    for (int j=0;j<ROWS;j++) {
      // 四边
      if (grid[i][j].wL) line(i*gW, j*gH, i*gW, (j+1)*gH);
      if (grid[i][j].wR) line((i+1)*gW, j*gH, (i+1)*gW, (j+1)*gH);
      if (grid[i][j].wU) line(i*gW, j*gH, (i+1)*gW, j*gH);
      if (grid[i][j].wD) line(i*gW, (j+1)*gH, (i+1)*gW, (j+1)*gH);
      // 每个格子的方向（没啥用）
      if (g.showDirections) {
        fill(255);
        switch (grid[i][j].to) {
          case GO_LEFT:
          line(i*gW+gW/4, j*gH+gH/2, i*gW+gW*3/4, j*gH+gH/2);
          circle(i*gW+gW/4, j*gH+gH/2, (gW+gH)/20);
          break;
          case GO_RIGHT:
          line(i*gW+gW/4, j*gH+gH/2, i*gW+gW*3/4, j*gH+gH/2);
          circle(i*gW+gW*3/4, j*gH+gH/2, (gW+gH)/20);
          break;
          case GO_UP:
          line(i*gW+gW/2, j*gH+gH/4, i*gW+gW/2, j*gH+gH*3/4);
          circle(i*gW+gW/2, j*gH+gH/4, (gW+gH)/20);
          break;
          case GO_DOWN:
          line(i*gW+gW/2, j*gH+gH/4, i*gW+gW/2, j*gH+gH*3/4);
          circle(i*gW+gW/2, j*gH+gH*3/4, (gW+gH)/20);
          break;
          case GO_START:
          ellipse(i*gW+gW/2, j*gH+gH/2, (gW+gH)/10,(gW+gH)/10);
          break;
          case GO_END:
          ellipse(i*gW+gW/2, j*gH+gH/2, (gW+gH)/15,(gW+gH)/15);
          break;
        }
      }
      // 迷宫生成中：高亮当前格子
      if (!g.generationComplete && i==g.x && j==g.y) {
        noStroke();
        fill(200);
        rect(i*gW,j*gH,gW,gH);
        stroke(255);
      }
    }
  }
  
  // 迷宫生成完成
  if (g.generationComplete) {
    // 画迷宫解法
    if (g.showPath) {
      strokeWeight(3);
      stroke(0,255,0);
      fill(0,255,0);
      for (int n:g.pathSearchList) {
        int i=g.xOfIndex(n);
        int j=g.yOfIndex(n);
        switch (grid[i][j].from) {
          case GO_LEFT:
          line(i*gW+gW/2, j*gH+gH/2, i*gW, j*gH+gH/2);
          break;
          case GO_RIGHT:
          line(i*gW+gW/2, j*gH+gH/2, i*gW+gW, j*gH+gH/2);
          break;
          case GO_UP:
          line(i*gW+gW/2, j*gH+gH/2, i*gW+gW/2, j*gH);
          break;
          case GO_DOWN:
          line(i*gW+gW/2, j*gH+gH/2, i*gW+gW/2, j*gH+gH);
          break;
          case GO_START:
          case GO_END:
          default:
          break;
        }
        switch (grid[i][j].to) {
          case GO_LEFT:
          line(i*gW+gW/2, j*gH+gH/2, i*gW, j*gH+gH/2);
          break;
          case GO_RIGHT:
          line(i*gW+gW/2, j*gH+gH/2, i*gW+gW, j*gH+gH/2);
          break;
          case GO_UP:
          line(i*gW+gW/2, j*gH+gH/2, i*gW+gW/2, j*gH);
          break;
          case GO_DOWN:
          line(i*gW+gW/2, j*gH+gH/2, i*gW+gW/2, j*gH+gH);
          break;
          case GO_START:
          case GO_END:
          default:
          break;
        }
      }
      strokeWeight(1);
    }
    // 画各种位置
    noStroke();
    fill(200);
    rect(endX*gW+gW/8,endY*gH+gH/8,gW*3/4,gH*3/4);// 画终点位置
    fill(50,50,255);
    rect(g.x*gW+gW/8,g.y*gH+gH/8,gW*3/4,gH*3/4);// 画玩家所在位置（蓝方块）
    stroke(255);
    noFill();
    int index = g.checkMousePosition(mouseX, mouseY);
    if (index>=0) {
      int indexx = index % COLS;
      int indexy = index / COLS;
      rect(indexx*gW+gW/8,indexy*gH+gH/8,gW*3/4,gH*3/4);// 画鼠标所在位置（空心白框）
    }
  }
  // 到达终点，胜利画面
  if (g.generationComplete && g.x==endX && g.y==endY) {
    stroke(150);
    fill(255,100,100);
    textAlign(CENTER,CENTER);
    textSize(100);
    text("YOU WIN", width/2-BORDER_L, height/2-BORDER_U);
  }
  popMatrix();
}

//++++++++++++++++++++++++++++ 类 ++++++++++++++++++++++++++++++++//

// 类：迷宫格子
class Grids {
  int col;// 横坐标（所在列）
  int row;// 纵坐标（所在行）
  boolean visited; // 是否访问过【用于迷宫生成】
  boolean searched;// 是否搜索过【用于迷宫寻路】
  int from;// 从哪个方向来
  int to;  // 去哪个方向
  boolean wL; // 左边墙壁是否还在
  boolean wR; // 右边墙壁是否还在
  boolean wU; // 上边墙壁是否还在
  boolean wD; // 下边墙壁是否还在
  boolean breakable_wL; // 左边墙壁能否打掉
  boolean breakable_wR; // 右边墙壁能否打掉
  boolean breakable_wU; // 上边墙壁能否打掉
  boolean breakable_wD; // 下边墙壁能否打掉
  int breakableWalls;    // 可打破的墙的数量（等于directionList.size()）
  IntList directionList; // 可打破墙的列表集合
  // 初始化赋值
  Grids(int x, int y) {
    directionList = new IntList();
    init(x,y);
  }
  void init(int x, int y) {
    col = x;
    row = y;
    visited = false;
    searched = false;
    wL = true;
    wR = true;
    wU = true;
    wD = true;
    breakable_wL = true;
    breakable_wR = true;
    breakable_wU = true;
    breakable_wD = true;
    breakableWalls = 4;
    directionList.clear();
  }
  // 判断和更新当前格子的哪些墙可以敲
  int updateBreakableWalls() {
    // 格子的任何一堵墙如果已经不在，当然不能再敲掉一次
    if (!wL) breakable_wL = false;
    if (!wR) breakable_wR = false;
    if (!wU) breakable_wU = false;
    if (!wD) breakable_wD = false;
    
    if (col==0) breakable_wL = false;// 最左边一列的左墙不能敲掉
    else if (grid[col-1][row].visited) breakable_wL = false;// 如果左边格子已经访问过，不能打通这两个格子，下同
    if (col>=COLS-1) breakable_wR = false;// 最右边一列的右墙不能敲掉
    else if (grid[col+1][row].visited) breakable_wR = false;
    if (row==0) breakable_wU = false;// 最上边一行的顶墙不能敲掉
    else if (grid[col][row-1].visited) breakable_wU = false;
    if (row>=ROWS-1) breakable_wD = false;// 最下边一行的底墙不能敲掉
    else if (grid[col][row+1].visited) breakable_wD = false;
    
    directionList.clear();
    if (breakable_wL) directionList.append(GO_LEFT);
    if (breakable_wR) directionList.append(GO_RIGHT);
    if (breakable_wU) directionList.append(GO_UP);
    if (breakable_wD) directionList.append(GO_DOWN);
    breakableWalls = directionList.size();// 可砸墙数量
    return breakableWalls;
  }
  // 从当前格子移到下一个格子（随机砸墙 or 传送回去过的格子并继续砸墙）
  int moveNext() {
    updateBreakableWalls();// 刷新当前格子还能砸几面墙
    if (breakableWalls==0) { // 已经无墙可砸（走到尽头了），就传送到一个去过的格子里
      println("grid[",col,row,"] has no breakable walls. will transfer to a new place.");
      return jumpToAVisitedGridAndMoveNext();
    } else {// 有墙可砸，就随机砸一个
      int newGridIndex=-1;
      int rnd = int(random(0,breakableWalls));// 在可砸墙里随机找一个墙
      to = directionList.get(rnd);// 确定砸墙方向
      switch (to) {
        case GO_LEFT:
        wL = false;// 砸墙
        grid[col-1][row].wR = false;// 砸下一个格子的对应墙
        grid[col-1][row].visited = true;// 下个格子标记为已访问
        newGridIndex = COLS*(row) + (col-1);
        break;
        case GO_RIGHT:
        wR = false;// 砸墙
        grid[col+1][row].wL = false;// 砸下一个格子的对应墙
        grid[col+1][row].visited = true;// 下个格子标记为已访问
        newGridIndex = COLS*(row) + (col+1);
        break;
        case GO_UP:
        wU = false;// 砸墙
        grid[col][row-1].wD = false;// 砸下一个格子的对应墙
        grid[col][row-1].visited = true;// 下个格子标记为已访问
        newGridIndex = COLS*(row-1) + (col);
        break;
        case GO_DOWN:
        wD = false;// 砸墙
        grid[col][row+1].wU = false;// 砸下一个格子的对应墙
        grid[col][row+1].visited = true;// 下个格子标记为已访问
        newGridIndex = COLS*(row+1) + (col);
        break;
        default:
        println("不该出现这句打印");
        newGridIndex=-1;
        break;
      }
      println("grid[",col,row,"] has",breakableWalls,"breakable walls. choose to break",
        (to==GO_LEFT)?"LEFT":"",(to==GO_RIGHT)?"RIGHT":"",(to==GO_UP)?"UP":"",(to==GO_DOWN)?"DOWN":"","wall.");
      return newGridIndex;
    }
  }
  // 跳到一个访问过的格子
  int jumpToAVisitedGridAndMoveNext() {
    // 找到所有访问过的、且有墙可敲的格子（如果已经没有墙可以敲，返回-1）
    // 随机跳到那个格子，并敲一堵墙（moveNext的递归调用）
    g.visitedGridsList.clear();// 重置可跳转格子的集合列表
    for (int i=0;i<COLS;i++){
      for (int j=0;j<ROWS;j++){
        if (grid[i][j].visited && grid[i][j].updateBreakableWalls()>0){// 两个条件都要满足：1已访问过，2有墙可砸
          g.visitedGridsList.append(COLS*j+i);
        }
      }
    }
    //print(visitedGridsList);
    if (g.visitedGridsList.size()==0) {// 一个满足条件的格子都没有，说明迷宫已生成完毕
      println("nowhere to go! maze generation complete.");
      return -1;
    } else {// 传送到一个随机格子里
      int rnd = int(random(0,g.visitedGridsList.size()));
      //println("rnd=",rnd);
      int index = g.visitedGridsList.get(rnd);// 在可传送格子里随机选一个
      int newx = index % COLS;
      int newy = index / COLS;
      int newGridIndex = grid[newx][newy].moveNext();// 对该格子进行随机砸墙和移动
      return newGridIndex;// 返回新格子的结果
    }
  }
}
// 类：全局
class Global {
  int x;// 当前格子列数
  int y;// 当前格子行数
  IntList visitedGridsList;// 已访问过的、有墙可砸的格子的集合列表
  IntList pathSearchList;  // 寻路路径堆栈列表
  boolean generationComplete;    // 迷宫是否生成完毕
  boolean pathSearchingComplete; // 迷宫是否寻路完毕
  boolean showDirections; // 开关：是否显示每个格子的from和to（其实没啥用）
  boolean showPath;       // 开关：显示解法路径
  Global() {
    visitedGridsList = new IntList();
    pathSearchList = new IntList();
    showDirections = false;
    showPath = false;
    init();
  }
  void init(){
    x=startX;
    y=startY;
    generationComplete = false;
    pathSearchingComplete = false;
    visitedGridsList.clear();
    pathSearchList.clear();
  }
  // 生成算法的发动处，由draw每帧调用一次
  void update() {
    if (generationComplete) return;// 已经生成完了就没事了
    int index = grid[x][y].moveNext();
    if (index == -1) { // 满了，所有格子都已visit过，无处可去了，说明迷宫生成完了。
      generationComplete = true;
      findingPath();// 寻路，生成路径
      x=startX;y=startY;// 光标回到起点，准备让人走迷宫
    } else { // 可以移动
      x = xOfIndex(index);
      y = yOfIndex(index);
    }
  }
  // index <--> （x,y)的相互转换函数
  int indexOf(int x, int y) { return COLS*y + x; }  //x,y转index
  int xOfIndex(int index) { return index % COLS; }  //index转x
  int yOfIndex(int index) { return index / COLS; }  //index转y
  
  // 检查鼠标位置并返回相应值
  int checkMousePosition(int mousex, int mousey){
    int index=-1;
    int posx = int(mousex-BORDER_L);
    int posy = int(mousey-BORDER_U);
    // 格子
    if (posx>0 && posx<gW*COLS && posy>0 && posy<gH*ROWS){
      index = int(posy/gH)*COLS + int(posx/gW);// 返回位置代号（0 ~ ROWS*COLS-1）
    }
    return index;
  }
  // 判断两个相邻格子之间有没有墙
  boolean noWallBetween(int Ax, int Ay, int Bx, int By) {
    if (Ax<0 || Bx<0 || Ay<0 || By<0) return false;//界外
    if (Ax>=COLS || Bx>=COLS || Ay>=ROWS || By>=ROWS) return false;//界外
    if (abs(Ax-Bx)+abs(Ay-By)==1) {// 两个格子的坐标差之和必须为1才可能相邻
      if (Ax-Bx==1 && !grid[Ax][Ay].wL && !grid[Bx][By].wR) return true;
      if (Ax-Bx==-1 && !grid[Ax][Ay].wR && !grid[Bx][By].wL) return true;
      if (Ay-By==1 && !grid[Ax][Ay].wU && !grid[Bx][By].wD) return true;
      if (Ay-By==-1 && !grid[Ax][Ay].wD && !grid[Bx][By].wU) return true;
    } else {
      println("error input. the two grids [",Ax,Ay,"][",Bx,By,"] are not neighbours.");
    }
    return false;
  }
  // 开始寻路
  void findingPath() {
    println("start searching paths...");
    pathSearchingComplete = false;
    for (int i=0;i<COLS;i++)
      for (int j=0;j<ROWS;j++)
        grid[i][j].searched = false;// 重置搜索
    pathSearchList.clear();
    // 设置起点的from和终点的to，形成链条
    grid[startX][startY].from = GO_START;
    grid[endX][endY].to = GO_END;
    
    dfs(startX, startY);// 从起点处开始递归
  }
  // 迷宫寻路：深度优先算法DFS（递归调用）
  boolean dfs(int x, int y) {
    grid[x][y].searched = true;           // 标记这个格子为被搜索过
    pathSearchList.append(indexOf(x, y)); // 格子push入栈
    // 终于找到了目的地，逐层递归返回
    if (x==endX && y==endY) {
      println("path exit found! path length:",pathSearchList.size());
      pathSearchingComplete = true;
      return false;  // false代表已经找到了终点
    }
    if (x+1<COLS && !grid[x+1][y].searched && noWallBetween(x,y,x+1,y)) {// 向右探索
      grid[x][y].to = GO_RIGHT;
      grid[x+1][y].from = GO_LEFT;// 这两句只是为了showDirections好看，删掉不影响DFS运算，下同
      if (dfs(x+1,y)==false) return false;
    }
    if (x-1>=0 && !grid[x-1][y].searched && noWallBetween(x,y,x-1,y)) {// 向左探索
      grid[x][y].to = GO_LEFT;
      grid[x-1][y].from = GO_RIGHT;
      if (dfs(x-1,y)==false) return false;
    }
    if (y+1<ROWS && !grid[x][y+1].searched && noWallBetween(x,y,x,y+1)) {// 向下探索
      grid[x][y].to = GO_DOWN;
      grid[x][y+1].from = GO_UP;
      if (dfs(x,y+1)==false) return false;
    }
    if (y-1>=0 && !grid[x][y-1].searched && noWallBetween(x,y,x,y-1)) {// 向上探索
      grid[x][y].to = GO_UP;
      grid[x][y-1].from = GO_DOWN;
      if (dfs(x,y-1)==false) return false;
    }
    pathSearchList.remove(pathSearchList.size()-1); // pop出栈
    return true;
  }
}

// ########################### 事件event #############################//

void keyPressed() {
  if (key==CODED) {
    switch (keyCode) {
      case UP:          // 方向键移动
      if (g.generationComplete && !grid[g.x][g.y].wU) g.y--;
      break;
      case DOWN:
      if (g.generationComplete && !grid[g.x][g.y].wD) g.y++;
      break;
      case LEFT:
      if (g.generationComplete && !grid[g.x][g.y].wL) g.x--;
      break;
      case RIGHT:
      if (g.generationComplete && !grid[g.x][g.y].wR) g.x++;
      break;
      default:
      println("ERROR input.");
      break;
    }
  } else if (key == ' ') {    // 显示/隐藏解法路径
    g.showPath = !g.showPath;
  } else if (key == ENTER) {  // 加速迷宫生成
    println("Accelerate generating maze...");
    while (!g.generationComplete)  g.update();
  } else if (key == 'd') {    // 隐藏/显示每个格子的箭头方向
    g.showDirections = !g.showDirections;
  } else if (key == 'r') {    // 重启
    // 格子信息重置
    for (int i=0;i<COLS;i++)
      for (int j=0;j<ROWS;j++)
        grid[i][j].init(i,j);
    g.init();
    grid[startX][startY].visited = true;
  } else {
    println("error input.");
  }
}

void mousePressed() {
  if (!g.generationComplete) return;// 生成没结束，返回
  if (!g.pathSearchingComplete) return;// 寻路没结束，返回
  
  int index = g.checkMousePosition(mouseX, mouseY);
  if (index<0) return; // 在有效区域外，返回
  int x = g.xOfIndex(index);
  int y = g.yOfIndex(index);
  if (mouseButton==LEFT) {
    endX = x;
    endY = y;
    println("END point set to [",x,y,"].");
  } else if (mouseButton==RIGHT) {
    startX = x;
    startY = y;
    println("START point set to [",x,y,"].");
  }
  // 寻路，快速or慢速
  if (FAST_SEARCH_PATH) {
    g.findingPath();// dfs寻路函数
  } else {
    thread("findingPathThread"); // 用线程代替一次性递归
  }
  // 这里解释一下：其实用上面的普通寻路函数是完全可以的，而且一次性完成效率更高
  // 但我希望寻路过程能像迷宫生成过程一样慢一点，让人能看清楚这个算法是如何一步步搜索迷宫的】
  // 为了减慢速度，我特意另做了一个线程：findingPathThread以及对应的dfsThread函数，
  // 它们和findingPath()、dfs()的功能一模一样，唯一区别是它每次递归调用时会等待来自draw的信号
  // 这样就有效减慢了递归速度，让人能慢慢欣赏遍历寻路的全过程了（好无聊啊
}

void mouseMoved() {
  if (!g.generationComplete) return;// 生成没结束，返回
  
  int index = g.checkMousePosition(mouseX, mouseY);
  int pindex = g.checkMousePosition(pmouseX, pmouseY);
  if (index<0 || pindex<0) return; // 在有效区域外，返回

  int indexx = index % COLS;
  int indexy = index / COLS;
  int pindexx = pindex % COLS;
  int pindexy = pindex / COLS;
  if (pindexx!=g.x || pindexy!=g.y) return;// 鼠标之前不是在蓝方块上，返回
  if (pindexx==indexx && pindexy==indexy) return;// 鼠标坐标没实质变化，返回
  // 剩下的情形是鼠标从蓝方块上移到了一个新位置，那么要判断有没有墙，能否移动
  if (indexx-pindexx==1 && !grid[pindexx][pindexy].wR) g.x++;// 鼠标右移且右墙为空，则蓝方块向右移动一格，下同
  else if (indexx-pindexx==-1 && !grid[pindexx][pindexy].wL) g.x--;
  else if (indexy-pindexy==1 && !grid[pindexx][pindexy].wD) g.y++;
  else if (indexy-pindexy==-1 && !grid[pindexx][pindexy].wU) g.y--;
}


// --------------- thread ------------------- //
boolean feedThread = false;

void findingPathThread() {
  println("start searching paths in thread...");
  g.pathSearchingComplete = false;
  for (int i=0;i<COLS;i++)
    for (int j=0;j<ROWS;j++)
      grid[i][j].searched = false;// 重置搜索
  g.pathSearchList.clear();
  // 设置起点的from和终点的to，形成链条
  grid[startX][startY].from = GO_START;
  grid[endX][endY].to = GO_END;
  
  dfsThread(startX, startY);// 从起点处开始递归
}


// 迷宫寻路：深度优先算法DFS（递归调用）
boolean dfsThread(int x, int y) {
  while(feedThread==false) {// 每次draw后才能进行下一次dfs，目的在于看清楚寻路过程
    delay(1);
  }
  feedThread = false;
  grid[x][y].searched = true;           // 标记这个格子为被搜索过
  g.pathSearchList.append(g.indexOf(x, y)); // 格子push入栈
  // 终于找到了目的地，逐层递归返回
  if (x==endX && y==endY) {
    println("path exit found by dfsThread! path length:",g.pathSearchList.size());
    g.pathSearchingComplete = true;
    return false;  // false代表已经找到了终点
  }
  if (x+1<COLS && !grid[x+1][y].searched && g.noWallBetween(x,y,x+1,y)) {// 向右探索
    grid[x][y].to = GO_RIGHT;
    grid[x+1][y].from = GO_LEFT;// 这两句只是为了showDirections好看，删掉不影响DFS运算，下同
    if (dfsThread(x+1,y)==false) return false;
  }
  if (x-1>=0 && !grid[x-1][y].searched && g.noWallBetween(x,y,x-1,y)) {// 向左探索
    grid[x][y].to = GO_LEFT;
    grid[x-1][y].from = GO_RIGHT;
    if (dfsThread(x-1,y)==false) return false;
  }
  if (y+1<ROWS && !grid[x][y+1].searched && g.noWallBetween(x,y,x,y+1)) {// 向下探索
    grid[x][y].to = GO_DOWN;
    grid[x][y+1].from = GO_UP;
    if (dfsThread(x,y+1)==false) return false;
  }
  if (y-1>=0 && !grid[x][y-1].searched && g.noWallBetween(x,y,x,y-1)) {// 向上探索
    grid[x][y].to = GO_UP;
    grid[x][y-1].from = GO_DOWN;
    if (dfsThread(x,y-1)==false) return false;
  }
  g.pathSearchList.remove(g.pathSearchList.size()-1); // pop出栈
  return true;
}