summaryrefslogtreecommitdiff
path: root/macros/latex/contrib/maze/maze.tex
blob: 28c6e70a81c0c83b2044d274fb2e9071d25a3c76 (plain)
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
\documentclass{ltxdoc}
\title{The \textsf{maze} package\footnote{~~This project is distributed under the \LaTeX~Project Public License, version 1.3c.}}
\usepackage[margin=2cm]{geometry}
\usepackage{graphicx}
\usepackage{listings}
\lstset{
    basicstyle=\fontspec{Consolas},numbers=left,
    numberstyle=\small,stepnumber=1,numbersep=5pt
}
\usepackage{xcolor}
\usepackage{fontspec}
\setmainfont{Times New Roman}
\usepackage{indentfirst}
\usepackage[misc]{ifsym}
\author{Sicheng Du\thanks{~~\Letter~~\href{mailto:siddsc@foxmail.com}{siddsc@foxmail.com}}}
\date{\today~~~~v1.2}
\usepackage[colorlinks,linkcolor=purple]{hyperref}
\usepackage{maze}
\begin{document}
\maketitle
\section{Changes in this version}
Thanks to the \TeX nicians who kindly gave valuable and earnest suggestions to this package, the version 1.2 is now released. The main changes include
\begin{enumerate}
\item Corrected some mistakes in this manual;
\item Modified the format in the source code to improve compatibility;
\item Improved the output map of the maze to make it clearer.
\end{enumerate}
\section{User instructions}
The \textsf{maze} package can generate random square mazes of a specified size. You need to start from the bottom-left corner and reach the top-right corner to play it.
\begin{macro}{\maze}
\marg{size}\oarg{seed} is the syntax of the command that generates a maze. Thereinto
\begin{description}
\item[\marg{size}] controls the density of the walls inside the maze and directly influences its complexity. It must be a positive integer in the range \textbf{[2,100]}.

To have the package produce a satisfactory output, it is recommended to input a number between 20 and 50 into \marg{text}. Over large numbers may cause \TeX~to exhaust its capacity and fail to produce anything.
\item[\oarg{seed}] is an optional parameter that specifies the seed for random numbers. If it is omitted, the current time (minute) will be used as the seed instead.
\end{description}\end{macro}

As an example, the mazes in Figure \ref{fig:mazes} can be created by \cs{maze\{30\}[4]}, \cs{maze\{20\}[7]} and \cs{maze\{25\}}\footnote{This maze is likely to look different because of the difference of compiling time.} respectively.
\begin{figure}[h]
\centering
\maze{30}[4]\hfill\maze{20}[7]\hfill\maze{25}
\caption{Examples of mazes}\label{fig:mazes}
\end{figure}
\clearpage
\section{Code implementation}
This package uses the \textsf{expl3} programming layer. Under the scope of \cs{ExplSyntaxOn} we first define some variables
\begin{lstlisting}[firstnumber=7]
\int_new:N\l_maze_rand_int                           % the random variable
\int_new:N\l_maze_old_int \int_new:N\l_maze_new_int
\dim_const:Nn\g_maze_size_dim{\linewidth}            % store the line width
\intarray_new:Nn\g_maze_map_intarray{10000}          % map of the maze
\intarray_new:Nn\g_walls_v_intarray{9900}            % existence of vertical
\intarray_new:Nn\g_walls_h_intarray{9900}            % /horizontal walls
\end{lstlisting}

