diff options
Diffstat (limited to 'macros/latex/contrib/maze/maze.tex')
-rw-r--r-- | macros/latex/contrib/maze/maze.tex | 149 |
1 files changed, 138 insertions, 11 deletions
diff --git a/macros/latex/contrib/maze/maze.tex b/macros/latex/contrib/maze/maze.tex index 0783535bfc..28c6e70a81 100644 --- a/macros/latex/contrib/maze/maze.tex +++ b/macros/latex/contrib/maze/maze.tex @@ -1,33 +1,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.1} +\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 greater or equal to 2. +\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 outcome, it is recommended to input a number between 20 and 30 into \marg{text}. Over large numbers may cause \TeX~to exhaust its capacity and fail to produce anything. +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 following can be created by \cs{maze{30}[4]} and \cs{maze{20}[6]} respectively. +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] -\begin{minipage}{.5\textwidth} -\maze{30}[4] -\end{minipage}\hfill -\begin{minipage}{.5\textwidth} -\maze{20}[6] -\end{minipage} +\centering +\maze{30}[4]\hfill\maze{20}[7]\hfill\maze{25} +\caption{Examples of mazes}\label{fig:mazes} \end{figure} -\eject +\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}
\ No newline at end of file |