\section{Introduction}

 A Riemannian $n$-manifold $M$  has lower integral Ricci curvature bound if there are constants $p>\frac{n}{2}, R>0, H$ such that
 $$\bar k(H ,p, R)=\sup_{x\in M}\left(\frac1{\operatorname{vol}(B_R(x))}\int_{B_R(x)} \rho_H^p dv\right)^{\frac{1}{p}} =\sup_{x\in M}\left(-\kern-1em\int_{B_R(x)} \rho_H^p dv\right)^{\frac{1}{p}}$$
 has an upper bound, where $\rho_H=\max\{-\rho(x)+(n-1)H, 0\}$ and $\rho\left( x\right) $ is the smallest
eigenvalue for the Ricci tensor $\operatorname{Ric} : T_xM\to T_xM$. If $R=\operatorname{diam}(M)$, the diameter of $M$, we also denote $\bar k(H, p, R)=\bar k(H, p)$.
Compared with manifolds with lower Ricci curvature bound, many basic properties and results have been generalized to manifolds with lower integral Ricci curvature bound. For instance, the  Laplacian comparison \cite{PW1, Au1}, relative volume comparison \cite{PW1,CW} and almost splitting theorem, almost metric cone rigidity \cite{PW2, TZ, Ch2}.

In this note, we will study the almost maximal volume entropy rigidity for compact manifolds with lower integral Ricci curvature bound.

Recall that for a compact manifold $M$, the volume entropy of $M$ is defined as
$$h(M)=\lim_{R\to \infty}\frac{\ln\operatorname{vol}(B_R(\tilde x))}{R},$$
where $\tilde x\in \tilde M$, the universal cover of $M$ and the limit always exists and independent of $\tilde x$ \cite{Ma}.

For a compact $n$-manifold $M$ with lower Ricci curvature bound $\operatorname{Ric}_M\geq -(n-1)$, the maximal volume entropy rigidity says that  $h(M)\leq n-1$ (by Bishop volume comparison) and when $h(M)$ obtains the maximal $h(M)=n-1$, $M$ is isometric to a hyperbolic manifold \cite{LW}. And the almost maximal volume entropy rigidity says that for $\operatorname{diam}(M)\leq d$,  when $h(M)$ is close to $n-1$, $M$ is diffeomorphic and Gromov-Hausdorff close to a hyperbolic manifold \cite{CRX}. For non-smooth metric measure spaces with some curvature dimension condition ($\mathsf{RCD}$ or Alexandrov), there are also some rigidity results about volume entropy taking maximal or almost maximal \cite{CDNPSW, Ji, Ch1}.

For compact manifolds $M$ with lower integral Ricci curvature bound, $\bar k(-1, p)\leq \delta<\delta_0(n, p, d)$,  in \cite{CW}, with G. Wei, we gave an optimal estimate of volume entropy,
$$h(M)\leq n-1+c(n, p,d)\delta^{\frac12}, \quad d=\operatorname{diam}(M).$$

In this note we will show that for integral Ricci curvature when $h(M)$ is close to $n-1$, the universal cover $\tilde M$ is Gromov-Hausdorff close to a hyperbolic space form $\Bbb H^k$, $k\leq n$:
\begin{Thm}
Given $n, d, p>\frac{n}{2}$, there exist $\delta(n, d,  p), \epsilon(n, d,  p)>0$, such that for $0< \delta<\delta(n, d,  p)$, $0<\epsilon<\epsilon(n, d, p)$, if a compact $n$-manifold $M$ satisfies that
$$\operatorname{diam}(M)\leq d, \quad \bar k(-1, p)\leq \delta, \quad h(M)\geq n-1-\epsilon,$$
then $\tilde M$ is $\Psi(\delta, \epsilon | n, d, p)$-Gromov-Hausdorff close to a simply connected hyperbolic space form $\Bbb H^k$, $k\leq n$, where $\Psi\to 0$ when $\delta, \epsilon\to 0$ and $n, d, p$ fixed.
\end{Thm}

By this result, it is easy to derive that in the non-collapsing case, i.e., $\operatorname{vol}(M)\geq v>0$, the almost maximal volume entropy rigidity holds:

 \begin{Thm}
Given $n, d, v>0, p>\frac{n}{2}$, there exist $\delta(n, d, v, p), \epsilon(n, d, v, p)>0$, such that for $0< \delta<\delta(n, d, v, p)$, $0<\epsilon<\epsilon(n, d, v, p)$, if a compact $n$-manifold $M$ satisfies that
$$\operatorname{diam}(M)\leq d, \quad \bar k(-1, p)\leq \delta, \quad \operatorname{vol}(M)\geq v,\quad h(M)\geq n-1-\epsilon,$$
then $M$ is diffeomorphic to a hyperbolic $n$-manifold by a $\Psi(\delta, \epsilon | n, d, v, p)$-isometry.
\end{Thm}

The proofs of our results is similar as the one of \cite[Theorem D]{CRX}. The key part is using the almost maximal volume entropy condition
$$h(M)\geq n-1-\epsilon,$$
and relative volume comparison to derive that for each fixed $\rho>2d$, $B_{\rho}(\tilde x)\subset \tilde M$ is Gromov-Hausdorff close to a ball in a warped product space
$\Bbb R\times_{e^r}Y$ where $Y$ is a connected length space. Then the same argument as \cite[Lemma 4.4]{CRX} gives that $\tilde M$ is Gromov-Hausdorff close to the hyperbolic manifold $\Bbb H^k$.

A difficulty here in the key part is that we do not have effective relative volume comparison between two arbitrary large annuluses in the integral Ricci curvature case.  However we can use the almost maximal volume entropy condition to supply all the controls we need (see \eqref{alm-vol-1} and \eqref{alm-vol-2} and Claim1-3 of the proof of Theorem~\ref{warp-pro}).

The author would like to thank Professor Guofang Wei for the recommendation of the topic of this note.

\section{Preliminaries}
In this section, we will give some properties we need for manifolds with integral Ricci curvature bound.
For a complete $n$-manifold $M$, $x\in M$,  let $r=d(x, \cdot)$ be the distance function from $x$ and let
$\psi=\max\{\Delta r-\underline{\Delta}_H r, 0\}$, where $\underline{\Delta}_H$ is the Laplacian operator in the simply connected space $\underline{M}_H^n$ with constant sectional curvature $H$. Then $\psi=0$ if $\operatorname{Ric}_M\geq (n-1)H$.
\begin{Thm}  \label{com-int}
Given $n, p> \frac{n}{2}$,$R>0, H$, for a complete $n$-manifold $M$, fix $x \in M$,
then the following holds:

{\rm (2.1.1)} Laplacian comparison estimates \cite[Lemma 2.2]{PW1}:
\begin{equation}
-\kern-1em\int_{B_R(x)}\psi \leq  c(n, p) \bar k^{\frac12}(H, p, R), \quad  c(n, p)= \left(\frac{(n-1)(2p-1)}{2p-n}\right)^{\frac{1}{2}}; \label{lap-com}
\end{equation}

{\rm (2.1.2)} Relative volume comparison  \cite{PW1, CW}:
There exist $\delta_0=\delta(n, p, H), c=c(n, p, H)$, such that if $\bar k(H, p, 1)\leq \delta\leq \delta_0$, then for each $0<r<R$, $R<\frac{\pi}{\sqrt H}$ for $H>0$,
 \begin{equation}\frac{\operatorname{vol}(\partial B_R(x))}{\operatorname{vol}(B_R(x))}\leq \frac{\svolsp{H}{R}}{\svolball{H}{R}}+c\bar k^{\frac12}(H, p, R), \label{rel-vol-1}\end{equation}
 \begin{equation}
 \frac{\operatorname{vol}(A_{r, R}(x))}{\svolann{H}{r, R}}\leq \frac{\operatorname{vol}(B_r(x))}{\svolball{H}{r}}\left(1+\left(e^{(\max\{R, 1\}-r)c\delta^{\frac12}}-1\right)\frac{\svolball{H}{R}}{\svolann{H}{r, R}}\right), \label{rel-vol-2}
 \end{equation}
 \begin{equation}
 \frac{\operatorname{vol}(B_R(x))}{\svolball{H}{R}}\leq e^{(\max\{R, 1\}-r)c\delta^{\frac12}}\frac{\operatorname{vol}(B_r(x))}{\svolball{H}{r}}. \label{rel-vol-3}
 \end{equation}

\end{Thm}

If $M$ has integral Ricci curvature bound, then by \cite{Au2}, the universal cover  $\tilde M$ also has integral Ricci curvature bound:
\begin{Thm}\cite[Lemma 1.0.1]{Au2} \label{univ-cover}
Given $n, p>\frac{n}{2}, d>0, H$, there is $\delta=\delta(n, p, d, H)>0,\ c(n, H, d)>0$ such that if a compact Riemannian $n$-manifold $M$ satisfies that
$$\bar k(H, p)\leq \delta, \quad \operatorname{diam}(M)\leq d,$$
then for any $\tilde x\in \tilde M$, the universal cover of $M$, and for any $R\geq 3d$,
\begin{equation}
\left(-\kern-1em\int_{B_R(\tilde x)}\rho_H^p\right)^{\frac1p}\leq c(n, H, d)\, \bar k(H, p).  \label{univ-rho}
\end{equation}
\end{Thm}