The internal command is defined as \cs{m@ze}. Starting with variable initialization,
\begin{lstlisting}[firstnumber=last]
\newcommand{\m@ze}[2]{
  \sys_gset_rand_seed:n{#2}
  \intarray_gzero:N\g_maze_map_intarray
  \intarray_gzero:N\g_walls_v_intarray
  \intarray_gzero:N\g_walls_h_intarray
  \int_step_inline:nn{#1*#1}{
    \intarray_gset:Nnn\g_maze_map_intarray{##1}{##1}
  }
  \int_step_inline:nn{#1*(#1-1)}{
    \intarray_gset:Nnn\g_walls_v_intarray{##1}{1}
    \intarray_gset:Nnn\g_walls_h_intarray{##1}{1}
  }
\end{lstlisting}

Then we apply the \textit{Kruskal} algorithm to the intarray-based variant of the \textit{Union-find set}. Our loop should end when the beginning and finishing cells are connected. (so that a path exists)
\begin{lstlisting}[firstnumber=last]
  \bool_do_until:nn{
    \int_compare_p:nNn{\intarray_item:Nn\g_maze_map_intarray{1}}
    ={\intarray_item:Nn\g_maze_map_intarray{#1*#1}}
  }{
    \int_set:Nn\l_maze_rand_int{\int_rand:n{#1*(#1-1)}}
    \int_compare:nNnTF{0}={\intarray_item:Nn\g_walls_v_intarray{\l_maze_rand_int}}{}{
      \int_compare:nNnTF{
        \intarray_item:Nn\g_maze_map_intarray{
          \l_maze_rand_int+\int_div_truncate:nn{\l_maze_rand_int-1}{#1-1}
        }
      }={
        \intarray_item:Nn\g_maze_map_intarray{
          1+\l_maze_rand_int+\int_div_truncate:nn{\l_maze_rand_int-1}{#1-1}
        }
        }{}{
        \int_set:Nn\l_maze_new_int{
          \intarray_item:Nn\g_maze_map_intarray{
            1+\l_maze_rand_int+\int_div_truncate:nn{\l_maze_rand_int-1}{#1-1}
          }
        }
        \int_set:Nn\l_maze_old_int{
          \intarray_item:Nn\g_maze_map_intarray{
            \l_maze_rand_int+\int_div_truncate:nn{\l_maze_rand_int-1}{#1-1}
          }
        }
        \intarray_gset:Nnn\g_walls_v_intarray{\l_maze_rand_int}{0}
        \int_step_inline:nn{#1*#1}{
          \int_compare:nNnTF{\l_maze_old_int}={\intarray_item:Nn\g_maze_map_intarray{##1}}
          {\intarray_gset:Nnn\g_maze_map_intarray{##1}{\l_maze_new_int}}{}
        }
      }
    }
    \int_set:Nn\l_maze_rand_int{\int_rand:n{#1*(#1-1)}}
    \int_compare:nNnTF{0}={\intarray_item:Nn\g_walls_h_intarray{\l_maze_rand_int}}{}{
      \int_compare:nNnTF{\intarray_item:Nn\g_maze_map_intarray{\l_maze_rand_int}}
      ={\intarray_item:Nn\g_maze_map_intarray{#1+\l_maze_rand_int}}{}{
        \int_set:Nn\l_maze_new_int{
          \intarray_item:Nn\g_maze_map_intarray{#1+\l_maze_rand_int}
        }
        \int_set:Nn\l_maze_old_int{
          \intarray_item:Nn\g_maze_map_intarray{\l_maze_rand_int}
        }
        \intarray_gset:Nnn\g_walls_h_intarray{\l_maze_rand_int}{0}
        \int_step_inline:nn{#1*#1}{
          \int_compare:nNnTF{\l_maze_old_int}={\intarray_item:Nn\g_maze_map_intarray{##1}}
          {\intarray_gset:Nnn\g_maze_map_intarray{##1}{\l_maze_new_int}}{}
        }
      }
    }
  }
}
\end{lstlisting}

Lastly, we finish off by defining the user command, which outputs a map of the maze. To set the size and draw the boundaries,
\begin{lstlisting}[firstnumber=last]
\NewDocumentCommand\maze{mO{\c_sys_minute_int}}{
  \m@ze{#1}{#2}
  \setlength{\unitlength}{\fp_eval:n{.4/#1}\g_maze_size_dim}
  \begin{picture}(#1,#1)(0,0)
  \put(0,0){\line(0,1){#1}} \put(#1,#1){\line(0,-1){#1}}
  \put(\int_eval:n{#1-1},#1){\line(-1,0){\int_eval:n{#1-1}}}
  \put(1,0){\line(1,0){\int_eval:n{#1-1}}}
\end{lstlisting}

We extract from \cs{g\_walls\_h\_intarray} and \cs{g\_walls\_v\_intarray} and draw a line wherever a wall exists.
\begin{lstlisting}[firstnumber=last]
  \int_step_inline:nn{#1*(#1-1)}{
    \int_compare:nNnTF{0}={\intarray_item:Nn\g_walls_h_intarray{##1}}{}{
      \put(
        \int_mod:nn{##1-1}{#1},
        \int_eval:n{1+\int_div_truncate:nn{##1-1}{#1}}
      ){\line(1,0){1}}
    }
    \int_compare:nNnTF{0}={\intarray_item:Nn\g_walls_v_intarray{##1}}{}{
      \put(
        \int_mod:nn{##1}{#1-1},
        \int_div_truncate:nn{##1-1}{#1-1}
      ){\line(0,1){1}}
    }
  }
  \end{picture}
}
\ExplSyntaxOff
% End of package code
\end{lstlisting}
\end{document}