# Recursive Maze Generation

Good morning everyone Currently I am attempting a small maze game, however I am tripping up at the first hurdle - generating a maze.
The following code is supposed to recursively create a maze, nothing more, nothing less. However, it randomly gives up with the emulator telling me that it has attempted to write to flash. (Attempt to write to flash (0x29c14c4) on PC=0x1728)

Can anyone seen an obvious error? a simple typo perhaps?

``````#include "Pokitto.h"
#include "smile.h"

// Globals for Maze
#define MAZEWIDTH 51    // Must be odd
#define MAZEHEIGHT 51   // Must be odd

uint8_t theMaze[MAZEHEIGHT*MAZEWIDTH];      // The maze itself
uint8_t mazeStack[MAZEHEIGHT*MAZEWIDTH];    // Stack for generating maze

// precalculated random list of possible directions
uint8_t posDirs[24][4]={
{0,1,2,3},{0,1,3,2},{0,2,1,3},{0,2,3,1},
{0,3,1,2},{0,3,2,1},{1,0,2,3},{1,0,3,2},
{1,2,0,3},{1,2,3,0},{1,3,0,2},{1,3,2,0},
{2,0,1,3},{2,0,3,1},{2,1,0,3},{2,1,3,0},
{2,3,0,1},{2,3,1,0},{3,0,1,2},{3,0,2,1},
{3,1,0,2},{3,1,2,0},{3,2,0,1},{3,2,1,0}
};

void recursion(int mx,int my){
Pokitto::Core::update();
wait_ms(25);

uint8_t directionSet = random(23);
for(uint8_t d=0; d<3; d++){
uint8_t direction = posDirs[directionSet][d];

switch(direction){
case 0: // up
if(my-2>0 && theMaze[mx+MAZEWIDTH*(my-2)] != 0){
my = my - 2;
theMaze[mx+MAZEWIDTH*my] = 0;       // next tile clear
theMaze[mx+MAZEWIDTH*(my+1)] = 0;   // path to next tie clear
Pokitto::Display::drawPixel(mx, my, 7);
Pokitto::Display::drawPixel(mx, my+1, 7);
recursion(mx,my);                   // keep trying
}
break;
case 1: // down
if(my+2<MAZEHEIGHT && theMaze[mx+MAZEWIDTH*(my+2)] != 0){
my = my + 2;
theMaze[mx+MAZEWIDTH*my] = 0;       // next tile clear
theMaze[mx+MAZEWIDTH*(my-1)] = 0;   // path to next tie clear
Pokitto::Display::drawPixel(mx, my, 7);
Pokitto::Display::drawPixel(mx, my-1, 7);
recursion(mx,my);                   // keep trying
}
break;
case 2: // left
if(mx-2>0 && theMaze[(mx-2)+MAZEWIDTH*my] != 0){
mx = mx - 2;
theMaze[mx+MAZEWIDTH*my] = 0;       // next tile clear
theMaze[(mx+1)+MAZEWIDTH*my] = 0;   // path to next tie clear
Pokitto::Display::drawPixel(mx, my, 7);
Pokitto::Display::drawPixel(mx+1, my, 7);
recursion(mx,my);                   // keep trying
}
break;
case 3: // right
if(mx+2<MAZEWIDTH && theMaze[(mx+2)+MAZEWIDTH*my] != 0){
mx = mx + 2;
theMaze[mx+MAZEWIDTH*my] = 0;       // next tile clear
theMaze[(mx-1)+MAZEWIDTH*my] = 0;   // path to next tie clear
Pokitto::Display::drawPixel(mx, my, 7);
Pokitto::Display::drawPixel(mx-1, my, 7);
recursion(mx,my);                   // keep trying
}
break;
default:
break;
}
}
}

void makeMaze(){
// fill maze with walls	to reset it
for(int y = 0; y< MAZEHEIGHT; y++){
for(int x = 0; x<MAZEWIDTH; x++){
theMaze[x+MAZEWIDTH*y] = 1;     // 1 = solid wall
}
}

// Start in random position and set that tile as open space
uint8_t startX = (random(MAZEWIDTH/2)*2)+1;
uint8_t startY = (random(MAZEHEIGHT/2)*2)+1;
theMaze[startX+MAZEWIDTH*startY] = 1;
uint8_t mx = startX;
uint8_t my = startY;
recursion(mx,my);
Pokitto::Display::drawPixel(mx, my, 5);
}