By the relative volume comparison, the set of manifolds with integral Ricci curvature bound is precompact.
\begin{Thm}[\cite{PW1, Au2} Precompactness] \label{compact}
For $n\geq 2, p>\frac{n}{2}, H$, there exists $c(n, p, H)$ such that if a sequence of  compact Riemannian $n$-manifold $M_i$ satisfies that
$\operatorname{diam}(M)^2\bar{k_i}(H, p)\leq c(p, n,  H)$, then  there are subsequences of $\{(M_i, x_i)\}$ and $\{(\tilde M_i, \tilde x_i)\}$ that converge in the pointed Gromov-Hausdorff topology where $\tilde M_i$ is the universal cover of $M_i$.
\end{Thm}

\section{Proofs of the main results}

\subsection{Warped product structure}
In this subsection, we will prove the following almost warped product rigidity for manifolds with lower integral Ricci curvature (compared with \cite[Theorem 1.4]{CRX}).

\begin{Thm} \label{key-lem}
Given $p>\frac{n}2, d>0$, there are $\delta_0=\delta_0(n, p, d)$, $\epsilon_0=\epsilon_0(n, p, d)$, such that for $\delta<\delta_0, \epsilon<\epsilon_0$, if a compact Riemannian $n$-manifold $M$ satisfies that
$$\bar k(-1, p)\leq \delta, \quad h(M)\geq n-1-\epsilon, \quad \operatorname{diam}(M)\leq d,$$
then for each $D>8d$,
there are $L_i\to \infty$ large, such that for any $\rho\in (2d, {D}/{4})$, there are disjoint metric balls,
$B_{\rho}(q^i_j)\subset A_{L_i, L_i+D}(\tilde x)$, such that
$$d_{GH}\left(B_{\rho}\left(q^i_j\right),
	B_{\rho}\left((0,y)\right)\right)\leq \Psi\left(\delta, \epsilon, L_i^{-1} | n, d, p, D\right),$$
	where $B_{\rho}((0,y))$ is a metric ball in a warped
	product space $\Bbb R^1\times_{e^s} Y$, $Y$ is a connected length space. And
	\begin{equation}\frac{\operatorname{vol}(\cup_jB_{\rho}(q^i_j))}{\operatorname{vol}(A_{L_i, L_i+D}(\tilde x))} \geq c(n, p, d, D)>0. \label{max}\end{equation}
\end{Thm}

As the discussion in \cite{CRX}, by \cite[Theorem 3.6]{CC1} (see also \cite[Theorem 5.1]{CRX} where the condition $\operatorname{Ric}_M\geq (n-1)H$ can be replaced by the condition that Segment inequality (see \cite{Ch2} for integral Ricci curvature) and local doubling property \eqref{rel-vol-3} hold), to prove Theorem~\ref{key-lem}, we only need to show that

\begin{Thm} \label{warp-pro}
	Let the assumptions be as in Theorem~\ref{key-lem}. For each $D>8d$, there are $L_i\to \infty$ large, such that for $\rho\in (2d, D/4)$, $0<\alpha<1$, there are disjoint metric balls,
	$B_{\rho}(q^i_j)\subset A_{L_i, L_i+D}(\tilde x)$, satisfying \eqref{max} and

	\noindent (i) for $y\in B_\rho(q^i_j)$, there is $z\in \partial B_{L_i+ D}(\tilde x)$
	satisfying $|\tilde x y|+ |yz|\leq L_i+D+ \Psi(\delta, \epsilon, L_i^{-1} |n, p, d,D)$;

	\noindent (ii) for each $q^i_j$, let $u(y)=|y \tilde x|-|q^i_j \tilde x|$, there is a
	smooth function $\tilde f$ satisfying

	(ii1) $|\tilde f-e^u|<\Psi(\delta, \epsilon, L_i^{-1} |n, p, D,d)$ for all $x\in B_{(1-\alpha)\rho}(q^i_j)$.

	(ii2) $-\kern-1em\int_{B_\rho(q^i_j)}|\nabla \tilde f-\nabla e^u|^2\le
	\Psi(\delta, \epsilon, L_i^{-1} |n,p, D,d)$.

	(ii3) $-\kern-1em\int_{B_{(1-\alpha)\rho}(q^i_j)}|\operatorname{Hess}\tilde f-e^u|^2
	\le \Psi(\delta, \epsilon, L_i^{-1}|n,p,D,\alpha,d)$.

\end{Thm}

Consider a compact $n$-manifold $M$ as in Theorem~\ref{key-lem}. By the definition of volume entropy, we know that $h(M)\geq n-1-\epsilon$ implies that there is $R_0>0$ such that  for $R>R_0$,
 \begin{equation}\frac{\operatorname{vol}(\partial B_R(\tilde x))}{\operatorname{vol}(B_R(\tilde x))}\geq n-1-\epsilon. \label{alm-vol-1}\end{equation}
 And by \cite[Lemma 4.2]{CRX}, for each $D>8d$, there are  $L_i\to \infty$ such that for $i>i_0$
 \begin{equation}
 \frac{\operatorname{vol}(\partial B_{L_i+D}(\tilde x))}{\operatorname{vol}(\partial B_{L_i}(\tilde x))}\geq e^{(n-1-\epsilon)D}-\epsilon. \label{alm-vol-2}
 \end{equation}

 By \eqref{univ-rho}, if $\bar k(-1, p)\leq \delta<\delta(n, p, d)$, for any $R>3d$, in the universal cover of $M$, $\tilde M$,
 \begin{equation}
 \bar k_{\tilde M}(-1, p, R)\leq c(n, p, d)\bar k(-1, p)\leq c(n, p, d)\delta. \label{uni-cur}
 \end{equation}

 \begin{proof}[Proof of Theorem~\ref{warp-pro}]

 Let $L_i\to \infty$, $i\geq i_0$, be as in \eqref{alm-vol-2}.  Take $\delta_0$ as in (2.1.2) and Theorem~\ref{univ-cover}.

 Claim 1:
 $$ -\kern-1em\int_{A_{L_i, L_i+D}(\tilde x)} \left| \Delta r - (n-1)\right|\leq \Psi(\delta, \epsilon, L_i^{-1} | n, p, d, D).$$

  By \eqref{alm-vol-1}, we have that for  $L>R_0$ and $D>0$ fixed,
 \begin{eqnarray*}
 \operatorname{vol}(A_{L, L+D}(\tilde x))&= & \int_L^{L+D}\operatorname{vol}(\partial B_{R}(\tilde x)) dR\\
 &\geq & \int_L^{L+D}(n-1-\epsilon)\operatorname{vol}(B_R(\tilde x))dR\geq \int_L^{L+D}(n-1-\epsilon)\operatorname{vol}(B_L(\tilde x))dR \\
 &=& (n-1-\epsilon)D\operatorname{vol}(B_L(\tilde x)).
 \end{eqnarray*}
 Thus
 \begin{equation}
 \frac{\operatorname{vol}(B_{L+D}(\tilde x))}{\operatorname{vol}(A_{L, L+D}(\tilde x))}=1+\frac{\operatorname{vol}(B_L(\tilde x))}{\operatorname{vol}(A_{L, L+D}(\tilde x))}
 \leq  1+ \frac1{(n-1-\epsilon)D}. \label{abgeq}
 \end{equation}

 By Laplacian  comparison \eqref{lap-com}, \eqref{uni-cur} and \eqref{abgeq},
 \begin{eqnarray*}
 -\kern-1em\int_{A_{L, L+D}(\tilde x)}  \Delta r &\leq & -\kern-1em\int_{A_{L, L+D}(\tilde x)}  \underline{\Delta} r +\psi\\
 &= & -\kern-1em\int_{A_{L, L+D}(\tilde x)}  \underline{\Delta} r +\frac{\operatorname{vol}(B_{L+D}(\tilde x))}{\operatorname{vol}(A_{L, L+D}(\tilde x))} -\kern-1em\int_{B_{L+D}(\tilde x)}\psi\\
 &\leq &-\kern-1em\int_{A_{L, L+D}(\tilde x)}  \underline{\Delta} r +\left(1+\frac1{(n-1-\epsilon)D}\right) -\kern-1em\int_{B_{L+D}(\tilde x)}\psi\\
 & \leq & n-1+ \Psi(\delta, L^{-1} | n, p, d, D),
 \end{eqnarray*}
where in the last inequality we used
$$\underline{\Delta}r=(n-1)\frac{\cosh r}{\sinh r}\to n-1, \text{ as } r\to \infty.$$

 On the other hand,  for $L>\max\{L_{i_0}, R_0\}$, $L=L_i$, by \eqref{alm-vol-1}, \eqref{alm-vol-2}, \eqref{rel-vol-2}
 \begin{eqnarray*}
 -\kern-1em\int_{A_{L, L+D}(\tilde x)}  \Delta r &= &  \frac{\operatorname{vol}(\partial B_{L+D}(\tilde x))-\operatorname{vol}(\partial B_L(\tilde x))}{\operatorname{vol}(A_{L, L+D}(\tilde x))}\\
 & \geq & \left(e^{(n-1-\epsilon)D}-1-\epsilon\right)\frac{\operatorname{vol}(\partial B_L(\tilde x))}{\operatorname{vol}(A_{L, L+D}(\tilde x))}\\
  & = & \left(e^{(n-1-\epsilon)D}-1-\epsilon\right)\frac{\operatorname{vol}(\partial B_L(\tilde x))}{\operatorname{vol}(B_L(\tilde x))}\frac{\operatorname{vol}(B_L(\tilde x))}{\operatorname{vol}(A_{L, L+D}(\tilde x))}\\
  & \geq & \left(e^{(n-1-\epsilon)D}-1-\epsilon\right)(n-1-\epsilon)\left(1+\left(e^{Dc\delta^{\frac12}}-1\right)\frac{\svolball{-1}{L+D}}{\svolann{-1}{L, L+D}}\right)^{-1}\frac{\svolball{-1}{L}}{\svolann{-1}{L, L+D}}\\
  &\geq & n-1-\Psi(\delta, \epsilon, L^{-1} | n, p, d, D),
 \end{eqnarray*}
 where in the last inequality we used
 $$\lim_{L\to \infty}\frac{\svolball{-1}{L}}{\svolann{-1}{L, L+D}}=\frac1{e^{(n-1)D}-1}.$$

 As in \cite{CRX},
