Skip to content
Permalink
master
Switch branches/tags
Go to file
1 contributor

Users who have contributed to this file

/*
OneLoneCoder.com - Recursive Backtracker Maze Algorithm
"Get lost..." - @Javidx9
License
~~~~~~~
Copyright (C) 2018 Javidx9
This program comes with ABSOLUTELY NO WARRANTY.
This is free software, and you are welcome to redistribute it
under certain conditions; See license for details.
Original works located at:
https://www.github.com/onelonecoder
https://www.onelonecoder.com
https://www.youtube.com/javidx9
GNU GPLv3
https://github.com/OneLoneCoder/videos/blob/master/LICENSE
From Javidx9 :)
~~~~~~~~~~~~~~~
Hello! Ultimately I don't care what you use this for. It's intended to be
educational, and perhaps to the oddly minded - a little bit of fun.
Please hack this, change it and use it in any way you see fit. You acknowledge
that I am not responsible for anything bad that happens as a result of
your actions. However this code is protected by GNU GPLv3, see the license in the
github repo. This means you must attribute me if you use it. You can view this
license here: https://github.com/OneLoneCoder/videos/blob/master/LICENSE
Cheers!
Background
~~~~~~~~~~
I really like perfect algorithms. This one shows how to generate a maze that guarantees
all cells can reach all other cells, it just may take some time to get there. I introduce
stacks, and show how the algorithm generates the maze visually.
Author
~~~~~~
Twitter: @javidx9
Blog: www.onelonecoder.com
Video:
~~~~~~
https://youtu.be/Y37-gB83HKE
Last Updated: 10/07/2017
*/
#include <iostream>
#include <stack>
using namespace std;
#include "olcConsoleGameEngine.h"
class OneLoneCoder_Maze : public olcConsoleGameEngine
{
public:
OneLoneCoder_Maze()
{
m_sAppName = L"MAZE";
}
private:
int m_nMazeWidth;
int m_nMazeHeight;
int *m_maze;
// Some bit fields for convenience
enum
{
CELL_PATH_N = 0x01,
CELL_PATH_E = 0x02,
CELL_PATH_S = 0x04,
CELL_PATH_W = 0x08,
CELL_VISITED = 0x10,
};
// Algorithm variables
int m_nVisitedCells;
stack<pair<int, int>> m_stack; // (x, y) coordinate pairs
int m_nPathWidth;
protected:
// Called by olcConsoleGameEngine
virtual bool OnUserCreate()
{
// Maze parameters
m_nMazeWidth = 40;
m_nMazeHeight = 25;
m_maze = new int[m_nMazeWidth * m_nMazeHeight];
memset(m_maze, 0x00, m_nMazeWidth * m_nMazeHeight * sizeof(int));
m_nPathWidth = 3;
// Choose a starting cell
int x = rand() % m_nMazeWidth;
int y = rand() % m_nMazeHeight;
m_stack.push(make_pair(x, y));
m_maze[y * m_nMazeWidth + x] = CELL_VISITED;
m_nVisitedCells = 1;
return true;
}
// Called by olcConsoleGameEngine
virtual bool OnUserUpdate(float fElapsedTime)
{
// Slow down for animation
this_thread::sleep_for(10ms);
// Little lambda function to calculate index in a readable way
auto offset = [&](int x, int y)
{
return (m_stack.top().second + y) * m_nMazeWidth + (m_stack.top().first + x);
};
// Do Maze Algorithm
if (m_nVisitedCells < m_nMazeWidth * m_nMazeHeight)
{
// Create a set of unvisted neighbours
vector<int> neighbours;
// North neighbour
if (m_stack.top().second > 0 && (m_maze[offset(0, -1)] & CELL_VISITED) == 0)
neighbours.push_back(0);
// East neighbour
if (m_stack.top().first < m_nMazeWidth - 1 && (m_maze[offset(1, 0)] & CELL_VISITED) == 0)
neighbours.push_back(1);
// South neighbour
if (m_stack.top().second < m_nMazeHeight - 1 && (m_maze[offset(0, 1)] & CELL_VISITED) == 0)
neighbours.push_back(2);
// West neighbour
if (m_stack.top().first > 0 && (m_maze[offset(-1, 0)] & CELL_VISITED) == 0)
neighbours.push_back(3);
// Are there any neighbours available?
if (!neighbours.empty())
{
// Choose one available neighbour at random
int next_cell_dir = neighbours[rand() % neighbours.size()];
// Create a path between the neighbour and the current cell
switch (next_cell_dir)
{
case 0: // North
m_maze[offset(0, -1)] |= CELL_VISITED | CELL_PATH_S;
m_maze[offset(0, 0)] |= CELL_PATH_N;
m_stack.push(make_pair((m_stack.top().first + 0), (m_stack.top().second - 1)));
break;
case 1: // East
m_maze[offset(+1, 0)] |= CELL_VISITED | CELL_PATH_W;
m_maze[offset( 0, 0)] |= CELL_PATH_E;
m_stack.push(make_pair((m_stack.top().first + 1), (m_stack.top().second + 0)));
break;
case 2: // South
m_maze[offset(0, +1)] |= CELL_VISITED | CELL_PATH_N;
m_maze[offset(0, 0)] |= CELL_PATH_S;
m_stack.push(make_pair((m_stack.top().first + 0), (m_stack.top().second + 1)));
break;
case 3: // West
m_maze[offset(-1, 0)] |= CELL_VISITED | CELL_PATH_E;
m_maze[offset( 0, 0)] |= CELL_PATH_W;
m_stack.push(make_pair((m_stack.top().first - 1), (m_stack.top().second + 0)));
break;
}
m_nVisitedCells++;
}
else
{
// No available neighbours so backtrack!
m_stack.pop();
}
}
// === DRAWING STUFF ===
// Clear Screen by drawing 'spaces' everywhere
Fill(0, 0, ScreenWidth(), ScreenHeight(), L' ');
// Draw Maze
for (int x = 0; x < m_nMazeWidth; x++)
{
for (int y = 0; y < m_nMazeHeight; y++)
{
// Each cell is inflated by m_nPathWidth, so fill it in
for (int py = 0; py < m_nPathWidth; py++)
for (int px = 0; px < m_nPathWidth; px++)
{
if (m_maze[y * m_nMazeWidth + x] & CELL_VISITED)
Draw(x * (m_nPathWidth + 1) + px, y * (m_nPathWidth + 1) + py, PIXEL_SOLID, FG_WHITE); // Draw Cell
else
Draw(x * (m_nPathWidth + 1) + px, y * (m_nPathWidth + 1) + py, PIXEL_SOLID, FG_BLUE); // Draw Cell
}
// Draw passageways between cells
for (int p = 0; p < m_nPathWidth; p++)
{
if (m_maze[y * m_nMazeWidth + x] & CELL_PATH_S)
Draw(x * (m_nPathWidth + 1) + p, y * (m_nPathWidth + 1) + m_nPathWidth); // Draw South Passage
if (m_maze[y * m_nMazeWidth + x] & CELL_PATH_E)
Draw(x * (m_nPathWidth + 1) + m_nPathWidth, y * (m_nPathWidth + 1) + p); // Draw East Passage
}
}
}
// Draw Unit - the top of the stack
for (int py = 0; py < m_nPathWidth; py++)
for (int px = 0; px < m_nPathWidth; px++)
Draw(m_stack.top().first * (m_nPathWidth + 1) + px, m_stack.top().second * (m_nPathWidth + 1) + py, 0x2588, FG_GREEN); // Draw Cell
return true;
}
};
int main()
{
// Seed random number generator
srand(clock());
// Use olcConsoleGameEngine derived app
OneLoneCoder_Maze game;
game.ConstructConsole(160, 100, 8, 8);
game.Start();
return 0;
}