summaryrefslogtreecommitdiff
path: root/macros/latex/contrib/maze/maze.tex
diff options
context:
space:
mode:
Diffstat (limited to 'macros/latex/contrib/maze/maze.tex')
-rw-r--r--macros/latex/contrib/maze/maze.tex149
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