let $E$ be a maximal subset of $\{q_i, \,B_{\rho}(q_i)\subset A_{L, L+D}(\tilde x)\}$
such that for all $q_{i_1}\neq q_{i_2} \in E$, $B_{\rho}(q_{i_1})\cap B_{\rho}(q_{i_2})=\emptyset$.
Let $F=\bigcup_{q_i\in E}B_{\rho}(q_i)$.

Claim 2:  There is $C(n, p, d, D)>0$ such  that
\begin{equation}\frac{\operatorname{vol}(F)}{\operatorname{vol}(A_{L, L+D}(\tilde x))}\geq C(n, p, d, D). \label{F-large}\end{equation}

Let $G=\bigcup_{q_i\in E}B_{2\rho}(q_i)$.
By the maximality of $E$, $A_{L+\rho, L+D-\rho}(\tilde x) \subset G$.
Then by \eqref{alm-vol-1}, \eqref{rel-vol-2}
\begin{eqnarray}
\frac{\operatorname{vol}(G)}{\operatorname{vol}(A_{L, L+D}(\tilde x))} &\geq & \frac{\operatorname{vol}(A_{L+\rho, L+D-\rho}(\tilde x))}{\operatorname{vol}(A_{L, L+D}(\tilde x))} \nonumber\\
& = & \frac{\int_{L+\rho}^{L+D-\rho}\operatorname{vol}(\partial B_R(\tilde x))dR}{\operatorname{vol}(A_{L, L+D}(\tilde x))} \nonumber \\
&\geq &\frac{(n-1-\epsilon)(D-2\rho)\operatorname{vol}(B_L(\tilde x))}{\operatorname{vol}(A_{L, L+D}(\tilde x))} \nonumber \\
&\geq & (n-1-\epsilon)(D-2\rho)\left(1+\left(e^{Dc\delta^{\frac12}}-1\right)\frac{\svolball{-1}{L+D}}{\svolann{-1}{L, L+D}}\right)^{-1}\frac{\svolball{-1}{L}}{\svolann{-1}{L, L+D}}. \nonumber \\
&\geq & C(n, p, d, D). \label{G-large}
\end{eqnarray}
By \eqref{rel-vol-3},
$$\frac{\operatorname{vol}(B_{2\rho}(x))}{\svolball{-1}{2\rho}}\leq e^{DC\delta^{1/2}_0} \frac{\operatorname{vol}(B_{\rho}(x))}{\svolball{-1}{\rho}}.$$
And thus
\begin{equation}\frac{\operatorname{vol}(F)}{\operatorname{vol}(G)}\geq \frac{\sum_{q_i\in E} \operatorname{vol}(B_{\rho}(q_i))}{\sum_{q_i\in E}
		\operatorname{vol}(B_{2\rho}(q_i))}\geq e^{-DC\delta_0^{1/2}}\frac{\svolball{-1}{\rho}}{\svolball{-1}{2\rho}}. \label{FG-large}\end{equation}

Then \eqref{F-large} is derived  by \eqref{G-large} and \eqref{FG-large}.

Let
$$S=\{y\in B_{L+D}(\tilde x),\, \exists z\in \partial B_{L+D}(\tilde x), d(y, \tilde x)+d(z, y)=L+D\}.$$

Claim 3:
\begin{equation}
\frac{\operatorname{vol}(S\cap A_{L, L+D}(\tilde x))}{\operatorname{vol}(A_{L, L+D}(\tilde x))}\geq 1-\Psi(\epsilon, \delta, L^{-1} | n, p, D, d). \label{pass-thr}
\end{equation}

By \eqref{rel-vol-1}, \eqref{alm-vol-1}
\begin{eqnarray*}
\frac{\operatorname{vol}(S)}{\svolball{-1}{L+D}} & \geq & \left(1+c\delta^{\frac12}\frac{\svolball{-1}{L+D}}{\svolsp{-1}{L+D}}\right)^{-1}\frac{\operatorname{vol}(\partial B_{L+D}(\tilde x))}{\svolsp{-1}{L+D}}\\
& \geq & \left(1+c\delta^{\frac12}\frac{\svolball{-1}{L+D}}{\svolsp{-1}{L+D}}\right)^{-1}(n-1-\epsilon)\frac{\operatorname{vol}(B_{L+D}(\tilde x))}{\svolsp{-1}{L+D}},
\end{eqnarray*}
i.e.,
\begin{equation}
\frac{\operatorname{vol}(S)}{\operatorname{vol}(B_{L+D}(\tilde x))}\geq  \left(1+c\delta^{\frac12}\frac{\svolball{-1}{L+D}}{\svolsp{-1}{L+D}}\right)^{-1}(n-1-\epsilon)\frac{\svolball{-1}{L+D}}{\svolsp{-1}{L+D}}.
\end{equation}
Since
$$\lim_{L\to \infty}\frac{\svolball{-1}{L+D}}{\svolsp{-1}{L+D}}=\frac1{n-1},$$
we know that for $L$ large,
$$\frac{\operatorname{vol}(S)}{\operatorname{vol}(B_{L+D}(\tilde x))}\geq 1-\Psi(\delta, \epsilon, L^{-1} | n, D, p, d).$$

Note that by \eqref{alm-vol-1}, \eqref{rel-vol-3},
\begin{eqnarray*}
\frac{\operatorname{vol}(A_{L, L+D}(\tilde x))}{\operatorname{vol}(B_{L+D}(\tilde x))} & = &\frac{\int_L^{L+D}\operatorname{vol}(\partial B_R(\tilde x)) dR}{\operatorname{vol}(B_{L+D}(\tilde x))}\\
&\geq &\frac{\int_L^{L+D}(n-1-\epsilon)\operatorname{vol}(B_R(\tilde x)) dR}{\operatorname{vol}(B_{L+D}(\tilde x))}\\
&\geq & \frac{(n-1-\epsilon)D\operatorname{vol}(B_{L}(\tilde x))}{\operatorname{vol}(B_{L+D}(\tilde x))}\\
&\geq & (n-1-\epsilon)De^{-Dc\delta^{\frac12}}\frac{\svolball{-1}{L}}{\svolball{-1}{L+D}}.
\end{eqnarray*}
Thus \eqref{pass-thr} holds.

By Claim 2 and Claim 3, we have that
\begin{equation}
\frac{\operatorname{vol}(S\cap F)}{\operatorname{vol}(F)}\geq 1-\Psi(\epsilon, \delta, L^{-1} | n, D, p,d).  \label{pass-thr-2}
\end{equation}

Take $0<\eta<1$ (which will be specified later) and let
$$E'(\eta)=\left\{q_i\in E,\,\,\, \;\frac{\operatorname{vol}(B_\rho(q_i)\setminus S)}{\operatorname{vol}(B_\rho(q_i))}<\eta\right\},$$
 $F'(\eta)=\bigcup_{q_i\in E'(\eta)}B_{\rho}(q_i)$.
 Then