int main(){
using PC=Pokitto::Core;
using PD=Pokitto::Display;
PC::begin();
PD::persistence = true;
PD::invisiblecolor = 0;
srand(time(0));

makeMaze();
PD::drawBitmap(rand()%(PD::width-32), rand()%(PD::height-32), Smile);

while( PC::isRunning() ){
if( !PC::update() )
continue;

for(int y = 0; y< MAZEHEIGHT; y++){
for(int x = 0; x<MAZEWIDTH; x++){
Pokitto::Display::drawPixel(x, y, theMaze[x+MAZEWIDTH*y]);
}
}

//PD::drawBitmap(rand()%(PD::width-32), rand()%(PD::height-32), Smile);
}

return 0;
}
``````
1 Like

At a guess youâ€™re probably either overflowing the call stack (very likely with a recursive algorithm) or youâ€™ve got a buffer overrun in your maze indexing.
Or perhaps invalid indices are being passed to `drawPixel.

It would help to know what these arbitrary numbers mean and what the algorithm actually is.
E.g. Why is a `0` in the maze significant? Why `mx - 2` and not `mx - 1` in `recursion`?

Instead of using a 1D array you should probably just use a 2D array.
Then instead of writing stuff like `theMaze[x+MAZEWIDTH*y]` you can just do `maze[y][x]` and let the compiler handle the index flattening.

One potential bug, though itâ€™s probably unrelated to your problem:
The `my-2>0` in `if(my-2>0 && theMaze[mx+MAZEWIDTH*(my-2)] != 0){` should possibly be `>= 0`.

Havenâ€™t found the problem yet, but I did a bit of pruning in case it helps:

``````#include <Pokitto.h>

#include "smile.h"

#include <cstddef>
#include <cstdint>

// Maze dimensions (must be odd)
constexpr std::size_t mazeWidth = 51;
constexpr std::size_t mazeHeight = 51;

// The maze itself
std::uint8_t maze[mazeHeight][mazeWidth];

// Stack for generating maze
std::uint8_t mazeStack[mazeHeight][mazeWidth];

enum class Direction : std::uint8_t
{
Up = 0, Down = 1, Left = 2, Right = 3,
};

// precalculated random list of possible directions
constexpr std::uint8_t possibleDirections[24][4]
{
{0,1,2,3},{0,1,3,2},{0,2,1,3},{0,2,3,1},
{0,3,1,2},{0,3,2,1},{1,0,2,3},{1,0,3,2},
{1,2,0,3},{1,2,3,0},{1,3,0,2},{1,3,2,0},
{2,0,1,3},{2,0,3,1},{2,1,0,3},{2,1,3,0},
{2,3,0,1},{2,3,1,0},{3,0,1,2},{3,0,2,1},
{3,1,0,2},{3,1,2,0},{3,2,0,1},{3,2,1,0},
};

Direction getDirection(std::size_t set, std::size_t index)
{
return static_cast<Direction>(possibleDirections[set][index]);
}

void recursion(std::size_t x, std::size_t y)
{
Pokitto::Core::update();
wait_ms(25);

const std::size_t directionSet = static_cast<std::size_t>(std::rand() % 24);

for(std::size_t directionIndex = 0; directionIndex < 3; ++directionIndex)
{
const Direction direction = getDirection(directionSet, directionIndex);

switch(direction)
{
case Direction::Up:
{
const int yOff = (y - 2);

if((yOff > 0) && (maze[yOff][x] != 0))
{
maze[yOff][x] = 0;
maze[yOff + 1][x] = 0;

Pokitto::Display::drawPixel(x, yOff, 7);
Pokitto::Display::drawPixel(x, yOff + 1, 7);

recursion(x, yOff);
}
break;
}
case Direction::Down:
{
const int yOff = (y + 2);

if((yOff < mazeHeight) && (maze[yOff][x] != 0))
{
maze[yOff][x] = 0;
maze[yOff - 1][x] = 0;

Pokitto::Display::drawPixel(x, yOff, 7);
Pokitto::Display::drawPixel(x, yOff - 1, 7);

recursion(x, yOff);
}
break;
}
case Direction::Left:
{
const int xOff = (x - 2);

if((xOff > 0) && (maze[y][xOff] != 0))
{
maze[y][xOff] = 0;
maze[y][xOff + 1] = 0;

Pokitto::Display::drawPixel(xOff, y, 7);
Pokitto::Display::drawPixel(xOff + 1, y, 7);

recursion(xOff, y);
}
break;
}
case Direction::Right:
{
const int xOff = (x + 2);

if((xOff < mazeWidth) && (maze[y][xOff] != 0))
{
maze[y][xOff] = 0;
maze[y][xOff - 1] = 0;

Pokitto::Display::drawPixel(xOff, y, 7);
Pokitto::Display::drawPixel(xOff - 1, y, 7);

recursion(xOff, y);
}
break;
}
default:
break;
}
}
}

void fillMaze(uint8_t value)
{
// fill maze with walls	to reset it
for(std::size_t y = 0; y < mazeHeight; ++y)
for(std::size_t x = 0; x < mazeWidth; ++x)
maze[y][x] = value;
}

void makeMaze()
{
// Start in random position and set that tile as open space
std::size_t startX = (random(mazeWidth / 2) * 2) + 1;
std::size_t startY = (random(mazeHeight / 2) * 2) + 1;

maze[startY][startX] = 1;

recursion(startX, startY);
Pokitto::Display::drawPixel(startX, startY, 5);
}

void drawMaze()
{
for(std::size_t y = 0; y < mazeHeight; ++y)
for(std::size_t x = 0; x < mazeWidth; ++x)
Pokitto::Display::drawPixel(x, y, maze[y][x]);
}

int main()
{
using Pokitto::Core;
using Pokitto::Display;

Core::begin();

Display::persistence = true;
Display::invisiblecolor = 0;

std::srand(std::time(0));

makeMaze();

std::size_t x = (std::rand() % (Display::width - 32));
std::size_t y = (std::rand() % (Display::height - 32));

Display::drawBitmap(x, y, Smile);

while(Core::isRunning())
{
if(!Core::update())
continue;

drawMaze();

//Display::drawBitmap(rand()%(Display::width-32), rand()%(Display::height-32), Smile);
}

return 0;
}
``````

Running the code without the Pokitto parts on desktop didnâ€™t give any crashes,
so Iâ€™m now thinking itâ€™s more likely to be related to the Pokitto specific parts than the general parts.

One thing I notice, `recursion` exits almost immediately because you set precisely 1 tile to be non-zero and then start looking for non-zero tiles everywhere but the tile youâ€™re actually on, which means all the checks fail immediately and `recursion` exists without ever even calling itself.

So at least we can probably rule out stack overflow. `:P`

Had a quick try of your code and it works worse than mine. The walls end up crossing each other all over the place

 - nope, mine sometimes does that also

[edit 2]
The following nearly works. Problem 1 was the maze dimensions. I assumed they needed to be odd, but it works better with even. Problem 2 might be stack overflow, perhaps I need a non-recursive approachâ€¦

``````#include "Pokitto.h"
#include "smile.h"

// Globals for Maze
#define MAZEWIDTH 22    // Must be odd
#define MAZEHEIGHT 22   // Must be odd

int WALL = 0;
int FLOOR  = 1;

uint8_t theMaze[MAZEWIDTH][MAZEHEIGHT];      // The maze itself

// precalculated random list of possible directions
int posDirs[][4]={
{0,1,2,3}, {0,1,3,2}, {0,2,1,3}, {0,2,3,1},
{0,3,1,2}, {0,3,2,1}, {1,0,2,3}, {1,0,3,2},
{1,2,0,3}, {1,2,3,0}, {1,3,0,2}, {1,3,2,0},
{2,0,1,3}, {2,0,3,1}, {2,1,0,3}, {2,1,3,0},
{2,3,0,1}, {2,3,1,0}, {3,0,1,2}, {3,0,2,1},
{3,1,0,2}, {3,1,2,0}, {3,2,0,1}, {3,2,1,0}
};

int getMaze(uint8_t x,uint8_t y){
return theMaze[x][y];
}

void putMaze(int x, int y, int pix){
theMaze[x][y] = pix;
}

void recursion(int mx,int my){
Pokitto::Core::update();

uint8_t directionSet = random(23);
for(uint8_t d=0; d<4; d++){
uint8_t direction = posDirs[directionSet][d];

char tempText[10];
sprintf(tempText, "%d ",direction);
Pokitto::Display::setColor(0);
Pokitto::Display::fillRect(80,0,8,8);
Pokitto::Display::setColor(1);
Pokitto::Display::print(80,0, tempText);
//wait_ms(250);
Pokitto::Display::drawPixel(mx, my, 7);

switch(direction){
case 0: // up
if(my<2)break;
if(getMaze(mx,my-2) == WALL){
my -= 2;
putMaze(mx,my,FLOOR);       // next tile clear
putMaze(mx,my+1,FLOOR);   // path to next tie clear
Pokitto::Display::drawPixel(mx, my, 7);
Pokitto::Display::drawPixel(mx, my+1, 7);
recursion(mx,my);                   // keep trying
}
break;
case 1: // down
if(my>MAZEHEIGHT-2)break;
if(getMaze(mx,my+2) == WALL){
my += 2;
putMaze(mx,my,FLOOR);       // next tile clear
putMaze(mx,my-1,FLOOR);   // path to next tie clear
Pokitto::Display::drawPixel(mx, my, 7);
Pokitto::Display::drawPixel(mx, my-1, 7);
recursion(mx,my);                   // keep trying
}
break;
case 2: // left
if(mx<2)break;
if(getMaze(mx-2,my) == WALL){
mx -= 2;
putMaze(mx,my,FLOOR);       // next tile clear
putMaze(mx+1,my,FLOOR);   // path to next tie clear
Pokitto::Display::drawPixel(mx, my, 7);
Pokitto::Display::drawPixel(mx+1, my, 7);
recursion(mx,my);                   // keep trying
}
break;
case 3: // right
if(mx>MAZEWIDTH-2)break;
if(getMaze(mx+2,my) == WALL){
mx += 2;
putMaze(mx,my,FLOOR);       // next tile clear
putMaze(mx-1,my,FLOOR);   // path to next tie clear
Pokitto::Display::drawPixel(mx, my, 7);
Pokitto::Display::drawPixel(mx-1, my, 7);
recursion(mx,my);                   // keep trying
}
break;
default:
break;
}
}
}

void makeMaze(){
// fill maze with walls	to reset it
for(int y = 0; y< MAZEHEIGHT; y++){
for(int x = 0; x<MAZEWIDTH; x++){
putMaze(x,y,WALL);     // 1 = solid wall
}
}

// Start in random position and set that tile as open space
uint8_t startX = (random(MAZEWIDTH/2)*2)+1;
uint8_t startY = (random(MAZEHEIGHT/2)*2)+1;
//putMaze(startX,startY,FLOOR);
uint8_t mx = startX;
uint8_t my = startY;
recursion(mx,my);
Pokitto::Display::drawPixel(mx, my, 5);
Pokitto::Display::setColor(1);
Pokitto::Display::print(80,8, "Finished");
}

int main(){
using PC=Pokitto::Core;
using PD=Pokitto::Display;
PC::begin();
PD::persistence = true;
PD::invisiblecolor = 0;
srand(time(0));

makeMaze();
PD::drawBitmap(rand()%(PD::width-32), rand()%(PD::height-32), Smile);

while( PC::isRunning() ){
if( !PC::update() )
continue;

for(int y = 0; y< MAZEHEIGHT; y++){
for(int x = 0; x<MAZEWIDTH; x++){
Pokitto::Display::drawPixel(x+MAZEWIDTH+1, y, getMaze(x,y));
}
}
}

return 0;
}
``````

While trying to write a non-recursive maze generator, I have nearly Frisbeed my laptop out of the window and was very close to throwing the mouse through the screen.

All my changes should be functionally equivalent to your existing code.

I thought maybe replacing `random` (a non-standard Arduino function) with `std::rand` (a standard function) might not be, but I checked the Pokitto library and it turns out that `random` is implemented in terms of `std::rand`, hence they are functionally equivalent.

Pretty much any recursive algorithm can be rewritten as an iterative algorithm.

For something like this youâ€™d have to replace the implicit call stack with an explicit stack.
Either `std::stack` if you think you can get away with using dynamic memory,
or a custom stack that allocates a fixed-size buffer so you have a well-defined stopping point.

You might also want to consider other algorithms.
There might not be enough memory for something graph based,
but something that incorporates hashing as a means to save memory might help.

What exactly is the algorithm youâ€™re using? A drunk walk of some kind?
Is there an article youâ€™re following or a reference to the algorithm, or are you just winging it?

Some notes about performance and safetyâ€¦

Youâ€™re probably better off putting the height first and the width second.

Why?...

When you iterate through a multidimensional array, itâ€™s generally cheaper for the innermost loop to index the rightmost dimension and the outermost loop to index the leftmost dimension.

Thatâ€™s because for an array `Type array[z_size][y_size][x_size]`, the offset from the start is calculated as `(z * (y_size * x_size)) + (y * x_size) + x`,
so the rightmost dimension always increments by `sizeof(Type)` whereas the other dimenions are much larger leaps.

Having the rightmost dimension in the innermost loop allows two specific optimisations.
Either the calculated address can be cached, like so:

``````for(std::size_t z = 0; z < z_size; ++z)
{
for(std::size_t y = 0; y < y_size; ++y)
{
Type * x_base = &array[z][y];

for(std::size_t x = 0; x < x_size; ++x)
{
// Only one offset to calculate each time
Type value = x_base[x];

}
}
}
``````

Or the compiler might be smart enough to see that the nested loops are effectively doing a linear iteration though the array and produce something like:

``````Type * array_pointer = &array[0][0][0];

for(std::size_t z = 0; z < z_size; ++z)
for(std::size_t y = 0; y < y_size; ++y)
for(std::size_t x = 0; x < x_size; ++x)
{
Type value = *array_pointer;

// ...

++array_pointer;
}
``````

Or if youâ€™re really lucky and only the inner loop contains code then the compiler might be allowed to go a step further and produce something like this:

``````Type * array_pointer = &array[0][0][0];
Type * const array_end = &array[z_size][y_size][x_size];

while(array_pointer < array_end)
{
Type value = *array_pointer;

// ...

++array_pointer;
}
``````

Of course, you can also do this manually.

(As always, such optimisations depend on whatâ€™s best for the target platform and what the compilerâ€™s legally allowed to do without altering the semantics of the program.)

The other alternative is to stick to `[width][height]` and make sure you always iterate `x` in the outer loop and `y` in the inner loop, but thatâ€™s the opposite of whatâ€™s expected (and thus violates the principle of least astonishment).

`std::sprintf` is an expensive (and unsafe) waste of time,
youâ€™re much better off doing `Pokitto::Display::print(80, 0, direction);` instead.

sprintf does a number of things that make it inefficient and unsafe

`sprintf`:

• Wastes time and effort by having to parse the format string
• It does this because it comes from C, which doesnâ€™t have function overloading, so thereâ€™s no way to efficiently detect the type as there is in C++. `Pokitto::Display`'s `print` and `write` are overloaded so they automatically infer type and print correctly (and almost certainly more efficiently).
• Wastes time and effort by tracking the length of the generated string, which it returns, so the result then has to be silently discarded
• Can overflow the buffer you pass it because it doesnâ€™t know how long the buffer is. This is a very easy way to clobber memory and silently introduce bugs.
• Needs a buffer in the first place
• Pokittoâ€™s drawing functions just print the characters directly onto the screen, one at a time, meaning no buffer is needed, which is more efficient

Also, while itâ€™s not an issue on Pokitto, `printf` & co are known security risks.

I just found out that there a faster, easier, stackless, recusrivless maze generation!
Binary tree generation bases the passages of the maze entirely on those in the row already randomised. It might not look as ransom as other types of maze, but its more than good enough for what Iâ€™m going to use it for!

``````#include "Pokitto.h"
#include "smile.h"

// Globals for Maze
#define MAZEWIDTH 55    // Must be odd
#define MAZEHEIGHT 45   // Must be odd

int WALL = 1;
int FLOOR  = 0;

uint8_t theMaze[MAZEWIDTH][MAZEHEIGHT];      // The maze itself

int getMaze(int x,int y){
return theMaze[x][y];
}

void putMaze(int x, int y, int pix){
theMaze[x][y] = pix;
}

void binaryTreeMaze(){
// fill maze with walls to reset it
for(int y = 0; y< MAZEHEIGHT; y++){
for(int x = 0; x<MAZEWIDTH; x++){
putMaze(x,y,WALL);
if((x==1 || x==MAZEWIDTH-2) && y != 0 && y != MAZEHEIGHT-1) putMaze(x,y,FLOOR);
if((y==1 || y==MAZEHEIGHT-2) && x != 0 && x != MAZEWIDTH-1) putMaze(x,y,FLOOR);
}
}

for(int y = 3; y < MAZEHEIGHT; y+=2){
for(int x = 3; x < MAZEWIDTH; x+=2){
putMaze(x,y,FLOOR);
if(getMaze(x-1,y)==WALL && getMaze(x,y-1)==WALL){
int number = random(100)/50;
if(number == 0){
putMaze(x,y-1,FLOOR);
}else{
putMaze(x-1,y,FLOOR);
}
}
}
}

}

int main(){
using PC=Pokitto::Core;
using PD=Pokitto::Display;
PC::begin();
PD::persistence = true;
PD::invisiblecolor = 0;
srand(time(0));

binaryTreeMaze();

while( PC::isRunning() ){
if( !PC::update() )
continue;

for(int y = 0; y< MAZEHEIGHT; y++){
for(int x = 0; x<MAZEWIDTH; x++){
Pokitto::Display::drawPixel(x, y, getMaze(x,y));
}
}
}

return 0;
}``````
3 Likes

Thereâ€™s lots of different maze generation techniques.
Primâ€™s, Kruskalâ€™s, recursive subdividsion, cellular automataâ€¦

The PCG wiki has a few good links:
http://pcg.wikidot.com/pcg-algorithm:maze

Donâ€™t forget to keep everything organised,
and use scoped enumerations and constexpr variables instead of raw integers and macros:

``````#include "Pokitto.h"
#include "smile.h"

#include <cstddef>
#include <cstdint>

// Globals for Maze (must be odd)
constexpr std::size_t mazeWidth = 55;
constexpr std::size_t mazeHeight = 45;

enum class MazeTile : std::uint8_t
{
Floor,
Wall,
};

// The maze itself
MazeTile theMaze[mazeHeight][mazeWidth];

MazeTile getMaze(std::size_t x, std::size_t y)
{
return theMaze[y][x];
}

void putMaze(std::size_t x, std::size_t y, MazeTile tile)
{
theMaze[y][x] = tile;
}

// Uses binary tree generation
void generateMaze()
{
// Fill maze with walls to reset it
for(std::size_t y = 0; y < mazeHeight; ++y)
for(std::size_t x = 0; x < mazeWidth; ++x)
{
putMaze(x,y,MazeTile::Wall);

if(((x == 1) || (x == (mazeWidth - 2))) && ((y != 0) && (y != (mazeHeight - 1))))
putMaze(x, y, MazeTile::Floor);

if(((y == 1) || (y == mazeHeight - 2)) && ((x != 0) && (x != (mazeWidth - 1))))
putMaze(x, y, MazeTile::Floor);
}

for(std::size_t y = 3; y < mazeHeight; y += 2)
for(std::size_t x = 3; x < mazeWidth; x += 2)
{
putMaze(x, y, MazeTile::Floor);

if((getMaze(x - 1, y) == MazeTile::Wall) && (getMaze(x, y - 1) == MazeTile::Wall))
{
const int randomNumber = (std::rand() % 2);

if(randomNumber == 0)
putMaze(x, y - 1, MazeTile::Floor);
else
putMaze(x - 1, y, MazeTile::Floor);
}
}

}

constexpr std::uint8_t getColour(MazeTile tile)
{
return static_cast<std::uint8_t>(tile);
}

void drawMaze()
{
for(std::size_t y = 0; y < mazeHeight; ++y)
for(std::size_t x = 0; x < mazeWidth; ++x)
Pokitto::Display::drawPixel(x, y, getColour(getMaze(x,y)));
}

int main()
{
using Pokitto::Core;
using Pokitto::Display;

Core::begin();
Core::initRandom();

Display::persistence = true;
Display::invisiblecolor = 0;

generateMaze();

while(Core::isRunning())
{
if(!Core::update())
continue;

drawMaze();
}

return 0;
}
``````

Macros arenâ€™t globals.

I think I will use the following instead. Larger mazes take a lot longer to create, but as I only want about 45x45 max it will do just fine.

No recursion, no stack just blind luck!

``````#include "Pokitto.h"

// Globals for Maze
#define MAZEWIDTH 45    // Must be odd
#define MAZEHEIGHT 45   // Must be odd

// Wall and floor colours
#define WALL 1
#define FLOOR  0

// The maze
uint8_t theMaze[MAZEWIDTH][MAZEHEIGHT];

// read pixel from maze array
int getMaze(int x,int y){
return theMaze[x][y];
}

// set pixel in maze and alto plot to screen
void putMaze(int x, int y, int pix){
theMaze[x][y] = pix;
Pokitto::Display::drawPixel(x, y, pix);
Pokitto::Core::update();
}

// draw the full maze to screen
void drawMaze(){
for(int y1 = 0; y1< MAZEHEIGHT; y1++){
for(int x1 = 0; x1<MAZEWIDTH; x1++){
Pokitto::Display::drawPixel(x1, y1, getMaze(x1,y1));
}
}
}

// randomly plot a maze using pure luck to complete it.
void stacklessMaze(){
for(int y = 0; y< MAZEHEIGHT; y++){
for(int x = 0; x<MAZEWIDTH; x++){
Pokitto::Display::drawPixel(x, y, WALL);
putMaze(x,y,WALL);
}
}

int mX = 1+random(MAZEWIDTH/2)*2;
int mY = 1+random(MAZEHEIGHT/2)*2;
putMaze(mX,mY,FLOOR);

bool mazeDone = false;
while (mazeDone == false){
for(int i=0; i<16; i++){
int oldX = mX;
int oldY = mY;
switch(random(100)/25){
case 0:
if(mX+2<MAZEWIDTH){mX+=2;}
break;
case 1:
if(mX-2>0){mX-=2;}
break;
case 2:
if(mY+2<MAZEHEIGHT){mY+=2;}
break;
case 3:
if(mY-2>0){mY-=2;}
break;
}
if(getMaze(mX,mY)==WALL){
putMaze(mX,mY,FLOOR);
putMaze((oldX+mX)/2,(oldY+mY)/2,FLOOR);
}

mazeDone = true;
for(int y = 1; y< MAZEHEIGHT-1; y+=2){
for(int x = 1; x<MAZEWIDTH-1; x+=2){
if(getMaze(x,y)==WALL){mazeDone = false;}
}
}
}
}

}

int main(){
using PC=Pokitto::Core;
using PD=Pokitto::Display;
PC::begin();
PD::persistence = true;
PD::invisiblecolor = -1;
srand(time(0));

stacklessMaze();
Pokitto::Display::setColor(1);
Pokitto::Display::print(0,MAZEHEIGHT+1, "Finished!");
Pokitto::Core::update();

while( PC::isRunning() ){
if( !PC::update() )
continue;

}

return 0;
}``````
3 Likes