\section{Introduction}

A locally recoverable code is a linear code where a single erased position may be recovered from a small set of coordinates. Tamo and Barg constructed a family of optimal LRCs using subcodes of Reed--Solomon codes. Guo et. al. \cite{GKS13} used the point--line geometry of affine space over $\F_q$ to make LRCs.  Later L\'opez et. al \cite{LMMPW21} used the point--line incidence of the affine part of the Hermitian curve in order to define LRCs.  We begin introducing the basic notions of codes with locality.

    \begin{definition}[Locality of a Linear Code]\cite{GHSY12}
    A code $C$ has \emph{locality} $r$ if for every $i \in [n]$ there exists a subset $R_{i} \subset [n] \setminus i,\| R_{i} \| \leq r$ and a function $\phi_{i}$ such that for every codeword  $c \in C$:
    \begin{equation}
        c_{i} = \phi_{i} (\{c_{j}, j \in R_{i}\})
    \end{equation}

    A code $C$ with locality $r$ has \emph{availability} $s$ if for any $i \in [n]$ there exists $s$ subsets $R_1, R_2, \ldots, R_s$ such that $i \in R_u$ and $R_{s_1} \cap R_{s_2} = \{i\}$.
    \end{definition}
    A linear code with locality $r$ and availability $s$ is a linear code that any erased position may be recovered by querying any of $s$ disjoint sets of $r$ positions.

\begin{definition}[Affine Points of the Hermitian curve]
Let $q$ be a prime power. The \emph{affine points of the Hermitian curve} over $\Fqd$ are the solutions to the polynomial equation $$X^{q+1} = Y^q+Y$$ over $\Fqd$. That is, the points are defined by $$ \mathcal{H} := \{ (\alpha, \beta) \in \Fqd^2 \ \| \ \alpha^{q+1} = \beta^q+\beta  \} $$

\end{definition}

Hermitian codes may be defined as evaluation codes of polynomials over $\mathcal{H}$. The set of affine points $\mathcal{H}$ is finite. One only needs a finite set of monomials in order to describe any function on $\mathcal{H}$. We introduce the following notation.

\begin{definition}
Denote by $\mathcal{M}$ the set $\mathcal{M}  := \{ X^iY^j \ \| \ 0 \leq i < q^2, 0 \leq j < q\}$.

Let $f \in \F_{q^2}[X,Y]$. Let $P_1, P_2, \ldots, P_n$ be some ordering of the elements of the set $L$. We denote the evaluation of $f$ on $L$ by $$ev_L(f) = (f(P_1),f(P_2), \ldots, f(P_n)) $$
\end{definition} The following proposition can be established with Gr\"obner bases, normal bases and quotient rings.

\begin{proposition}\cite{CLO07}
Let $q$ be a prime power. Let $\mathcal{H}$ denote the set of all points over $\F_{q^2}$ of the Hermitian curve. Let $f \in \F_{q^2}[X,Y]$ be any polynomial. Then there exists $g \in \langle \mathcal{M} \rangle_{F_{q^2}}$ such that $$ev_\mathcal{H}(f) = ev_\mathcal{H}(g).$$

\end{proposition}

In fact, the evaluation functions from $\langle \mathcal{M} \rangle_{F_{q^2}}$ are linearly independent.

\begin{proposition}\cite{CLO07}
Let $q$ be a prime power. Let $\mathcal{H}$ denote the set of all points over $\F_{q^2}$ of the Hermitian curve. Let $f, g\in \langle \mathcal{M} \rangle_{F_{q^2}}$.  Then there $$f = g \makebox{ if and only if } ev_\mathcal{H}(f) = ev_\mathcal{H}(g).$$

\end{proposition}

Codes over the Hermitian curve may be defined as follows.

\begin{definition}[Evaluation codes over the Hermitian curve]\cite{G08}
Let $L$ be a subset of $\F_{q^2}[X,Y]$. Let $\mathcal{H}$ denote the set of affine points of the Hermitian curve. We define an evaluation code over $\mathcal{H}$ as:

$$C(L, \mathcal{H}) := \{ ev_{\mathcal{H}}(f) \ \| \ f \in \langle L \rangle_{\F_{q^2}} \} $$
\end{definition}

An evaluation code is defined as the linear code generated by the evaluation of a set of functions on a given set of points. In the case of Hermitian codes the set $L$ is taken as the set of all monomials of the form $X^iY^j$ where $iq+j(q+1) \leq s$ for a given $s$. Due to the kernel of the evaluation map, we may assume all function $f(X,Y)$ are contained in  $\mathcal{M}$ without loss of generality. Any linear code may be defined as an evaluation code using multivariate Lagrange interpolation polynomials. Now we shall define the lines of the Hermitian curve. These lines will be the locally recovery sets for the Hermitian Lifted codes.

\begin{definition}[Lines of the Hermitian curve]\cite{LMMPW21}
Let $q$ be a prime power. Let $a,b \in \Fqd$. A \emph{line of the Hermitian curve} is a set $L_{a,b}$ of the form $$L_{a,b} := \{(x,y) \in \mathcal{H} \ \| y = ax+b \} \makebox{ and } \#(L_{a,b}) = q+1.$$

\end{definition}

Not all lines of the affine space are lines of the Hermitian curve. We exclude vertical lines (those of the form $X = c$) because they have only $q$ points in common with the Hermitian curve. We also omit tangent lines with the Hermitian curve because those have only one point in common with the Hermitian curve. The following lemma states the polynomial equation that the $x$--coordinates of a line of the Hermitian curve must satisfy.

\begin{definition}
Let $q$ be a prime power. Let $a,b \in \Fqd$. Define by $L_{a,b,x}$ the set of $x$--coordinates of the line $L_{a,b}$. That is: $$L_{a,b,x} = \{ x \ \| \ (x,y) \in L_{a,b} \}.$$

\end{definition}
\begin{lemma}

Let $a,b \in \Fqd$ be such that $L_{a,b}$ is a line of the Hermitian curve. Then $$\prod\limits_{\gamma \in L_{a,b,x}} (X - \gamma) = (X-a^q)^{q+1} -(a^{q+1}-b^q-b).$$

\end{lemma} \begin{proof} We need to determine the common points to $Y = aX+b$ and $X^{q+1} = Y^q +Y$ over $\Fqd$. Substitute $Y = aX+b$ on the equation of the Hermitian curve to obtain:

 $$X^{q+1} = (aX+b)^q+(aX+b).$$ We rearrange terms and obtain:
  $$X^{q+1}-a^qX^q -aX^q = b^q+b.$$ We add $a^{q+1}$ to both sides.
  $$X^{q+1}-a^qX^q -aX^q +a^{q+1} = b^q+b + a^{q+1}.$$ The right hand side factors as: $$(X^q-a)(X-a^q) = b^q+b + a^{q+1}.$$
  Therefore $$(X-a^q)^{q+1} = b^q+b + a^{q+1}.$$ This implies the elements of $L_{a,b,x}$ satisfy  $(X-a^q)^{q+1} -(a^{q+1}-b^q-b) = 0$ \end{proof}

Now we state the condition on $a,b$ such that $L_{a,b}$ is a line of the Hermitian curve.
\begin{lemma}\cite{LMMPW21} Let $a,b \in \Fqd$ be such that $L_{a,b}$ is a line of the Hermitian curve. Then $a^{q+1} + b^q+b \neq 0$.

\end{lemma}
 \begin{proof} Let $L_{a,b}$ be a line of the Hermitian curve. The $x$--coordinates satisfy the polynomial equation  $(X-a^q)^{q+1} -(a^{q+1}-b^q-b) = 0$. Note that since $b^q+b + a^{q+1} \in \F_q$, the equation has $1$ solution if $b^q+b + a^{q+1} = 0$ and $q+1$ solutions if $b^q+b + a^{q+1} \neq 0$. For each solution in $X$ there is one point in $L_{a,b}$. Therefore if $L_{a,b}$ is a line of the Hermitian curve, it has $q+1$ points. This implies $(X-a^q)^{q+1} = b^q+b + a^{q+1}$ has $q+1$ solutions and therefore $b^q+b + a^{q+1} \neq 0$. \end{proof}

\begin{definition}\cite{LMMPW21} Let $f(X,Y)$ be a bivariate polynomial. Let $L_{a,b}$ be a line of the Hermitian curve. The \emph{restriction of $f$ onto $L_{a,b}$} is the function obtained by evaluating $f$ on the points of the line $L$. We denote the restriction by $f_{L_{a,b}}$. \end{definition}

We must make the distinction between a polynomial and its evaluation. If the the line $L_{a,b}$ is represented by the equations $X = T, Y = aX+b$ then the polynomial restricted to the line $L_{a,b}$ is the univariate polynomial $f(T, aT+b)$. An evaluation code is defined via the evaluation function $ev_{\mathcal{H}}(f)$. The restriction of the evaluation code to the line $L_{a,b}$ is simply the evaluation vector $ev_{L_{a,b}}(f)$. Even if $f(T, aT+b)$ has an arbitrarily high degree, the evaluation vector $ev_{L_{a,b}}(f)$ may be represented by evaluating a univariate polynomial of degree $q$ or less on the $q+1$ points in $L_{a,b,x}$. In order to construct an LRC we need functions which restrict "nicely" on each line.

\begin{definition}[Good functions]\cite{LMMPW21}
Let $f(X,Y)$ be a bivariate polynomial. Let $a,b \in \Fqd$ such that $L_{a,b}$ is a line of the Hermitian curve. We say $f$ is a \emph{good polynomial} if and only the evaluation $$ev_{L_{a,b}}(f) = ev_{L_{a,b,x}}(g(T))$$ where $g$ is a univariate polynomial of degree  less than $q$ on $L_{a,b,x}$ for each line $L_{a,b}$ of the Hermitian curve.

We denote the set of good functions as $\mathcal{G}_f$.

\end{definition}

\begin{definition}[Hermitian Lifted Codes]\cite{LMMPW21}

Let $q = 2^k$. We define the \emph{Hermitian Lifted code} over the Hermitian curve as $$\mathcal{C}  := C(\mathcal{G}_f, \mathcal{H}).$$

\end{definition}

We denote the dimension of $\mathcal{C}$ by $K$, its rate by $R$ and its distance by $D$. L\'opez et. al \cite{LMMPW21} claim the following.

\begin{proposition} \cite[Claim 12]{LMMPW21}
Let $q = 2^k$. Then the monomial set $\mathcal{M}$ contains at least $$\sum\limits_{r=0}^{k-1}(4^r-3^r)4^{k-r-2}2^{k-r-1}$$ good monomials.  Consequently $$K \geq \sum\limits_{r=0}^{k-1}(4^r-3^r)4^{k-r-2}2^{k-r-1}.$$
\end{proposition}