\begin{equation}\frac{\operatorname{vol}(F'(\eta))}{\operatorname{vol}(F)}\ge1-\eta^{-1}\Psi(\delta,\epsilon, L^{-1}|n, D, p, d). \label{F1-large}\end{equation}

In fact, by \eqref{pass-thr-2}
$$\Psi(\epsilon, \delta, L^{-1} | n, D, p, d)\operatorname{vol}(F)\geq \operatorname{vol}(F\setminus S)\geq \operatorname{vol}((F\setminus F'(\eta))\setminus S)\geq \eta\operatorname{vol}(F\setminus F'(\eta)).$$

Now as the discussion of \cite[Lemma 5.7, 5.8]{CRX}, by Claim 1 and Claim 2, we can take $\eta=\Psi^{\frac12}(\delta, \epsilon, L^{-1} | n, p, D, d)$ such that for
$$E''(\eta)=\left\{q_i\in E,\,\, -\kern-1em\int_{B_\rho(q_i)} \left|\Delta r-(n-1)\right|<\eta^{-1}\Psi(\delta, \epsilon,L^{-1}|n,p,D, d)\right\},$$
and  $F''(\eta)=\bigcup_{q_i\in E''(\eta)}B_{\rho}(q_i)$ we have that
\begin{equation}\frac{\operatorname{vol}(F''(\eta))}{\operatorname{vol} (F)}\ge 1-\eta. \label{F2-large}\end{equation}

Take $q\in E'(\eta)\cap E''(\eta)$. Then by the definition of $E'(\eta)$ and doubling property \eqref{rel-vol-3},  (i) holds for any $y\in B_{\rho}(q)$ and
\begin{equation}-\kern-1em\int_{B_\rho(q)} \left|\Delta r-(n-1)\right|<\Psi(\delta, \epsilon,L^{-1}|n,p,D, d).\label{lap-ball}\end{equation}

Let $f=e^u, u(y)=|\tilde xy|-|\tilde xq|$ and let  $\tilde f$ be the solution of
$$\begin{cases}\Delta \tilde f = ne^u, & \text{in } B_\rho(q);\\
\tilde f =f, &\text{on } \partial B_\rho(q).\end{cases}$$
Then as in \cite[Lemma 5.9]{CRX}, by \eqref{lap-ball}, we have that
\begin{eqnarray}
	-\kern-1em\int_{B_{\rho}(q)\setminus C_p}|\Delta (\tilde f-e^u)|&=&-\kern-1em\int_{B_{\rho}(q)\setminus C_p} |n e^u - e^u(|\nabla u|^2 + \Delta u)| \nonumber\\
	&=& -\kern-1em\int_{B_{\rho}(q)\setminus C_p}e^u|n-1-\Delta u| \nonumber\\
	&\leq & \Psi(\delta, \epsilon, L^{-1}|n,p,D ,d). \label{lap-f}
	\end{eqnarray}
By a standard argument as in \cite[Lemma 5.9]{CRX}, we have (ii1)-(ii3). Namely, Maximal principle \cite{DWZ} (cf. \cite[Theorem 2.4]{Ch2}) and \eqref{lap-f} implies $|\tilde f-f|\leq c(n, p, D, d)$. Then integral by parts gives (ii2). By Gradient estimates \cite{DWZ} (cf. \cite[Theorem 2.5]{Ch2}) and (ii2) we have that  $|\nabla f-\nabla\tilde f|\leq c(n, p, D, d)$ which implies (ii1) by Segment inequality \cite{Ch2}. Finally, Bochner's formula, cut-off function \cite{DWZ} (cf. \cite[Lemma 2.8]{Ch2}) and (ii1), (ii2) gives (ii3).

And \eqref{max} follows by \eqref{F1-large}, \eqref{F2-large} and Claim 2.
\end{proof}

\subsection{Proofs of Theorem 1.1 and 1.2}

By Theorem~\ref{key-lem}, the following proofs of Theorem 1.1 and 1.2 are the same as in \cite{CRX}. Here we will give a rough discussion.

Argue by contradictions.  By the procompactness Theorem~\ref{compact}, assume there is a sequence of $n$-manifolds $M_i$ satisfies:
 \begin{equation}
 \operatorname{diam}(M_i)\leq d, \quad \bar k_i(-1, p)\leq \delta_i, \quad h(M_i)\geq n-1-\epsilon_i
  \end{equation}
 with $\delta_i\to 0$, $\epsilon_i\to 0$ and the following communicate diagram:

 \begin{equation}\begin{array}[c]{ccc}
(\tilde M_i,\tilde x_i,\Gamma_i)&\xrightarrow{GH}&(\tilde X,\tilde x,G)\\
\downarrow\scriptstyle{\pi_i}&&\downarrow\scriptstyle{\pi}\\
(M_i,x_i)&\xrightarrow{GH} &(X, x),
\end{array} \end{equation}
 where $\Gamma_i=\pi_1(M_i, x_i)$ the fundamental group of $M_i$. Note that by \cite{Ket} and \cite{Ch2}, $\tilde X$ is a $\mathsf{RCD}(-(n-1), n)$-space. And by \cite{Ch2} or the theory of $\mathsf{RCD}$-spaces (see \cite{GR, So}), $G$ is a Lie group.

 To prove Theorem 1.1, we will show that $\tilde X$ is isometric to a simply connected hyperbolic space form $\Bbb H^k$, $k\leq n$. And to get Theorem 1.2, by \cite{PW2}, we only need to show that  if in addition there is $v>0$ such that $\operatorname{vol}(M_i)\geq v$, then $X$ is isometric to a hyperbolic $n$-manifold.

By Theorem~\ref{key-lem}, for any fixed $D>4\rho>8d$, there are $L_j\to \infty$ large, $B_{\rho}(q_j)\subset A_{L_j, L_j+D}(\tilde x_i)$,
$$d_{GH}\left(B_{\rho}\left(q_j\right),
	B_{\rho}\left((0,y_i)\right)\right)\leq \Psi\left(\delta, \epsilon, L_j^{-1} | n, d, p, D\right),$$
where $B_{\rho}((0,y_i))$ is a metric ball in a warped product space $\Bbb R^1\times_{e^s} Y_i$, $Y_i$ is a connected length space.

Since $\operatorname{diam}(M_i)\leq d$, there is $\gamma_{ij}\in \Gamma_i$ such that $B_{\frac{\rho}{2}}(\tilde x_i)\subset B_{\rho}(\gamma_{ij}(q_j))=\gamma_{ij}(B_{\rho}(q_j))$.  Thus
$$d_{GH}\left(B_{\frac{\rho}2}\left(\tilde x_i\right),
	B_{\frac{\rho}2}\left((0,y_i)\right)\right)\leq \Psi\left(\delta, \epsilon, L_j^{-1} | n, d, p, D\right).$$
Let $L_j\to \infty$, we have that
$$d_{GH}\left(B_{\frac{\rho}2}\left(\tilde{x_i}\right),
	B_{\frac{\rho}2}\left((0,y_i)\right)\right)\leq \Psi\left(\delta, \epsilon | n, d, p, D\right).$$

Let $i\to \infty$, we derive that for any  fixed $D>4\rho>8d$ there is a connected length metric space $Y$
	such that
	$$B_{\frac{\rho}2}\left(\tilde{x}\right)= B_{\frac{\rho}2}\left((0,y)\right),$$
	where $B_{\frac{\rho}2}((0,y))$ is a metric ball in a warped
	product space $\Bbb R^1\times_{e^s} Y$, i.e.,
$$\tilde X=\Bbb R\times_{e^s}Y.$$

Now by the regularity of $\tilde X$ (see \cite[Theorem 4.7]{Ch2} or use the regularity of $\mathsf{RCD}$-spaces), we can take $\tilde x$ as a regular point. Then the same argument as the proof of \cite[Lemma 4.4]{CRX} gives that $\tilde X=\Bbb H^k$, $k\leq n$.

If in addition there is $v>0$, such that $\operatorname{vol}(M_i)\geq v$, then $k=n$ and thus the identity component of $G$, $G_0=\{e\}$, i.e., $G$ is discrete. To see $X$ is a hyperbolic manifold, one only need to show $G$ acting freely on $\tilde X$. This fact can be seen by the same argument as in \cite[Theorem 2.1]{CRX} where one needs the volume convergence theorem \cite{PW2} and almost metric cone rigidity and almost splitting theorem  \cite{PW2, TZ, Ch2}.


\section{Introduction}

From the  top-left corner of the  map, 2 minutes 38  seconds after the
beginning of  the game, the  blue player sends two  \emph{stalkers}, a
basic  fast-moving  unit  of  the Protoss  faction,  towards  the  red
player's base.  Red has the same number of stalkers to defend himself,
but  Blue's  micromanagement  is  so  efficient  that  the  battle  is
completely at Blue's advantage.

Red is defending  well, and he managed to  produce \emph{immortals}, a
strong unit  known to be  a hard counter  against an army  composed of
stalkers. However,  Blue is continuously, tirelessly  sending waves of
stalkers  against Red's  army,  and combined  with  an excellent  unit
control, has overwhelmed the opponent that has no other choice than to
resign.

Despite the headlong, stubborn strategy of Blue, who did not scout the
opponent and was  then rolling this strategy out  blindly, and despite
the  good  strategical  decisions  from  Red,  Blue's  domination  was
indisputable. This was the third  game between the professional player
MaNa, in  red, versus  Alphastar, in  blue, on  December 19,  2018. In
fact, this  describes most of the  games played by Alphastar  that day
and  some months  later  on  the StarCraft~2\xspace  ladder:  Alphastar starts  and
finishes a game  with the same strategy rolled out  at the perfection,
without any significant adaptations regarding its opponent's strategy.

But Alphastar is not an exception  in StarCraft AI: the large majority
of    StarCraft~1\xspace   and    StarCraft~2\xspace    bots   have    scripted   or    unadaptive
behaviors\cite{Certicky2019}.    Despite    being   potentially   very
effective, those bots  are somehow getting around  the difficulty, and
thus the interest,  of RTS games used as AI  benchmarks, by exploiting
those benchmarks' flaws and imperfections.

Several directions  are possible for  making StarCraft bots  with some
real capacities of adaptability.  One  way is to design a non-scripted
bot, able  to play  the three  races on  StarCraft~1\xspace and  StarCraft~2\xspace with  the same
high-level decision-making mechanisms.

However, to  enable homogeneous  spatial reasoning  over both  StarCraft~1\xspace and
StarCraft~2\xspace, bots need a terrain analysis tool working the same way on these
two games.   Ideally, such  a tool  should be  flexible enough  to fit
different needs in  terms of terrain analysis, to be  exploited at the
best by different bots applying different methods.

This is the starting  point of this work. In this  paper, we propose a
flexible method to tackle terrain  analysis in both StarCraft games as
a  combinatorial  optimization  problem,  that  can  be  expressed  by
different models  supporting different analyses. After  presenting our
method  and our  combinatorial  optimization problem  models, we  show
experimental  results of  the C++  library we  developed, tested  upon
diverse StarCraft~1\xspace and StarCraft~2\xspace maps.

\section{Background}

\subsection{RTS games and StarCraft}

A Real-Time Strategy game, or RTS game, is a genre of video game where
players must gather resources to develop an army, and must destroy the
army  or  the buildings  of  other  players  to win.   Unlike  classic
strategic  board games  such as  Chess, players  are not  making moves
alternatively, by simultaneously in real-time. The most popular way to
play this kind of games involves two players in a 1 vs 1 game.

This  study tackles  terrain analysis  on the  two widely  popular RTS
games of  the StarCraft series:  the first one  ``StarCraft'' together
with its extension ``StarCraft: Brood  War'', denoted in this paper as
\emph{StarCraft 1}, and the second one ``StarCraft II'' under its last
version named ``Legacy of the  Void'', denoted here as \emph{StarCraft
  2}. To explain something concerning both games, we will simply write
\emph{StarCraft}.   Both  games  have  a similar  gameplay  with  some
different  features,  such  as   unit  characteristics  and  some  map
properties.

In StarCraft, players must gather two types of resources (minerals and
gas) in order to construct buildings.  Those buildings are required to
produce units, to improve some unit characteristics or even to add new
ones.  All of these have a given cost to be paid in resources.

Games are played  on a rectangular map, discretized  into tiles called
\emph{buildable} tiles,  upon which buildings can  be constructed, and
smaller tiles called \emph{walkable} tiles,  which are discrete in StarCraft~1\xspace
but continuous values  in StarCraft~2\xspace (so not tiles per  se), on which units
can walk. Indeed,  some pixels on a map can  be walkable without being
buildable.  This  mostly happens at  the edge of some  natural borders
such as cliffs or water.

Like most RTS games, the map is covered by a ``fog of war'' preventing
players  seeing   enemy  units  that   are  not  next  to   their  own
units. However, since each game on  a given map will always start with
the same initial properties (except the starting position of players),
it is  considered that the  map topology  and properties, such  as the
position and quantity of each resource, are known.

\subsection{Terrain Analysis}

A bot  playing StarCraft must  know the  terrain topology and  the map
properties to be able to  do some spacial reasoning. Spacial reasoning
is  necessary to  make  good decisions  such as  where  to expend  for
colonizing an unclaimed part of the  map, where to attack the opponent
in priority, and where defense must be reinforced.

Terrain  analysis  is gathering  and  processing  data about  the  map
topology and properties to  have a qualitative spatial representation,
required to  make spatial  reasoning.  In  StarCraft, map  topology is
characterized among other things by  the terrain height (low, high and
very high, to take StarCraft~1\xspace terminology,  and a rare fourth level in StarCraft~2\xspace)
and  the  nature  of  each   tile  paving  the  map  (walkable  and/or
buildable).  Map properties  include the height and width  of the map,
the  position and  the quantity  of resources,  the possible  starting
position  of  players,  the  presence,  position  and  hit  points  of
destructible obstacles, etc.

One of the main  jobs done by a terrain analysis  is splitting the map
into regions,  and spotting choke points  that are easy to  defend and
make evident region delimiters.

\section{Related work}

There are only a few relevant  papers dealing with terrain analysis in
RTS  games,  and  more  specifically about  StarCraft.   We  can  cite
Perkins'  article in  2010  to  be the  first  significant work  about
terrain   analysis   for    StarCraft~1\xspace~\cite{Perkins2010},   describing   the
\emph{Brood War Terrain Analysis}  library, or~BWTA.  In 2016, Uriarte
and    Ontañón   have    improved   Perkings'    work   and    propose
BWTA2~\cite{Uriarte2016}.

Some other terrain analysis tools have been developed for StarCraft~1\xspace, such as
BWEM\footnote{\href{https://github.com/N00byEdge/BWEM-community}{github.com/N00byEdge/BWEM-community}},
and                              its                             clone
\textsc{Overseer}\footnote{\href{https://gitlab.com/OverStarcraft/Overseer}{gitlab.com/OverStarcraft/Overseer}}
for StarCraft~2\xspace.  However, none of  them have led  to a publication,  to the
best of  our knowledge,  and they  do not  propose the  computation of
polygons surrounding regions, a useful  feature available in both BWTA
and BWTA2 to get the list of points composing borders of each region.

Since our  work propose  the same  features as  BWTA and  BWTA2, and
share with the latter the same  first steps, we briefly describe these
tools in the following.

In a nutshell, BWTA proposed by Perkins~\cite{Perkins2010} follows
the steps in Alg.~\ref{algo:bwta}:

\begin{algorithm}
    \caption{BWTA}
    \label{algo:bwta}
    \begin{algorithmic}[1]
      \State Convert the map into a Boolean 2D-vector of walkable tiles.
      \State Detect connected components of obstacles by flood-fill.
      \State Create contour polygons around these connected components.
      \State Compute the Voronoi diagram of walkable lands.
      \State Prune the Voronoi diagram by eliminating  leafs with  a parent
      farther away  from the obstacle  contour than the leaf  itself. This
      minimal distance from  a point to the contour is  called the point's
      \emph{radius}.
      \State Identity nodes   of the Voronoi diagram with  smaller radius than
      their    neighbors.    Those    nodes   are    considered   to    be
      choke point. Regions are then areas on each side of a choke point.
      \State Merge regions  following some  criteria about their areas and the
      radius of their common choke point.  This step is considered by the
      author to  be problematic  since the final  result depends  on which
      order regions have been merged.
      \State Compute choke point polygons.
      \State Compute region polygons.
    \end{algorithmic}
\end{algorithm}

Uriarte and Ontañón's library BWTA2~\cite{Uriarte2016} follows BWTA's main
steps, with some differences in  the algorithm and the implementation.
Algorithmic differences are written in Alg.~\ref{algo:bwta2}.

For detecting connected components of obstacles (Step~2), BWTA2 uses a
contour  tracing algorithm  proposed by  Chang et  al~\cite{Chang2004}
instead of a flood-fill algorithm.  This brings two advantages: 1.  It
allows detecting at the same time the inner and outer contours of each
component.  2.   Each inner tile  is labeled,  allowing us to  know in
constant time to which component a tile belongs to.

Step 4 did  not exist in BWTA. Obstacle contours  are simplified using
the    \texttt{boost::geometry}    library     and    its    algorithm
\texttt{simplify},    which    is    an    implementation    of    the
Ramer-Douglas-Peucker algorithm~\cite{Douglas1973}.

\begin{algorithm}
    \caption{BWTA2}
    \label{algo:bwta2}
    \begin{algorithmic}[1]
      \State Convert the map.
      \State Detect connected components of obstacles with a contour
        tracing algorithm.
      \State Create contour polygons.
      \State Simplify contours.
      \State Compute the Voronoi diagram.
      \State Prune  the Voronoi  diagram.
      \State Identity nodes.
      \State Merge regions.
      \State Compute choke point polygons.
      \State Compute region polygons.
    \end{algorithmic}
\end{algorithm}

\noindent%
The major differences between BWTA and BWTA2 implementations are:
\begin{itemize}
\item Voronoi diagram are computed using the \texttt{boost} library in
  BWTA2, when BWTA is using  the \texttt{CGAL} library. Compare to the
  latter,  the \texttt{boost}  implementation  build Voronoi  diagrams
  containing more information, like the  coordinates of the centers of
  the  inscribed  circles tangent  to  three  points of  the  obstacle
  contour, which gives us a centroid of each region for free.
\item Pruning the Voronoi diagram  takes advantages of the R-Tree data
  structure~\cite{Guttman1984}    in     BWTA2,    on     which    the
  \texttt{boost::geometry} library  lies on.  Indeed, R-Tree  are data
  structures  used  for  spatial   searching.   Combine  with  packing
  algorithms~\cite{Leutenegger1997,    Garcia1998}   implemented    in
  \texttt{boost::geometry} to  make bulk loading, it  allows answering
  very  quickly  to  many  different queries  about  the  overlapping,
  crossing, etc, of geometrical elements.
\item  Building region  polygons also  takes advantage  of R-Trees  in
  BWTA2,  since it  boils down  to  a query  computing the  difference
  between an obstacle contour with the polygon of each choke point.
\end{itemize}

\section{Terrain Analysis as Combinatorial Optimization}

In this paper, we present a new terrain analysis working with both StarCraft~1\xspace
and StarCraft~2\xspace,  named \textsc{Taunt}\xspace\footnote{The source code,  experimental setup
  and results can be found at \href{https://github.com/richoux/Taunt/releases/tag/0.1}{github.com/richoux/Taunt/releases/tag/0.1}}.

\subsection{Features}\label{sec:features}

\textsc{Taunt}\xspace offers the same features BWTA  and BWTA2 provide: split the map
into regions, mark choke points and base placements, compute contour
polygons of regions and choke points, etc.

The new features  compare to BWTA/BWTA2 are listed below.  To the best
of our knowledge, the two first  ones have not been implemented by any
other terrain analysis tools for StarCraft.
\begin{itemize}
\item Proposing a unique terrain analysis library working with StarCraft~1\xspace and
  StarCraft~2\xspace maps, with the same library interface.
\item Offering different  options of  terrain analysis,  to better  fit
  different needs.
\item Allowing  dynamic terrain analysis, such  as recomputing regions
  after  some  dynamic  event  like the  suppression  of  destructible
  obstacles (also implemented  in by the StarCraft~1\xspace  terrain analysis library
  BWEM).
\end{itemize}

\textsc{Taunt}\xspace stands for ``Terrain Analysis: UNiversal Tool''. Our goal is to
propose a terrain  analysis library which is universal  because it can
be used  for both StarCraft  games, but  also universal because  it is
able to analyze the same map differently, aiming to provide an adapted
analysis to various StarCraft bots.

\subsection{Process}\label{sec:process}

\textsc{Taunt}\xspace roughly follows  the same steps as BWTA2 until  its fifth step,
with  a   significant  difference  at   Step~2.   It  also   uses  the
\texttt{boost::geometry}  library,  then  exploiting the  R-Tree  data
structure   for   diverse   queries.    Its  process   is   given   in
Alg.~\ref{algo:taunt}.

\begin{algorithm}
    \caption{\textsc{Taunt}\xspace}
    \label{algo:taunt}
    \begin{algorithmic}[1]
      \State Convert the map.
      \State Detect connected components {\bf of walkable lands} with a contour
        tracing algorithm.
      \State Create contour polygons.
      \State Simplify contours.
      \State Split the  land into areas regarding their  height and if
      they are buildable or not.
      \State Compute contour polygons of unbuildable areas
      (slopes, bridges, etc).
      \State Spot the clusters of resources in each area.
      \State For each area with  more than one resource cluster, run
      the combinatorial optimization problem modeled and solved within
      the framework GHOST\cite{Richoux2016}.
      \State Compute region polygons.
    \end{algorithmic}
\end{algorithm}

One problem  with all existing  terrain analysis libraries for  StarCraft~1\xspace or
StarCraft~2\xspace is that they tend to cut  the map into numerous regions. Some of
these regions  do not  contain any  relevant strategic  properties and
would be  probably not  considered as an  independent region  by human
players.  This  is due  to the  fact that  all existing  libraries are
building regions by  considering each slight narrowing  of the ground,
even large ones, as a choke point.

We  wanted to  counter-balance  this  with \textsc{Taunt}\xspace,  and  to propose  a
different way  (actually, different ways) to  cut the map. To  be sure
all regions have some strategical interest, we ensure that all of them
must  contain  exactly one  \emph{resource  cluster},  \textit{i.e.,}\xspace a  pack  of
mineral  patches,  with  or  without  gas  geyser  around,  with  some
exceptions like islands, areas  surrounded by walkable but unbuildable
lands, and areas surrounded by  areas of different heights but without
any resource clusters (which is very rare in practice).

Let's use  the StarCraft~2\xspace  map \emph{Oxide  LE} in  Fig.~\ref{fig:oxide} to
illustrate the different steps of Alg.~\ref{algo:taunt}.

\begin{figure}[htbp]
	\centering
  \includegraphics[width=0.7\linewidth]{oxide}
  \caption{Oxide LE (StarCraft 2 map)}\label{fig:oxide}
\end{figure}

At Step~1, \textsc{Taunt}\xspace gathers information about the map via the right API,
\textit{i.e.,}\xspace
BWAPI\footnote{\href{https://github.com/bwapi/bwapi}{github.com/bwapi/bwapi}}
for                   StarCraft~1\xspace                   maps                   and
CPP-SC2\footnote{\href{https://github.com/cpp-sc2/cpp-sc2}{github.com/cpp-sc2/cpp-sc2}}
for StarCraft~2\xspace  maps. Step~2 uses  the same contour tracing  algorithm from
Chang et  al~\cite{Chang2004}, but to compute  connected components of
walkable lands  rather than  obstacles like  in BWTA2.   Although this
algorithm is  from 2004, a  recent survey from He  et al~\cite{He2017}
indicates that  it is  still state-of-the-art for  computing connected
components together with contours.

After Step~3 and~4,  we obtain labeled connected  components and their
contour.    The    result   gives    what    we    can   observe    in
Fig.~\ref{fig:oxide_contour},   where   green  parts   are   connected
components (only one in this map) together with their contour in black.

\begin{figure}[htbp]
	\centering
  \includegraphics[width=0.7\linewidth]{oxide_contour}
  \caption{Connected components and contours (Steps 1-4)}\label{fig:oxide_contour}
\end{figure}

Step~5  consists in  splitting each  component of  walkable land  into
separated areas regarding their height  and if they are unbuildable or
not.   In StarCraft~2\xspace,  unbuildable parts  are usually  slopes, bridges  and
woods, and are therefore natural choke points.  In StarCraft~1\xspace, in addition to
slopes  and bridges,  we can  also  have large  chunks of  unbuildable
areas,  usually located  in  the  central part  of  the  map (see  for
instance  Fig~\ref{fig:circuit_breakers_short}).  Step~6  computes the
contour polygons of these unbuildable areas.

The     result    of     Steps~5    and~6     can    be     seen    in
Fig.~\ref{fig:oxide_regions}. Blue  parts are unbuildable  areas. Low,
high and very high areas are respectively in yellow, khaki and green.

\begin{figure}[htbp]
	\centering
  \includegraphics[width=0.7\linewidth]{oxide_regions}
  \caption{Splitting areas by height (Steps 5-6)}\label{fig:oxide_regions}
\end{figure}

Since we  aim to have  exactly one  resource cluster per  region (with
some exceptions listed at the beginning  of this section), we need to
locate and  count clusters on each  walkable area. This is  done with
Step~7, and areas with more than  one resource cluster will be handled
by Step~8. Only  buildable areas are concerned by  these steps: since,
by  definition, players  cannot  build bases  upon unbuildable  tiles,
there are never resource clusters on unbuildable areas.

In  Fig.~\ref{fig:oxide_resources}, we  can see  resource clusters  in
blue or red boxes. Red dots are  the centroid of a cluster, and orange
lines  connect this  centroid  to  all tiles  upon  which  there is  a
resource of the cluster.

\begin{figure}[htbp]
	\centering
  \includegraphics[width=0.7\linewidth]{oxide_resources}
  \caption{Spotting resource clusters in areas (Step 7)}\label{fig:oxide_resources}
\end{figure}

If there is only one cluster in an area, it is framed by a blue box on
the figure.   Otherwise, if they  are two  or more clusters,  they are
framed by a red box. In that case, if \(n\) resource clusters exist on
the same  area, we need  to find  \(n-1\) separations to  make regions
containing  exactly  one  cluster  each.   To  do  this,  we  solve  a
combinatorial  optimization  problem   (Step~8)  to  find  separations
satisfying  some   mandatory  constraints  and  optimizing   a  giving
objective  function.   We  show   separations  found  by  solving  two
combinatorial optimization problems while trying to minimize the total
length of  separations (Fig.~\ref{fig:oxide_short}),  corresponding to
choke  points,  and  while  trying   to  minimize  the  least  squares
difference    of    region   surfaces    (Fig.~\ref{fig:oxide_areas}).
Separations are represented by red lines.

\begin{figure}[htbp]
	\centering
  \includegraphics[width=0.7\linewidth]{oxide_short}
  \caption{Building region: short separations (Steps 8-9)}\label{fig:oxide_short}
\end{figure}

\begin{figure}[htbp]
	\centering
  \includegraphics[width=0.7\linewidth]{oxide_areas}
  \caption{Building region: equivalent surfaces (Steps 8-9)}\label{fig:oxide_areas}
\end{figure}

Once regions have been computed, it  is trivial to merge two separated
regions by an  obstacle if the latter is destroyed,  and to run Step~8
on this merged region if making  a new separation is required. The way
\textsc{Taunt}\xspace decides separations area by area,  allows us to reanalyze a map
locally, without the need to reconsider it as a whole.

\subsection{Intuition behind our combinatorial optimization models}\label{sec:model}

We  modeled the  problem of  placing  \(n-1\) separations  in an  area
containing \(n\) resource clusters to  make \(n\) regions with exactly
one  resource  cluster  each,  with  \(n \geq  2\),  in  a  Constraint
Programming formalism  called Error Function Optimization  Problem, or
EFOP~\cite{Richoux2021}.

An  EFOP model  is  actually an  Error  Function Satisfaction  Problem
model, or EFSP, together with an objective function we aim to maximize
or minimize. An EFSP model is defined  by a set of variables, a set of
domains, \textit{i.e.,}\xspace the possible values each  variable can take, and a set of
constraints  determining which  combinations  of  variable values  are
possible or forbidden. Our EFSP model is defined as follows:
\cspmodel%
{All possible  separations, \textit{i.e.,}\xspace  all possible pairs  of points  on the
  contour polygon of an area,}%
{Each  variable   has  the  domain  \(\{0,1\}\),   indicating  if  its
  corresponding separation is selected or not,}%
{\begin{enumerate}\item  \emph{NoCrossings}:  No separations  crossing
    each other, \item  \emph{MaxOneClusterPerRegion}: Separations must
    split  the terrain  into  regions such  that  each region  exactly
    contains one resource cluster.\end{enumerate}}%

In  EFSP  and  EFOP  models,  constraints  are  represented  as  error
functions. For the two constraints in our model, their error function
is expressed as follows:
\begin{itemize}
\item \emph{NoCrossings}: Number of separations crossing each other.
\item  \emph{MaxOneClusterPerRegion}: The  highest number  of resource
  clusters on the  same region minus 1, added to  the number of regions
  without any clusters.
\end{itemize}

Having  models as  small as  possible, \textit{i.e.,}\xspace  with few  variables, small
domains and few constraints, is important to solve them faster.  We
have the following tricks to reduce the model size:
\begin{itemize}
\item    Ill-formed   separations,    \textit{i.e.,}\xspace   crossing    resources   or
  unwalkable/unbuildable  tiles,  are filtered  out  from  the set  of
  variables before running the constraint solver.
\item Since  we know how  many separations we  must have to  get \(n\)
  regions, we randomly select \(n-1\)  initial separations and ask the
  solver to handle  the problem as a permutation  problem. This allows
  us  not to  consider a  constraint  checking the  correct number  of
  selected separations.
\end{itemize}

In order to  allow better separations, we enrich the  set of variables
by  adding some  points in  the contour  polygon to  break long  lines
(typically, when  the contour contains  an edge of the  map). Although
this increases the model size by  adding variables, it may allow nicer
separations improving the objective function.

After these variable  reduction tricks and this  enrichment, we obtain
models from  some hundreds to  2,000 variables, regarding the  map and
their areas. The mean numbers of variables among areas within the same
maps are given in Table~\ref{tab:maps}.

We use this EFSP model for  the experiments in this paper. When \textsc{Taunt}\xspace
will  be  released,  we  plan  to  propose  other  models  with  other
constraints to offer more  diverse analysis possibilities to StarCraft
bot authors. For instance, we could  add a constraint to force regions
to have a  minimal surface, or to get  perfectly symmetric separations
on symmetrical maps.

We  get an  EFOP model  upon this  EFSP model  by adding  an objective
function. We have tested two different ones:
\objective%
{\begin{enumerate}\item  \emph{MinSeparationLength}: Minimize  the sum
    of separation length. \item \emph{LeastSquaresAreas}: Least squares area difference, \textit{i.e.,}\xspace minimize the difference of region areas.\end{enumerate}}%

The different region-making we got  with these two objective functions
can        be       observed        in       Fig~\ref{fig:oxide_short}
and~\ref{fig:oxide_areas}, respectively.

\subsection{Our formal combinatorial optimization models}

The EFOP model above is informal and is here to give the intuition. We
show below the formal EFOP model:
\cspmodel%
{\(V = \{v_1, v_2, \ldots, v_k\}\), with \(v_i\) a possible separation}%
{\(D_i = \{0,1\}, \forall i \in [1,k]\)}%
{\(C = \{f_{cross}, f_{clust}\}\)}%
\vspace{-0.3cm}
\begin{IEEEeqnarray*}{rCl}
  f_{cross}(\vec v) & = & \#\{(v_i, v_j) \mid
  cross(v_i, v_j), \forall 1 \leq i,j \leq k, i \neq j\}\\
  f_{clust}(\vec v) & = & Max( 0,
  Max(\#cluster_1,  \ldots, \#cluster_n) - 1 )\\ & &+ \#\{region_j \mid \#cluster_i = 0\}
\end{IEEEeqnarray*}
\noindent%
with  \(\vec  v  =  (v_1,   v_2,  \ldots,  v_k)\),  \(f_{cross}\)  and
\(f_{clust}\) the error  functions representing constraints NoCrossing
and  MaxOneClusterPerRegion,  respectively,  \(cross(v_i,  v_j)\)  the
predicate returning  true iff  \(v_i\) and  \(v_j\) are  crossing each
other,  and \(\#cluster_i\)  the number  of resource  clusters in  the
\(i\)-th region.

Thus, our objectives functions are:
\objective%
{\(O = \{f_{sep}, f_{areas}\}\)}%
\vspace{-0.3cm}
\begin{IEEEeqnarray*}{rCl}
  f_{sep}(\vec v)  & = &  Min \sum_{i=1}^k \left( v_i  \times length_i
  \right)\\
  f_{areas}(\vec v) & = & Min \sum_{i=1}^n\left( mean\_area - area_i \right)^2
\end{IEEEeqnarray*}
\noindent%
with  \(length_i\)  the length  of  the  \(i\)-th separation  \(v_i\),
\(area_i\) the surface  of the \(i\)-th region  and \(mean\_area\) the
mean surface of considered regions.

These   models    have   been   implemented   using    the   framework
GHOST~\cite{Richoux2016}, which contains a local search solver to find
a solution of the problem within  a given timeout. For our experiments
presented   in    Section~\ref{sec:xp},   we   set   a    timeout   of
\(n \times 100\)ms  to find separations in each  area containing \(n\)
resource clusters, with \(n \geq 2\). \textsc{Taunt}\xspace contains a mechanism that
double timeouts  and relaunch this  solving step if no  solutions have
been found in its previous run.

\section{Experimental results}\label{sec:xp}

We  tested our  library over  the 10  StarCraft~1\xspace maps  from the  annual AIIDE
StarCraft                                                           AI
competition\footnote{\href{https://www.cs.mun.ca/~dchurchill/starcraftaicomp/}{www.cs.mun.ca/~dchurchill/starcraftaicomp}}
and  the 7  StarCraft~2\xspace  maps from  the  pre-season 11  of  the SC2AI  Arena
competition\footnote{\href{https://aiarena.net/}{aiarena.net}}.    Map
names as well as the mean number of variables of their EFOP models are
listed  in Table~\ref{tab:maps},  and visual  results considering  the
\emph{MinSeparationLength}   objective    function   are    given   in
Fig.~\ref{fig:maps}, except Oxide  LE since it is  our running example
in Section~\ref{sec:process}.

Tables~\ref{tab:xp}  and~\ref{tab:sc2_runtimes}  give \textsc{Taunt}\xspace  runtimes
considering  the   EFOP  model  with   the  \emph{MinSeparationLength}
objective   function,  but   the  \emph{LeastSquaresAreas}   objective
function  leads to  equivalent runtimes.  Unless the  chosen objective
function is computation-heavy, \textsc{Taunt}\xspace  runtimes generally depend on the
satisfaction part of the combinatorial problem model.

\begin{table}[htbp]
  \caption{StarCraft maps  used for experiments and  mean number
    of variables of their EFOP models.}
  \begin{center}
    \begin{tabular}{|c|r|c|r|}
      \hline
      \multicolumn{2}{|c|}{StarCraft~1\xspace maps}&\multicolumn{2}{c|}{StarCraft~2\xspace maps}\\
      \hline
      Name & Mean \#vars & Name & Mean \#vars\\
      \hline
      Benzene & 308 & Deathaura LE & 732 \\
      \rowcolor{Gray}
      Destination & 0 & Jagannatha LE & 1434 \\
      Heartbreak Ridge & 673& Lightshade LE & 1103\\
      \rowcolor{Gray}
      Aztec & 292 & Oxide LE & 1285\\
      Tau Cross & 2052& Pillar Of Gold LE & 1001\\
      \rowcolor{Gray}
      Andromeda & 164& Romanticide LE & 1188\\
      Circuit Breakers & 339 & Submarine LE & 454\\
      \hhline{|~~|--}
      \rowcolor{Gray}
      Empire of the Sun & 508 & \multicolumn{2}{c}{\cellcolor{white}} \\
      Fortress & 495 & \multicolumn{2}{c}{(LE: Ladder Edition)}\\
      \rowcolor{Gray}
      Python & 1063 & \multicolumn{2}{c}{\cellcolor{white}}\\
      \cline{1-2}
    \end{tabular}
    \label{tab:maps}
  \end{center}
\end{table}

\begin{figure*}[htbp]
	\centering
	\begin{subfigure}[t]{0.24\linewidth}
		\centering
    \includegraphics[width=\linewidth]{benzene_short}
		\caption{Benzene (StarCraft 1)}\label{fig:benzene_short}
	\end{subfigure}
  \hfill
	\begin{subfigure}[t]{0.24\linewidth}
		\centering
    \includegraphics[width=\linewidth]{destination_short}
		\caption{Destination (StarCraft 1)}\label{fig:destination_short}
	\end{subfigure}
  \hfill
	\begin{subfigure}[t]{0.24\linewidth}
		\centering
    \includegraphics[width=\linewidth]{heartbreak_ridge_short}
		\caption{Heartbreak Ridge (StarCraft 1)}\label{fig:heartbreak_ridge_short}
	\end{subfigure}
  \hfill
	\begin{subfigure}[t]{0.24\linewidth}
		\centering
    \includegraphics[width=\linewidth]{aztec_short}
		\caption{Aztec (StarCraft 1)}\label{fig:aztec_short}
	\end{subfigure}
  \vskip\baselineskip
	\begin{subfigure}[t]{0.24\linewidth}
		\centering
    \includegraphics[width=\linewidth]{tau_cross_short}
		\caption{Tau Cross(StarCraft 1)}\label{fig:tau_cross_short}
	\end{subfigure}
  \hfill
	\begin{subfigure}[t]{0.24\linewidth}
		\centering
    \includegraphics[width=\linewidth]{andromeda_short}
		\caption{Andromeda (StarCraft 1)}\label{fig:andromeda_short}
	\end{subfigure}
  \hfill
	\begin{subfigure}[t]{0.24\linewidth}
		\centering
    \includegraphics[width=\linewidth]{circuit_breakers_short}
		\caption{Circuit Breakers (StarCraft 1)}\label{fig:circuit_breakers_short}
	\end{subfigure}
  \hfill
	\begin{subfigure}[t]{0.24\linewidth}
		\centering
    \includegraphics[width=\linewidth]{empire_of_the_sun_short}
		\caption{\footnotesize Empire of the Sun (StarCraft 1)}\label{fig:empire_of_the_sun_short}
	\end{subfigure}
  \vskip\baselineskip
	\begin{subfigure}[t]{0.24\linewidth}
		\centering
    \includegraphics[width=\linewidth]{fortress_short}
		\caption{Fortress (StarCraft 1)}\label{fig:fortress_short}
	\end{subfigure}
  \hfill
	\begin{subfigure}[t]{0.24\linewidth}
		\centering
    \includegraphics[width=\linewidth]{python_short}
		\caption{Python (StarCraft 1)}\label{fig:python_short}
	\end{subfigure}
  \hfill
	\begin{subfigure}[t]{0.24\linewidth}
		\centering
    \includegraphics[width=\linewidth]{deathaura_short}
		\caption{Deathaura LE (StarCraft 2)}\label{fig:deathaura_short}
	\end{subfigure}
  \hfill
	\begin{subfigure}[t]{0.24\linewidth}
		\centering
    \includegraphics[width=0.93\linewidth]{jagannatha_short}
		\caption{Jagannatha LE (StarCraft 2)}\label{fig:jagannatha_short}
	\end{subfigure}
  \vskip\baselineskip
	\begin{subfigure}[t]{0.24\linewidth}
		\centering
    \includegraphics[width=\linewidth]{lightshade_short}
		\caption{Lightshade LE (StarCraft 2)}\label{fig:lightshade_short}
	\end{subfigure}
  \hfill
	\begin{subfigure}[t]{0.24\linewidth}
		\centering
    \includegraphics[width=0.93\linewidth]{pillar_of_gold_short}
		\caption{\footnotesize Pillar Of Gold LE (StarCraft 2)}\label{fig:pillar_of_gold_short}
	\end{subfigure}
  \hfill
	\begin{subfigure}[t]{0.24\linewidth}
		\centering
    \includegraphics[width=\linewidth]{romanticide_short}
		\caption{Romanticide LE (StarCraft 2)}\label{fig:romanticide_short}
	\end{subfigure}
  \hfill
	\begin{subfigure}[t]{0.24\linewidth}
		\centering
    \includegraphics[width=\linewidth]{submarine_short}
		\caption{Submarine LE (StarCraft 2)}\label{fig:submarine_short}
	\end{subfigure}
  \caption{StarCraft maps}
  \label{fig:maps}
\end{figure*}

\subsection{Comparaison BWTA2}

Tests have been  conducted using a bot under development  able to play
both at StarCraft~1\xspace  and StarCraft~2\xspace, on a  machine equipped with a Core  i9 9900 CPU
and 32 GB of RAM, running on  Windows 10. \textsc{Taunt}\xspace is written in C++ and
has been  compiled with the Visual  Studio 2022 compiler with  the /02
optimization option.

The  terrain  analysis  results,  namely  the  region-making  and  the
computation of  their contour  polygon, are good  on all  tested maps:
\textsc{Taunt}\xspace shows its ability to split  a map into regions with the desired
properties.  In order  to have  a  point of  comparison with  existing
libraries and  an objective  metric for  the evaluation  of $\textsc{Taunt}\xspace$'s
performance, we compare  runtimes of BWTA2 and \textsc{Taunt}\xspace on  StarCraft~1\xspace maps. We
choose BWTA2  rather than a more  modern library like BWEM,  since the
latter   does   not  propose   features   like   the  computation   of
contours. BWTA2 is  actually the more modern  terrain analysis library
for StarCraft~1\xspace offering equivalent features as \textsc{Taunt}\xspace.

\begin{table}[htbp]
  \caption{Runtime comparison in milliseconds between BWTA2 and \textsc{Taunt}\xspace.}
  \begin{center}
    \begin{tabular}{|c|r|r|}
      \hline
      \textbf{StarCraft~1\xspace Map}& \textbf{BWTA2}& \textbf{\textsc{Taunt}\xspace} \\
      \hline
      Benzene & 906~~~\, & 344~~~\, \\

      \rowcolor{Gray}
      Heartbreak Ridge & 794~~~\, & 821~~~\, \\
      Aztec & 1112~~~\, & 751~~~\, \\
      \rowcolor{Gray}
      Tau Cross & 1046~~~\, & 1839~~~\, \\
      Andromeda & 1114~~~\, & 626~~~\, \\
      \rowcolor{Gray}
      Circuit Breakers & 1187~~~\, & 654~~~\, \\
      Empire of the Sun & 1132~~~\, & 842~~~\, \\
      \rowcolor{Gray}
      Fortress & 1074~~~\, & 491~~~\, \\
      Python & 1089~~~\, & 1203~~~\, \\
      \hline
      Median runtime & 1089~~~\, & 751~~~\, \\
      Mean runtime & 1050.44 & 841.22\\
      Pop. standard deviation & 116.34 & 419.82\\
      \hline
    \end{tabular}
    \label{tab:xp}
  \end{center}
\end{table}

Runtime comparisons are shown in Table~\ref{tab:xp}.  BWTA2 and \textsc{Taunt}\xspace
have been run on the same machine through the same bot, under the same
conditions.  The full  run of BWTA2 and \textsc{Taunt}\xspace  algorithms is measured
in milliseconds, including fetching data  from APIs and preparing data
structures.  The reader can observe that the map Destination is not on
this table.   We have taken out  this map from comparisons  because it
would  be completely  at  the  advantage of  \textsc{Taunt}\xspace,  being an  unfair
comparison with  BWTA2.  Indeed,  Destination is a  map such  that all
walkable areas contain one resource  cluster only, so there is nothing
to compute for \textsc{Taunt}\xspace at Step~8 in Alg.~\ref{algo:taunt}, which is the
more  complex  and  computation  heavy  step.  This  is  why  we  have
0~variables  in  Table~\ref{tab:maps},  and   why  there  are  no  red
separation  lines  in  Fig~\ref{fig:destination_short}. As  a  result,
Destination is processed in 15ms by \textsc{Taunt}\xspace, against 843ms by BWTA2.

Results from Table~\ref{tab:xp} allow us  to conclude that \textsc{Taunt}\xspace runs
faster over most  maps than BWTA2, and has a  significant lower median
and mean  runtime.  The standard  deviation is almost 4  times higher,
though: this is due to  the runtime of Step~8 in Alg.~\ref{algo:taunt}
that  depends on  the number  of  areas to  handle and  the number  of
separations to found.

\begin{table}[htbp]
  \caption{Runtimes in milliseconds on StarCraft~2\xspace maps.}
  \begin{center}
    \begin{tabular}{|c|r|}
      \hline
      \textbf{StarCraft~2\xspace maps}& \textbf{\textsc{Taunt}\xspace} \\
      \hline
      Deathaura LE& 1283~~~\, \\
      \rowcolor{Gray}
      Jagannatha LE& 431~~~\, \\
      Lightshade LE& 755~~~\, \\
      \rowcolor{Gray}
      Oxide LE& 377~~~\, \\
      Pillar Of Gold LE& 824~~~\, \\
      \rowcolor{Gray}
      Romanticide LE& 3475~~~\, \\
      Submarine LE& 242~~~\, \\
      \hline
      Median runtime & 755~~~\, \\
      Mean runtime & 1055.28\\
      Pop. standard deviation & 1039.35\\
      \hline
    \end{tabular}
    \label{tab:sc2_runtimes}
  \end{center}
\end{table}

Since there are no terrain  analysis library for StarCraft~2\xspace with equivalent
features as \textsc{Taunt}\xspace, we could not  make any runtime comparison on StarCraft~2\xspace
maps.   Thus, Table~\ref{tab:sc2_runtimes}  shows runtimes  for \textsc{Taunt}\xspace
only. Like for Table~\ref{tab:xp}, runtimes take into account the full
run   of  $\textsc{Taunt}\xspace$'s   algorithm,   including   building  inputs   and
initializing    data    structures.     Looking    at    medians    in
Tables~\ref{tab:xp} and~\ref{tab:sc2_runtimes},  we can  conclude that
runtimes  over  StarCraft~1\xspace and  StarCraft~2\xspace  maps  are  equivalent. The  StarCraft~2\xspace  map
Romanticide is  an exception: it  contains 2 areas with  2 separations
required  for each,  and  1  area requiring  5  separations, which  is
significantly more than  the average map.  This is the  only map where
\textsc{Taunt}\xspace needed to use its inner  mechanism that doubles the timeout and
relaunch the solver,  since no satisfying separations  have been found
during the first  run of the solver.  This explains  the difference of
runtimes between Romanticide and other StarCraft~2\xspace maps.

\section{Conclusion and perspectives}

In this paper, we propose a library, \textsc{Taunt}\xspace, handling terrain analysis
in StarCraft games  as a combinatorial optimization  problem.  This is
the first terrain analysis work for StarCraft to tackle the problem as
a combinatorial optimization problem, and  the first to use Constraint
Programming to model  and solve it.  We give the  problem model in the
Error Function Optimization Problem formalism, and we test our library
on 10 StarCraft~1\xspace maps and 7 StarCraft~2\xspace maps from StarCraft AI competitions.

The main features of our library  are: 1.  The possibility for StarCraft~1\xspace and
StarCraft~2\xspace bots  to use it  with the same interface,  2. The split  of maps
into  regions in  a  human-like fashion,  avoiding  creating too  many
regions without  significant strategical values, 3.   The computing of
region contours, 4.  The ability  to dynamically reanalyze the terrain
(for  instance  after  the  destruction   of  an  obstacle),  5.   The
possibility to  make different  kind of terrain  analysis of  the same
map. At the moment this article  is written, no other terrain analysis
libraries for StarCraft games propose all these features.

Concerning this last feature, we show  in this paper two ways to split
a  map into  regions, according  to the  model objective  function.  A
future work  to enhance the  library can consist in  implementing more
diverse  combinatorial optimization  problem models  to fit  different
needs  in terms  of terrain  analysis.   For instance,  we could  have
models with a constraint to give  a maximal or minimal bound of region
surfaces,  to  force  symmetrical  regions   (if  the  map  is  itself
symmetrical), or to allow large, central buildable regions without any
resource clusters.

We strongly  believe that having  a universal tool to  get qualitative
spatial  representations,   able  to   handle  both   StarCraft  games
homogeneously  and  offering  the   possibility  of  making  different
analyses of  the same map, is  a necessary step toward  bots with true
adaptability,  able to  make non-scripted  decisions according  to the
environment and the current situation in a  game. We hope to see a new
wave of bots emerges thanks to \textsc{Taunt}\xspace.

\bibliographystyle{IEEEtran}