· 8 years ago · May 15, 2018, 03:08 AM
1%% bare_conf.tex
2%% V1.4b
3%% 2015/08/26
4%% by Michael Shell
5%% See:
6%% http://www.michaelshell.org/
7%% for current contact information.
8%%
9%% This is a skeleton file demonstrating the use of IEEEtran.cls
10%% (requires IEEEtran.cls version 1.8b or later) with an IEEE
11%% conference paper.
12%%
13%% Support sites:
14%% http://www.michaelshell.org/tex/ieeetran/
15%% http://www.ctan.org/pkg/ieeetran
16%% and
17%% http://www.ieee.org/
18
19%%*************************************************************************
20%% Legal Notice:
21%% This code is offered as-is without any warranty either expressed or
22%% implied; without even the implied warranty of MERCHANTABILITY or
23%% FITNESS FOR A PARTICULAR PURPOSE!
24%% User assumes all risk.
25%% In no event shall the IEEE or any contributor to this code be liable for
26%% any damages or losses, including, but not limited to, incidental,
27%% consequential, or any other damages, resulting from the use or misuse
28%% of any information contained here.
29%%
30%% All comments are the opinions of their respective authors and are not
31%% necessarily endorsed by the IEEE.
32%%
33%% This work is distributed under the LaTeX Project Public License (LPPL)
34%% ( http://www.latex-project.org/ ) version 1.3, and may be freely used,
35%% distributed and modified. A copy of the LPPL, version 1.3, is included
36%% in the base LaTeX documentation of all distributions of LaTeX released
37%% 2003/12/01 or later.
38%% Retain all contribution notices and credits.
39%% ** Modified files should be clearly indicated as such, including **
40%% ** renaming them and changing author support contact information. **
41%%*************************************************************************
42
43
44% *** Authors should verify (and, if needed, correct) their LaTeX system ***
45% *** with the testflow diagnostic prior to trusting their LaTeX platform ***
46% *** with production work. The IEEE's font choices and paper sizes can ***
47% *** trigger bugs that do not appear when using other class files. *** ***
48% The testflow support page is at:
49% http://www.michaelshell.org/tex/testflow/
50
51
52
53\documentclass[conference]{IEEEtran}
54% Some Computer Society conferences also require the compsoc mode option,
55% but others use the standard conference format.
56%
57% If IEEEtran.cls has not been installed into the LaTeX system files,
58% manually specify the path to it like:
59% \documentclass[conference]{../sty/IEEEtran}
60
61
62
63
64
65% Some very useful LaTeX packages include:
66% (uncomment the ones you want to load)
67
68
69% *** MISC UTILITY PACKAGES ***
70%
71%\usepackage{ifpdf}
72% Heiko Oberdiek's ifpdf.sty is very useful if you need conditional
73% compilation based on whether the output is pdf or dvi.
74% usage:
75% \ifpdf
76% % pdf code
77% \else
78% % dvi code
79% \fi
80% The latest version of ifpdf.sty can be obtained from:
81% http://www.ctan.org/pkg/ifpdf
82% Also, note that IEEEtran.cls V1.7 and later provides a builtin
83% \ifCLASSINFOpdf conditional that works the same way.
84% When switching from latex to pdflatex and vice-versa, the compiler may
85% have to be run twice to clear warning/error messages.
86
87
88
89
90
91
92% *** CITATION PACKAGES ***
93%
94\usepackage{cite}
95% cite.sty was written by Donald Arseneau
96% V1.6 and later of IEEEtran pre-defines the format of the cite.sty package
97% \cite{} output to follow that of the IEEE. Loading the cite package will
98% result in citation numbers being automatically sorted and properly
99% "compressed/ranged". e.g., [1], [9], [2], [7], [5], [6] without using
100% cite.sty will become [1], [2], [5]--[7], [9] using cite.sty. cite.sty's
101% \cite will automatically add leading space, if needed. Use cite.sty's
102% noadjust option (cite.sty V3.8 and later) if you want to turn this off
103% such as if a citation ever needs to be enclosed in parenthesis.
104% cite.sty is already installed on most LaTeX systems. Be sure and use
105% version 5.0 (2009-03-20) and later if using hyperref.sty.
106% The latest version can be obtained at:
107% http://www.ctan.org/pkg/cite
108% The documentation is contained in the cite.sty file itself.
109
110
111\usepackage{algpseudocode}
112\usepackage{algorithm}
113%\usepackage{program}
114
115\usepackage{pifont}
116
117
118
119
120
121% *** GRAPHICS RELATED PACKAGES ***
122%
123\ifCLASSINFOpdf
124 % \usepackage[pdftex]{graphicx}
125 % declare the path(s) where your graphic files are
126 % \graphicspath{{../pdf/}{../jpeg/}}
127 % and their extensions so you won't have to specify these with
128 % every instance of \includegraphics
129 % \DeclareGraphicsExtensions{.pdf,.jpeg,.png}
130\else
131 % or other class option (dvipsone, dvipdf, if not using dvips). graphicx
132 % will default to the driver specified in the system graphics.cfg if no
133 % driver is specified.
134 % \usepackage[dvips]{graphicx}
135 % declare the path(s) where your graphic files are
136 % \graphicspath{{../eps/}}
137 % and their extensions so you won't have to specify these with
138 % every instance of \includegraphics
139 % \DeclareGraphicsExtensions{.eps}
140\fi
141% graphicx was written by David Carlisle and Sebastian Rahtz. It is
142% required if you want graphics, photos, etc. graphicx.sty is already
143% installed on most LaTeX systems. The latest version and documentation
144% can be obtained at:
145% http://www.ctan.org/pkg/graphicx
146% Another good source of documentation is "Using Imported Graphics in
147% LaTeX2e" by Keith Reckdahl which can be found at:
148% http://www.ctan.org/pkg/epslatex
149%
150% latex, and pdflatex in dvi mode, support graphics in encapsulated
151% postscript (.eps) format. pdflatex in pdf mode supports graphics
152% in .pdf, .jpeg, .png and .mps (metapost) formats. Users should ensure
153% that all non-photo figures use a vector format (.eps, .pdf, .mps) and
154% not a bitmapped formats (.jpeg, .png). The IEEE frowns on bitmapped formats
155% which can result in "jaggedy"/blurry rendering of lines and letters as
156% well as large increases in file sizes.
157%
158% You can find documentation about the pdfTeX application at:
159% http://www.tug.org/applications/pdftex
160
161
162
163
164
165% *** MATH PACKAGES ***
166%
167\usepackage{amsmath}
168% A popular package from the American Mathematical Society that provides
169% many useful and powerful commands for dealing with mathematics.
170%
171% Note that the amsmath package sets \interdisplaylinepenalty to 10000
172% thus preventing page breaks from occurring within multiline equations. Use:
173\interdisplaylinepenalty=2500
174% after loading amsmath to restore such page breaks as IEEEtran.cls normally
175% does. amsmath.sty is already installed on most LaTeX systems. The latest
176% version and documentation can be obtained at:
177% http://www.ctan.org/pkg/amsmath
178
179
180
181
182
183% *** SPECIALIZED LIST PACKAGES ***
184%
185%\usepackage{algorithmic}
186% algorithmic.sty was written by Peter Williams and Rogerio Brito.
187% This package provides an algorithmic environment fo describing algorithms.
188% You can use the algorithmic environment in-text or within a figure
189% environment to provide for a floating algorithm. Do NOT use the algorithm
190% floating environment provided by algorithm.sty (by the same authors) or
191% algorithm2e.sty (by Christophe Fiorio) as the IEEE does not use dedicated
192% algorithm float types and packages that provide these will not provide
193% correct IEEE style captions. The latest version and documentation of
194% algorithmic.sty can be obtained at:
195% http://www.ctan.org/pkg/algorithms
196% Also of interest may be the (relatively newer and more customizable)
197% algorithmicx.sty package by Szasz Janos:
198% http://www.ctan.org/pkg/algorithmicx
199
200
201
202
203% *** ALIGNMENT PACKAGES ***
204%
205\usepackage{array}
206% Frank Mittelbach's and David Carlisle's array.sty patches and improves
207% the standard LaTeX2e array and tabular environments to provide better
208% appearance and additional user controls. As the default LaTeX2e table
209% generation code is lacking to the point of almost being broken with
210% respect to the quality of the end results, all users are strongly
211% advised to use an enhanced (at the very least that provided by array.sty)
212% set of table tools. array.sty is already installed on most systems. The
213% latest version and documentation can be obtained at:
214% http://www.ctan.org/pkg/array
215
216
217% IEEEtran contains the IEEEeqnarray family of commands that can be used to
218% generate multiline equations as well as matrices, tables, etc., of high
219% quality.
220
221
222
223
224% *** SUBFIGURE PACKAGES ***
225%\ifCLASSOPTIONcompsoc
226% \usepackage[caption=false,font=normalsize,labelfont=sf,textfont=sf]{subfig}
227%\else
228% \usepackage[caption=false,font=footnotesize]{subfig}
229%\fi
230% subfig.sty, written by Steven Douglas Cochran, is the modern replacement
231% for subfigure.sty, the latter of which is no longer maintained and is
232% incompatible with some LaTeX packages including fixltx2e. However,
233% subfig.sty requires and automatically loads Axel Sommerfeldt's caption.sty
234% which will override IEEEtran.cls' handling of captions and this will result
235% in non-IEEE style figure/table captions. To prevent this problem, be sure
236% and invoke subfig.sty's "caption=false" package option (available since
237% subfig.sty version 1.3, 2005/06/28) as this is will preserve IEEEtran.cls
238% handling of captions.
239% Note that the Computer Society format requires a larger sans serif font
240% than the serif footnote size font used in traditional IEEE formatting
241% and thus the need to invoke different subfig.sty package options depending
242% on whether compsoc mode has been enabled.
243%
244% The latest version and documentation of subfig.sty can be obtained at:
245% http://www.ctan.org/pkg/subfig
246
247
248
249
250% *** FLOAT PACKAGES ***
251%
252%\usepackage{fixltx2e}
253% fixltx2e, the successor to the earlier fix2col.sty, was written by
254% Frank Mittelbach and David Carlisle. This package corrects a few problems
255% in the LaTeX2e kernel, the most notable of which is that in current
256% LaTeX2e releases, the ordering of single and double column floats is not
257% guaranteed to be preserved. Thus, an unpatched LaTeX2e can allow a
258% single column figure to be placed prior to an earlier double column
259% figure.
260% Be aware that LaTeX2e kernels dated 2015 and later have fixltx2e.sty's
261% corrections already built into the system in which case a warning will
262% be issued if an attempt is made to load fixltx2e.sty as it is no longer
263% needed.
264% The latest version and documentation can be found at:
265% http://www.ctan.org/pkg/fixltx2e
266
267
268%\usepackage{stfloats}
269% stfloats.sty was written by Sigitas Tolusis. This package gives LaTeX2e
270% the ability to do double column floats at the bottom of the page as well
271% as the top. (e.g., "\begin{figure*}[!b]" is not normally possible in
272% LaTeX2e). It also provides a command:
273%\fnbelowfloat
274% to enable the placement of footnotes below bottom floats (the standard
275% LaTeX2e kernel puts them above bottom floats). This is an invasive package
276% which rewrites many portions of the LaTeX2e float routines. It may not work
277% with other packages that modify the LaTeX2e float routines. The latest
278% version and documentation can be obtained at:
279% http://www.ctan.org/pkg/stfloats
280% Do not use the stfloats baselinefloat ability as the IEEE does not allow
281% \baselineskip to stretch. Authors submitting work to the IEEE should note
282% that the IEEE rarely uses double column equations and that authors should try
283% to avoid such use. Do not be tempted to use the cuted.sty or midfloat.sty
284% packages (also by Sigitas Tolusis) as the IEEE does not format its papers in
285% such ways.
286% Do not attempt to use stfloats with fixltx2e as they are incompatible.
287% Instead, use Morten Hogholm'a dblfloatfix which combines the features
288% of both fixltx2e and stfloats:
289%
290% \usepackage{dblfloatfix}
291% The latest version can be found at:
292% http://www.ctan.org/pkg/dblfloatfix
293
294
295
296
297% *** PDF, URL AND HYPERLINK PACKAGES ***
298%
299\usepackage{url}
300% url.sty was written by Donald Arseneau. It provides better support for
301% handling and breaking URLs. url.sty is already installed on most LaTeX
302% systems. The latest version and documentation can be obtained at:
303% http://www.ctan.org/pkg/url
304% Basically, \url{my_url_here}.
305
306
307
308
309% *** Do not adjust lengths that control margins, column widths, etc. ***
310% *** Do not use packages that alter fonts (such as pslatex). ***
311% There should be no need to do such things with IEEEtran.cls V1.6 and later.
312% (Unless specifically asked to do so by the journal or conference you plan
313% to submit to, of course. )
314
315
316% correct bad hyphenation here
317\hyphenation{op-tical net-works semi-conduc-tor}
318
319
320%Math operators
321\DeclareMathOperator*{\argmax}{argmax}
322
323\begin{document}
324%
325% paper title
326% Titles are generally capitalized except for words such as a, an, and, as,
327% at, but, by, for, in, nor, of, on, or, the, to and up, which are usually
328% not capitalized unless they are the first or last word of the title.
329% Linebreaks \\ can be used within to get better formatting as desired.
330% Do not put math or special symbols in the title.
331\title{Resource Gathering algorithms in the Game of StarCraft}
332
333
334% author names and affiliations
335% use a multiple column layout for up to three different
336% affiliations
337\author{\IEEEauthorblockN{Martin Rooijackers and Mark H. M. Winands}
338\IEEEauthorblockA{Games \& AI Group, Department of Data Science and Knowledge Engineering\\Maastricht University, Maastricht, The Netherlands\\
339Email: \{mlm.rooijackers,m.winands\}@maastrichtuniversity.nl}}
340
341% conference papers do not typically use \thanks and this command
342% is locked out in conference mode. If really needed, such as for
343% the acknowledgment of grants, issue a \IEEEoverridecommandlockouts
344% after \documentclass
345
346% for over three affiliations, or if they all won't fit within the width
347% of the page, use this alternative format:
348%
349%\author{\IEEEauthorblockN{Michael Shell\IEEEauthorrefmark{1},
350%Homer Simpson\IEEEauthorrefmark{2},
351%James Kirk\IEEEauthorrefmark{3},
352%Montgomery Scott\IEEEauthorrefmark{3} and
353%Eldon Tyrell\IEEEauthorrefmark{4}}
354%\IEEEauthorblockA{\IEEEauthorrefmark{1}School of Electrical and Computer Engineering\\
355%Georgia Institute of Technology,
356%Atlanta, Georgia 30332--0250\\ Email: see http://www.michaelshell.org/contact.html}
357%\IEEEauthorblockA{\IEEEauthorrefmark{2}Twentieth Century Fox, Springfield, USA\\
358%Email: homer@thesimpsons.com}
359%\IEEEauthorblockA{\IEEEauthorrefmark{3}Starfleet Academy, San Francisco, California 96678-2391\\
360%Telephone: (800) 555--1212, Fax: (888) 555--1212}
361%\IEEEauthorblockA{\IEEEauthorrefmark{4}Tyrell Inc., 123 Replicant Street, Los Angeles, California 90210--4321}}
362
363
364
365
366% use for special paper notices
367%\IEEEspecialpapernotice{(Invited Paper)}
368
369
370
371
372% make the title area
373\maketitle
374
375%-----------------------------------------------------------------------------
376% A B S T R A C T
377%-----------------------------------------------------------------------------
378\begin{abstract}
379{\it StarCraft} is a Real-Time Strategy game, which has a large state-space, is played in real-time, and commonly features two opposing players, capable of acting simultaneously.
380One of the aspects of the game is building a wall.
381We present an algorithm which can be used for wall building for an intelligent agent playing the game of {\it StarCraft: Brood War}.
382
383
384%$$\keywords{(StarCraft, Monte-Carlo Tree Search, Lanchester's Square Law}}
385\end{abstract}
386
387
388% no keywords
389
390% For peer review papers, you can put extra information on the cover
391% page as needed:
392% \ifCLASSOPTIONpeerreview
393% \begin{center} \bfseries EDICS Category: 3-BBND \end{center}
394% \fi
395%
396% For peerreview papers, this IEEEtran command inserts a page break and
397% creates the second title. It will be ignored for other modes.
398\IEEEpeerreviewmaketitle
399
400
401
402
403%-----------------------------------------------------------------------------
404% I N T R O D U C T I O N
405%-----------------------------------------------------------------------------
406\section{Introduction}
407
408
409One of the aspects of real time strategy games is wall building.
410The general strategy of wall building is placing down structures such that you are safe from an attack at a given position.
411Usually this is done to protect your base and production facilities without having to rely solely on combat units.
412
413This topic is not unique to StarCraft. Previous work has been done in the game Empire Earth \cite{teich2006ai}, where the developers used Graham Scan to decide where to place a wall.
414A generic wall building algorithm was a topic in the book AI game programming wisdom 2 \cite{grimani2004wall}.
415The algorithm is also described in the online presentation \url{http://slideplayer.com/slide/1511614/}
416
417In StarCraft:Brood War, wall building requires an extra property which these algorithms don't take into account.
418Namely, building have gaps between them (see figure \ref{fig:TerranGap}). Depending on the size of the unit, walls might not be closed off for all units.
419This sometimes is desirable as well, in case you want your own (small) units to pass through, but don't want the enemy units to pass your wall.
420
421For wall building specifically for StarCraft, there has been one paper that uses answer set programming to add this extra constraint \cite{certicky2013implementing}.
422This approach has been improved by Richoux et al. \cite{richoux2014walling}
423
424
425Another approach for wall building used in the game of StarCraft is to use potential fields \cite{de2015creating}
426
427
428The problem with these approaches is that none of them address the gap between buildings and the terrain (mainly cliffs and other natural obstacles).
429Because of this, some of the walls created with these methods will still have gaps in them that let enemy units through.
430We propose an algorithm based on the pathfinding algorithm A* to ensure that the wall from our algorithm will stop whichever enemy unit it is supposed to stop.
431With an extra calculation step, our algorithm can also create walls where smaller units can pass through, but the larger units of the opponent cannot.
432
433
434
435This paper is structured as follows:
436The second section gives the problem definition of wall building.
437The third section describes the different approaches for the algorithm which can be used for that task.
438The fourth section describes the pseudocode implementation of the wall building algorithm.
439The fifth section describes the experimental setup and the results of the experiments.
440The sixth section draws conclusions from the results and talks about future work.
441
442\section{Problem Definition}
443
444In the RTS game of StarCraft, a wall is a set of structures and units placed in such a way that no enemy unit can pass from one side of the wall to the other.
445In this chapter we describe the problem that our algorithm tries to solve.
446
447The StarCraft map consists of two types of grids:
448The walk grid, where each cell is an 8 x 8 pixels square, and the build grid, where each cell is a 4 x 4 walk tile square (hence 32 x 32 square of pixels).
449Some of these build tiles are buildable, and other are not due to natural obstacles (ex. cliffs) or due to the game rules (buildings cannot overlap).
450
451Each building has a build size and a real size. The build size indicates the height and width of the building in terms of building tiles.
452For example, a Terran supply depot has a build width of 3 and a build height of 2
453The real size indicates how much walkable space the building takes up.
454In the case of StarCraft Brood War, the actual walk space taken up by buildings is less than the build size x 32 pixels.
455This causes gaps to be created between building pace next to each other and to natural obstacles (cliffs have these gaps as well).
456
457Thus the wall building problem is about finding locations for buildings such that a given enemy unit (given in pixel width and height) cannot pass through the wall.
458An extra constraint can be that another smaller unit has to be able to pass through while the given enemy unit still cannot pass through (this allow for hit & run tactics where ranged units can retreat behind a wall after shooting).
459
460The algorithm presented in this paper is specifically for checking if a given set of buildings can satisfy these constraints.
461The problem of determining the minimum amount of buildings needed for building a wall is out of the scope of this paper.
462This however can be easily added by having an algorithm generate a list of buildings and using the algorithm presented in this paper to check if those building can form a wall, until a suitable combination of buildings is found.
463
464
465%\section{Formal definition}
466
467\section{Approach}\label{sec:approachwall}
468
469
470\begin{figure}[h]
471\begin{center}
472\includegraphics[scale=0.4]{images/ExampleWall.png}
473\caption{Example of a wall found using the wall building algorithm. Chokepoint is indicated with a red line and a purple circle.} %\cite{terrangap}
474\label{fig:ExampleWall}
475\end{center}
476\end{figure}
477
478In our approach we use a wall to seal off a choke point.
479A \textit{choke point} is a location on the map (terrain) which connects two regions \citebay{TerrainAnalysis2010} (see also Figure \ref{fig:ExampleWall}).
480If a wall is built near this choke point, then the two regions of the choke point are separated (no longer reachable by ground units).
481
482%In the case of the game of StarCraft, a wall consists of placing buildings in such
483Since both buildings and units can be used in a wall, we use the term structure to indicate a part of a wall (either a building or a unit).
484The first part of the wall algorithm requires a way to generate a set of structure locations which can potentially form a wall.
485In the game of StarCraft, units and buildings cannot overlap, buildings cannot overlap with unsuitable ground and units cannot overlap with unwalkable ground.
486We use a depth-first search algorithm to determine possible structure locations.
487At the initial depth, the algorithm places a structure close to the choke point.
488After selecting a location for the first structure, the next depth includes a new structure that is placed adjacent to any of the structures already placed.
489This is done because a wall should not contain a gap. Therefore each building and unit is adjacent to at least one other building or unit.
490This process continues until all structures have been placed.
491
492Each time that the building placement algorithm placed all structures (reached maximum depth), the validation algorithm checks if the placement of the structures forms a wall.
493Determining if a set of structures forms a wall requires checking if there is a path that goes from one side of the choke point to the other side that passes through the choke point that is supposed to be walled of.
494For this we compare two different methods.
495In both methods we limit the search to a 16$\times$16 grid around the choke point to ensure that all possible paths have to go through the choke point that is supposed to be walled of.
496The first method that we use is a floodfill starting from one side of the choke point.
497If the floodfill reaches the other side of the choke point then the algorithm will generate the next set of possible structure locations which can potentially form a wall.
498The second method is the $A^{*}$ shortest path algorithm \citebay{astar}.
499The $A^{*}$ algorithm tries to reach the other side of the wall based on heuristic search instead of a brute force approach like floodfill. % does.
500
501\section{Wall Building Algorithm}
502
503%Depth first search, flood fill
504
505The wall building algorithm used to calculate a wall is based on a depth-first search approach to find possible structure placements combined with floodfill or $A^{*}$ to check if a structure placement is a wall.
506Just like the declarative programming approach from Certicky \citeby{certicky2013implementing}, we construct a 16$\times$16 grid around a choke point (see Section \ref{sec:approachwall} for the definition of a choke point). %'s center.
507Besides the choke point location, the algorithm also requires the list of buildings and units available to create the wall.
508
509The wall placement algorithm starts off with no structures placed (depth-first search at a depth of 0).
510At this point (depth) the algorithm will pick one of the possible structures and place it down at a location close to the choke point. %possible location.
511Determining a possible location is performed by checking if every tile occupied is buildable (if it is a building) or walkable (if it is a unit).
512After the initial placement, the wall placement algorithm places the next structure adjacent to the initial structure.
513This adjacency is 8-ways (horizontal, diagonal, vertical).
514Every next structure from this point is then placed adjacent to at least one of the structures already placed.
515This process continues until all available structures have been placed.
516
517Once all structures are placed (at the leaf node), the algorithm starts a floodfill or $A^{*}$ from a tile on one side of the wall.
518Both the floodfill and $A^{*}$ algorithm try to reach a tile on the other side of the choke point by passing through the choke point.
519If successful, the current placement of structures is not a wall.
520In this case the depth-first search backtracks and tries a different placement of structures.
521Besides walkable gaps on the tiles not covered by the structure, the floodfill and $A^{*}$ can also pass between gaps formed by buildings (see also Figure \ref{fig:TerranGap}).
522Each building has a certain number of pixels as a gap on each side (top, bottom, left, right).
523When a side of a building is adjacent to the side of another building, the corresponding sides combine the pixel values.
524The algorithm used by Certicky et al. \citeby{certicky2013implementing} did not take into account that two buildings placed diagonally have a gap equal to the gap resulting from the two buildings being placed horizontally (see also \url{http://wiki.teamliquid.net/starcraft/Walling})
525
526The algorithm from Richoux et al. doesn't take the terrain (cliffs and other natural obstacles) into account.
527These terrain features have gap values as well.
528The exact values for these are not yet known, so to compensate, the pathfinding algorithm uses the walkable data given by the BWAPI to determine if a unit can walk between the gap of a building and a cliff or other terrain feature.
529This is what allows our algorithm to produce walls that are guaranteed to be thigh against any unit it is supposed to stop.
530The exact details of this process is an implementation detail.
531The code for the wall building can be found at \url{https://github.com/MartinRooijackers/LetaBot}
532
533\begin{figure}[h]
534\begin{center}
535\includegraphics[scale=0.5]{images/460px-Terran_buildings_gaps.png}
536\caption{Gaps between Terran buildings. From teamliquid wiki .} %\cite{terrangap}
537\label{fig:TerranGap}
538\end{center}
539\end{figure}
540
541
542\section{Implementation}
543
544The wall building algorithm requires a choke point, a tile on one side of the choke, a tile at other side of the choke and a list of structures.
545The other information about buildable and walkable locations can be derived from the BWAPI.
546This pseudocode gives a high level overview of the wall implementation in a StarCraft agent.
547
548The wall building algorithm requires the following input:
549\begin{itemize}
550 \item \textit{S}: a list of structures, each containing its width and height
551 \item \textit{choke}: tile location of a choke point
552 \item \textit{sTile}: start location of the floodfill
553 \item \textit{eTile}: end location of the floodfill
554\end{itemize}
555The algorithm is split into two components: the wall placement algorithm which determines valid structure locations and a wall validation algorithm that checks if these locations form a wall.
556The second step can be performed by either $A^{*}$ or floodfill.
557The wall placement algorithm is given in the pseudocode below (see Algorithm \ref{BuildingPlacement} ),
558The wall algorithm starts with calling the \textsc{WallIn} function with the parameters mentioned above.
559This function calls \textsc{BuildingPlacement}, which uses depth-first search to place the buildings.
560As long as a structure needs to be placed, the algorithm uses the \textsc{ValidLoc} function to determine a place to put the building.
561This process is repeated until all buildings are placed.
562Once all buildings are placed, the algorithm check if the building placement is a wall with the \textsc{CheckWall} function.
563This function can be implemented by both \textsc{FloodFill} (see algorithm \ref{FloodFill} ) and \textsc{$A^{*}$} (see algorithm \ref{Astar}).
564
565
566
567%\begin{algorithmic}
568 %\caption{Wall placement algorithm}
569
570%\Function{WallIn}{S,choke,sTile,eTile}
571 %\State BuildingPlacement(0,S,choke,sTile,eTile)
572%\EndFunction
573
574
575%\Function{BuildingPlacement}{depth,S,choke,sTile,eTile}
576 %\If{$ size( S ) = 0 $ } \Comment all structures placed
577 %\ForAll{ $x \in \{ choke_x - 8, \dots, choke_x + 8 \}$ }
578 % \ForAll{ $y \in \{ choke_y - 8, \dots, choke_y + 8 \}$ }
579 % \State Visited(x,y) $\gets$ 1 \Comment clear last floodfill
580 % \EndFor
581 % \EndFor
582 % \State isWall $\gets CheckWall( sTile_x,sTile_y,eTile,Visited )$
583 % \If{$ isWall = 0 $ }
584 % \State \Return Backtrack \Comment not a wall in, generate a new structure location
585 % \EndIf
586 % \If{$ isWall = 1 $ }
587 % \Return \State Output/Store current structure locations and end algorithm
588 % \EndIf
589 %\EndIf
590 %\ForAll{ $x \in \{ choke_x - 8, \dots, choke_x + 8 \}$ }
591 % \ForAll{ $y \in \{ choke_y - 8, \dots, choke_y + 8 \}$ }bid
592 % \If{ ValidLoc(x,y,$S_0$,depth) }
593 % \State BuildingPlacement(depth+1, $S \setminus S_0 $ ,choke,sTile,eTile)
594 % \EndIf
595 % \EndFor
596 %\EndFor
597 % \State BuildingPlacement(0,S,choke,sTile,eTile)
598%\EndFunction
599
600%\end{algorithmic}
601
602
603\begin{algorithm}
604\caption{WallPlacement}
605\label{BuildingPlacement}
606\begin{algorithmic}[1]
607
608
609\Procedure{WallIn}{S,choke,sTile,eTile}
610 \State BuildingPlacement(0,S,choke,sTile,eTile)
611\EndProcedure
612\State
613\Procedure{BuildingPlacement}{depth,S,choke,sTile,eTile}
614
615 \If{$ size( S ) = 0 $ } \Comment all structures placed
616 \ForAll{ $x \in \{ choke_x - 8, \dots, choke_x + 8 \}$ }
617 \ForAll{ $y \in \{ choke_y - 8, \dots, choke_y + 8 \}$ }
618 \State Visited(x,y) $\gets$ 1 \Comment clear last floodfill
619 \EndFor
620 \EndFor
621 \State isWall $\gets CheckWall( sTile_x,sTile_y,eTile,Visited )$
622 \If{$ isWall = false $ }
623 \State \Return \Comment This is not a wall in, generate a new structure location
624 \EndIf
625 \If{$ isWall = true $ }
626 \Return \State Output/Store current structure locations and end algorithm
627 \EndIf
628 \EndIf
629 \ForAll{ $x \in \{ choke_x - 8, \dots, choke_x + 8 \}$ }
630 \ForAll{ $y \in \{ choke_y - 8, \dots, choke_y + 8 \}$ }
631 \If{ ValidLoc(x,y,$S_0$,depth) }
632 \State BuildingPlacement(depth+1, $S \setminus S_0 $ ,choke,sTile,eTile)
633 \EndIf
634 \EndFor
635 \EndFor
636 \State BuildingPlacement(0,S,choke,sTile,eTile)
637
638\EndProcedure
639\end{algorithmic}
640\end{algorithm}
641
642
643The \textsc{ValidLoc} function (see Algorithm \ref{ValidLoc} ) checks if a building can be placed at a certain location.
644Since a wall requires all buildings to be adjacent,
645this function also checks if the build location is adjacent to another location already occupied.
646The only exception is the first building, since it cannot be adjacent to anything yet.
647
648%\begin{algorithmic}
649
650%\Function{ValidLoc}{x,y,struct,depth}
651 %\State $Adjacent \gets False$
652 %\ForAll{ $xTile \in \{ x, \dots, x + ( struct_{w} - 1 ) \}$ }
653 % \ForAll{ $yTile \in \{ y , \dots, y + ( struct_{h} - 1 ) \}$ }
654 % \If{$ Occupied(x,y) = True$ } \Comment BWAPI function
655 % \State \Return False
656 % \EndIf
657 % \If{ Tile adjacent to other structure } \Comment 8-way
658 % \State $Adjacent \gets True$
659 % \EndIf
660 % \EndFor
661 %\EndFor
662 %\If{$ Adjacent = False \wedge depth \neq 0$ } \Comment adjacency check
663 % \State \Return False
664 % \EndIf
665 % \State \Return True
666%\EndFunction
667
668%\end{algorithmic}
669
670
671
672\begin{algorithm}
673\caption{ValidLoc}
674\label{ValidLoc}
675\begin{algorithmic}[1]
676
677
678\Procedure{ValidLoc}{x,y,struct,depth}
679
680 \State $Adjacent \gets False$
681 \ForAll{ $xTile \in \{ x, \dots, x + ( struct_{w} - 1 ) \}$ }
682 \ForAll{ $yTile \in \{ y , \dots, y + ( struct_{h} - 1 ) \}$ }
683 \If{$ Occupied(x,y) = True$ } \Comment BWAPI function
684 \State \Return False
685 \EndIf
686 \If{ Tile adjacent to other structure } \Comment 8-way
687 \State $Adjacent \gets True$
688 \EndIf
689 \EndFor
690 \EndFor
691 \If{$ Adjacent = False \wedge depth \neq 0$ } \Comment adjacency check
692 \State \Return False
693 \EndIf
694 \State \Return True
695
696\EndProcedure
697\end{algorithmic}
698\end{algorithm}
699
700
701
702There are two ways to implement the \textsc{CheckWall} function used in the wall placement algorithm. %depth-first search.
703The first option is to use the floodfill algorithm.
704The second option is to use the $A^{*}$ algorithm.
705Both algorithms use information from the BWAPI to determine if a position is invalid.
706If a position is invalid, it cannot be traversed.
707An invalid position is a position where:
708\begin{itemize}
709 \item The \textit{x} or \textit{y} position is outside of the map.
710 \item The \textit{x} or \textit{y} position is outside of the 16$\times$16 grid.
711 \item The gap between buildings is not large enough (see figure \ref{fig:terrangap}).
712\end{itemize}
713Hence a valid position is a position on the map that does not have these characteristics.
714The pseudocode for the floodfill algorithm is given in Algorithm \ref{FloodFill}. %below: %\ref{alg:CheckWall}
715
716%\begin{algorithmic}
717
718%\Function{CheckWall}{$sTile_x,sTile_y,eTile,Visited$}
719 %\State \Return $FloodFill( sTile_x,sTile_y,eTile,Visited )$
720%\EndFunction
721
722%\Function{FloodFill}{x,y,eTile,Visited}
723 % \If{ Visited(x,y) = 1 }
724 % \State \Return $0$
725 % \EndIf
726 % \State Visited(x,y) $\gets$ 1
727 % \If{ Current (x,y) tile is invalid }
728 % \State \Return $0$ \Comment Current configuration is not a wall
729 % \EndIf
730 % \If{ (x,y) = eTile }
731 % \State \Return $1$ \Comment Current configuration is a wall
732 % \EndIf
733 % \State EndTiles $\gets$ 0
734 % \State $EndTiles \gets EndTiles + FloodFill(x+1,y,eTile,Visited)$
735 % \State $EndTiles \gets EndTiles + FloodFill(x-1,y,eTile,Visited)$
736 % \State $EndTiles \gets EndTiles + FloodFill(x,y+1,eTile,Visited)$
737 % \State $EndTiles \gets EndTiles + FloodFill(x,y-1,eTile,Visited)$
738 % \State $EndTiles \gets EndTiles + FloodFill(x+1,y+1,eTile,Visited)$
739 % \State $EndTiles \gets EndTiles + FloodFill(x-1,y-1,eTile,Visited)$
740 % \State $EndTiles \gets EndTiles + FloodFill(x-1,y+1,eTile,Visited)$
741 % \State $EndTiles \gets EndTiles + FloodFill(x+1,y-1,eTile,Visited)$
742 % \State \Return EndTiles
743%\EndFunction
744
745
746%\label{alg:CheckWall}
747%\end{algorithmic}
748
749
750\begin{algorithm}
751\caption{FloodFill}
752\label{FloodFill}
753\begin{algorithmic}[1]
754
755
756\Procedure{CheckWall}{$sTile_x,sTile_y,eTile,Visited$}
757 \State \Return $FloodFill( sTile_x,sTile_y,eTile,Visited )$
758\EndProcedure
759\State
760\Procedure{FloodFill}{x,y,eTile,Visited}
761
762 \If{ Visited(x,y) = true }
763 \State \Return $0$
764 \EndIf
765 \State Visited(x,y) $\gets$ true
766 \If{ Current (x,y) tile is invalid }
767 \State \Return $false$ \Comment Current configuration is not a wall
768 \EndIf
769 \If{ (x,y) = eTile }
770 \State \Return $true$ \Comment Current configuration is a wall
771 \EndIf
772
773 \ForAll{ $xStep \in { -1,0,1 } $ }
774 \ForAll{ $yStep \in { -1,0,1 } $ }
775 \If{ $ xStep \neq 0 \vee yStep \neq 0 $ }
776 \If{ $ FloodFill(x + xStep, y + yStep,eTile,Visited) = true $ }
777 \State \Return $true$
778 \EndIf
779 \EndIf
780 \EndFor
781 \EndFor
782
783 %\State EndTiles $\gets$ 0
784 %\If{ $FloodFill(x+1,y,eTile,Visited) = true$ }
785 % \State \Return $true$
786 %\EndIf
787 %\If{ $FloodFill(x-1,y,eTile,Visited) = true$ }
788 % \State \Return $true$
789 %\EndIf
790 %\If{ $FloodFill(x,y+1,eTile,Visited) = true$ }
791 % \State \Return $true$
792 %\EndIf
793 %\If{ $FloodFill(x,y-1,eTile,Visited) = true$ }
794 % \State \Return $true$
795 %\EndIf
796 %\If{ $FloodFill(x+1,y+1,eTile,Visited) = true$ }
797 % \State \Return $true$
798 %\EndIf
799 %\If{ $FloodFill(x-1,y-1,eTile,Visited) = true$ }
800 % \State \Return $true$
801 %\EndIf
802 %\If{ $FloodFill(x-1,y+1,eTile,Visited) = true$ }
803 % \State \Return $true$
804 %\EndIf
805 %\If{ $FloodFill(x+1,y-1,eTile,Visited) = true$ }
806 % \State \Return $true$
807 %\EndIf
808
809 \State \Return $false$
810
811\EndProcedure
812\end{algorithmic}
813\end{algorithm}
814
815
816% \State EndTiles $\gets$ 0
817% \State $EndTiles \gets EndTiles + FloodFill(x+1,y,eTile,Visited)$
818% \State $EndTiles \gets EndTiles + FloodFill(x-1,y,eTile,Visited)$
819% \State $EndTiles \gets EndTiles + FloodFill(x,y+1,eTile,Visited)$
820% \State $EndTiles \gets EndTiles + FloodFill(x,y-1,eTile,Visited)$
821% \State $EndTiles \gets EndTiles + FloodFill(x+1,y+1,eTile,Visited)$
822% \State $EndTiles \gets EndTiles + FloodFill(x-1,y-1,eTile,Visited)$
823% \State $EndTiles \gets EndTiles + FloodFill(x-1,y+1,eTile,Visited)$
824% \State $EndTiles \gets EndTiles + FloodFill(x+1,y-1,eTile,Visited)$
825% \State \Return EndTiles
826
827
828
829For the implementation of $A^{*}$ from Algorithm \ref{Astar}, we use the Manhattan distance heuristic.
830Since we only need to know if there is a path, we only use the heuristic function to determine the order of nodes that the algorithm visits.
831Instead of a ClosedSet variable, we use the Visited variable to keep track of nodes already visited.
832The pseudocode for the $A^{*}$ algorithm is given in Algorithm \ref{Astar}. % below:
833%TODO: a star algorithm
834
835%\begin{algorithmic}
836
837%\Function{CheckWall}{$sTile_x,sTile_y,eTile,Visited$}
838 % \State \Return $Astar( sTile_x,sTile_y,eTile,Visited )$
839%\EndFunction
840
841%\Function{Astar}{x,y,eTile,Visited}
842 %\State ClosedSet $\gets \emptyset$ \Comment set of positions already evaluated.
843 % \State OpenSet $\gets \{ (x,y) \} $ \Comment set of positions to be evaluated.
844 % \While{ OpenSet $\neq \emptyset$ }
845 % \State CurrentPos $\gets$ position in OpenSet with lowest Manhattan distance to eTile.
846 % \If{ CurrentPos = eTile } \Comment Check if current position is equal to the end tile.
847 % \State \Return 1 \Comment Current configuration is a wall.
848 % \EndIf
849
850 %\State Visited($CurrentPos_x$,$CurrentPos_y$) $\gets$ 1
851 %\ForAll{positions $p$ which are 8-way adjacent to CurrentPos}
852 %\If{ Visited($p_x$,$p_y$) = 0 and ($p_x$,$p_y$) is valid } \Comment Check is position should be added.
853 % \State OpenSet $\gets$ OpenSet $\cup \{p\}$
854 % \EndIf
855 % \EndFor
856 % \State OpenSet $\gets$ OpenSet $\setminus$ CurrentPos \Comment Remove CurrentPos from the open set.
857 % \EndWhile
858 %\State Visited(x,y) $\gets$ 1
859
860 % \State \Return 0 \Comment Current configuration is not a wall
861%\EndFunction
862
863
864
865%\end{algorithmic}
866
867
868\begin{algorithm}
869\caption{Astar}
870\label{Astar}
871\begin{algorithmic}[1]
872
873
874\Procedure{CheckWall}{$sTile_x,sTile_y,eTile,Visited$}
875 \State \Return $Astar( sTile_x,sTile_y,eTile,Visited )$
876\EndProcedure
877\State
878\Procedure{Astar}{x,y,eTile,Visited}
879
880 %\State ClosedSet $\gets \emptyset$ \Comment set of positions already evaluated.
881 \State OpenSet $\gets \{ (x,y) \} $ \Comment set of positions to be evaluated.
882 \While{ OpenSet $\neq \emptyset$ }
883 \State CurrentPos $\gets$ position in OpenSet with lowest Manhattan distance to eTile.
884 \If{ CurrentPos = eTile } \Comment Check if current position is equal to the end tile.
885 \State \Return $true$ \Comment Current configuration is a wall.
886 \EndIf
887
888 \State Visited($CurrentPos_x$,$CurrentPos_y$) $\gets$ 1
889 \ForAll{positions $p$ which are 8-way adjacent to CurrentPos}
890 \If{ Visited($p_x$,$p_y$) = 0 and ($p_x$,$p_y$) is valid } \Comment Check is position should be added.
891 \State OpenSet $\gets$ OpenSet $\cup \{p\}$
892 \EndIf
893 \EndFor
894 \State OpenSet $\gets$ OpenSet $\setminus$ CurrentPos \Comment Remove CurrentPos from the open set.
895 \EndWhile
896 %\State Visited(x,y) $\gets$ 1
897
898 \State \Return $false$ \Comment Current configuration is not a wall
899
900\EndProcedure
901\end{algorithmic}
902\end{algorithm}
903
904
905
906%-----------------------------------------------------------------------------
907% E X P E R I M E N T S
908%-----------------------------------------------------------------------------
909\section{Experiments}
910
911% Setup
912\subsection{Setup}
913
914
915In the experiment of this paper, we use the standard 1 barracks 2 supply depots to wall off the starting location.
916We pick 4 CIG maps from the 2017 tournament and 1 from the general CIG map pool since the map "Alchemist 1.0" has multiple entrances to the main base and is thus not wall-able anyway with the three given building.
917The maps we picked are:
918\begin{itemize}
919 \item Hitchhiker 1.1
920 \item Tau Cross 1.1
921 \item Neo Aztec 2.1 (replaces Alchemist)
922 \item Andromeda 1.0
923 \item Python 1.3
924\end{itemize}
925
926
927We run the test on each map 20 times. The mean running time of the flood fill and A* variant of the algorithm can be found in Table \ref{tab:MeanTimeT}.
928
929%These results are obtained from running
930%When replicating the experiment, note that due to the randomness in the supply depot building process the total minerals gathered may vary by around 8 minerals (one extra trip).
931
932
933%Results (supply depot at 9 instead of 10, used in most build orders):
934%\begin{itemize}
935% \item Build-in:3930
936% \item Mineral-lock: 4458
937% \item Queue algorithm: 4522
938%\end{itemize}
939
940\begin{table}[h]
941\begin{center}
942 \begin{tabular}{ | l | | l | l | l | l | l | l | l | l | l | l | }
943 \hline
944 Map/Algorthim & Flood Fill & A* \\ \hline \hline
945 Hitchhiker 1.1 & tbd & 6.5s \\ \hline
946 Tau Cross 1.1 & tbd & 1.7s \\ \hline
947 Neo Aztec 2.1 & tbd & 0.7s \\ \hline
948 Andromeda 1.0 & tbd & 3.3s \\ \hline
949 Python 1.3 & tbd & 11.4s \\ \hline
950 %\hline
951 \end{tabular}
952\end{center}
953 \caption{Running time of each algorithm variant in seconds. Average of 20 experiment runs.}
954\label{tab:MeanTimeT}
955\end{table}
956
957
958
959
960
961
962%-----------------------------------------------------------------------------
963% C O N C L U S I O N S & F U T U R E R E S E A R C H
964%-----------------------------------------------------------------------------
965\section{Conclusions \& Future Research}
966In this article, we have shown two variants of an algorithm which can be used for building walls in StarCraft.
967Unlike other methods, this algorithm guarantees that a wall can be used to ensure that a given unit cannot pass through it.
968The downside compared to other methods is that iterating through the possibilities to ensure that the wall is thight, is a costly calculation.
969The A* heuristic search improves this, but this algorithm is still mainly recommended to be used for pre-calculating building positions to ensure a thight wall.
970Because the map of StarCraft is static, this information can be calculated and stored, such that it can be retrieved next game and be used immediately.
971Thus this algorithm becomes a tool, like the terrain analysis tool BWTA, which is used by our StarCraft agent for choke point analysis and splitting the map in regions.
972
973One of the things still missing from the pathfinding is the exact data on gaps created by the terrain. For now our algorithm used the walkable data given by the BWTA.
974The walls created by this are thight, but the criteria are more strict than they need to be,
975Thus our algorithm sometimes report that there is no wall possible, even though one exists.
976This explain the large variance of running time between maps, since our algorithm takes less time if it finds a wall (because then it can terminate the search).
977Most of the time, an alternative wall (further away from the starting position) will be found at the cost of extra running time. This is especially the case on maps like "Python".
978
979A way to improve the running time is to have some extra checks in place for the buiding placement to reduce the amount of building placement choices that can be triviably calculated to not be walls.
980
981
982\bibliographystyle{IEEEtran}
983\bibliography{IEEEabrv,cig16}
984
985% argument is your BibTeX string definitions and bibliography database(s)
986%
987% <OR> manually copy in the resultant .bbl file
988% set second argument of \begin to the number of references
989% (used to reserve space for the reference number labels box)
990%\begin{thebibliography}{1}
991
992%\bibitem{IEEEhowto:kopka}
993%H.~Kopka and P.~W. Daly, \emph{A Guide to \LaTeX}, 3rd~ed.\hskip 1em plus
994% 0.5em minus 0.4em\relax Harlow, England: Addison-Wesley, 1999.
995
996%\end{thebibliography}
997
998
999
1000
1001% that's all folks
1002\end{document}