As a corollary it was proven that the rate of Hermitian Lifted codes is at least $R \geq 0.007$. Our aim is to find more monomials in $\mathcal{M}$ which are also good functions. Our proof is based in univariate polynomial division. To simplify our arguments, we introduce the following notation.

\begin{definition}
Let $\gamma \neq 0 $. We shall denote by $$P_{a,\gamma} := (T-a^q)^{q+1} - \gamma.$$
\end{definition}

The nonzero positions of the parity check equations for $\mathcal{C}$ are the point sets of lines of the Hermitian unital. The binary code generated by the lines of the Hermitian unital is a code of dimension $q^3+1$. This means that its dual code and the LRC defined by the lines of the Hermitian unital has dimension $0$ (see \cite[Theorem 8.3.1]{AK92}). We find it remarkable that even though the parity check equations for $\mathcal{C}$ have the same nonzero positions than the Hermitian unital code, the dimension of $\mathcal{C}$ is relatively large.

A function $f(X,Y)$ is good or bad depending on the residue $f(T, aT+b) \mod (T-a^q)^{q+1}-\gamma$. The polynomial $P_{a,\gamma}$ will determine the degree of $f(T,aT+b) \mod P_{a, \gamma}$. In this section we prove key properties of this reduction. For the remainder of this article we assume we are working over characteristic $2$.

We remark that if $0 \leq i,j \leq \frac{q}{2^r}-1$ then $ 0 \leq i 2^r \leq q-2^r$. Now we shall prove a lemma on the degree of certain $2^r$--powers of $T$.
\begin{lemma}\label{lem:little2r pow}
Let $q$ be a power of $2$, let $0 < 2^r < q$. Let $k$ be odd and let $j$ be such that $0 \leq k,j < \frac{q}{2^r}$. Then

$$T^{k2^rq}T^{j2^r} \mod P_{a, \gamma} $$ has degree at most $q+1-2^r$.
\end{lemma}
\begin{proof}
Recall that $P_{a, \gamma} = (T-a^q)^{q+1}-\gamma$, where $\gamma \neq 0$. We shall apply the change of variables $T \mapsto S+a^q$ and compute the degree of $(S+a^q)^{k2^rq}(S+a^q)^{j2^r} \mod S^{q+1}-\gamma$. instead. Since we are working over  characteristic $2$:

$$(S+a^q)^{k2^rq}(S+a^q)^{j2^r} = (S^{2^rq}+a^{2^r})^{k}(S^{2^r}+a^{2^rq})^{j}. $$ We expand the binomial and obtain
$$  = \left(\sum\limits_{i_1=0}^k\binom{k}{i_1}S^{i_12^rq}\left(a^{(k-i_1)2^r}\right)\right)\left (\sum\limits_{i_2=0}^j \binom{j}{i_2}S^{i_2 2^r}\left(a^{(j-i_2)2^rq}\right)\right)$$
We multiply both binomial expansions and obtain:
$$  = \sum\limits_{i_1=0}^k\sum\limits_{i_2=0}^j \binom{k}{i_1}\binom{j}{i_2}S^{(i_1q+i_2)2^r}a^{(j-i_2)q+(k-i_1)2^r}$$
The degree of  $S^{(i_12^r q+i_2 2^r}\mod S^{q+1}-\gamma$ depends on $(i_1q+i_2)2^r$.
\begin{itemize} \item  \textbf{Case 1: $i_1 = 0$} If $i_1 = 0$, then $(i_1q+i_2)2^r = i_2 2^r$ and $i_2 2^r \leq q-2^r$. Therefore $$S^{(i_12^r)q+i_22^r} = S^{i_2 2^r} \equiv S^{i_2 2^r} \mod S^{q+1}-\gamma.$$
\item \textbf{Case 2: $i_1 \geq 1, i_1 < i_2$}. If $i_1 \geq 1$ and $i_1 < i_2$, then let $i_2 = i_1 +\delta$ where $\delta > 0$. Write $(i_1q+i_2)2^r = i_1 2^r q + i_12^r +\delta 2^r =  (i_1 2^r)(q+1) +\delta 2^r$.   In this case $$S^{(i_12^r)q+i_22^r} = S^{ (i_1 2^r)(q+1) +\delta 2^r} \equiv \gamma^{i_1 2^r}S^{\delta 2^r} \mod S^{q+1}-\gamma.$$ Clearly the reduction has degree at most $\delta 2^r \leq q-2^r$.
\item \textbf{Case 3: $i_1 \geq 1, i_1 =i_2$ } If $i_1 \geq 1$ and $i_1  = i_2$ then $(i_1q+i_2)2^r = (i_2+\delta)2^r q = (i_2 2^r)(q+1)$. Reducing $\mod S^{q+1}-\gamma$ we obtain $$S^{(i_12^r q + i_2 2^r)} = S^{((q+1)i_2 2^r)} \equiv \gamma^{i_2 2^r}. $$ Therefore $S^{(i_12^r q + i_2 2^r)} \mod S^{q+1}-\gamma$ is a constant.
\item \textbf{Case 4: $i_1 \geq 1, i_1 > i_2$ } If $i_1 \geq 1$ and $i_1 \geq i_2$ then $i_1 = i_2 + \delta$ where $\delta >  0$. Write $(i_1q+i_2)2^r = (i_2+\delta)2^r q + i_22^r = (i_2 2^r)(q+1) + \delta 2^r q$. This implies that  $$S^{(i_2 2^r)(q+1) + \delta 2^r} = S^{((i_2+\delta)2^r-1)(q+1) +(q+1-\delta 2^r)}.$$
  Reducing $S$ modulo $S^{q+1}- \gamma$ we obtain  $$S^{(i_2 2^r)(q+1) + \delta 2^r} \equiv \gamma^{(i_2+\delta)2^r-1} S^{q+1-\delta2^r}.$$ Since $1 \leq \delta \leq \frac{q}{2^r}-1$, it follows that the degree of the reduction is at most $q+1-2^r$.\end{itemize}

Note that on all cases the degree of each power of $S$ in the expansion of $(S+a^q)^{k2^rq}(S+a^q)^{j2^r}$ reduces $\mod S^{q+1}-\gamma$ to something of degree at most $q+1-2^r$. Since the change of variables $T \mapsto S+a^q$ preserves the degree, the result follows. \end{proof}

It is worth mentioning that because $k$ is odd, $\binom{k}{1} = 1$. Therefore $S^{2^rq} \equiv  \gamma^{2^r-1}S^{q+1-2^r} \mod S^{q+1}-\gamma $. If $k$ was even, (say $k = k'2^s$) then the same argument holds with $2^{r+s}$ instead of $2^r$ and obtain better bounds on the degree.

\section{Finding good monomials}
In the previous section we have found that certain powers of $T$, namely $T^{k2^rq+j2^r}$ have degree $q+1-2^r$ when reduced modulo $P_{a,\gamma}$. As a good monomial has a reduction $\mod P_{a,\gamma}$ with degree is less than $q$. Therefore if $2^r \geq 2$, then those monomials are good. Now we count the monomials of the form $X^iY^j$ where $0 \leq i < q^2, 0 \leq j < q$ which are known to give good reductions.

\begin{definition}\cite{GKS13}

Let $0 \leq i, j \leq 2^r-1$. Suppose that the expansion of $i$ in base $2$ is $i = i_{r-1}2^{r-1}+i_{r-2}2^{r-2}+  \cdots+ i_12+i_0$ where $0 \leq i_s \leq 1$. and that the expansion of $j$ in base $2$ is $j_{r-1}2^{r-1}+j_{r-2}2^{r-2}+  \cdots+ j_12+j_0$ where $0 \leq j_s \leq 1$. We say $i$ \emph{lies in the $2$--shadow of $j$} if $i_s \leq j_s$ for all $s$, We denote it by $i \leq_2 j$.
\end{definition}

\begin{lemma}[Lucas' Theorem]\cite{L78}
Let $0 \leq i,j \leq 2^r-1$.
$$\binom{j}{i} = 0 \mod 2 \makebox{ if and only if } i \not \leq_2 j.$$
\end{lemma}

With an elementary counting argument with $0 \leq i,j < 2^r$ it may be proven that there are $4^r-3^r$ pairs $(i,j)$ such that $i \not\leq_2 j$.

\begin{lemma}\label{lem:goodmonomialsnb}

Let $i = i_1q+i_2 2^r+ i_3$ where $0 \leq i_1, i_2, i_3$ where $2^r$ is the highest power of $2$ dividing $i_1$,$0 \leq i_2 < \frac{q}{2^{r}}$ and $0 \leq i_3 < 2^r$ Let $j = j_2 2^r + j_3$ where $0 \leq j < q$, $0 \leq j_2 < \frac{q}{2^{r}}$ and $j_3 < 2^r$. The monomial $X^{i}Y^{j}$ is a good monomial if $i_2 2^r + i_3 +j_2 2^r + j_3 < q$ and $ 2^r-1-i_3 \not \leq_2 j_3 $

\end{lemma}

\begin{proof}

We shall evaluate the monomial $X^iY^j$ on the line given by $Y = aX+b$, $b^q+b \neq a^{q+1}$. Denote $a^{q+1} - b^q-b$ by $\gamma$. In this case, we set $X = T$ and $Y = aT+b$. The powers of $T$ satisfy the polynomial equation $(T-a^q)^{q+1} = \gamma$.

From the conditions of the theorem, $i_1 = k_12^r$ where $k_1$ is odd. We need to determine the degree of $$T^{i}(aT+b)^j \mod (T-\alpha^q)^{q+1}-\gamma $$

Note that  $$T^{i}(aT+b)^j  = T^{k_1 2^r q} T^{i_2 2^r} T^{i_3}(aT+b)^{j_2 2^r} (aT+b)^{j_3}.$$

Therefore we rewrite the product as:

$$T^{i}(aT+b)^j  = T^{k_1 2^r q} (T^{2^r})^{i_2} T^{i_3}(a^{2^r}T^{2^r}+b^{2^r})^{j_2} (aT+b)^{j_3}.$$

Expanding the terms of $(a^{2^r}T^{2^r}+b^{2^r})^{j_2}$ we obtain:

$$T^{i}(aT+b)^j  = T^{k_1 2^r q} (T^{2^r})^{i_2} T^{i_3}(aT+b)^{j_3}\left( \sum\limits_{k_1=0}^{j_2}\binom{j_2}{k_1} a^{k_2 2^r}b^{2^r(j_2-k_2)} T^{k_2 2^r} \right)  .$$

We include the term $(T^{2^r})^{i_2}$ into the sum
$$T^{i}(aT+b)^j  = T^{k_1 2^r q}  T^{i_3}(aT+b)^{j_3}\left( \sum\limits_{k_1=0}^{j_2}\binom{j_2}{k_1} a^{k_2 2^r}b^{2^r(j_2-k_2)} T^{ (k_2+i_2) 2^r} \right)  .$$

Since $k_2+j_2<\frac{q}{2^r}$ Lemma \ref{lem:little2r pow} implies that $T^{k_1 2^r q}T^{k_2+j_2} \mod P(a^q, \gamma)$ has degree $q+1-2^r$. Let us denote $$T^{k_1 2^r q}  \left( \sum\limits_{k_1=0}^{j_2}\binom{j_2}{k_1} a^{k_2 2^r}b^{2^r(j_2-k_2)} T^{ (k_2+i_2) 2^r} \right) \mod P(a^q, \gamma)$$ by = $A(T)$ where $deg A = q+1-2^r$.

Now

$$T^i(aT+b)^j \equiv  T^{i_3}(aT+b)^{j_3}A(T) \mod (T-\alpha^q)^{q+1}-\gamma $$

In the binomial expansion of $T^{i_3}(aT+b)^{j_3}$ the coefficient of the term $T^{q-2^r}$ is $\binom{j_3}{2^r-1-i_3}a^{2^r-1-i_3}b^{j_3+i_3+1-2^r}$. The condition on $i_3$ and $j_3$ implies that $\binom{j_3}{2^r-1-i_3} = 0$. Therefore $$T^i(aT+b)^j \equiv  T^{i_3}(aT+b)^{j_3}A(T) \mod (T-\alpha^q)^{q+1}-\gamma $$ has no coefficients of degree $T^{q}$, which implies the reduction of $T^i(aT+b)^j \mod P(a^q, \gamma)$ is good.\end{proof}

\begin{corollary}

There are at least $$\sum\limits_{r = 1}^{k} \frac{q}{2^{r+1}}\left(      \binom{\frac{q}{2^r}}{2}(4^r-3^r)  +  \frac{q}{2^r} \binom{2^r+1}{2}\right)  $$ good monomials in $\mathcal{M}$.

\end{corollary}
\begin{proof}
Lemma \ref{lem:goodmonomialsnb} implies that monomials $X^iY^j$ satisfying: $i = i_1q+i_2 2^r+ i_3$ where $0 \leq i_1, i_2, i_3$ where $2^r$ is the highest power of $2$ dividing $i_1$,$0 \leq i_2 < \frac{q}{2^{r}}$ and $0 \leq i_3 < 2^r$ and $j = j_2 2^r + j_3$ where $0 \leq j < q$, $0 \leq j_2 < \frac{q}{2^{r}}$ and $j_3 < 2^r$ are good. Now we count the number of such $(i,j)$ pairs. If $i < q$ there are $\binom{q+1}{2}$ pairs such that $0 \leq i+j \leq q-1.$

There are $\frac{q}{2^{r+1}}$ numbers $0 \leq i_1 \leq q-1$ such that $2^r$ is the highest power of $2$ dividing $i_1$. For each such $i_1$, we count the possible values of $i_2 2^r+i_3$ and $j_2 2^r + j_3$ satisfying the conditions of the corollary. There are $\frac{q}{2^{r}}$ values of $i_2$ and $j_2$ satisfying $i_2+j_2 = \frac{q}{2^r}-1$. For those values, the conditions of the Lemma imply that $i_3+ j_3 \leq 2^r-1$. There are $\binom{2^r+1}{2}$ pairs of $i_3, j_3$ satisfying that condition. There are $\binom{\frac{q}{2^r}}{2}$ pairs of $i_2, j_2$ which satisfy $0 \leq i_2+j_2 \leq \frac{q}{2^r}-2$. Of those there are $4^r-3^r$ pairs of $i_3, j_3$ such that $2^r-1-j_3 \not\leq_2 i_3$. Adding the cases together we get that there are at least $$\sum\limits_{r = 1}^{k} \frac{q}{2^{r+1}}\left(      \binom{\frac{q}{2^r}}{2}(4^r-3^r)  +  \frac{q}{2^r} \binom{2^r+1}{2}\right)  $$ good independent monomials in the footprint.

\end{proof}

Since the monomials in $\mathcal{M}$ give linearly independent evaluations over the affine points of the Hermitian curve, we have the following corollary.

\begin{corollary} Let $q = 2^k$.  Then $$K \geq \sum\limits_{r = 1}^{k} \frac{q}{2^{r+1}}\left(      \binom{\frac{q}{2^r}}{2}(4^r-3^r)  +  \frac{q}{2^r} \binom{2^r+1}{2}\right)$$
\end{corollary}

We can use the improved dimension estimate of the Hermitian Lifted code to improve their asymptotic rate bound.

\begin{corollary} Let $q = 2^k$.  Then the rate of $\mathcal{C}$ is at least $0.1$.
\end{corollary}
\begin{proof}
There are at least $$\sum\limits_{r = 1}^{k} \frac{q}{2^{r+1}}\left(      \binom{\frac{q}{2^r}}{2}(4^r-3^r)  +  \frac{q}{2^r} \binom{2^r+1}{2}\right)  $$ good monomials in $\mathcal{M}$.

We expand the binomial coefficients $$\sum\limits_{r = 1}^{k} \frac{q}{2^{r+1}}\left(      \frac{\frac{q}{2^r}(\frac{q}{2^r}-1)}{2}(4^r-3^r)  +  \frac{q}{2^r} \frac{(2^r+1)2^r}{2}\right) .$$

We take out $\frac{1}{4}$ as a common term from the sums and rewrrite $\frac{q}{2^r} = 2^{k-r}$ $$\frac{1}{4}\sum\limits_{r = 1}^{k} 2^{k-r}\left(      2^{k-r}(2^{k-r}-1)(4^r-3^r)  +  2^{k-r} (2^r+1)2^r\right) .$$

We collect powers $$\frac{1}{4}\sum\limits_{r = 1}^{k} 2^{k-r}\left(      (4^{k-r}-2^{k-r})(4^r-3^r)  +  2^{k+r}+2^k\right) .$$
$$\frac{1}{4}\sum\limits_{r = 1}^{k} 2^{k-r}\left(         q^2 -q^2\left(\frac{3}{4}\right)^r -q2^r + q\left(\frac{3}{2}\right)^r   +  q2^r+q\right) .$$
$$\frac{1}{4}\sum\limits_{r = 1}^{k} 2^{k-r}\left(         q^2 -q^2\left(\frac{3}{4}\right)^r + q\left(\frac{3}{2}\right)^r +q\right) .$$

We multiply everything by $2^{k-r} = \frac{q}{2^r}$ $$\frac{1}{4}\sum\limits_{r = 1}^{k}         q^3\left(\frac{1}{2}\right)^r -q^3\left(\frac{3}{8}\right)^r + q^2\left(\frac{3}{4}\right)^r +q^2\left(\frac{1}{2}\right)^r .$$

We rewrite the geometric series as:

$$\frac{1}{4} \left( q^3 \frac{1}{2}\frac{1-\left( \frac{1}{2}\right)^k}{1- \frac{1}{2}} -  q^3 \frac{3}{8}\frac{1-\left( \frac{3}{8}\right)^k}{1- \frac{3}{8}} +  q^2 \frac{3}{4}\frac{1-\left( \frac{3}{4}\right)^k}{1- \frac{3}{4}} +  q^2 \frac{1}{2}\frac{1-\left( \frac{1}{2}\right)^k}{1- \frac{1}{2}} \right) .$$

$$\frac{1}{4} \left( q^3 \left(1-\left( \frac{1}{2}\right)^k\right) -  q^3 \frac{3}{5} \left(1-\left( \frac{3}{8}\right)^k\right)+  q^2 3 \left(1-\left( \frac{3}{4}\right)^k\right) +  q^2 \left(1-\left( \frac{1}{2}\right)^k\right) \right) .$$

If we divide by $q^3$ and take the limit as $k$ the only two terms that survive are ones multiplied by $q^3.$ The limit of the first one is $1$ and the limit of the second one is $\frac{3}{5}$. After multiplying by $\frac{1}{4}$ the asymptotic limit is $$r = \frac{1}{4} - \frac{3}{20} = \frac{1}{10}.$$\end{proof}
This rate bound is a vast improvement from the previously known  bound of $0.007$.

\section*{Conclusion}

We have improved the dimension bound of a class of Locally Recoverable codes defined from the Hermitian curve using functions which behave like a low--degree polynomial on each line of the Hermitian curve. The rate of Hermitian--Lifted codes is much  smaller than the rate of the Reed--Muller lifted codes. However, it is remarkable that we can find codes of a positive rate using parity check equations over a field $\F_q$ when the code from the corresponding binary vector would give a code of dimension $0$. We hope that this leads to codes with better rates from the Hermitian unital and other designs.

\section*{Acknowledgements}

The authors would like to thank Beth Malmskog for her insightful comments and thoughtful conversations on the article.


\section*{Extensions to PCGNN\xspace}
\label{sec:appdx}
We extend standard PCGNN\xspace by adding in additional features useful for \texttt{MCHAMR}\xspace. The specific features we use are as follows:
\begin{LaTeXdescription}
    \item[3D] We simply generalise the generation procedure to three dimensions, by considering a level as a $W\times H\times D$ block of tiles, and iterating through all of the tiles.
    \item[Multiple Iterations] Using multiple iterations is also a relatively simple change: after performing the generation once, we use this as a starting point, and repeat the process for multiple iterations. The intuition here is that performing this process multiple times has the effect of increasing the effective \textit{receptive field} of the network. This is similar to how deep convolutional neural networks are able to focus on long-range dependencies by stacking local interactions~\citep{luo2017Understanding}. An approach like this has been used successfully in PCG before; specifically, \citet{earle2021Illuminating} perform multiple processing iterations of a neural cellular automaton to generate levels.
    \item[Input Center Tile] This adds in the center tile the model is currently focusing on as an input. This is beneficial in the case of multiple iterations, so that the network can pass along information to the subsequent iterations.

    \item[Various Starting Points] While we mostly still use random initialisations, some experiments instead initialised the level with a specific ``default'' tile, so that the starting points are all the same.
\end{LaTeXdescription}
\section*{Reproducibility Details}
As mentioned in the main text, we publicly release our source code at \url{https://github.com/Michael-Beukman/MCHAMR}. Implementation details, as well as instructions to reproduce our results, can be found there.
\section*{Experimental Setup}
When plotting the fitness value in our experiments, we use the maximum fitness in the current population. This is done because we use the best individual at the end of generation as our chosen generator. Furthermore, all of our fitness functions are scaled between 0 and 1, so $1.0$ corresponds to the optimal fitness.
\section*{Hyperparameters}
Here we detail the hyperparameters and exact setups used to generate the images in the main paper. If a particular parameter is not mentioned, the default value from \citet{beukman2022Procedural} was used; for example, all of our experiments padded the boundaries with $-1$. When we used novelty, we used the Hamming distance, which was denoted as \textit{Visual Diversity} by \citet{beukman2022Procedural}.
\label{sec:hierarchy_vals}
In this experiment, we compared the results when using different logical window sizes, from $1\times 1$, representing a composed approach, to $10\times 10$.
For all of these experiments, we used the hyperparameters shown in \autoref{tab:appdx:hierarchy}, with \autoref{fig:appx:tile_sizes_examples} containing some examples of generated levels. We calculated the individual's fitness as the average of the following two fitness functions:
\label{sec:reach_fit}
\begin{LaTeXdescription}
    \item[Probability]: We compute the level's tile distribution, representing the frequency of each tile type in the level. This fitness is the square root of the Jensen-Shannon divergence~\citep{fuglede2004JensenShannon} between the level's tile distribution and an ``ideal'' distribution of 40\% house, 30\% garden and 30\% road.
    \item[Reachability]: All houses must be reachable (with allowable moves being up, down, left and right) from all other houses via roads without being directly connected. This fitness is calculated as $a \times b$, where $a = \min{(\frac{H}{20}, 1)}$, with $H$ being the number of houses that have between 1 and 3 (inclusive) neighbouring road tiles. $b = \frac{1}{(d_{house,road} + 1)(d_{road} + 1)}$, where $d_i = \min{(|1 - c_i|, 10)}$ and $c_i$ is the number of disconnected regions of tile type $i$. For example, if a level consists entirely of roads, with a vertical line of gardens through the middle of the level, then there would be two disconnected regions of road (to the left and right of the vertical line).
     When calculating $c_{house,road}$, we label houses and roads as the same tile, and find the number of disconnected regions (i.e. those regions separated by gardens). All of these operations can be efficiently implemented using morphological image operations, notably image labelling.\footnote{\url{https://scikit-image.org/docs/stable/api/skimage.morphology.html\#label}} Here, $a$ incentivises each house to be reachable by a road, without being completely isolated from gardens or other houses; $b$ specifies that there must be one connected road region, and that each house must be reachable from every other house (as $b$ is maximised when $c_i = 1$, corresponding to there only being one connected region).
\end{LaTeXdescription}

\begin{figure*}[h]
    \centering
    \begin{subfigure}{0.49\linewidth}
        \includegraphics[width=1\linewidth]{hierarchy_examples/example_levels_0_True.jpg}
        \caption{}
    \end{subfigure}
    \begin{subfigure}{0.49\linewidth}
        \includegraphics[width=1\linewidth]{hierarchy_examples/example_levels_1_True.jpg}
        \caption{}
    \end{subfigure}

    \caption{Showcasing example levels generated by the networks with different logical tile sizes for two different seeds.}
    \label{fig:appx:tile_sizes_examples}
\end{figure*}

\begin{figure*}[h!]
    \centering
    \begin{minipage}[t]{.47\textwidth}
        \centering
        \begin{subfigure}{0.32\linewidth}
            \includegraphics[width=1\linewidth]{hand_designed_correct.pdf}
            \caption{}
        \end{subfigure}
        \begin{subfigure}{0.32\linewidth}
            \includegraphics[width=1\linewidth]{hand_designed_compose.pdf}
            \caption{}
        \end{subfigure}
        \begin{subfigure}{0.32\linewidth}
            \includegraphics[width=1\linewidth]{hand_designed_flat.pdf}
            \caption{}
        \end{subfigure}
        \caption{}
        \label{fig:appx:compose_examples:hand}
    \end{minipage}
    \hfill
    \begin{minipage}[t]{.47\textwidth}
    \centering
    \begin{subfigure}{0.32\linewidth}
        \includegraphics[width=1\linewidth]{random_correct.pdf}
        \caption{}
    \end{subfigure}
    \begin{subfigure}{0.32\linewidth}
        \includegraphics[width=1\linewidth]{random_compose.pdf}
        \caption{}
    \end{subfigure}
    \begin{subfigure}{0.32\linewidth}
        \includegraphics[width=1\linewidth]{random_flat.pdf}
        \caption{}
    \end{subfigure}
    \caption{}
    \label{fig:appx:compose_examples:random}
    \end{minipage}
    \caption*{The (a) desired, (b) composed and (c) flat levels for a (\autoref{fig:appx:compose_examples:hand}) hand-designed or (\autoref{fig:appx:compose_examples:random}) randomly generated target layout. Note that in the main text, we did not use the fitness results from the hand-designed layout and just show it here for comparison.}
\end{figure*}

\begin{table}[h]
    \centering
    \caption{Hyperparameters where we experimented with different window sizes, i.e. differing complexity levels of the base structures.}
    \label{tab:appdx:hierarchy}
    \begin{adjustbox}{width=1\linewidth}
    \begin{tabular}{ll}
        \toprule
        Name & Value \\
        \midrule
        One Hot Encoding & True \\
        Generations & 50 \\
        Population Size & 50 \\
        Number of Random Variables & 1 \\
        Random Perturb Size & 0 \\
        Number of Iterations & 3 \\
        Input Center Tile & Yes \\
        Default Tile & Garden \\
        Novelty & No Novelty \\
        Level Starting Point & Default Tile (Garden) \\
        Number of levels for fitness calculations & 5 \\
        \bottomrule
    \end{tabular}
\end{adjustbox}
\end{table}

\subsection*{Composition vs flat}
\autoref{tab:appdx:compose_vs_flat} shows the hyperparameters we used when directly comparing \texttt{MCHAMR}\xspace and PCGNN\xspace.

In this experiment, we have 20 random, but fixed town layouts. Thus, for each method (\texttt{MCHAMR}\xspace and PCGNN\xspace), we have the same desired levels.

\Autoref{fig:appx:compose_examples:hand,fig:appx:compose_examples:random} show the desired layout and the result from both the composed and flat methods. While the composed method does not generate perfect levels, they are significantly closer to the desired layouts compared to the flat generator. When using the flat method, the levels are very poor, not containing house structures at all.

\begin{table*}[h]
    \centering
    \caption{Hyperparameters used for the Composed vs Flat Towns}
    \label{tab:appdx:compose_vs_flat}
    \begin{adjustbox}{width=1\linewidth}
    \begin{tabular}{llll}
        \toprule
        Name & Flat (PCGNN\xspace) & Composed Town & Composed House\\
        \midrule
        Level Size                                  & $25\times 25$     & $5\times 5$             & $5\times 5$\\
        One Hot Encoding                            & False             & False                   & False\\
        Generations                                 & 150               & 150                     & 150\\
        Population Size                             & 50                & 50                      & 50\\
        Number of Random Variables                  & 1                 & 1                       & 1\\
        Random Perturb Size                         & 0                 & 0                       & 0\\
        Number of Iterations                        & 5                & 5                      & 5\\
        Input Center Tile                           & Yes               & Yes                     & Yes\\
        Novelty                                     & No Novelty & No Novelty & No Novelty \\
        Level Starting Point                        & Default (Road)             & Default (Road)                   & Default (Air)\\
        \# of levels for fitness calculations       & 5                 & 5                       & 5\\
        \bottomrule
    \end{tabular}
\end{adjustbox}
\end{table*}

\subsection*{Showcase}
\autoref{tab:appdx:showcase} details the hyperparameters used for each showcase result. The generator that we used to generate both towns and cities is denoted as ``Town \& City''.
We used the following fitness functions for these experiments:
\begin{LaTeXdescription}
    \item[House] The house was incentivised to be a hollow cube, with roof tiles at the top by setting the fitness to the average overlap between the generated house and the ``ideal'', hollow cube. Here we weighted novelty, intra-generator novelty and this fitness using the ratio $1:1:8$.
    \item[Garden] The garden had multiple fitness functions, incentivising it to have at least one tree and one flower, contain some water tiles (less than 5\%) and not be too dense (the fraction of grass tiles must be between $0.2$ and $0.7$ and trees should not be too close to each other). We weighted novelty, intra-generator novelty and this fitness using the ratio $1:1:4$.
    \item[Town] This incentivised the distribution of tiles to be 40\% house, 30\% garden and 30\% road (by computing the square root of the Jensen-Shannon divergence between this distribution and the actual one), in addition to the houses being reachable via roads. This was calculated as $\frac{a + b}{2}$, with $a$ and $b$ defined in the \hyperref[sec:reach_fit]{Hyperparameters Section}.
    \item[City] The average of two fitnesses, the first one incentivising an equal number of houses, roads and gardens, calculated as $\frac{1}{3}\sum_{i \in \{ house, road, garden\}}\max(1 - 10 (n_i - \frac{1}{3})^2, 0)$ where $n_i$ is the fraction of tiles of type $i$. The second fitness is \textit{reachability}, again calculated as $\frac{a + b}{2}$.
    \item[Town \& City] This fitness incentivises the boundary of the town to be houses, with an inner ring of roads, and a large interior section of gardens. This fitness was calculated as the average overlap between the ideal layout and the actual level for each section. This generator also used a context size of $2$, i.e. it took in a $5\times 5$ block around the current tile, instead of the normal $3\times 3$.
\end{LaTeXdescription}
\begin{table*}
    \centering
    \caption{This table details the hyperparameters used for the showcase images shown in the main text.}
    \label{tab:appdx:showcase}
    \begin{adjustbox}{width=1\linewidth}
    \begin{tabular}{llllll}
        \toprule
        Name                                   & House & Garden & Town & City  & Town  \& City \\
        \midrule
        One Hot Encoding                       & False            & False           & False            & False             & False\\
        Generations                            & 500              & 100             & 150              & 150               & 350\\
        Population Size                        & 20               & 20              & 50               & 50                & 30\\

        Number of Random Variables             & 1                & 2               & 1                & 1                 & 1\\
        Random Perturb Size                    & 0                & 0.1565          & 0                & 0                 & 0.1\\
        Number of Iterations                   & 10               & 1               & 10               & 10                & 5\\
        Input Center Tile                      & Yes              & No              & Yes              & Yes               & Yes\\
        Level Starting Point                   & Random           & Random          & Default (Road)          & Default (Road)           & Random \\
        \# of levels for fitness calculations  & 15               & 15              & 5                & 5                & 15\\
        Novelty Distance Function                & Hamming          & Hamming         & No Novelty       & No Novelty        & No Novelty\\
        \bottomrule
    \end{tabular}
\end{adjustbox}
\end{table*}

\section{}\label{}

\begin{figure}[<options>]
	\centering
		\includegraphics[<options>]{}
	  \caption{}\label{fig1}
\end{figure}

\begin{table}[<options>]
\caption{}\label{tbl1}
\begin{tabular*}{\tblwidth}{@{}LL@{}}
\toprule
  &  \\
\midrule
 & \\
 & \\
 & \\
 & \\
\bottomrule
\end{tabular*}
\end{table}

\section{}\label{}

\printcredits

\bibliographystyle{cas-model2-names}

\section{Introduction}
\label{chap:intro}

Procedural content generation (PCG) is a research field focused on generating game content, such as levels, maps, music, etc., in an automated way~\citep{togelius2011Searchbased}. PCG has numerous benefits, such as being cheaper to use than the alternative of manually designing content~\citep{hendrikx2013Procedural} and being able to generate significantly more content than would be possible through manual creation~\citep{smith2017Procedural,korn2017Procedural}.
PCG has recently garnered more attention~\citep{brewer2017computerized} as video games have become more popular~\citep{esa_2022,esa_2023}, leading to impressive results in numerous games~\citep{volz2018Evolving,gisslen2021Adversarial,earle2021Illuminating}.

However, much of the research done in the field of PCG focuses on simple, 2D tilemap games, such as \textit{Super Mario Bros}, \textit{The Legend of Zelda}, and maze games~\citep{beukman2022Procedural,khalifa2020Pcgrl,earle2021Illuminating,ferreira2014Multipopulation,shaker2011Mario}. While these are useful test domains, the games themselves are often very simple, and do not exhibit complex structures. This focus on simplicity makes it non-trivial to generalise these methods to more complex and modern games. Furthermore, few methods focus on, or excel at, generating large and complex levels, which would be necessary for PCG to become more mainstream~\citep{togelius2013Procedural}.

This has led to recent research that applies PCG to more complex titles~\citep{grbic2020Evocraft,salge2018Generative,jiang2022Learning,barthet2022openended}, one notable example being Minecraft\xspace. Minecraft\xspace is a 3D, discrete voxel-based game, making it amenable to grid-based PCG methods originally developed for 2D tilemaps. It is also more complex than these aforementioned games, and thus provides a useful domain to bridge the gap between traditional and modern games.

There are still numerous problems with current methods, however. In particular, some methods rely on significant hand-designed effort~\citep{salge2021Settlement}. These approaches carry many disadvantages, primarily cost~\citep{hendrikx2013Procedural} and being hard to generalise to new games~\citep{khalifa2020Pcgrl}. Other approaches generate levels that lack some functional requirements, such as being playable~\citep{grbic2020Evocraft}, which is a core part of PCG. Lastly, some methods generate relatively small and simple structures~\citep{jiang2022Learning,barthet2022openended}, limiting their applicability to complex games.

Our work aims to address these limitations by proposing an approach that breaks the problem of generating a complex and large-scale level down into smaller, but manageable pieces. For instance, it is simple to generate an abstract, high-level layout of a town (by considering houses, roads and gardens as the individual building blocks) while ensuring all houses are reachable via roads. Similarly, it is relatively straightforward to learn to generate a single house, garden, or farm. Composed together, however, these simple generators can easily generate a fully-fledged, and functional, town.

In particular, we develop a compositional approach to level generation, where multiple generators are hierarchically composed to generate large and complex structures. This approach is inspired by \textit{hierarchical reinforcement learning}~\citep{al2015Hierarchical,pateria2021Hierarchical}, where a complex task is broken down into smaller components and an agent learns how to optimally perform each subcomponent. We break the construction of a high-level structure (e.g. a town) into simple subtasks (e.g. houses, gardens, etc.) and train agents to generate these individual components.

This approach has three main benefits: (1) the level of control a user has over each component, being able to change each component individually (at different levels of abstraction) without modifying the others; (2) the combinatorial explosion in the number of final structures that can be generated~\citep{tasse2020Boolean,tasse2022Generalisation}; and (3) being able to specify the desired structure in an interpretable way by referencing subcomponents, allowing easier generation of complex levels compared to normal, non-hierarchical PCG methods.

Our approach builds on a recent method, PCGNN\xspace~\citep{beukman2022Procedural}, which uses neuroevolution and novelty search to evolve diverse level generators. We extend this method by hierarchically composing these generators to create large and complex structures.

We demonstrate that using composition makes it significantly easier to generate complex structures compared to using a single, non-compositional generator, an effect which becomes more pronounced as we increase the complexity of the low-level structures. Furthermore, we can automatically generate large-scale towns and cities by specifying a few, simple objectives. We finally provide a qualitative showcase of the generated levels.\footnote{Source code is publicly released at \url{https://github.com/Michael-Beukman/MCHAMR}}

\section{Background}
\label{chapter:background}
\label{sec:bg}

\subsection{Hierarchical and Compositional Reinforcement Learning}
Reinforcement learning (RL)~\citep{rlbookold} is a field focused on solving sequential decision-making problems, where an agent interacts with an environment (e.g. by placing specific tiles in a tilemap level) and receives a scalar reward signal indicating how good an action was (e.g. obtaining a high reward when removing a tile that creates a path in a maze~\citep{khalifa2020Pcgrl}).

Generally, however, \textit{long-horizon tasks}, i.e. those that require a long sequence of actions to solve~\citep{pateria2021Hierarchical} (e.g. generating a video game level by sequentially placing a large number of tiles), are often quite challenging~\citep{bellemare2016Unifying,nachum2019Does,pathak2017Curiositydriven} for the normal RL paradigm. Hierarchical RL (HRL) has emerged as a solution to this, where a long and complex task is decomposed into smaller and simpler individual tasks~\citep{pateria2021Hierarchical}. Each subtask can itself be solved using an RL policy, and the top-level policy simply chooses which subtask to perform~\citep{hengst2010Hierarchical,hengst2012Hierarchical}.

Relatedly, there has recently been more interest in \textit{compositional RL}, where agents, having learned some low-level skills, can compose them together to perform more complex behaviours~\citep{niekerk2019Composing,tasse2020Boolean,tasse2022Generalisation}. This has the additional benefit of allowing tasks to be specified in an understandable way, by referencing the lower-level skills.
\subsection{Evolutionary Algorithms}
Many PCG methods~\citep{togelius2011Searchbased,ferreira2014Multipopulation,earle2021Illuminating} use some aspects of evolutionary computing, which is a subclass of optimisation algorithms that attempt to mimic natural selection, as found in the natural world~\citep{goldberg1989genetic}.

Genetic algorithms usually consist of a collection (or population) of individuals. Each of these individuals possesses a \textit{genome}, which describes the individual (e.g. an integer vector representing the height of a platform~\citep{ferreira2014Multipopulation}). These genomes are mapped to \textit{phenotypes}, which can be thought of as the result or instantiation of this individual in the actual problem domain (e.g. a level generated using the given height information).

To obtain the next generation, the high-performing individuals (according to the \textit{fitness function}) in the current population are combined using crossover -- combining multiple parents to form a single child. These children are also mutated slightly to form the new population.
\subsubsection{NeuroEvolution of Augmenting Topologies (NEAT)}
NEAT~\citep{neat} is a genetic algorithm that evolves the weights and structure of neural networks. Generally, NEAT starts with a simple neural network with no hidden layers. Through the process of crossover and mutation, however, these networks can become more complex, thereby becoming fitter, and thus solving the problem better.
\subsubsection{Novelty Search}
Novelty search~\citep{novelty_search} uses a different idea of fitness compared to traditional genetic algorithms. Instead of rewarding individuals based on their objective performance, this algorithm instead rewards individuals for being novel compared to the rest of the population. This results in improved exploration and can help to solve hard or deceptive\footnote{Deceptive problems are those where directly maximising fitness can lead to being stuck in local minima~\citep{whitley1991Fundamental,novelty_search}.} problems.
\subsection{PCGNN\xspace}
PCGNN\xspace~\citep{beukman2022Procedural} is a method that uses NEAT~\citep{neat} and novelty search~\citep{novelty_search} to evolve level generators. The main goal of this work is to learn reusable level generators that could quickly generate multiple different levels, as opposed to searching for single levels each time one is desired.  Each individual in this population is a neural network, which can be used to generate multiple levels. To obtain a level from a network, an initial, random, tilemap is created. Then, for each tile, the neural network receives as input the surrounding tiles and outputs the current center tile. This process is repeated, sequentially, for each tile. PCGNN\xspace generally uses multiple fitness functions: (1) the normal novelty search objective, to incentivise exploration; (2) intra-generator novelty, which incentivises one neural network to generate multiple diverse levels; and (3) one or more \textit{feasibility} fitness functions, which describe the feasibility criteria for the specific game (e.g. solvability in a maze). PCGNN\xspace generates levels with comparable metrics to baselines, while being significantly faster. Additionally, the generators can generalise to unseen level sizes, allowing the generation of arbitrarily-sized levels without retraining.

\section{Related Work}

\subsection{General PCG}
While there are numerous approaches to PCG, many of them focus on generating simple levels, and are therefore difficult to generalise to more complex settings, such as modern games. Many methods use some form of search~\citep{togelius2011Searchbased}, often evolutionary-based algorithms, to maximise a specific objective function~\citep{beukman2022Procedural,earle2021Illuminating,ferreira2014Multipopulation,barthet2022openended}. However, it is challenging to design an objective function that is optimisable while also incentivising the generation of complex structures~\citep{togelius2013Procedural}. Other methods rely on a dataset of existing content (which may not be available for many games), applying machine learning to generate novel content~\citep{summerville2017Procedural,liu2021Deep,shu2021Experiencedriven}. Finally, the recent paradigm of Procedural Content Generation via Reinforcement Learning (PCGRL) generates levels using RL, training an agent policy to sequentially place tiles to maximise some reward~\citep{khalifa2020Pcgrl,earle2021Learning,jiang2022Learning}. Similarly to search-based methods, however, designing a monolithic reward function that leads to complex and functional levels can also be challenging.
\subsubsection{Generating Complex Levels}

While many approaches focus on simple games, such as \textit{Super Mario Bros}, \textit{The Legend of Zelda}, etc., there is research that rather aims to generate more complex content.
One notable example of this is the \textit{Generative Design in Minecraft (GDMC)} competition, where the task is to generate an entire settlement in Minecraft\xspace~\citep{salge2018Generative, salge2019Generative, salge2021Settlement}. This competition aims to improve the generation of content while taking the external environment into account, as well as generating holistic and more complex constructions (i.e. an entire, coherent town instead of just a single building). Many submissions to this competition, however, focused on more hand-designed, rule-based~\citep{barthet2022openended} methods specifically designed for settlement generation, which may require much effort to generalise to other scenarios.
This has led to work that focuses on automatically generating lower-level structures one would find in a settlement, such as buildings. For instance, \citet{green2019Organic} leverage constrained growth algorithms to generate useful and natural floor plans for buildings in Minecraft\xspace. They employ a modular approach, generating the building separately from the floor plan, which can be useful when customisation is desired. \citet{barthet2022openended} use a recent method, DeLeNoX~\citep{liapis2021Transforming}, to evolve diverse building generators for Minecraft\xspace using an autoencoder-based novelty score. Here the focus was on generating creative buildings, as opposed to complex and functional structures such as settlements. Additionally, these methods do not focus on how to combine these generated buildings into an actual settlement.
\subsubsection{Adversarial and Open-Ended Approaches}
Recently, PCG has also been used to generate environments on which machine learning agents can be trained. Training on a large collection of diverse and complex levels often has the benefit of making agents more robust and generalisable~\citep{justesen2018illuminating,cobbe2019quantifying}.

In some cases, level generators and game-playing agents can work in tandem, where the generator generates levels that challenge the agent. As the agent improves, the level generator must also improve to generate more complex and harder levels. Examples of this include work by \citet{gisslen2021Adversarial}, where two RL agents (one generator and one player) compete against each other; and \citet{bontrager2020Learning}, where a game-playing agent provides the learning signal to the level generator, enabling them to generate levels without explicit domain knowledge.

Some {Open-Ended Learning} methods aim to generate increasingly complex environments, alongside increasingly capable agents in an ever-evolving adversarial game. For instance, POET~\citep{wang2019POET} evolves a population of terrain layouts and agents that traverse these layouts. \citet{holder2022Evolving} instead train a single, robust agent by leveraging the automated generation of increasingly complex mazes, resulting in a natural curriculum.

Most of these methods, however, focus on simple games (such as mazes~\citep{holder2022Evolving}, 2D terrains~\citep{wang2019POET} and \textit{The Legend of Zelda}~\citep{bontrager2020Learning}), making it non-obvious how to generalise them to more complex games.
Furthermore, the focus here is often on obtaining robust and high-performing artificial agents~\citep{holder2022Evolving} instead of generating video game levels to be played and enjoyed by humans. These two goals may have different priorities in general, and focusing on the former could result in levels that are too difficult for humans.
These levels may also have different characteristics compared to human-designed ones~\citep{dharna2020Cogeneration}, making it more difficult to use these levels as an alternative to manually created content.
Finally, while considering the generation process as one large problem makes sense as an initial solution, this may limit the ability of the generator to generate levels with enough complexity to challenge the agent.
Instead, having multiple generators that solve simpler problems at different levels of abstraction could enable the generation of more complex and larger-scale structures~\citep{snodgrass2015Hierarchical}.
\subsection{Compositional PCG}
Much work has also been done on combining different PCG methods~\citep{togelius2012Compositional,liapis2019Orchestrating} to generate more complex pieces of content, or even entire games. For instance, \citet{togelius2012Compositional} combine an Answer Set Programming (ASP)-based approach~\citep{smith2011Answer,smith2010Variations} with a search-based genetic algorithm that searches over variables for this ASP. This allowed them to benefit from the advantages of each method while mitigating the disadvantages.
\citet{liapis2019Orchestrating} advocate for game design orchestration, where different content generators are combined to generate full, coherent, games. One benefit of this compositional approach is allowing algorithms to specialise in (and thus excel at generating) specific pieces of content. There are still numerous open problems in this field, however, such as how to best coordinate automated generators and human designers.

Hierarchy can also be used to improve the generation speed of PCG methods. For example, \citet{smith2014Logical} find that using ASPs to generate large levels is infeasibly slow but that using hierarchy can lead to significantly faster generation. In particular, they first generate the high-level structure of a level, followed by filling in the details within the already-defined structure. However, this work focused on using hand-designed high-level structures, which may not be easily generalisable to new games~\citep{togelius2013Procedural}.

\citet{snodgrass2015Hierarchical} also leverage hierarchy to generate structures at different scales. From a set of example levels, they extract a set of high-level and low-level patterns and fit two multi-dimensional Markov chains to this data. To generate a level, then, the high-level model generates the structure while the low-level generator fills in the details. This method results in improved generation compared to a non-hierarchical approach, but requires example levels as training data, which may not always be available~\citep{summerville2017Procedural}.

\section{Hierarchically Composing Level Generators}\label{sec:method:mcc}
This section describes our approach, \textbf{M}ulti-level \textbf{C}omposition of \textbf{H}ierarchical and \textbf{A}daptive \textbf{M}odels via \textbf{R}ecursion (\texttt{MCHAMR}\xspace), in depth.

To illustrate and explain our method, we first consider a straightforward example, generating a simple medieval town. At a high level, we can represent it as a 2D tilemap, shown in \autoref{fig:mcc:we:1-town}, with some houses, a large castle, and roads. Each of these components, however, can be composed of simpler components. For instance, a house that is a single tile in \autoref{fig:mcc:we:1-town} actually consists of external walls and an empty interior, as shown in \autoref{fig:mcc:we:2-components:house}. Using our composition algorithm (described below), we can use the definitions of these smaller structures together with the high-level map to obtain a fully-fledged and detailed town, shown in \autoref{fig:mcc:we:3-composed}. Furthermore, the user has control over each of these components. Should they wish to make a similar town but would prefer to replace or modify a specific structure, this would be possible without retraining all of the generators.

To implement this method in an automatic way, we require the concept of a \textit{generator} $g \in G$. This object can generate a tilemap $W$, which is represented as a 2- or 3-dimensional matrix, where each element is taken from some tile set $T$. Each generator optionally has a \textit{tile mapping} $M_g: T \to G$, that controls which subgenerators are used when this generator places a specific tile. For instance, in the above example, the town generator's mapping specifies that the ``house'' tile actually maps to the generator shown in \autoref{fig:mcc:we:2-components:house}. In essence, we construct a tree (\autoref{fig:mcc:high_level_tree} shows the tree for the previous example), where each node is a level generator, with parent nodes generating placeholders to be filled by their children and leaf nodes producing the lowest-level, non-abstract, structures. To generate the level, we start at the root and traverse through the tree. Finally, for each generator $g$, we also have $S_g$, which indicates the size of the subtiles of this generator, i.e. the size at which the next level of the hierarchy will be generated. As an example of this, if our town generator $g_{town}$ produces an abstract tilemap of size $10\times 10$, and has an associated $S_{g_{town}}$ of $3\times 3$, then the final level will have size $30\times 30$, with each tile in the abstract map corresponding to a $3\times 3$ block.

Given a set of generators, our algorithm (detailed in \autoref{alg:mcc}) works as follows: We start with the top-level generator, which generates a tilemap (line 4 in \autoref{alg:mcc}). In standard PCG, the procedure would terminate here. We instead go further and interpret each tile as an instruction to use another generator and place its output at that location (lines 14-16). Each of these lower-level generators can also be composed of generators. If at any point, though, the generator does not contain a \textit{tile mapping} $M_g$, we end the recursion (lines 5-6). A summary of the overall generation process is illustrated in \autoref{fig:mcc:high_level_tldr}.

This approach generally creates somewhat blocky structures, due to each lower-level tile being the same size. What we do to mitigate this is to coalesce separate connected tiles of the same type into one larger, ``logical'', tile of that type (line 12). Then, at generation time, we generate one large structure of this size, instead of many small ones.
Coalescing works by finding contiguous rectangles and merging them. We intuitively start with each tile and attempt to enlarge its dimensions, one at a time until we cannot do so any longer. This additionally allows the top-level generator to effectively control the scale at which the lower-level components get generated. We coalesce connected tiles at every level of the hierarchy before we recursively call the subgenerators. \autoref{fig:mcc:coalesce} shows an example of this process.

Now, if we are interested in using \texttt{MCHAMR}\xspace with actual, automatic level generators, they must satisfy some requirements. Specifically, the generators must generate levels quickly (as we need to generate many low-level structures); be able to generate structures of arbitrary sizes (as the sizes of the final level and its components are not fixed beforehand); and generate many diverse levels (to prevent the different structures from looking identical, and thus uninteresting to a player).

\begin{figure*}[h!]
    \captionsetup{width=.35\linewidth}
    \centering
    \begin{minipage}[t]{.45\textwidth}
        \centering
        \includegraphics[width=0.85\linewidth]{composition_we_town.pdf}
        \caption{High-level view of a town}
        \label{fig:mcc:we:1-town}
    \end{minipage}
    \begin{minipage}[t]{.45\textwidth}
        \centering
        \includegraphics[width=0.85\linewidth]{composition_we_final.pdf}
        \caption{The town after composition}
        \label{fig:mcc:we:3-composed}
    \end{minipage}
\end{figure*}

\newcommand{0.24}{0.24}
\begin{figure}
    \centering
    \begin{subfigure}{0.24\linewidth}
        \includegraphics[width=1\linewidth]{images/composition_we_house.pdf}
        \caption{House}
        \label{fig:mcc:we:2-components:house}
    \end{subfigure}
    \begin{subfigure}{0.24\linewidth}
        \includegraphics[width=1\linewidth]{composition_we_road.pdf}
        \caption{Road}
    \end{subfigure}
    \begin{subfigure}{0.24\linewidth}
        \includegraphics[width=1\linewidth]{composition_we_castle.pdf}
        \caption{Castle}
    \end{subfigure}
    \begin{subfigure}{0.24\linewidth}
        \includegraphics[width=1\linewidth]{composition_we_farm.pdf}
        \caption{Farm}
    \end{subfigure}
    \caption{Individual components. Note that the castle is composed of houses, whereas the other components consist only of low-level tiles.}
    \label{fig:mcc:we:2-components}
\end{figure}

\begin{figure}
    \centering
    \includegraphics[width=1\linewidth]{model_tree.pdf}
    \caption{An example tree structure, representing the generators involved in generating \autoref{fig:mcc:we:3-composed}.}
    \label{fig:mcc:high_level_tree}
\end{figure}

\begin{figure*}
    \centering
    \includegraphics[width=1\linewidth]{mc/model_new.pdf}
    \caption{A high-level illustration of \texttt{MCHAMR}\xspace. We first start with a top-level generator, which generates an abstract tilemap. Each tile in this map is an instruction to use a lower-level generator and to place its output at that location. Each of these generators can be further composed of other generators. In the end, we obtain a fully-fledged level.}
    \label{fig:mcc:high_level_tldr}
\end{figure*}

\begin{figure}
    \centering
    \begin{subfigure}{0.45\linewidth}
        \includegraphics[width=1\linewidth]{images/coalesce_True.pdf}
        \caption{}
    \end{subfigure}
    \begin{subfigure}{0.45\linewidth}
        \includegraphics[width=1\linewidth]{images/coalesce_False.pdf}
        \caption{}
    \end{subfigure}
    \caption{This plot shows a generated level in (a), and the result after coalescing connected tiles in (b). Cyan indicates those tiles that were coalesced into one larger tile.}
    \label{fig:mcc:coalesce}
\end{figure}

One specific method that is particularly well-suited to act as the low-level generator is PCGNN\xspace, which satisfies all of our requirements. Additional benefits include that the training time is generally quite low~\citep{beukman2022Procedural} and, while we can include detailed domain knowledge, this is not required.

\begin{algorithm}
    \caption{\texttt{MCHAMR}\xspace}\label{alg:mcc}
    \begin{algorithmic}[1]
    \State
        \Comment{We call this initially with the top-level generator, as well as the desired size of the final level.}
        \Procedure{Generate}{$g \in G, \text{size} \in \mathbb{Z}^2 \cup \mathbb{Z}^3$}
          \State \Comment{Generate a map, possibly abstract, using $g$}
          \State map = \Call{MakeMap}{g, $size / S_g$}
          \If {$M_g$ is null}
                \State return map \Comment{Return map if this is the lowest level}
          \EndIf
          \State \Comment{Otherwise recurse to the next level in the hierarchy}
          \State \Comment{Create an empty map of sufficient size}
          \State FilledOutMap = Empty(size)
          \State \Comment{For each position, tile and coalesced size in the map}
          \ForAll {$pos, tile, {S}_{c} \in \Call{Coalesce}{\text{map}}$}
            \State   \Comment{Recursively generate using the appropriate size}
            \State $\text{NewMap} = \Call{Generate}{M_g(tile), \text{size}=S_g \times {S}_{c}}$
            \State   \Comment{Place this generated map at the correct location}
            \State $\text{FilledOutMap}[pos \times S_g:(pos + {S_{c}}) \times S_g] = \text{NewMap}$
          \EndFor
          \State \Return FilledOutMap
        \EndProcedure
    \end{algorithmic}
\end{algorithm}

\subsection{Using PCGNN\xspace in \texttt{MCHAMR}\xspace}\label{sec:method:pcgnn_plus_mcc}
Having presented the workings of \texttt{MCHAMR}\xspace in \autoref{sec:method:mcc}, we next describe a concrete approach that uses PCGNN\xspace to train the low-level generators.

Firstly, we train each component separately, using some objective function that describes a feasible individual. Once each of these generators has been trained, we can compose them together, needing only to specify which tiles map to which generators. This has multiple benefits; for instance, we can train and design multiple generators in parallel, obtaining a repertoire of components that can be composed later on. The approach is also modular, so we could leverage the same generator for different purposes (e.g. a house could be used in many different scenarios).

Additionally, we can also train generators faster in this factored way compared to training one monolithic generator.
Say we want to build an $n \times n$ level, consisting of some high-level structure (e.g. an abstract map consisting of single-tile houses and roads) and low-level components (e.g. a generated house).
Let us compose the $n\times n$ level out of a high-level structure of size $\sqrt{n} \times \sqrt{n}$ and low-level components of size $\sqrt{n} \times \sqrt{n}$.
Now, during training, the flat method must generate levels of size $n \times n$. For the composed method, however, we have two separate training procedures, each generating levels of size $\sqrt{n} \times \sqrt{n}$.
Thus, the overall time complexity\footnote{We omit factors such as the population size and the number of generations as they are kept constant for both approaches.} of training the flat method would be $O((n \times n)) = O(n^2)$, whereas the composed method would be $O(2(\sqrt{n} \times \sqrt{n})) = O(n)$.
For large levels, this speedup in training time can be quite impactful. During inference, however, each method generates the same amount of tiles.

Furthermore, as there is no dependence between different level generators during training, we can redefine the meaning of a specific generator. For instance, a town generates a tilemap containing houses, roads and gardens. We could also change the interpretation of the individual tiles, resulting in this generator generating cities, consisting of towns, highways and parks. This effectively constructs multiple different tree structures, with the same generator as the root and different child generators. In general, this approach would work as long as the same feasibility criteria are valid in both cases.

Finally, while PCGNN\xspace is particularly suited to be used as the low-level generator in \texttt{MCHAMR}\xspace, this is by no means a requirement. We could use other suitable level generators (e.g. approaches such as \citep{earle2021Illuminating,shu2021Experiencedriven,earle2021Learning}), hand-designed components, or a combination of all of these. This provides a significant amount of control and flexibility, which is useful in designing a game~\citep{lai2020Towards}.

\section{Experiments and Results}
\label{chap:experiments}
\subsection{Experimental Setup}
\subsubsection{Domains}
We consider two benchmark domains to demonstrate the capabilities of \texttt{MCHAMR}\xspace. The first, where we quantitatively demonstrate the effects of composition, is a simple 2D game, where we build towns. The second domain is Minecraft\xspace, to demonstrate that our approach can work equally well in 3 dimensions, and to show some of the complex structures that were generated.
\subsubsection{Experiments}
We perform three main experiments in this section. In \autoref{sec:exp:hierarchical}, we first illustrate the benefits of having a hierarchical generation approach, as the complexity of the lower-level structures increases. The second experiment, in \autoref{sec:exp:comp_vs_flat}, directly compares our hierarchical method against a non-compositional, flat approach. Finally, in \autoref{sec:showcase}, we qualitatively evaluate our method by generating complex towns and cities in Minecraft\xspace. More information about the different experiments, including hyperparameters and fitness functions, is listed in the \refappendix{sec:appdx}.
\subsection{Hierarchical Generation}\label{sec:exp:hierarchical}
In this experiment, we show the benefits of using composition compared to a non-compositional approach. To do this, we consider a simple town level, with houses, gardens and roads. To simulate our compositional approach, where each high-level structure is simple to build, we generate a normal $10\times 10$ level using PCGNN\xspace. To simulate the effect of a non-compositional method, where each component (e.g. a house) is not trivial, we generate $20\times 20$ levels, where each non-overlapping $2 \times 2$ window is considered as a single tile. If the window consists of 4 matching tiles, a single tile of this type is placed. Otherwise, the tile is replaced with a ``default'' tile -- gardens in this case. We repeat this with window sizes of $3\times 3$, $4\times 4$, $5\times 5$ and $10\times 10$, to evaluate how the complexity of the low-level structures influences our final performance.
The window size effectively controls how many coordinated actions are required to build a low-level structure. For example, $1\times 1$ represents our composed approach where a house can be built using one top-level action, whereas the larger window sizes represent non-compositional approaches, where building a house requires multiple coordinated actions.

This experimental setup has the added benefit of being comparable, as each method uses the same fitness functions, and the only difference is in the size of the generated structures.

The fitness functions used here are (1) reachability, where houses must be reachable via roads and (2) a probability fitness, incentivising a roughly equal number of house, garden and road tiles. See the \refappendix{sec:appdx} for more details.

We compare the fitness of each method over time in \autoref{fig:mcc:results:composition}, where we demonstrate that using the compositional approach results in a higher final fitness value compared to the other, non-compositional methods. The performance decreases significantly when we have a much larger, $10\times 10$ window size (corresponding to an overall level size of $100\times 100$), where each house requires $100$ coordinated actions to build. Even this is still significantly fewer actions than a real Minecraft\xspace house. Overall, this experiment shows that simplifying the task of the top-level generator by abstracting away the details of the lower-level components is beneficial.
\begin{figure}
  \centering
  \includegraphics[width=1\linewidth]{3551-hl_all.pdf}
  \caption{A plot showing the maximum fitness value in the population (i.e., how ``correct'' the generated levels are) over time for different window sizes (corresponding to the complexity of the lower-level structures). The mean across 10 seeds is shown, with the standard deviation shaded.}
  \label{fig:mcc:results:composition}
\end{figure}

\subsection{Composition vs Flat Generation}\label{sec:exp:comp_vs_flat}
Our next experiment directly compares \texttt{MCHAMR}\xspace against a non-compositional baseline that generates the entire level using PCGNN\xspace. In particular, we are again interested in building towns, this time attempting to replicate a specific, randomly generated, town layout.

For the compositional approach, we learn two separate generators, to generate houses and towns respectively, while the non-compositional method generates the entire level at once. In particular, we have a $25\times 25$ level, consisting of a collection of $5\times 5$ houses. The high-level town structure also has a size of $5\times 5$. The fitness functions used did not include novelty, and measured the average overlap between the desired level and the generated one. The desired levels use one set layout for houses, where walls surround empty space, and a randomly generated town layout. We generate 20 of these random town layouts, train a separate generator on each of them, and average the fitness values obtained.

The fitness results over time are shown in \autoref{fig:mcc:results:composed_vs_not}, and it is clear that PCGNN\xspace's fitness cannot touch that of \texttt{MCHAMR}\xspace. Our composed method achieves significantly higher fitness, and generates much more accurate levels than the flat method. See the \refappendix{sec:appendix} for examples of the generated levels.

\begin{figure}
  \centering
  \includegraphics[width=1\linewidth]{1/composed_more_structures_better.pdf}
  \caption{Illustrating the fitness over time for \texttt{MCHAMR}\xspace (consisting of the composed town and house generators) compared to the flat, non-compositional method, corresponding to vanilla PCGNN\xspace. We run this over 20 different random layouts, and the mean is shown, with the standard deviation shaded. Each run was averaged over 10 random seeds.}
  \label{fig:mcc:results:composed_vs_not}
\end{figure}

\subsection{Showcase}\label{sec:showcase}
Finally, we evaluate our method on Minecraft\xspace, and show a few qualitative examples of interesting and complex structures that were generated by \texttt{MCHAMR}\xspace. We use the Evocraft~\citep{grbic2020Evocraft} library to place and visualise the generated structures in game.\footnote{\url{https://github.com/real-itu/Evocraft-py}}

Here, we generate 3D settlements, where each town consists of houses, gardens and roads. Additionally, to demonstrate the notion of reusing a single generator, we further generate \textit{cities} using the town generator, by redefining houses to be towns. Concretely, we use the following generators, with more information about the fitness functions used in the \refappendix{sec:appendix}:
\begin{LaTeXdescription}
  \item[Town] A high level 2D tilemap of a town.
  \item[House] A 3D house, consisting of a roof, walls and doors.
  \item[Garden] A 2D tilemap with flowers, grass, ponds, and trees.
\end{LaTeXdescription}

Some generated cities are shown in \autoref{fig:mcc:showcase:subfigs}. In \autoref{fig:mcc:showcase:town1} we have a generated city, consisting of lower-level towns, and gardens. \autoref{fig:mcc:showcase:town2} shows the same generation, without using the abovementioned coalescing technique. Here all the towns are the same size, and are not joined together.

In \autoref{fig:mcc:showcase:town3}, we use the same generator for the city and the town. We also show a first-person view of a specific section to illustrate the detail in each part of the generated settlement.

\autoref{fig:mcc:showcase:annotate} shows an annotated example of a generated city. We have the large, high-level structure of the city being generated by the top-level generator. Then, each tile that it places is transformed into a town by the town generator. We see that the coalescing here results in longer towns and the towns themselves, while not identical, contain similar repeating structures.

Finally, we note that the structures we generate are very large in the scale of standard PCG. For instance, levels in \textit{Super Mario Bros.} have size $114 \times 14$. Much of the work in Minecraft\xspace also generates relatively small structures, such as $7\times 7\times 7$ mazes~\citep{jiang2022Learning} or $20\times 20 \times 20$ lattices~\citep{barthet2022openended}. The composed towns we generate can easily be $200\times 5\times 200$ or larger, totalling more than $100\text{ }000$ blocks. Despite this massive scale, we are still able to generate coherent structures and sensible towns. Large settlements are also generated for the GDMC competition~\citep{salge2018Generative}, but unlike our approach, these generations often require significant hand-designing effort~\citep{salge2021Settlement}.

\section{Discussion and Future Work}
The approach introduced here, \texttt{MCHAMR}\xspace, follows a recent trend of emphasising the importance of more complex and open-ended creations in PCG~\citep{salge2018Generative,grbic2020Evocraft,barthet2022openended}.
Our method has numerous applications; in particular, it could be (partially) leveraged for the generation of large open-world games, e.g. Massively Multiplayer Online (MMO) games. This would allow designers freedom in specifying certain, reusable low-level components that can be composed in numerous different ways, thereby enticing players towards exploration.

Furthermore, in contrast to many other methods, we abstract away details relevant to a particular game by having separate high-level and low-level generators. Separating these responsibilities could enable the abstract generators to be used in a variety of games, needing only to swap out the low-level generators for each specific game.

Relatedly, since we independently train the generators, it would be possible to have a community-driven database of interesting and useful generators, which can then be seamlessly composed together to generate novel artifacts. This could be similar to \textit{Picbreeder}~\citep{secretan2011Picbreeder},\footnote{\url{https://nbenko1.github.io/}} where users collectively contribute to the generation of many novel and interesting images.

Our method is just a first step in this direction, and there are numerous avenues for future work. For instance, we could use a combination of different PCG methods as low-level generators~\citep{khalifa2020Pcgrl,earle2021Illuminating,jiang2022Learning}, instead of just PCGNN\xspace. Additionally, we would like to explore the use of quality-diversity algorithms~\citep{mouret2015Illuminating} to obtain a collection of diverse and high-performing low-level generators, and use these interchangeably to obtain more diverse content. Furthermore, the generated levels do not have large vertical components, due to using a 2D level for the root generator. Expanding upon this by adding more verticality (e.g. mountains, hills, multi-story houses, etc.) to the generators would also be valuable. Finally, we would like to explore more open-ended avenues, where the structures we generate increase in complexity over time, as opposed to reaching an endpoint when the feasibility fitness is maximised~\citep{grbic2020Evocraft,barthet2022openended}. This could, for example, be achieved by dynamically learning to compose different generators, or using learned objective functions.

\section{Conclusion}
We introduce \texttt{MCHAMR}\xspace, a compositional approach to procedural level generation, which leverages multiple simple generators to generate large and complex structures. Our approach has multiple benefits, such as (1) being configurable, allowing the designer to choose which low-level generators are used; (2) it being straightforward to combine different generators, without needing to specify one monolithic fitness function; and (3) by composing multiple levels of generators, each individual generator's task is much simpler, which allows for potentially less training or smaller (and thus faster) models. We demonstrate that our approach improves generation compared to a non-compositional approach, and that it is able to generate large-scale and complex settlements in Minecraft\xspace.
Ultimately, we hope that this work is the first step towards more complex and large-scale generations, which will be necessary for the adoption of PCG in the modern gaming industry.

\begin{figure*}[h!]
  \centering
  \begin{subfigure}{0.45\linewidth}
    \includegraphics[width=1\linewidth]{mc/show1.jpg}
      \caption{}
      \label{fig:mcc:showcase:town1}
  \end{subfigure}
  \begin{subfigure}{0.45\linewidth}
      \includegraphics[width=1\linewidth]{mc/show2.jpg}
      \caption{}
      \label{fig:mcc:showcase:town2}
  \end{subfigure}

  \begin{subfigure}{0.9\linewidth}
    \includegraphics[width=1\linewidth]{mc/mincraft_picture_zoom_figure.jpg}
    \caption{}
    \label{fig:mcc:showcase:town3}
  \end{subfigure}
  \caption{Demonstrating some generated cities. In (a) and (b) we use the same generators, but (a) uses coalescing whereas (b) does not. In (c) we show the result when the city generator and town generator are the same, as well as a zoomed in portion of an alleyway.}
  \label{fig:mcc:showcase:subfigs}
\end{figure*}

\begin{figure*}[h!]
  \centering
  \includegraphics[width=0.9\linewidth]{mc/minecraft_small.jpg}
  \caption{An annotated example of a generator similar to that in \autoref{fig:mcc:showcase:town1}}
  \label{fig:mcc:showcase:annotate}
\end{figure*}


\section{Introduction}
\IEEEPARstart{T}{he} simulation of eddy currents in electrical machines consisting of many steel sheets with the finite element method quickly leads to infeasibly large equation systems. In many machines each sheet in the active zone is exposed to the same field, which allows for a great reduction in computational effort by simulating only a single sheet. However, this reduced problem is still far from trivial. One method to further simplify the problem while maintaining a good approximation of the solution is by spacial decomposition.

The thickness of one sheet is less than a millimeter while the length and width are in the range of meters. A method to treat the two dimensional (2D) cross section and the one dimensional (1D) thickness of the sheet as two coupled problems has been presented in \cite{BottChiamp:02}. It solves the two problems iteratively until convergence is reached. The nature of this coupling has been analyzed in more detail in \cite{PippBelaDlaArkk:10}.

In \cite{GysSabDul:06} and \cite{HenSteHamGeu:15} different approaches have been presented which isolate the one dimensional problem as a pre-processing step in order to obtain parameters for the two dimensional one.

The 2D/1D multiscale finite element method (MSFEM) presented in \cite{Schoeb:19} uses ideas from the multiscale finite element method to use classic finite element functions for the two dimensional problem while approximating the dependence on the third axis with pre-defined polynomial shape functions, similar to the method presented in \cite{RasDlaFonPippBelaArkkio:11} which is based on trigonometrical shape functions. This enables the solution of the problem within a single iteration while requiring only a mesh for the two dimensional cross section of the sheet. It is also able to include the insulation layers between sheets and correctly treat the edge effect \cite{HollEE:20}.

This paper presents an error estimator for the $\vecT$-formulation of the 2D/1D MSFEM. It is based on flux equilibration and based on the same theory as the error estimator for the $\vecT$-formulation for the MSFEM presented in \cite{Schoeb:21}. In order to fit within the 2D/1D MSFEM framework it has been restructured so both the construction and the evaluation of the estimator require only the two dimensional mesh while being valid in the complete three dimensional domain.

A numerical example shows that the estimator gives a good approximation of the error in both a global and a local sense. This latter property is used to implement adaptive mesh refinement which allows for a high accuracy of the 2D/1D MSFEM solution while requiring significantly less degrees of freedom than uniform mesh refinement.

\section{The $\vecT -\Phi$-Formulation}

We use the $\vecT -\Phi$ formulation for the reference solution of the eddy current problem as described in \cite{Biro:99}. The problem domain $\Omega$ is split into the conducting domain $\Omega_c$, consisting of the steel sheet, and the non-conducting domain $\Omega_0$, consisting of the air regions and the insulation layers. The sheet is assumed to be axis-aligned with the cross-section in the $x-y$ plane and the thickness aligned with the $z$ axis. The total thickness of $\Omega$ is $d=d_{Fe}+d_0$ with the thickness of the sheet $d_{Fe}$ and the thickness of the insulation layer $d_0$.

The magnetic field strength $\vecH$ is written as
\begin{align}
\vecH = \vecT - \nabla\Phi + \vecH_{BS}
\end{align}
with the current vector potential $\vecT\in H(\opcurl ,\Omega_c)$ fulfilling $\opcurl\vecT=\vecJ$, the magnetic scalar potential $\Phi\in H^1(\Omega)$ and a prescribed Biot-Savart field $\vecH_{BS}$. The strong formulation of the eddy current problem in the frequency domain is given as
\begin{align}\label{eq:strong}
\opcurl\rho\opcurl\vecT + i\omega\mu(\vecT - \nabla\Phi + \vecH_{BS}) = \veczero ,
\end{align}
where $\rho=\sigma^{-1}$ is the electric resistivity with the electric conductivity $\sigma$, $\mu$ is the magnetic permeability, $\omega = 2\pi f$ with the frequency $f$ and $i$ is the imaginary unit.

Multiplication with a test function and integration by parts, together with the auxiliary condition $\opdiv\vecB =0$, lead to the weak formulation: Find $\vecT\in H(\opcurl ,\Omega_c)$ and $\Phi\in H^1(\Omega)$ so that
\begin{align}\label{eq:weak3D}
\begin{split}
\int_\Omega \rho\opcurl\vecT\cdot\opcurl\vecv + i\omega\mu(\vecT - \nabla\Phi)\cdot(\vecv - \nabla q) \\
=-\int_\Omega i\omega\mu\vecH_{BS}\cdot(\vecv - \nabla q)
\end{split}
\end{align}
for all $\vecv\in H(\opcurl ,\Omega_c)$ and all $q\in H^1(\Omega)$.

\section{The 2D/1D MSFEM $\vecT$-Formulation}

This paper uses the 2D/1D MSFEM approach for the $\vecT$-formulation which has been described in detail in \cite{Schoeb:19} and \cite{Holl:20}. The three dimensional unknown components $\vecT - \nabla\Phi$ are approximated by
\begin{align}\label{eq:T2D1D}
\vecT_{\text{2D/1D}}= \left( \begin{matrix}
\phi_0(z)\vecT_{0,x}(x,y) + \phi_2(z)\vecT_{2,x}(x,y) \\
\phi_0(z)\vecT_{0,x}(x,y) + \phi_2(z)\vecT_{2,y}(x,y)
\\ 0
 \end{matrix}\right),
\end{align}
where $\vecT_2\in H(\opcurl_{2D},\Omega_{2D,c})$ and $\vecT_0 = \nabla\Phi_0$ with $\Phi_0\in H^1(\Omega_{2D})$ are defined on the two dimensional projection $\Omega_{2D}$ of $\Omega$. Here and in the following, coordinates $x$, $y$ or $z$ in the index denote the individual components of a vector-valued function. The shape functions $\phi_0$ and $\phi_2$ are predefined piecewise polynomial of order $0$ and $2$, respectively, see also