maze (10jan23)

git-svn-id: svn://tug.org/texlive/trunk@65508 c570f23f-e606-0410-a88d-b1316a301751

4 files changed, 139 insertions, 12 deletions

diff --git a/Master/texmf-dist/doc/latex/maze/README.md b/Master/texmf-dist/doc/latex/maze/README.md
index c20c91c7914..3e3e0c18f18 100644
--- a/Master/texmf-dist/doc/latex/maze/README.md
+++ b/Master/texmf-dist/doc/latex/maze/README.md
@@ -14,7 +14,7 @@ You can read the package manual for some explanations.
 Copyright and License
 ---------------------
 
-    Copyright (C) 2022 by Sicheng Du <siddsc@foxmail.com>
+    Copyright (C) 2023 by Sicheng Du <siddsc@foxmail.com>
     -----------------------------------------------------------------
 
     This work may be distributed and/or modified under the
diff --git a/Master/texmf-dist/doc/latex/maze/maze.pdf b/Master/texmf-dist/doc/latex/maze/maze.pdf
index 3f75e2a64d1..4317bfee456 100644
--- a/Master/texmf-dist/doc/latex/maze/maze.pdf
+++ b/Master/texmf-dist/doc/latex/maze/maze.pdf
diff --git a/Master/texmf-dist/doc/latex/maze/maze.tex b/Master/texmf-dist/doc/latex/maze/maze.tex
index 0783535bfc3..28c6e70a81c 100644
--- a/Master/texmf-dist/doc/latex/maze/maze.tex
+++ b/Master/texmf-dist/doc/latex/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
diff --git a/Master/texmf-dist/doc/latex/maze/mazes-picture.png b/Master/texmf-dist/doc/latex/maze/mazes-picture.png
new file mode 100644
index 00000000000..d742860de5a
--- /dev/null
+++ b/Master/texmf-dist/doc/latex/maze/mazes-picture.png