%% Identification
% Science Dude
% Maze generator
% September 25, 2019
%
%% Code
% Generate a maze and plot it

%% Clean up
clc
close all
clear
drawnow

%% Parameters
% Number of nodes in width or height
N = 8;

% Bearing diameter, mm
bearing_diameter = 4.7;

% Set the random number generator seed
rng(6);

%% Create the maze
% Convention
% The maze is made up of locations, with bottom left as 0, and top right as
% the largest number, i.e.
% (N * N - N), (N * N - N + 1), ..., (N * N - 1)
% ...
% N, (N + 1), (N + 2), ..., (N + N - 1)
% 0, 1,       2,       ..., (N - 1)

% The walls
W = ones(N * N, 4);

% List of visited nodes
the_list = -1 * ones(N * N, 1);
% First entry is "0" which is the bottom left corner in X/Y coordinates
the_list(1) = 0;
% Location of adding to the list is the first entry
add_loc_list = 1;
% Location of tracking in the list is the first entry
loc_list = 1;

% Create a figure to visualize as the maze is created
figure

x = mod(0, N);
y = floor(0 / N);
            
plot(x, y, 'go');
axis([-1, N, -1, N]);
axis square
hold on

while add_loc_list < (N * N)
    
    % The current location
    current_loc = the_list(loc_list);
        
    % Check if you are at a dead end
    dead_end = 0;
    % If you are at a corner, perform the dead end check
    if current_loc == 0 % Bottom left corner
        if any(the_list == 1) && any(the_list == N)
            dead_end = 1;
        end
    end    
    if current_loc == (N - 1) % Bottom right corner
        if any(the_list == (N - 2)) && any(the_list == (N - 1 + N))
            dead_end = 1;
        end
    end
    if current_loc == (N * N - N) % Top left corner
        if any(the_list == (N * N - N + 1)) && any(the_list == (N * N - N - N))
            dead_end = 1;
        end
    end
    if current_loc == (N * N - 1) % Top right corner
        if any(the_list == (N * N - 2)) && any(the_list == (N * N - 1 - N))
            dead_end = 1;
        end
    end
    
    % If you are at an edge, check for a dead end
    if current_loc < N % Bottom edge
        if any(the_list == (current_loc - 1)) && any(the_list == (current_loc + 1)) && any(the_list == (current_loc + N))
            dead_end = 1;
        end
    end
    
    if mod(current_loc, N) == 0 % Left edge
        if any(the_list == (current_loc + 1)) && any(the_list == (current_loc + N)) && any(the_list == (current_loc - N))
            dead_end = 1;
        end
    end
    
    if mod(current_loc, N) == (N - 1) % Right edge
        if any(the_list == (current_loc - 1)) && any(the_list == (current_loc + N)) && any(the_list == (current_loc - N))
            dead_end = 1;
        end
    end
    
    if current_loc >= (N * N - N) % Top edge
        if any(the_list == (current_loc - 1)) && any(the_list == (current_loc + 1)) && any(the_list == (current_loc - N))
            dead_end = 1;
        end
    end
    
    % If you are in the interior, check for a dead end
    if (current_loc >= N) && (current_loc < (N * N - N)) && (mod(current_loc, N) > 0) && (mod(current_loc, N) < (N - 1))
        if any(the_list == (current_loc - 1)) && any(the_list == (current_loc + 1)) && any(the_list == (current_loc + N)) && any(the_list == (current_loc - N))
            dead_end = 1;
        end
    end
    
    if dead_end == 1 % At a dead end
        % Backup!        
        loc_list = loc_list - 1;
        
    else % Not at a dead end
        % Try to move
        temp = randi([0, 3], 1, 1);

        if temp == 0 % Try to move up
            if current_loc < (N * N - N)
                try_loc = current_loc + N;
            else
                try_loc = -1;
            end
            
        elseif temp == 1 % Try to move right
            if mod(current_loc, N) < (N - 1)
                try_loc = current_loc + 1;
            else
                try_loc = -1;
            end
            
        elseif temp == 2 % Try to move down
            if current_loc >= N
                try_loc = current_loc - N;
            else
                try_loc = -1;
            end
            
        elseif temp == 3 % Try to move left
            if mod(current_loc, N) > 0
                try_loc = current_loc - 1;
            else
                try_loc = -1;
            end
        end

        if any(try_loc == the_list)
            % Do nothing, not allowed to visit a location twice
        else
            % Never been to this location, so remove the wall
            if temp == 0 % Remove upper wall
                W(current_loc + 1, 1) = 0;
                W(current_loc + N + 1, 3) = 0;
            elseif temp == 1 % Remove right wall
                W(current_loc + 1, 2) = 0;
                W(current_loc + 1 + 1, 4) = 0;
            elseif temp == 2 % Remove bottom wall
                W(current_loc + 1, 3) = 0;
                W(current_loc - N + 1, 1) = 0;
            elseif temp == 3 % Remove left wall
                W(current_loc + 1, 4) = 0;
                W(current_loc - 1 + 1, 2) = 0;
            end
                        
            % Add the location to the list
            add_loc_list = add_loc_list + 1;
            the_list(add_loc_list) = try_loc; 
            loc_list = add_loc_list;
            
            % Plot the result in the figure
            x = mod(try_loc, N);
            y = floor(try_loc / N);
            
            plot(x, y, 'r*');
            drawnow                       
        end
    end    
