Embedded Files
In another project, I created a way to control a 8x8 RGB Matrix using an Atari Joystick. While waiting for one of the components to arrive, I had an idea that a maze could be constructed on the RGB Matrix and a user could go through the maze with a joystick.
Most maze algorithms assume that the maze can have "paper-thin" walls. That is, that the occupiable spaces don't occupy the same amount of space as the walls. However, with the RGB Matrix the walls have to be represented by a whole LED being turned on. So in essence each LED is marked as a "wall" or as an "occupiable space"
I found this algorithm and rewrote it in processing (below)
void GenerateMaze()
{
int cNX = 0; int cNY = 0;
int cSX = 0; int cSY = 0;
int intDir = 0;
int intDone = 0;
boolean painted;
boolean blnBlocked = false;
do
{
do {
cSX = (int)random(1,(MAZE_X));
}
while (cSX % 2 == 0);
do {
cSY = (int)random(1,(MAZE_Y));
}
while (cSY % 2 == 0);
if (intDone == 0) {
blnMaze[cSX][cSY] = true;
}
if (blnMaze[cSX][cSY])
{
do
{
RandomDirections();
blnBlocked = true;
painted = false;
for(intDir = 0; (intDir < 4); intDir++)
{
if (!painted)
{
if (intDir == 0)
{
cNX = cSX + (cDir0X * 2);
cNY = cSY + (cDir0Y * 2);
}
if (intDir == 1)
{
cNX = cSX + (cDir1X * 2);
cNY = cSY + (cDir1Y * 2);
}
if (intDir == 2)
{
cNX = cSX + (cDir2X * 2);
cNY = cSY + (cDir2Y * 2);
}
if (intDir == 3)
{
cNX = cSX + (cDir3X * 2);
cNY = cSY + (cDir3Y * 2);
}
if (isfree(cNX, cNY))
{
blnMaze[cNX][cNY] = true;
if (intDir == 0 ){blnMaze[cSX+cDir0X][cSY+cDir0Y] = true;}
if (intDir == 1 ){blnMaze[cSX+cDir1X][cSY+cDir1Y] = true;}
if (intDir == 2 ){blnMaze[cSX+cDir2X][cSY+cDir2Y] = true;}
if (intDir == 3 ){blnMaze[cSX+cDir3X][cSY+cDir3Y] = true;}
cSX = cNX;
cSY = cNY;
blnBlocked = false;
intDone++;
painted = true;
}
}
}
}
while(!blnBlocked);
}
}
while ( ((intDone + 1) < (((MAZE_X - 1 ) * (MAZE_Y -1 )) / 4)));
}
void RandomDirections()
{
//randomSeed(analogRead(0));
int randdirection;
randdirection = (int)(random(0,4)); // 0,1,2,3
cDir0X = 0;
cDir0Y = 0;
cDir1X = 0;
cDir1Y = 0;
cDir2X = 0;
cDir2Y = 0;
cDir3X = 0;
cDir3Y = 0;
if (randdirection == 0)
{
cDir0X = -1;
cDir1X = 1;
cDir2Y = -1;
cDir3Y = 1;
}
if (randdirection == 1)
{
cDir3X = -1;
cDir2X = 1;
cDir1Y = -1;
cDir0Y = 1;
}
if (randdirection == 2)
{
cDir2X = -1;
cDir3X = 1;
cDir0Y = -1;
cDir1Y = 1;
}
if (randdirection == 3)
{
cDir1X = -1;
cDir0X = 1;
cDir3Y = -1;
cDir2Y = 1;
}
}
boolean isfree(int xpos, int ypos)
{
if ((xpos < MAZE_X -1) && (xpos >= 1) && (ypos < MAZE_Y -1) && (ypos >= 1))
{
return (!blnMaze[xpos][ypos]);
}
return false;
}
Since an 8x8 maze would be trivial to solve, I wanted to come up with an approach where several of these 8x8 pixel mazes (let's call them "tiles") could be stitiched together to form a much larger maze, and then when the cursor reached the edge of one tile we could slide the viewable part of the maze around.
Using a maze 21x21 pixels in size, which amounts to a 3x3 tile grid, I got the following result running:
Code for Rainbowduino and Arduino posted here.
Update 1/7/2014
I got a box at Michaels, stained it, and put some gloss glaze on it. I routed out a square hole with my Dremel and hooked up a 9v battery and toggle switch.
In addition, I wired the Atari button to the Arduino Reset switch, so that a new maze can be generated on button-push. Hours of fun!
Here's a video of the new features. The LEDs are too bright for the camera so I had to diffuse them by covering it.
Das a huge maze!
Through some trial and error I found that the maximum size I seem to be able to make is with an array of size 35x35. I presume this has something to do with Arduino single variable memory limitations, but I'm not sure. Regardless of where the limitation comes from, it results in a maze that's, at maximum, 5x5 in displayable tiles. A maze this size is somewhat challenging, and can take up to a minute or two to solve, but I wanted to be able to make an even larger maze.
If I create 4 mazes of size 35x35 independently and stitch them together, I can end up with a maze of 70x70 cells and 10x10 tiles. There are 2 challenges with this.
First, the "stitching" part. The maze algorithm, by default creates solid walls along the extreme North, South, East and West borders. In order for the Mazes to be stitched, we need to get rid of one of those walls on each border. Also, after we get rid of the wall, the other wall along that same border needs to have some of it's walls removed, clearing a path from one maze to the next. Side note: There are a couple additional rules we want to follow here when selecting the wall for demolition. For example, I don't want to demolish 2 cells that are adjacent, and I want to make sure that the wall I demolish leads me to an occupiable space in the next maze, not another wall.
Secondly, when the user is navigating the maze, and we're drawing the pixels on the 8x8 displayable LED Matrix, I need to know which rows and columns to pull maze wall data from. In the most complicated example (when the user is near the center of the maze) we will need to pull wall data from all 4 maze arrays. So I need an algorithm for this purpose as well.
Algorithm written, unable to implement...
I wrote the algorithm to generate stitch the 4 mazes together, but when I loaded it on the Arduino, it apparently comes down to overall memory limitations, not those for a single variable. Bummer, too, since I came up with this cool animation showing the steps of the algorithm. Maybe some more powerful microcontroller can be used to implement it in the future.
Algorithm
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
}
bool[,] blnMaze1;
bool[,] blnMaze2;
bool[,] blnMaze3;
bool[,] blnMaze4;
Random rnd = new Random(DateTime.Now.Millisecond);
private void Form1_Load(object sender, EventArgs e)
{
blnMaze1 = new bool[35, 35];
blnMaze2 = new bool[35, 35];
blnMaze3 = new bool[35, 35];
blnMaze4 = new bool[35, 35];
GenerateMaze(1);
GenerateMaze(2);
GenerateMaze(3);
GenerateMaze(4);
//remove leftmost column from mazes 2,4
for (int i = 0; i < 35; i++)
{
for (int j = 0; j < 35; j++)
{
if (j != 0)
{
blnMaze2[i, j - 1] = blnMaze2[i, j];
blnMaze4[i, j - 1] = blnMaze4[i, j];
}
}
}
//remove topmost row from mazes 3,4
for (int i = 0; i < 35; i++)
{
for (int j = 0; j < 35; j++)
{
if (i != 0)
{
blnMaze3[i - 1, j] = blnMaze3[i, j];
blnMaze4[i - 1, j] = blnMaze4[i, j];
}
}
}
//stitch mazes 1 and 2 together
for (int i = 0; i < 4; i++)
{
int DemolishWallIndex = rnd.Next(1, 34);
if ((blnMaze1[DemolishWallIndex, 34] == false) &&
(blnMaze1[DemolishWallIndex, 33] == true) &&
(blnMaze1[DemolishWallIndex + 1, 34] == false) &&
(blnMaze1[DemolishWallIndex - 1, 34] == false) &&
(blnMaze2[DemolishWallIndex, 0] == true))
blnMaze1[DemolishWallIndex, 34] = true;
else
i--;
}
//stitch mazes 1 and 3 together
for (int i = 0; i < 4; i++)
{
int DemolishWallIndex = rnd.Next(1, 34);
if ((blnMaze1[34, DemolishWallIndex] == false) &&
(blnMaze1[33, DemolishWallIndex] == true) &&
(blnMaze1[34, DemolishWallIndex + 1] == false) &&
(blnMaze1[34, DemolishWallIndex - 1] == false) &&
(blnMaze3[0, DemolishWallIndex] == true))
blnMaze1[34, DemolishWallIndex] = true;
else
i--;
}
//stitch mazes 3 and 4 together
for (int i = 0; i < 4; i++)
{
int DemolishWallIndex = rnd.Next(1, 34);
if ((blnMaze3[DemolishWallIndex, 34] == false) &&
(blnMaze3[DemolishWallIndex, 33] == true) &&
(blnMaze3[DemolishWallIndex + 1, 34] == false) &&
(blnMaze3[DemolishWallIndex - 1, 34] == false) &&
(blnMaze4[DemolishWallIndex, 0] == true))
blnMaze3[DemolishWallIndex, 34] = true;
else
i--;
}
//stitch mazes 2 and 4 together
for (int i = 0; i < 4; i++)
{
int DemolishWallIndex = rnd.Next(1, 34);
if ((blnMaze2[34, DemolishWallIndex] == false) && (blnMaze2[33, DemolishWallIndex] == true) && (blnMaze2[34, DemolishWallIndex + 1] == false) && (blnMaze2[34, DemolishWallIndex - 1] == false))
blnMaze2[34, DemolishWallIndex] = true;
else
i--;
}
//display...
for (int i = 0; i < 35; i++)
{
for (int j = 0; j < 35; j++)
{
if (blnMaze1[i, j] == false)
lblMaze.Text = lblMaze.Text + "#";
else
lblMaze.Text = lblMaze.Text + " ";
}
lblMaze.Text = lblMaze.Text + Environment.NewLine;
}
for (int i = 0; i < 35; i++)
{
for (int j = 0; j < 35; j++)
{
if (blnMaze2[i, j] == false)
lblMaze2.Text = lblMaze2.Text + "#";
else
lblMaze2.Text = lblMaze2.Text + " ";
}
lblMaze2.Text = lblMaze2.Text + Environment.NewLine;
}
for (int i = 0; i < 35; i++)
{
for (int j = 0; j < 35; j++)
{
if (blnMaze3[i, j] == false)
lblMaze3.Text = lblMaze3.Text + "#";
else
lblMaze3.Text = lblMaze3.Text + " ";
}
lblMaze3.Text = lblMaze3.Text + Environment.NewLine;
}
for (int i = 0; i < 35; i++)
{
for (int j = 0; j < 35; j++)
{
if (blnMaze4[i, j] == false)
lblMaze4.Text = lblMaze4.Text + "#";
else
lblMaze4.Text = lblMaze4.Text + " ";
}
lblMaze4.Text = lblMaze4.Text + Environment.NewLine;
}
}
int cDir0X;
int cDir0Y;
int cDir1X;
int cDir1Y;
int cDir2X;
int cDir2Y;
int cDir3X;
int cDir3Y;
int MAZE_X = 35;
int MAZE_Y = 35;
bool GetMazeCell(int MazeNbr, int X, int Y)
{
if (MazeNbr == 1)
return blnMaze1[X, Y];
else if (MazeNbr == 2)
return blnMaze2[X, Y];
else if (MazeNbr == 3)
return blnMaze3[X, Y];
else if (MazeNbr == 4)
return blnMaze4[X, Y];
return false;
}
void SetMazeCell(int MazeNbr, int X, int Y, bool value)
{
if (MazeNbr == 1)
blnMaze1[X, Y] = value;
else if (MazeNbr == 2)
blnMaze2[X, Y] = value;
else if (MazeNbr == 3)
blnMaze3[X, Y] = value;
else if (MazeNbr == 4)
blnMaze4[X, Y] = value;
}
bool[,] GetTileData(int YPos, int XPos, bool Use0X, bool Use0Y)
{
int YTile= -1;
int XTile = -1;
bool[,] Tiledata = new bool[8,8];
int TileI = 0;
int TileJ = 0;
if (XPos == 0) XPos++;
if (YPos == 0) YPos++;
if ((XPos <= 27) || ((XPos == 28) && (!Use0X)))
{
//branch 1
XTile = Convert.ToInt16(Math.Floor(Convert.ToDouble(XPos - 1) / 7.00) + (Use0X ? 1 : 0));
if ((YPos <= 27) || ((YPos == 28) && (!Use0Y)))
{
YTile = Convert.ToInt16(Math.Floor(Convert.ToDouble(YPos - 1) / 7.00) + (Use0Y ? 1 : 0));
for (int i = (YTile * 7); i < (((YTile + 1) * 7) + 1); i++)
{
TileJ = 0;
for (int j = (XTile * 7); j < (((XTile + 1) * 7) + 1); j++)
{
Tiledata[TileI, TileJ] = GetMazeCell(1,i,j);
TileJ++;
}
TileI++;
}
}
else if (((YPos <= 34) && (YPos >= 29)) ||
((YPos == 28) && (Use0Y)) ||
((YPos == 35) && (!Use0Y)))
{
YTile = 4;
for (int i = (YTile * 7); i < (((YTile + 1) * 7)); i++)
{
TileJ = 0;
for (int j = (XTile * 7); j < (((XTile + 1) * 7)+1); j++)
{
Tiledata[TileI, TileJ] = GetMazeCell(1, i, j);
TileJ++;
}
TileI++;
}
TileJ = 0;
for (int j = (XTile * 7); j < (XTile * 7) + 8; j++)
{
Tiledata[7, TileJ] = GetMazeCell(3, 0,j);
TileJ++;
}
}
else if (((YPos == 35) && (Use0Y)) || (YPos >= 36))
{
YTile = Convert.ToInt16(Math.Floor(Convert.ToDouble(YPos - 1) / 7.00) + (Use0Y ? 1 : 0));
YTile = YTile - 5;
for (int i = (YTile * 7); i < (((YTile + 1) * 7) + 1); i++)
{
TileJ = 0;
for (int j = (XTile * 7); j < (((XTile + 1) * 7) + 1); j++)
{
if (i <35)
Tiledata[TileI, TileJ] = GetMazeCell(3, i, j);
TileJ++;
}
TileI++;
}
}
}
else if (((XPos <= 34) && (XPos >= 29)) ||
((XPos == 28) && (Use0X)) ||
((XPos == 35) && (!Use0X)))
{
//branch 2
XTile = 4;
if ((YPos <= 27) || ((YPos == 28) && (!Use0Y)))
{
YTile = Convert.ToInt16(Math.Floor(Convert.ToDouble(YPos - 1) / 7.00) + (Use0Y ? 1 : 0));
for (int i = (YTile * 7); i < (((YTile + 1) * 7) + 1); i++)
{
TileJ = 0;
for (int j = (XTile * 7); j < (((XTile + 1) * 7)); j++)
{
Tiledata[TileI, TileJ] = GetMazeCell(1, i, j);
TileJ++;
}
TileI++;
}
TileJ = 0;
for (int j = (YTile * 7); j < (YTile * 7) + 8; j++)
{
Tiledata[TileJ, 7] = GetMazeCell(2, j, 0);
TileJ++;
}
}
else if (((YPos <= 34) && (YPos >= 29)) ||
((YPos == 28) && (Use0Y)) ||
((YPos == 35) && (!Use0Y)))
{
YTile = 4;
for (int i = (YTile * 7); i < (((YTile + 1) * 7)); i++)
{
TileJ = 0;
for (int j = (XTile * 7); j < (((XTile + 1) * 7) + 1); j++)
{
if (j != 35)
Tiledata[TileI, TileJ] = GetMazeCell(1, i, j);
TileJ++;
}
TileI++;
}
TileJ = 0;
for (int j = (XTile * 7); j < (XTile * 7) + 8; j++)
{
if (j != 35)
Tiledata[7, TileJ] = GetMazeCell(3, 0, j);
else
Tiledata[7, TileJ] = GetMazeCell(4,0,0);
TileJ++;
}
TileJ = 0;
for (int j = (YTile * 7); j < (YTile * 7) + 8; j++)
{
if (j != 35)
Tiledata[TileJ, 7] = GetMazeCell(2, j, 0);
TileJ++;
}
}
else if (((YPos == 35) && (Use0Y)) || (YPos >= 36))
{
YTile = Convert.ToInt16(Math.Floor(Convert.ToDouble(YPos - 1) / 7.00) + (Use0Y ? 1 : 0));
YTile = YTile - 5;
for (int i = (YTile * 7); i < (((YTile + 1) * 7) + 1); i++)
{
TileJ = 0;
for (int j = (XTile * 7); j < (((XTile + 1) * 7) + 1); j++)
{
if ((j != 35) && (i != 35))
Tiledata[TileI, TileJ] = GetMazeCell(3, i, j);
TileJ++;
}
TileI++;
}
TileJ = 0;
for (int j = (YTile * 7); j < (YTile * 7) + 8; j++)
{
if (j != 35)
Tiledata[TileJ, 7] = GetMazeCell(4,j,0);
TileJ++;
}
}
}
else if (((XPos == 35) && (Use0X)) || (XPos >= 36))
{
//branch 3
//refactor with branch 1
XTile = Convert.ToInt16(Math.Floor(Convert.ToDouble(XPos - 1) / 7.00) + (Use0X ? 1 : 0));
XTile = XTile - 5;
if ((YPos <= 27) || ((YPos == 28) && (!Use0Y)))
{
YTile = Convert.ToInt16(Math.Floor(Convert.ToDouble(YPos - 1) / 7.00) + (Use0Y ? 1 : 0));
for (int i = (YTile * 7); i < (((YTile + 1) * 7) + 1); i++)
{
TileJ = 0;
for (int j = (XTile * 7); j < (((XTile + 1) * 7) + 1); j++)
{
if (j < 35)
Tiledata[TileI, TileJ] = GetMazeCell(2, i, j);
TileJ++;
}
TileI++;
}
}
else if (((YPos <= 34) && (YPos >= 29)) ||
((YPos == 28) && (Use0Y)) ||
((YPos == 35) && (!Use0Y)))
{
YTile = 4;
for (int i = (YTile * 7); i < (((YTile + 1) * 7)); i++)
{
TileJ = 0;
for (int j = (XTile * 7); j < (((XTile + 1) * 7) + 1); j++)
{
if (j != 35)
Tiledata[TileI, TileJ] = GetMazeCell(2, i, j);
TileJ++;
}
TileI++;
}
TileJ = 0;
for (int j = (XTile * 7); j < (XTile * 7) + 8; j++)
{
if (j <=34)
Tiledata[7, TileJ] = GetMazeCell(4, 0, j);
TileJ++;
}
}
else if (((YPos == 35) && (Use0Y)) || (YPos >= 36))
{
YTile = Convert.ToInt16(Math.Floor(Convert.ToDouble(YPos - 1) / 7.00) + (Use0Y ? 1 : 0));
YTile = YTile - 5;
for (int i = (YTile * 7); i < (((YTile + 1) * 7) + 1); i++)
{
TileJ = 0;
for (int j = (XTile * 7); j < (((XTile + 1) * 7) + 1); j++)
{
if ((j < 35) && (i<35))
Tiledata[TileI, TileJ] = GetMazeCell(4, i, j);
TileJ++;
}
TileI++;
}
}
}
lblXTile.Text = XTile.ToString();
lblYTile.Text = YTile.ToString();
return Tiledata;
}
void GenerateMaze(int MazeNbr)
{
int cNX = 0; int cNY = 0;
int cSX = 0; int cSY = 0;
int intDir = 0;
int intDone = 0;
//c# boolean painted;
bool painted;
//c# boolean blnBlocked = false;
bool blnBlocked = false;
do
{
do
{
//c# cSX = (int)random(1, (MAZE_X));
cSX = (int)rnd.Next(1, (MAZE_X - 1));
}
while (cSX % 2 == 0);
do
{
//c# cSY = (int)random(1, (MAZE_Y));
cSY = (int)rnd.Next(1, (MAZE_Y - 1));
}
while (cSY % 2 == 0);
if (intDone == 0)
{
//c# blnMaze[cSX][cSY] = true;
SetMazeCell(MazeNbr, cSX, cSY, true);
}
//c# if (blnMaze[cSX][cSY])
if (GetMazeCell(MazeNbr, cSX, cSY))
{
do
{
RandomDirections();
blnBlocked = true;
painted = false;
for (intDir = 0; (intDir < 4); intDir++)
{
if (!painted)
{
if (intDir == 0)
{
cNX = cSX + (cDir0X * 2);
cNY = cSY + (cDir0Y * 2);
}
if (intDir == 1)
{
cNX = cSX + (cDir1X * 2);
cNY = cSY + (cDir1Y * 2);
}
if (intDir == 2)
{
cNX = cSX + (cDir2X * 2);
cNY = cSY + (cDir2Y * 2);
}
if (intDir == 3)
{
cNX = cSX + (cDir3X * 2);
cNY = cSY + (cDir3Y * 2);
}
if (isfree(cNX, cNY, MazeNbr))
{
//c# blnMaze[cNX][cNY] = true;
SetMazeCell(MazeNbr, cNX, cNY, true);
//c# if (intDir == 0) { blnMaze[cSX + cDir0X][cSY + cDir0Y] = true; }
if (intDir == 0) { SetMazeCell(MazeNbr,cSX + cDir0X, cSY + cDir0Y, true); }
//c# if (intDir == 1) { blnMaze[cSX + cDir1X][cSY + cDir1Y] = true; }
if (intDir == 1) { SetMazeCell(MazeNbr,cSX + cDir1X, cSY + cDir1Y, true); }
//c# if (intDir == 2) { blnMaze[cSX + cDir2X][cSY + cDir2Y] = true; }
if (intDir == 2) { SetMazeCell(MazeNbr, cSX + cDir2X, cSY + cDir2Y, true); }
//c# if (intDir == 3) { blnMaze[cSX + cDir3X][cSY + cDir3Y] = true; }
if (intDir == 3) { SetMazeCell(MazeNbr, cSX + cDir3X, cSY + cDir3Y, true); }
cSX = cNX;
cSY = cNY;
blnBlocked = false;
intDone++;
painted = true;
}
}
}
}
while (!blnBlocked);
}
}
while (((intDone + 1) < (((MAZE_X - 1) * (MAZE_Y - 1)) / 4)));
}
void RandomDirections()
{
//randomSeed(analogRead(0));
int randdirection;
//c# randdirection = (int)(random(0, 4)); // 0,1,2,3
randdirection = (int)(rnd.Next(0, 3)); // 0,1,2,3
cDir0X = 0;
cDir0Y = 0;
cDir1X = 0;
cDir1Y = 0;
cDir2X = 0;
cDir2Y = 0;
cDir3X = 0;
cDir3Y = 0;
if (randdirection == 0)
{
cDir0X = -1;
cDir1X = 1;
cDir2Y = -1;
cDir3Y = 1;
}
if (randdirection == 1)
{
cDir3X = -1;
cDir2X = 1;
cDir1Y = -1;
cDir0Y = 1;
}
if (randdirection == 2)
{
cDir2X = -1;
cDir3X = 1;
cDir0Y = -1;
cDir1Y = 1;
}
if (randdirection == 3)
{
cDir1X = -1;
cDir0X = 1;
cDir3Y = -1;
cDir2Y = 1;
}
}
bool isfree(int xpos, int ypos, int MazeNbr)
{
if ((xpos < MAZE_X - 1) && (xpos >= 1) && (ypos < MAZE_Y - 1) && (ypos >= 1))
{
//c# return (!blnMaze[xpos][ypos]);
if (MazeNbr == 1)
return (!blnMaze1[xpos, ypos]);
if (MazeNbr == 2)
return (!blnMaze2[xpos, ypos]);
if (MazeNbr == 3)
return (!blnMaze3[xpos, ypos]);
if (MazeNbr == 4)
return (!blnMaze4[xpos, ypos]);
}
return false;
}
private void button1_Click(object sender, EventArgs e)
{
lblTile.Text = "";
bool[,] Tiledata = GetTileData(Convert.ToInt16(textBox1.Text), Convert.ToInt16(textBox2.Text), chkUseZeroXforTile.Checked, chkUseZeroYForTile.Checked);
for (int i = 0; i < 8; i++)
{
for (int j = 0; j < 8; j++)
if (Tiledata[i, j] == false)
lblTile.Text = lblTile.Text + "#";
else
lblTile.Text = lblTile.Text + " ";
lblTile.Text = lblTile.Text + Environment.NewLine;
}
}
Here's a video of each of the steps:
1) Generate 4 mazes
2) Remove leftmost columns from mazes 2,4
3) Remove topmost rows from mazes 3,4
4) Stitch Mazes together and demolish legitimate walls
Page updated
Google Sites
Report abuse