Backtracking maze generation with Arduino

Last Updated or created 2023-04-19

As POC for the maze game.

Maze generation!

Make an initial cell the current cell
   mark it as visited
While there are unvisited cells
   If the current cell has any neighbours
   which have not been visited
         Choose randomly one of the unvisited neighbours
                Push the current cell to the stack
                Mark wall hole
                Make the chosen cell the current cell
                mark it as visited
        Else if stack is not empty
                Pop a cell from the stack
                Make it the current cell

This is my implementation of backtracking

The displaymatrix function is a implementation of different led mappings

Still have to decide where to place endpoint …
At 8,8 or at first stack pop?
Maybe both?

Code

#include <WEMOS_Matrix_LED.h>
#include <StackArray.h>

int directions[4]{};
int notalldone = 1;
int tmpx=0;
int tmpy=0;
int x = 1;
int y = 1;
MLED mled(5); //set intensity=5

int maze[8][8] = { 
  };

int displaymatrix[8][8] = { 
{ 0,1,2,3,4,5,6,7 },
{ 8,9,10,11,12,13,14,15 }, 
{16,17,18,19,20,21,22,23},
{24,25,26,27,28,29,30,31},
{32,33,34,35,36,37,38,39},
{40,41,42,43,44,45,46,47},
{48,49,50,51,52,53,54,55},
{56,57,58,59,60,61,62,63}
};

int visitmatrix[10][10] = { 
  1,1,1,1,1,1,1,1,1,1,
  1,0,0,0,0,0,0,0,0,1,
  1,0,0,0,0,0,0,0,0,1,
  1,0,0,0,0,0,0,0,0,1,
  1,0,0,0,0,0,0,0,0,1,
  1,0,0,0,0,0,0,0,0,1,
  1,0,0,0,0,0,0,0,0,1,
  1,0,0,0,0,0,0,0,0,1,
  1,0,0,0,0,0,0,0,0,1,
  1,1,1,1,1,1,1,1,1,1
  };

void setup() {
    Serial.begin(115200);
    randomSeed(analogRead(0));
    mazegen();
    drawmaze();
}

void mazegen(){
  visitmatrix[x][y]=1;       
  StackArray <int> rowStack; 
  StackArray <int> colStack;
        rowStack.push(x);
        colStack.push(y);
  while(notalldone == 1){    
     visitmatrix[x][y]=1;
        while(!rowStack.isEmpty()) {
        int count=0;
        //up
        if ( visitmatrix[x-1][y] == 0 ){
          directions[count]=1;
          count++;    
        }
        //right
        if ( visitmatrix[x][y+1] == 0 ){
          directions[count]=2;
          count++;    
        }
        //down
        if ( visitmatrix[x+1][y] == 0 ){
          directions[count]=4;
          count++;    
        }
        //left
        if ( visitmatrix[x][y-1] == 0 ){
          directions[count]=8;
          count++;    
        }  
        // no dir found
        if (count == 0 ) {

          mled.dot(x-1,y-1);
          mled.display();
          x = rowStack.pop();
          y = colStack.pop();

          Serial.println("popping ");
          } else {
          // count random direction
          int dir = directions[random(count)];
          Serial.println("push ");
          rowStack.push(x); 
          colStack.push(y);
          Serial.print("nr dir : "); 
          Serial.println(count);
          //delay(100);
          Serial.println(dir);
          // move 1,1 to 0,0
          mled.dot(x-1,y-1);
          mled.display();
          // set direction in maze, dit moet bit set worden
          int mybits = maze[x-1][y-1];
          int storedir = mybits | dir;
          maze[x-1][y-1] = storedir;
          if ( dir == 1){
          int getup = maze[x-2][y-1];
          int storedir = getup | 4;
          maze[x-2][y-1] = storedir;
          }
          if ( dir == 2){
          int getup = maze[x-1][y];
          int storedir = getup | 8;
          maze[x-1][y] = storedir;
          }
          if ( dir == 4){
          int getup = maze[x][y-1];
          int storedir = getup | 1;
          maze[x][y-1] = storedir;
          }
          if ( dir == 8){
          int getup = maze[x-1][y-2];
          int storedir = getup | 2;
          maze[x-1][y-2] = storedir;
          }


          
        //  maze[x-1][y-1] = dir;
          //set new square
          if (dir == 1){ x--; }
          if (dir == 2){ y++; }
          if (dir == 4){ x++; }
          if (dir == 8){ y--; }
          visitmatrix[x][y]=1;
          drawmaze();
          }
        }
        notalldone = 0;                                                  //#2
        // if found 0 in 10x10 matrix visited, do
        for(int checkx=0;checkx<10;checkx++){
          for(int checky=0;checky<10;checky++){
            if ( visitmatrix[checkx][checky] == 0 ){
              tmpx=x;
              tmpy=y;
              notalldone = 1;  
            }
          }
        }
   }
rowStack.push(tmpx); 
colStack.push(tmpy);
}



void drawmaze(){
  Serial.println("Generating done - Drawing");
  for(int ledx=0;ledx<8;ledx++)
  {
    for(int ledy=0;ledy<8;ledy++){
    Serial.print(maze[ledx][ledy]);  
    if ( maze[ledx][ledy] != 0 ) {
        mled.dot(ledx,ledy); // draw dot
        mled.display();
       // delay(50);
    }
      }  
    Serial.println("");
  }
  Serial.println("");
  delay(100);
}


void loop() {
}
Spread the love

Leave a Reply

Your email address will not be published. Required fields are marked *