end

%% Plot the maze and output the open scad code
% The wall spacing is: the bearing diameter, plus clearance of 1 mm, plus half a wall 
% 0.6 mm, and another half wall 0.6 mm
wall_space = bearing_diameter + 1 + 0.6 + 0.6;

% First items of OpenSCAD code
disp(['bearing_diameter = ' num2str(bearing_diameter) ';']);
disp('wall_w = 1.2 + bearing_diameter + 1 + 1.2;');
disp('wall_h = bearing_diameter + 0.6;');
disp('difference() {');
disp(' ');
disp('union() {');
disp( '    // Base');
disp( '    translate([-0.6, -0.6, -1.4]) {');
disp(['        cube([' num2str(N * wall_space) ' + 1.2, ' num2str(N * wall_space) ' + 1.2, 1.4]);}']);

figure
for ii = 1 : length(W)
    for jj = 1 : 4
        if W(ii, jj) == 1
            % Plot the wall
            x1 = mod(ii - 1, N) - 0.5;
            x2 = mod(ii - 1, N) + 0.5;
            y1 = floor((ii - 1) / N) - 0.5;
            y2 = floor((ii - 1) / N) + 0.5;
            
            go_wall = 1;
            z = 0;
            
            if jj == 1 % Top wall
                plot([x1, x2], y2 * [1, 1], 'k-');              
                a = 0;
                
                x = mod(ii - 1, N) * wall_space;
                y = floor((ii - 1) / N) * wall_space + wall_space;
                
            elseif jj == 2 % Right wall
                plot(x2 * [1, 1], [y1, y2], 'k-');
                a = 90;
                
                x = mod(ii - 1, N) * wall_space + wall_space;
                y = floor((ii - 1) / N) * wall_space;
                
            elseif jj == 3 % Bottom wall                
                plot([x1, x2], y1 * [1, 1], 'k-');
                % Only include the bottom wall on the first row
                if W > N
                    go_wall = 0;
                end
                a = 0;
                x = mod(ii - 1, N) * wall_space;
                y = floor((ii - 1) / N) * wall_space;
            elseif jj == 4 % Left wall
                plot(x1 * [1, 1], [y1, y2], 'k-');
                % Only include the left wall on the first column
                if mod(ii - 1, N) ~= 0
                    go_wall = 0;
                end   
                a = 90;
                x = mod(ii - 1, N) * wall_space;
                y = floor((ii - 1) / N) * wall_space;
            end
            
            if go_wall == 1
                disp(['translate([ ' num2str(x) ', ' num2str(y) ', ' num2str(z) ']) {']);
                disp(['    rotate(a = ' num2str(a) ', v = [0, 0, 1]) {']);
                disp( '        translate([-0.6, -0.6, 0]) {');
                disp( '            cube([wall_w, 1.2, wall_h]);');
                disp( '        }');
                disp( '        translate([-0.6, -0.6, wall_h]) {');
                disp( '            polyhedron( points = [[0,0,0],[wall_w,0,0],[wall_w,1.2,0],[0,1.2,0],[-2,-2,2],[wall_w + 2,-2,2],[wall_w + 2,3.2,2],[-2,3.2,2]], faces = [[0,1,2,3],[4,5,1,0],[7,6,5,4],[5,6,2,1],[6,7,3,2],[7,4,0,3]], convexity=10);}}}');
            end
            
            if ii == 1
                hold on
                axis([-1, N, -1, N]);
                axis square
                
            end
        end
    end
end

disp('}');

disp(' ');
disp('// Difference - remove exterior overhangs');
disp('translate([-5, -4 - 0.6, 0]) {');
disp(['    cube([' num2str(wall_space * (N + 1)) ', 4, 20]);}']); 

disp('translate([-5 - 0.6, -5, 0]) {');
disp(['    cube([5, ' num2str(wall_space * (N + 1)) ', 20]);}']); 

disp(['translate([' num2str(wall_space * N) ' + 0.6, -5, 0]) {']);
disp(['    cube([5, ' num2str(wall_space * (N + 2)) ', 20]);}']); 

disp(['translate([-5, ' num2str(wall_space * N) ' + 0.6, 0]) {']);
disp(['    cube([' num2str(wall_space * (N + 2)) ', 4, 20]);}']); 

disp('}');