Commits

Vincent Fiack  committed 951b718

first version. Starter kit reformatted

  • Participants

Comments (0)

Files changed (126)

+syntax: glob
+target
+.classpath
+.project
+.settings
+*.pyc
+<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
+	xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd">
+	<modelVersion>4.0.0</modelVersion>
+
+
+	<!-- identique au project.xml, avec ajout du packaging -->
+	<groupId>vfiack.fr</groupId>
+	<artifactId>mybot</artifactId>
+	<packaging>jar</packaging>
+	<version>1.00</version>
+	<name>aichallenge</name>
+	<description>AI Challenge</description>
+	<url>http://xxx</url>
+
+
+	<!-- configuration des plugins -->
+	<build>
+		<plugins>
+			<plugin>
+				<groupId>org.apache.maven.plugins</groupId>
+				<artifactId>maven-compiler-plugin</artifactId>
+				<configuration>
+					<source>1.5</source>
+					<target>1.5</target>
+					<encoding>ISO-8859-15</encoding>
+				</configuration>
+			</plugin>
+		</plugins>
+	</build>
+
+	<dependencies>
+	</dependencies>
+</project>

File src/main/java/MyBot.java

+import java.io.IOException;
+
+import fr.vfiack.ants.AntsBot;
+
+public class MyBot {   
+    public static void main(String[] args) throws IOException {
+        new AntsBot().readSystemInput();
+    }    
+}

File src/main/java/fr/vfiack/ants/AntsBot.java

+package fr.vfiack.ants;
+
+import org.aichallenge.Aim;
+import org.aichallenge.Ants;
+import org.aichallenge.Bot;
+import org.aichallenge.Tile;
+
+public class AntsBot extends Bot {
+
+    /**
+     * For every ant check every direction in fixed order (N, E, S, W) and move it if the tile is
+     * passable.
+     */
+    @Override
+    public void doTurn() {
+        Ants ants = getAnts();
+        
+        for (Tile myAnt : ants.getMyAnts()) {
+            for (Aim direction : Aim.values()) {
+                if (ants.getIlk(myAnt, direction).isPassable()) {
+                    ants.issueOrder(myAnt, direction);
+                    break;
+                }
+            }
+        }
+    }
+}

File src/main/java/org/aichallenge/AbstractSystemInputParser.java

+package org.aichallenge;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Scanner;
+import java.util.regex.Pattern;
+
+/**
+ * Handles system input stream parsing.
+ */
+public abstract class AbstractSystemInputParser extends AbstractSystemInputReader {
+    private static final String READY = "ready";
+    
+    private static final String GO = "go";
+    
+    private static final char COMMENT_CHAR = '#';
+    
+    private final List<String> input = new ArrayList<String>();
+    
+    private enum SetupToken {
+        LOADTIME, TURNTIME, ROWS, COLS, TURNS, VIEWRADIUS2, ATTACKRADIUS2, SPAWNRADIUS2;
+        
+        private static final Pattern PATTERN = compilePattern(SetupToken.class);
+    }
+    
+    private enum UpdateToken {
+        W, A, F, D, H;
+        
+        private static final Pattern PATTERN = compilePattern(UpdateToken.class);
+    }
+    
+    private static Pattern compilePattern(Class<? extends Enum> clazz) {
+        StringBuilder builder = new StringBuilder("(");
+        for (Enum enumConstant : clazz.getEnumConstants()) {
+            if (enumConstant.ordinal() > 0) {
+                builder.append("|");
+            }
+            builder.append(enumConstant.name());
+        }
+        builder.append(")");
+        return Pattern.compile(builder.toString());
+    }
+    
+    /**
+     * Collects lines read from system input stream until a keyword appears and then parses them.
+     */
+    @Override
+    public void processLine(String line) {
+        if (line.equals(READY)) {
+            parseSetup(input);
+            doTurn();
+            finishTurn();
+            input.clear();
+        } else if (line.equals(GO)) {
+            parseUpdate(input);
+            doTurn();
+            finishTurn();
+            input.clear();
+        } else if (!line.isEmpty()) {
+            input.add(line);
+        }
+    }
+    
+    /**
+     * Parses the setup information from system input stream.
+     * 
+     * @param input setup information
+     */
+    public void parseSetup(List<String> input) {
+        int loadTime = 0;
+        int turnTime = 0;
+        int rows = 0;
+        int cols = 0;
+        int turns = 0;
+        int viewRadius2 = 0;
+        int attackRadius2 = 0;
+        int spawnRadius2 = 0;
+        for (String line : input) {
+            line = removeComment(line);
+            if (line.isEmpty()) {
+                continue;
+            }
+            Scanner scanner = new Scanner(line);
+            if (!scanner.hasNext()) {
+                continue;
+            }
+            String token = scanner.next().toUpperCase();
+            if (!SetupToken.PATTERN.matcher(token).matches()) {
+                continue;
+            }
+            SetupToken setupToken = SetupToken.valueOf(token);
+            switch (setupToken) {
+                case LOADTIME:
+                    loadTime = scanner.nextInt();
+                break;
+                case TURNTIME:
+                    turnTime = scanner.nextInt();
+                break;
+                case ROWS:
+                    rows = scanner.nextInt();
+                break;
+                case COLS:
+                    cols = scanner.nextInt();
+                break;
+                case TURNS:
+                    turns = scanner.nextInt();
+                break;
+                case VIEWRADIUS2:
+                    viewRadius2 = scanner.nextInt();
+                break;
+                case ATTACKRADIUS2:
+                    attackRadius2 = scanner.nextInt();
+                break;
+                case SPAWNRADIUS2:
+                    spawnRadius2 = scanner.nextInt();
+                break;
+            }
+        }
+        setup(loadTime, turnTime, rows, cols, turns, viewRadius2, attackRadius2, spawnRadius2);
+    }
+    
+    /**
+     * Parses the update information from system input stream.
+     * 
+     * @param input update information
+     */
+    public void parseUpdate(List<String> input) {
+        beforeUpdate();
+        for (String line : input) {
+            line = removeComment(line);
+            if (line.isEmpty()) {
+                continue;
+            }
+            Scanner scanner = new Scanner(line);
+            if (!scanner.hasNext()) {
+                continue;
+            }
+            String token = scanner.next().toUpperCase();
+            if (!UpdateToken.PATTERN.matcher(token).matches()) {
+                continue;
+            }
+            UpdateToken updateToken = UpdateToken.valueOf(token);
+            int row = scanner.nextInt();
+            int col = scanner.nextInt();
+            switch (updateToken) {
+                case W:
+                    addWater(row, col);
+                break;
+                case A:
+                    if (scanner.hasNextInt()) {
+                        addAnt(row, col, scanner.nextInt());
+                    }
+                break;
+                case F:
+                    addFood(row, col);
+                break;
+                case D:
+                    if (scanner.hasNextInt()) {
+                        removeAnt(row, col, scanner.nextInt());
+                    }
+                break;
+                case H:
+                    if (scanner.hasNextInt()) {
+                        addHill(row, col, scanner.nextInt());
+                    }
+                break;
+            }
+        }
+        afterUpdate();
+    }
+    
+    /**
+     * Sets up the game state.
+     * 
+     * @param loadTime timeout for initializing and setting up the bot on turn 0
+     * @param turnTime timeout for a single game turn, starting with turn 1
+     * @param rows game map height
+     * @param cols game map width
+     * @param turns maximum number of turns the game will be played
+     * @param viewRadius2 squared view radius of each ant
+     * @param attackRadius2 squared attack radius of each ant
+     * @param spawnRadius2 squared spawn radius of each ant
+     */
+    public abstract void setup(int loadTime, int turnTime, int rows, int cols, int turns,
+            int viewRadius2, int attackRadius2, int spawnRadius2);
+    
+    /**
+     * Enables performing actions which should take place prior to updating the game state, like
+     * clearing old game data.
+     */
+    public abstract void beforeUpdate();
+    
+    /**
+     * Adds new water tile.
+     * 
+     * @param row row index
+     * @param col column index
+     */
+    public abstract void addWater(int row, int col);
+    
+    /**
+     * Adds new ant tile.
+     * 
+     * @param row row index
+     * @param col column index
+     * @param owner player id
+     */
+    public abstract void addAnt(int row, int col, int owner);
+    
+    /**
+     * Adds new food tile.
+     * 
+     * @param row row index
+     * @param col column index
+     */
+    public abstract void addFood(int row, int col);
+    
+    /**
+     * Removes dead ant tile.
+     * 
+     * @param row row index
+     * @param col column index
+     * @param owner player id
+     */
+    public abstract void removeAnt(int row, int col, int owner);
+    
+    /**
+     * Adds new hill tile.
+     *
+     * @param row row index
+     * @param col column index
+     * @param owner player id
+     */
+    public abstract void addHill(int row, int col, int owner);
+    
+    /**
+     * Enables performing actions which should take place just after the game state has been
+     * updated.
+     */
+    public abstract void afterUpdate();
+    
+    /**
+     * Subclasses are supposed to use this method to process the game state and send orders.
+     */
+    public abstract void doTurn();
+    
+    /**
+     * Finishes turn.
+     */
+    public void finishTurn() {
+        System.out.println("go");
+        System.out.flush();
+    }
+    
+    private String removeComment(String line) {
+        int commentCharIndex = line.indexOf(COMMENT_CHAR);
+        String lineWithoutComment;
+        if (commentCharIndex >= 0) {
+            lineWithoutComment = line.substring(0, commentCharIndex).trim();
+        } else {
+            lineWithoutComment = line;
+        }
+        return lineWithoutComment;
+    }
+}

File src/main/java/org/aichallenge/AbstractSystemInputReader.java

+package org.aichallenge;
+import java.io.IOException;
+
+/**
+ * Handles system input stream reading.
+ */
+public abstract class AbstractSystemInputReader {
+    /**
+     * Reads system input stream line by line. All characters are converted to lower case and each
+     * line is passed for processing to {@link #processLine(String)} method.
+     * 
+     * @throws IOException if an I/O error occurs
+     */
+    public void readSystemInput() throws IOException {
+        StringBuilder line = new StringBuilder();
+        int c;
+        while ((c = System.in.read()) >= 0) {
+            if (c == '\r' || c == '\n') {
+                processLine(line.toString().toLowerCase().trim());
+                line.setLength(0);
+            } else {
+                line = line.append((char)c);
+            }
+        }
+    }
+    
+    /**
+     * Process a line read out by {@link #readSystemInput()} method in a way defined by subclass
+     * implementation.
+     * 
+     * @param line single, trimmed line of system input
+     */
+    public abstract void processLine(String line);
+}

File src/main/java/org/aichallenge/Aim.java

+package org.aichallenge;
+import java.util.HashMap;
+import java.util.Map;
+
+/**
+ * Represents a direction in which to move an ant.
+ */
+public enum Aim {
+    /** North direction, or up. */
+    NORTH(-1, 0, 'n'),
+    
+    /** East direction or right. */
+    EAST(0, 1, 'e'),
+    
+    /** South direction or down. */
+    SOUTH(1, 0, 's'),
+    
+    /** West direction or left. */
+    WEST(0, -1, 'w');
+    
+    private static final Map<Character, Aim> symbolLookup = new HashMap<Character, Aim>();
+    
+    static {
+        symbolLookup.put('n', NORTH);
+        symbolLookup.put('e', EAST);
+        symbolLookup.put('s', SOUTH);
+        symbolLookup.put('w', WEST);
+    }
+    
+    private final int rowDelta;
+    
+    private final int colDelta;
+    
+    private final char symbol;
+    
+    Aim(int rowDelta, int colDelta, char symbol) {
+        this.rowDelta = rowDelta;
+        this.colDelta = colDelta;
+        this.symbol = symbol;
+    }
+    
+    /**
+     * Returns rows delta.
+     * 
+     * @return rows delta.
+     */
+    public int getRowDelta() {
+        return rowDelta;
+    }
+    
+    /**
+     * Returns columns delta.
+     * 
+     * @return columns delta.
+     */
+    public int getColDelta() {
+        return colDelta;
+    }
+    
+    /**
+     * Returns symbol associated with this direction.
+     * 
+     * @return symbol associated with this direction.
+     */
+    public char getSymbol() {
+        return symbol;
+    }
+    
+    /**
+     * Returns direction associated with specified symbol.
+     * 
+     * @param symbol <code>n</code>, <code>e</code>, <code>s</code> or <code>w</code> character
+     * 
+     * @return direction associated with specified symbol
+     */
+    public static Aim fromSymbol(char symbol) {
+        return symbolLookup.get(symbol);
+    }
+}

File src/main/java/org/aichallenge/Ants.java

+package org.aichallenge;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Set;
+
+/**
+ * Holds all game data and current game state.
+ */
+public class Ants {
+    /** Maximum map size. */
+    public static final int MAX_MAP_SIZE = 256;
+    
+    private final int loadTime;
+    
+    private final int turnTime;
+    
+    private final int rows;
+    
+    private final int cols;
+    
+    private final int turns;
+    
+    private final int viewRadius2;
+    
+    private final int attackRadius2;
+    
+    private final int spawnRadius2;
+    
+    private long turnStartTime;
+    
+    private final Ilk map[][];
+    
+    private final Set<Tile> myAnts = new HashSet<Tile>();
+    
+    private final Set<Tile> enemyAnts = new HashSet<Tile>();
+    
+    private final Set<Tile> myHills = new HashSet<Tile>();
+    
+    private final Set<Tile> enemyHills = new HashSet<Tile>();
+    
+    private final Set<Tile> foodTiles = new HashSet<Tile>();
+    
+    private final Set<Order> orders = new HashSet<Order>();
+    
+    /**
+     * Creates new {@link Ants} object.
+     * 
+     * @param loadTime timeout for initializing and setting up the bot on turn 0
+     * @param turnTime timeout for a single game turn, starting with turn 1
+     * @param rows game map height
+     * @param cols game map width
+     * @param turns maximum number of turns the game will be played
+     * @param viewRadius2 squared view radius of each ant
+     * @param attackRadius2 squared attack radius of each ant
+     * @param spawnRadius2 squared spawn radius of each ant
+     */
+    public Ants(int loadTime, int turnTime, int rows, int cols, int turns, int viewRadius2,
+            int attackRadius2, int spawnRadius2) {
+        this.loadTime = loadTime;
+        this.turnTime = turnTime;
+        this.rows = rows;
+        this.cols = cols;
+        this.turns = turns;
+        this.viewRadius2 = viewRadius2;
+        this.attackRadius2 = attackRadius2;
+        this.spawnRadius2 = spawnRadius2;
+        map = new Ilk[rows][cols];
+        for (Ilk[] row : map) {
+            Arrays.fill(row, Ilk.LAND);
+        }
+    }
+    
+    /**
+     * Returns timeout for initializing and setting up the bot on turn 0.
+     * 
+     * @return timeout for initializing and setting up the bot on turn 0
+     */
+    public int getLoadTime() {
+        return loadTime;
+    }
+    
+    /**
+     * Returns timeout for a single game turn, starting with turn 1.
+     * 
+     * @return timeout for a single game turn, starting with turn 1
+     */
+    public int getTurnTime() {
+        return turnTime;
+    }
+    
+    /**
+     * Returns game map height.
+     * 
+     * @return game map height
+     */
+    public int getRows() {
+        return rows;
+    }
+    
+    /**
+     * Returns game map width.
+     * 
+     * @return game map width
+     */
+    public int getCols() {
+        return cols;
+    }
+    
+    /**
+     * Returns maximum number of turns the game will be played.
+     * 
+     * @return maximum number of turns the game will be played
+     */
+    public int getTurns() {
+        return turns;
+    }
+    
+    /**
+     * Returns squared view radius of each ant.
+     * 
+     * @return squared view radius of each ant
+     */
+    public int getViewRadius2() {
+        return viewRadius2;
+    }
+    
+    /**
+     * Returns squared attack radius of each ant.
+     * 
+     * @return squared attack radius of each ant
+     */
+    public int getAttackRadius2() {
+        return attackRadius2;
+    }
+    
+    /**
+     * Returns squared spawn radius of each ant.
+     * 
+     * @return squared spawn radius of each ant
+     */
+    public int getSpawnRadius2() {
+        return spawnRadius2;
+    }
+    
+    /**
+     * Sets turn start time.
+     * 
+     * @param turnStartTime turn start time
+     */
+    public void setTurnStartTime(long turnStartTime) {
+        this.turnStartTime = turnStartTime;
+    }
+    
+    /**
+     * Returns how much time the bot has still has to take its turn before timing out.
+     * 
+     * @return how much time the bot has still has to take its turn before timing out
+     */
+    public int getTimeRemaining() {
+        return turnTime - (int)(System.currentTimeMillis() - turnStartTime);
+    }
+    
+    /**
+     * Returns ilk at the specified location.
+     * 
+     * @param tile location on the game map
+     * 
+     * @return ilk at the <cod>tile</code>
+     */
+    public Ilk getIlk(Tile tile) {
+        return map[tile.getRow()][tile.getCol()];
+    }
+    
+    /**
+     * Sets ilk at the specified location.
+     * 
+     * @param tile location on the game map
+     * @param ilk ilk to be set at <code>tile</code>
+     */
+    public void setIlk(Tile tile, Ilk ilk) {
+        map[tile.getRow()][tile.getCol()] = ilk;
+    }
+    
+    /**
+     * Returns ilk at the location in the specified direction from the specified location.
+     * 
+     * @param tile location on the game map
+     * @param direction direction to look up
+     * 
+     * @return ilk at the location in <code>direction</code> from <cod>tile</code>
+     */
+    public Ilk getIlk(Tile tile, Aim direction) {
+        Tile newTile = getTile(tile, direction);
+        return map[newTile.getRow()][newTile.getCol()];
+    }
+    
+    /**
+     * Returns location in the specified direction from the specified location.
+     * 
+     * @param tile location on the game map
+     * @param direction direction to look up
+     * 
+     * @return location in <code>direction</code> from <cod>tile</code>
+     */
+    public Tile getTile(Tile tile, Aim direction) {
+        int row = (tile.getRow() + direction.getRowDelta()) % rows;
+        if (row < 0) {
+            row += rows;
+        }
+        int col = (tile.getCol() + direction.getColDelta()) % cols;
+        if (col < 0) {
+            col += cols;
+        }
+        return new Tile(row, col);
+    }
+    
+    /**
+     * Returns a set containing all my ants locations.
+     * 
+     * @return a set containing all my ants locations
+     */
+    public Set<Tile> getMyAnts() {
+        return myAnts;
+    }
+    
+    /**
+     * Returns a set containing all enemy ants locations.
+     * 
+     * @return a set containing all enemy ants locations
+     */
+    public Set<Tile> getEnemyAnts() {
+        return enemyAnts;
+    }
+    
+    /**
+     * Returns a set containing all my hills locations.
+     * 
+     * @return a set containing all my hills locations
+     */
+    public Set<Tile> getMyHills() {
+        return myHills;
+    }
+    
+    /**
+     * Returns a set containing all enemy hills locations.
+     * 
+     * @return a set containing all enemy hills locations
+     */
+    public Set<Tile> getEnemyHills() {
+        return enemyHills;
+    }
+    
+    /**
+     * Returns a set containing all food locations.
+     * 
+     * @return a set containing all food locations
+     */
+    public Set<Tile> getFoodTiles() {
+        return foodTiles;
+    }
+    
+    /**
+     * Returns all orders sent so far.
+     * 
+     * @return all orders sent so far
+     */
+    public Set<Order> getOrders() {
+        return orders;
+    }
+    
+    /**
+     * Calculates distance between two locations on the game map.
+     * 
+     * @param t1 one location on the game map
+     * @param t2 another location on the game map
+     * 
+     * @return distance between <code>t1</code> and <code>t2</code>
+     */
+    public int getDistance(Tile t1, Tile t2) {
+        int rowDelta = Math.abs(t1.getRow() - t2.getRow());
+        int colDelta = Math.abs(t1.getCol() - t2.getCol());
+        rowDelta = Math.min(rowDelta, rows - rowDelta);
+        colDelta = Math.min(colDelta, cols - colDelta);
+        return rowDelta * rowDelta + colDelta * colDelta;
+    }
+    
+    /**
+     * Returns one or two orthogonal directions from one location to the another.
+     * 
+     * @param t1 one location on the game map
+     * @param t2 another location on the game map
+     * 
+     * @return orthogonal directions from <code>t1</code> to <code>t2</code>
+     */
+    public List<Aim> getDirections(Tile t1, Tile t2) {
+        List<Aim> directions = new ArrayList<Aim>();
+        if (t1.getRow() < t2.getRow()) {
+            if (t2.getRow() - t1.getRow() >= rows / 2) {
+                directions.add(Aim.NORTH);
+            } else {
+                directions.add(Aim.SOUTH);
+            }
+        } else if (t1.getRow() > t2.getRow()) {
+            if (t1.getRow() - t2.getRow() >= rows / 2) {
+                directions.add(Aim.SOUTH);
+            } else {
+                directions.add(Aim.NORTH);
+            }
+        }
+        if (t1.getCol() < t2.getCol()) {
+            if (t2.getCol() - t1.getCol() >= cols / 2) {
+                directions.add(Aim.WEST);
+            } else {
+                directions.add(Aim.EAST);
+            }
+        } else if (t1.getCol() > t2.getCol()) {
+            if (t1.getCol() - t2.getCol() >= cols / 2) {
+                directions.add(Aim.EAST);
+            } else {
+                directions.add(Aim.WEST);
+            }
+        }
+        return directions;
+    }
+    
+    /**
+     * Clears game state information about my ants locations.
+     */
+    public void clearMyAnts() {
+        myAnts.clear();
+    }
+    
+    /**
+     * Clears game state information about enemy ants locations.
+     */
+    public void clearEnemyAnts() {
+        enemyAnts.clear();
+    }
+    
+    /**
+     * Clears game state information about my hills locations.
+     */
+    public void clearMyHills() {
+        myHills.clear();
+    }
+    
+    /**
+     * Clears game state information about enemy hills locations.
+     */
+    public void clearEnemyHills() {
+        enemyHills.clear();
+    }
+
+    /**
+     * Clears game map state information
+     */
+    public void clearMap() {
+        for (int row = 0; row < rows; row++) {
+            for (int col = 0; col < cols; col++) {
+                if (map[row][col] != Ilk.WATER) {
+                    map[row][col] = Ilk.LAND;
+                }
+            }
+        }
+    }
+    
+    /**
+     * Updates game state information about new ants and food locations.
+     * 
+     * @param ilk ilk to be updated
+     * @param tile location on the game map to be updated
+     */
+    public void update(Ilk ilk, Tile tile) {
+        map[tile.getRow()][tile.getCol()] = ilk;
+        switch (ilk) {
+            case FOOD:
+                foodTiles.add(tile);
+            break;
+            case MY_ANT:
+                myAnts.add(tile);
+            break;
+            case ENEMY_ANT:
+                enemyAnts.add(tile);
+            break;
+        }
+    }
+    
+    /**
+     * Updates game state information about hills locations.
+     *
+     * @param owner owner of hill
+     * @param tile location on the game map to be updated
+     */
+    public void updateHills(int owner, Tile tile) {
+        if (owner > 0)
+            enemyHills.add(tile);
+        else
+            myHills.add(tile);
+    }
+    
+    /**
+     * Issues an order by sending it to the system output.
+     * 
+     * @param myAnt map tile with my ant
+     * @param direction direction in which to move my ant
+     */
+    public void issueOrder(Tile myAnt, Aim direction) {
+        Order order = new Order(myAnt, direction);
+        orders.add(order);
+        System.out.println(order);
+    }
+}

File src/main/java/org/aichallenge/Bot.java

+package org.aichallenge;
+/**
+ * Provides basic game state handling.
+ */
+public abstract class Bot extends AbstractSystemInputParser {
+    private Ants ants;
+    
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    public void setup(int loadTime, int turnTime, int rows, int cols, int turns, int viewRadius2,
+            int attackRadius2, int spawnRadius2) {
+        setAnts(new Ants(loadTime, turnTime, rows, cols, turns, viewRadius2, attackRadius2,
+            spawnRadius2));
+    }
+    
+    /**
+     * Returns game state information.
+     * 
+     * @return game state information
+     */
+    public Ants getAnts() {
+        return ants;
+    }
+    
+    /**
+     * Sets game state information.
+     * 
+     * @param ants game state information to be set
+     */
+    protected void setAnts(Ants ants) {
+        this.ants = ants;
+    }
+    
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    public void beforeUpdate() {
+        ants.setTurnStartTime(System.currentTimeMillis());
+        ants.clearMyAnts();
+        ants.clearEnemyAnts();
+        ants.clearMyHills();
+        ants.clearEnemyHills();
+        ants.getFoodTiles().clear();
+        ants.getOrders().clear();
+        ants.clearMap();
+    }
+    
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    public void addWater(int row, int col) {
+        ants.update(Ilk.WATER, new Tile(row, col));
+    }
+    
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    public void addAnt(int row, int col, int owner) {
+        ants.update(owner > 0 ? Ilk.ENEMY_ANT : Ilk.MY_ANT, new Tile(row, col));
+    }
+    
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    public void addFood(int row, int col) {
+        ants.update(Ilk.FOOD, new Tile(row, col));
+    }
+    
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    public void removeAnt(int row, int col, int owner) {
+        ants.update(Ilk.DEAD, new Tile(row, col));
+    }
+    
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    public void addHill(int row, int col, int owner) {
+        ants.updateHills(owner, new Tile(row, col));
+    }
+    
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    public void afterUpdate() {
+    }
+}

File src/main/java/org/aichallenge/Ilk.java

+package org.aichallenge;
+/**
+ * Represents type of tile on the game map.
+ */
+public enum Ilk {
+    /** Water tile. */
+    WATER,
+    
+    /** Food tile. */
+    FOOD,
+    
+    /** Land tile. */
+    LAND,
+    
+    /** Dead ant tile. */
+    DEAD,
+    
+    /** My ant tile. */
+    MY_ANT,
+    
+    /** Enemy ant tile. */
+    ENEMY_ANT;
+    
+    /**
+     * Checks if this type of tile is passable, which means it is not a water tile.
+     * 
+     * @return <code>true</code> if this is not a water tile, <code>false</code> otherwise
+     */
+    public boolean isPassable() {
+        return ordinal() > WATER.ordinal();
+    }
+    
+    /**
+     * Checks if this type of tile is unoccupied, which means it is a land tile or a dead ant tile.
+     * 
+     * @return <code>true</code> if this is a land tile or a dead ant tile, <code>false</code>
+     *         otherwise
+     */
+    public boolean isUnoccupied() {
+        return this == LAND || this == DEAD;
+    }
+}

File src/main/java/org/aichallenge/Order.java

+package org.aichallenge;
+/**
+ * Represents an order to be issued.
+ */
+public class Order {
+    private final int row;
+    
+    private final int col;
+    
+    private final char direction;
+    
+    /**
+     * Creates new {@link Order} object.
+     * 
+     * @param tile map tile with my ant
+     * @param direction direction in which to move my ant
+     */
+    public Order(Tile tile, Aim direction) {
+        row = tile.getRow();
+        col = tile.getCol();
+        this.direction = direction.getSymbol();
+    }
+    
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    public String toString() {
+        return "o " + row + " " + col + " " + direction;
+    }
+}

File src/main/java/org/aichallenge/Tile.java

+package org.aichallenge;
+/**
+ * Represents a tile of the game map.
+ */
+public class Tile {
+    private final int row;
+    
+    private final int col;
+    
+    /**
+     * Creates new {@link Tile} object.
+     * 
+     * @param row row index
+     * @param col column index
+     */
+    public Tile(int row, int col) {
+        this.row = row;
+        this.col = col;
+    }
+    
+    /**
+     * Returns row index.
+     * 
+     * @return row index
+     */
+    public int getRow() {
+        return row;
+    }
+    
+    /**
+     * Returns column index.
+     * 
+     * @return column index
+     */
+    public int getCol() {
+        return col;
+    }
+    
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    public int hashCode() {
+        return row * Ants.MAX_MAP_SIZE + col;
+    }
+    
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    public boolean equals(Object o) {
+        boolean result = false;
+        if (o instanceof Tile) {
+            Tile tile = (Tile)o;
+            result = row == tile.row && col == tile.col;
+        }
+        return result;
+    }
+    
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    public String toString() {
+        return row + " " + col;
+    }
+}

File tools/VERSION

+This tools package was published on Mon Oct 24 07:46:56 UTC 2011.
+
+Last change in the ants/ folder was:
+commit 1db33f66800f8e137adf9e5ef9e5da2b2e5f3490
+Date:   Mon Oct 24 03:46:11 2011 -0400
+
+    Don't use the highlight color for a regular player
+
+Check https://github.com/aichallenge/aichallenge/ants/ for new versions.

File tools/ants.py

+#!/usr/bin/env python
+from random import randrange, choice, shuffle, randint, seed, random
+from math import sqrt
+from collections import deque, defaultdict
+
+from fractions import Fraction
+import operator
+import string
+from game import Game
+from copy import deepcopy
+try:
+    from sys import maxint
+except ImportError:
+    from sys import maxsize as maxint
+
+ANTS = 0
+DEAD = -1
+LAND = -2
+FOOD = -3
+WATER = -4
+UNSEEN = -5
+
+PLAYER_ANT = 'abcdefghij'
+HILL_ANT = string = 'ABCDEFGHI'
+PLAYER_HILL = string = '0123456789'
+MAP_OBJECT = '?%*.!'
+MAP_RENDER = PLAYER_ANT + HILL_ANT + PLAYER_HILL + MAP_OBJECT
+
+HILL_POINTS = 2
+RAZE_POINTS = -1
+
+# possible directions an ant can move
+AIM = {'n': (-1, 0),
+       'e': (0, 1),
+       's': (1, 0),
+       'w': (0, -1)}
+
+# precalculated sqrt
+SQRT = [int(sqrt(r)) for r in range(101)]
+
+class Ants(Game):
+    def __init__(self, options=None):
+        # setup options
+        map_text = options['map']
+        self.turns = int(options['turns'])
+        self.loadtime = int(options['loadtime'])
+        self.turntime = int(options['turntime'])
+        self.viewradius = int(options["viewradius2"])
+        self.attackradius = int(options["attackradius2"])
+        self.spawnradius = int(options["spawnradius2"])
+        self.engine_seed = options.get('engine_seed', randint(-maxint-1, maxint))
+        self.player_seed = options.get('player_seed', randint(-maxint-1, maxint))
+        seed(self.engine_seed)
+        self.food_rate = options.get('food_rate', (2,8)) # total food
+        if type(self.food_rate) in (list, tuple):
+            self.food_rate = randrange(self.food_rate[0], self.food_rate[1]+1)
+        self.food_turn = options.get('food_turn', (12,30)) # per turn
+        if type(self.food_turn) in (list, tuple):
+            self.food_turn = randrange(self.food_turn[0], self.food_turn[1]+1)
+        self.food_start = options.get('food_start', (75,175)) # per land area
+        if type(self.food_start) in (list, tuple):
+            self.food_start = randrange(self.food_start[0], self.food_start[1]+1)
+        self.food_visible = options.get('food_visible', (1,3)) # in starting loc
+        if type(self.food_visible) in (list, tuple):
+            self.food_visible = randrange(self.food_visible[0], self.food_visible[1]+1)
+        self.food_extra = Fraction(0,1)
+
+        self.cutoff_percent = options.get('cutoff_percent', 0.90)
+        self.cutoff_turn = options.get('cutoff_turn', 100)
+
+        self.do_attack = {
+            'focus':   self.do_attack_focus,
+            'closest': self.do_attack_closest,
+            'support': self.do_attack_support,
+            'damage':  self.do_attack_damage
+        }.get(options.get('attack'), self.do_attack_focus)
+
+        self.do_food = {
+            'none':      self.do_food_none,
+            'random':    self.do_food_random,
+            'sections':  self.do_food_sections,
+            'symmetric': self.do_food_symmetric
+        }.get(options.get('food'), self.do_food_sections)
+
+        self.scenario = options.get('scenario', False)
+
+        map_data = self.parse_map(map_text)
+
+        self.turn = 0
+        self.num_players = map_data['num_players']
+
+        self.current_ants = {} # ants that are currently alive
+        self.killed_ants = []  # ants which were killed this turn
+        self.all_ants = []     # all ants that have been created
+
+        self.all_food = []     # all food created
+        self.current_food = {} # food currently in game
+        self.pending_food = defaultdict(int)
+
+        self.hills = {}        # all hills
+        self.hive_food = [0]*self.num_players # food waiting to spawn for player
+        self.hive_history = [[0] for _ in range(self.num_players)]
+
+        # used to cutoff games early
+        self.cutoff = None
+        self.cutoff_bot = LAND # Can be ant owner, FOOD or LAND
+        self.cutoff_turns = 0
+        # used to calculate the turn when the winner took the lead
+        self.winning_bot = None
+        self.winning_turn = 0
+        # used to calculate when the player rank last changed
+        self.ranking_bots = None
+        self.ranking_turn = 0
+
+        # initialize size
+        self.height, self.width = map_data['size']
+        self.land_area = self.height*self.width - len(map_data['water'])
+
+        # initialize map
+        # this matrix does not track hills, just ants
+        self.map = [[LAND]*self.width for _ in range(self.height)]
+
+        # initialize water
+        for row, col in map_data['water']:
+            self.map[row][col] = WATER
+
+        # for new games
+        # ants are ignored and 1 ant is created per hill
+        # food is ignored
+        # for scenarios, the map file is followed exactly
+
+        # initialize hills
+        for owner, locs in map_data['hills'].items():
+            for loc in locs:
+                hill = self.add_hill(loc, owner)
+                if not self.scenario:
+                    self.add_ant(hill)
+
+        if self.scenario:
+            # initialize ants
+            for player, player_ants in map_data['ants'].items():
+                for ant_loc in player_ants:
+                    self.add_initial_ant(ant_loc, player)
+            # initialize food
+            for food in map_data['food']:
+                self.add_food(food)
+
+        # initialize scores
+        # points start at # of hills to prevent negative scores
+        self.score = [len(map_data['hills'][0])]*self.num_players
+        self.bonus = [0]*self.num_players
+        self.score_history = [[s] for s in self.score]
+
+        # used to remember where the ants started
+        self.initial_ant_list = sorted(self.current_ants.values(), key=operator.attrgetter('owner'))
+        self.initial_access_map = self.access_map()
+
+        # cache used by neighbourhood_offsets() to determine nearby squares
+        self.offsets_cache = {}
+
+        # used to track dead players, ants may still exist, but orders are not processed
+        self.killed = [False for _ in range(self.num_players)]
+
+        # used to give a different ordering of players to each player
+        #   initialized to ensure that each player thinks they are player 0
+        self.switch = [[None]*self.num_players + list(range(-5,0)) for i in range(self.num_players)]
+        for i in range(self.num_players):
+            self.switch[i][i] = 0
+        # used to track water and land already reveal to player
+        self.revealed = [[[False for col in range(self.width)]
+                          for row in range(self.height)]
+                         for _ in range(self.num_players)]
+        # used to track what a player can see
+        self.init_vision()
+
+        # the engine may kill players before the game starts and this is needed to prevent errors
+        self.orders = [[] for i in range(self.num_players)]
+        
+
+    def distance(self, a_loc, b_loc):
+        """ Returns distance between x and y squared """
+        d_row = abs(a_loc[0] - b_loc[0])
+        d_row = min(d_row, self.height - d_row)
+        d_col = abs(a_loc[1] - b_loc[1])
+        d_col = min(d_col, self.width - d_col)
+        return d_row**2 + d_col**2
+
+    def parse_map(self, map_text):
+        """ Parse the map_text into a more friendly data structure """
+        ant_list = None
+        hill_list = []
+        hill_count = defaultdict(int)
+        width = height = None
+        water = []
+        food = []
+        ants = defaultdict(list)
+        hills = defaultdict(list)
+        row = 0
+        score = None
+        hive = None
+        num_players = None
+
+        for line in map_text.split('\n'):
+            line = line.strip()
+
+            # ignore blank lines and comments
+            if not line or line[0] == '#':
+                continue
+
+            key, value = line.split(' ', 1)
+            key = key.lower()
+            if key == 'cols':
+                width = int(value)
+            elif key == 'rows':
+                height = int(value)
+            elif key == 'players':
+                num_players = int(value)
+                if num_players < 2 or num_players > 10:
+                    raise Exception("map",
+                                    "player count must be between 2 and 10")
+            elif key == 'score':
+                score = list(map(int, value.split()))
+            elif key == 'hive':
+                hive = list(map(int, value.split()))
+            elif key == 'm':
+                if ant_list is None:
+                    if num_players is None:
+                        raise Exception("map",
+                                        "players count expected before map lines")
+                    ant_list = [chr(97 + i) for i in range(num_players)]
+                    hill_list = list(map(str, range(num_players)))
+                    hill_ant = [chr(65 + i) for i in range(num_players)]
+                if len(value) != width:
+                    raise Exception("map",
+                                    "Incorrect number of cols in row %s. "
+                                    "Got %s, expected %s."
+                                    %(row, len(value), width))
+                for col, c in enumerate(value):
+                    if c in ant_list:
+                        ants[ant_list.index(c)].append((row,col))
+                    elif c in hill_list:
+                        hills[hill_list.index(c)].append((row,col))
+                        hill_count[hill_list.index(c)] += 1
+                    elif c in hill_ant:
+                        ants[hill_ant.index(c)].append((row,col))
+                        hills[hill_ant.index(c)].append((row,col))
+                        hill_count[hill_ant.index(c)] += 1
+                    elif c == MAP_OBJECT[FOOD]:
+                        food.append((row,col))
+                    elif c == MAP_OBJECT[WATER]:
+                        water.append((row,col))
+                    elif c != MAP_OBJECT[LAND]:
+                        raise Exception("map",
+                                        "Invalid character in map: %s" % c)
+                row += 1
+
+        if score and len(score) != num_players:
+            raise Exception("map",
+                            "Incorrect score count.  Expected %s, got %s"
+                            % (num_players, len(score)))
+        if hive and len(hive) != num_players:
+            raise Exception("map",
+                            "Incorrect score count.  Expected %s, got %s"
+                            % (num_players, len(score)))
+
+        if height != row:
+            raise Exception("map",
+                            "Incorrect number of rows.  Expected %s, got %s"
+                            % (height, row))
+
+        # look for ants without hills to invalidate map for a game
+        if not self.scenario:
+            for hill, count in hill_count.items():
+                if count == 0:
+                    raise Exception("map",
+                                    "Player %s has no starting hills"
+                                    % hill)
+
+        return {
+            'size':        (height, width),
+            'num_players': num_players,
+            'hills':       hills,
+            'ants':        ants,
+            'food':        food,
+            'water':       water
+        }
+
+    def neighbourhood_offsets(self, max_dist):
+        """ Return a list of squares within a given distance of loc
+
+            Loc is not included in the list
+            For all squares returned: 0 < distance(loc,square) <= max_dist
+
+            Offsets are calculated so that:
+              -height <= row+offset_row < height (and similarly for col)
+              negative indicies on self.map wrap thanks to python
+        """
+        if max_dist not in self.offsets_cache:
+            offsets = []
+            mx = int(sqrt(max_dist))
+            for d_row in range(-mx,mx+1):
+                for d_col in range(-mx,mx+1):
+                    d = d_row**2 + d_col**2
+                    if 0 < d <= max_dist:
+                        offsets.append((
+                            d_row%self.height-self.height,
+                            d_col%self.width-self.width
+                        ))
+            self.offsets_cache[max_dist] = offsets
+        return self.offsets_cache[max_dist]
+
+    def init_vision(self):
+        """ Initialise the vision data """
+        # calculate and cache vision offsets
+        cache = {}
+        # all offsets that an ant can see
+        locs = set(self.neighbourhood_offsets(self.viewradius))
+        locs.add((0,0))
+        cache['new'] = list(locs)
+        cache['-'] = [list(locs)]
+
+        for d in AIM:
+            # determine the previous view
+            p_r, p_c = -AIM[d][0], -AIM[d][1]
+            p_locs = set(
+                (((p_r+r)%self.height-self.height),
+                 ((p_c+c)%self.width-self.width))
+                for r,c in locs
+            )
+            cache[d] = [list(p_locs), list(locs-p_locs), list(p_locs-locs)]
+        self.vision_offsets_cache = cache
+
+        # create vision arrays
+        self.vision = []
+        for _ in range(self.num_players):
+            self.vision.append([[0]*self.width for __ in range(self.height)])
+
+        # initialise the data based on the initial ants
+        self.update_vision()
+        self.update_revealed()
+
+    def update_vision(self):
+        """ Incrementally updates the vision data """
+        for ant in self.current_ants.values():
+            if not ant.orders:
+                # new ant
+                self.update_vision_ant(ant, self.vision_offsets_cache['new'], 1)
+            else:
+                order = ant.orders[-1]
+                if order in AIM:
+                    # ant moved
+                    self.update_vision_ant(ant, self.vision_offsets_cache[order][1], 1)
+                    self.update_vision_ant(ant, self.vision_offsets_cache[order][-1], -1)
+                # else: ant stayed where it was
+        for ant in self.killed_ants:
+            order = ant.orders[-1]
+            self.update_vision_ant(ant, self.vision_offsets_cache[order][0], -1)
+
+    def update_vision_ant(self, ant, offsets, delta):
+        """ Update the vision data for a single ant
+
+            Increments all the given offsets by delta for the vision
+              data for ant.owner
+        """
+        a_row, a_col = ant.loc
+        vision = self.vision[ant.owner]
+        for v_row, v_col in offsets:
+            # offsets are such that there is never an IndexError
+            vision[a_row+v_row][a_col+v_col] += delta
+
+    def update_revealed(self):
+        """ Make updates to state based on what each player can see
+
+            Update self.revealed to reflect the updated vision
+            Update self.switch for any new enemies
+            Update self.revealed_water
+        """
+        self.revealed_water = []
+        for player in range(self.num_players):
+            water = []
+            revealed = self.revealed[player]
+            switch = self.switch[player]
+
+            for row, squares in enumerate(self.vision[player]):
+                for col, visible in enumerate(squares):
+                    if not visible:
+                        continue
+
+                    value = self.map[row][col]
+
+                    # if this player encounters a new enemy then
+                    #   assign the enemy the next index
+                    if value >= ANTS and switch[value] is None:
+                        switch[value] = self.num_players - switch.count(None)
+
+                    # mark square as revealed and determine if we see any
+                    #   new water
+                    if not revealed[row][col]:
+                        revealed[row][col] = True
+                        if value == WATER:
+                            water.append((row,col))
+
+            # update the water which was revealed this turn
+            self.revealed_water.append(water)
+
+    def get_perspective(self, player=None):
+        """ Get the map from the perspective of the given player
+
+            If player is None, the map is return unaltered.
+            Squares that are outside of the player's vision are
+               marked as UNSEEN.
+            Enemy identifiers are changed to reflect the order in
+               which the player first saw them.
+        """
+        if player is not None:
+            v = self.vision[player]
+        result = []
+        for row, squares in enumerate(self.map):
+            map_row = []
+            for col, square in enumerate(squares):
+                if player is None or v[row][col]:
+                    if (row,col) in self.hills:
+                        if (row,col) in self.current_ants:
+                            # assume ant is hill owner
+                            # numbers should be divisible by the length of PLAYER_ANT
+                            map_row.append(square+10)
+                        else:
+                            map_row.append(square+20)
+                    else:
+                        map_row.append(square)
+                else:
+                    map_row.append(UNSEEN)
+            result.append(map_row)
+        return result
+
+    def render_changes(self, player):
+        """ Create a string which communicates the updates to the state
+
+            Water which is seen for the first time is included.
+            All visible transient objects (ants, food) are included.
+        """
+        updates = self.get_state_changes()
+        v = self.vision[player]
+        visible_updates = []
+
+        # first add unseen water
+        for row, col in self.revealed_water[player]:
+            visible_updates.append(['w', row, col])
+
+        # next list all transient objects
+        for update in updates:
+            type, row, col = update[0:3]
+
+            # only include updates to squares which are visible
+            # and the current players dead ants
+            if v[row][col] or (type == 'd' and update[-1] == player):
+                visible_updates.append(update)
+
+                # switch player perspective of player numbers
+                if type in ['a', 'd', 'h']:
+                    # an ant can appear in a bots vision and die the same turn
+                    # in this case the ant has not been assigned a number yet
+                    #   assign the enemy the next index
+                    if self.switch[player][update[-1]] is None:
+                        self.switch[player][update[-1]] = self.num_players - self.switch[player].count(None)
+                    update[-1] = self.switch[player][update[-1]]
+
+        visible_updates.append([]) # newline
+        return '\n'.join(' '.join(map(str,s)) for s in visible_updates)
+
+    def get_state_changes(self):
+        """ Return a list of all transient objects on the map.
+
+            Food, living ants, ants killed this turn
+            Changes are sorted so that the same state will result in the same output
+        """
+        changes = []
+
+        # hills not razed
+        changes.extend(sorted(
+            [['h', hill.loc[0], hill.loc[1], hill.owner]
+             for loc, hill in self.hills.items()
+             if hill.killed_by is None]
+        ))
+
+        # current ants
+        changes.extend(sorted(
+            ['a', ant.loc[0], ant.loc[1], ant.owner]
+            for ant in self.current_ants.values()
+        ))
+        # current food
+        changes.extend(sorted(
+            ['f', row, col]
+            for row, col in self.current_food
+        ))
+        # ants killed this turn
+        changes.extend(sorted(
+            ['d', ant.loc[0], ant.loc[1], ant.owner]
+            for ant in self.killed_ants
+        ))
+
+        return changes
+
+    def get_map_output(self, player=None):
+        """ Render the map from the perspective of the given player.
+
+            If player is None, then no squares are hidden and player ids
+              are not reordered.
+        """
+        result = []
+        for row in self.get_perspective(player):
+            result.append(''.join([MAP_RENDER[col] for col in row]))
+        return result
+
+    def nearby_ants(self, loc, max_dist, exclude=None):
+        """ Returns ants where 0 < dist to loc <= sqrt(max_dist)
+
+            If exclude is not None, ants with owner == exclude
+              will be ignored.
+        """
+        ants = []
+        row, col = loc
+        for d_row, d_col in self.neighbourhood_offsets(max_dist):
+            if ANTS <= self.map[row+d_row][col+d_col] != exclude:
+                n_loc = self.destination(loc, (d_row, d_col))
+                ants.append(self.current_ants[n_loc])
+        return ants
+
+    def parse_orders(self, player, lines):
+        """ Parse orders from the given player
+
+            Orders must be of the form: o row col direction
+            row, col must be integers
+            direction must be in (n,s,e,w)
+        """
+        orders = []
+        valid = []
+        ignored = []
+        invalid = []
+
+        for line in lines:
+            line = line.strip().lower()
+            # ignore blank lines and comments
+            if not line or line[0] == '#':
+                continue
+
+            data = line.split()
+
+            # validate data format
+            if data[0] != 'o':
+                invalid.append((line, 'unknown action'))
+                continue
+            if len(data) != 4:
+                invalid.append((line, 'incorrectly formatted order'))
+                continue
+
+            row, col, direction = data[1:]
+            loc = None
+
+            # validate the data types
+            try:
+                loc = int(row), int(col)
+            except ValueError:
+                invalid.append((line,'invalid row or col'))
+                continue
+            if direction not in AIM:
+                invalid.append((line,'invalid direction'))
+                continue
+
+            # this order can be parsed
+            orders.append((loc, direction))
+            valid.append(line)
+
+        return orders, valid, ignored, invalid
+
+    def validate_orders(self, player, orders, lines, ignored, invalid):
+        """ Validate orders from a given player
+
+            Location (row, col) must be ant belonging to the player
+            direction must not be blocked
+            Can't multiple orders to one ant
+        """
+        valid = []
+        valid_orders = []
+        seen_locations = set()
+        for line, (loc, direction) in zip(lines, orders):
+            # validate orders
+            if loc in seen_locations:
+                invalid.append((line,'duplicate order'))
+                continue
+            try:
+                if self.map[loc[0]][loc[1]] != player:
+                    invalid.append((line,'not player ant'))
+                    continue
+            except IndexError:
+                invalid.append((line,'out of bounds'))
+                continue
+            if loc[0] < 0 or loc[1] < 0:
+                invalid.append((line,'out of bounds'))
+                continue
+            dest = self.destination(loc, AIM[direction])
+            if self.map[dest[0]][dest[1]] in (FOOD, WATER):
+                ignored.append((line,'move blocked'))
+                continue
+
+            # this order is valid!
+            valid_orders.append((loc, direction))
+            valid.append(line)
+            seen_locations.add(loc)
+
+        return valid_orders, valid, ignored, invalid
+
+    def do_orders(self):
+        """ Execute player orders and handle conflicts
+
+            All ants are moved to their new positions.
+            Any ants which occupy the same square are killed.
+        """
+        # set old ant locations to land
+        for ant in self.current_ants.values():
+            row, col = ant.loc
+            self.map[row][col] = LAND
+
+        # determine the direction that each ant moves
+        #  (holding any ants that don't have orders)
+        move_direction = {}
+        for orders in self.orders:
+            for loc, direction in orders:
+                move_direction[self.current_ants[loc]] = direction
+        for ant in self.current_ants.values():
+            if ant not in move_direction:
+                move_direction[ant] = '-'
+
+        # move all the ants
+        next_loc = defaultdict(list)
+        for ant, direction in move_direction.items():
+            ant.loc = self.destination(ant.loc, AIM.get(direction, (0,0)))
+            ant.orders.append(direction)
+            next_loc[ant.loc].append(ant)
+
+        # if ant is sole occupant of a new square then it survives
+        self.current_ants = {}
+        colliding_ants = []
+        for loc, ants in next_loc.items():
+            if len(ants) == 1:
+                self.current_ants[loc] = ants[0]
+            else:
+                for ant in ants:
+                    self.kill_ant(ant, True)
+                    colliding_ants.append(ant)
+
+        # set new ant locations
+        for ant in self.current_ants.values():
+            row, col = ant.loc
+            self.map[row][col] = ant.owner
+
+    def do_gather(self):
+        """ Gather food
+
+            If there are no ants within spawnradius of a food then
+              the food remains.
+            If all the ants within spawnradius of a food are owned by the
+              same player then the food gets added to the hive and will
+              spawn a new ant as soon as possible ( 1 turn later ).
+            If ants of more than one owner are within spawnradius of a food
+              then that food disappears.
+        """
+        # gather food
+        for f_loc in list(self.current_food.keys()):
+            # find the owners of all the ants near the food
+            nearby_players = set(
+                ant.owner for ant in self.nearby_ants(f_loc, self.spawnradius)
+            )
+
+            if len(nearby_players) == 1:
+                # gather food because there is only one player near the food
+                owner = nearby_players.pop()
+                self.remove_food(f_loc, owner)
+            elif nearby_players:
+                # remove food because it is contested
+                self.remove_food(f_loc)
+
+    def do_spawn(self):
+        """ Spawn new ants at hills from hive amount
+
+            Ants spawn at hills.  The least recently touched hill has priority.
+            Ties are done randomly.  The bot can control by standing over a hill
+            to prevent spawning where they don't want to spawn.
+        """
+        # Determine new ant locations
+        for player in range(self.num_players):
+            player_hills = sorted(self.player_hills(player),
+                                  key=lambda hill: (hill.last_touched, random()))
+            for hill in player_hills:
+                # hill must not be razed or occupied to be used
+                # player must have food in hive to spawn
+                if (self.hive_food[player] > 0 and
+                        hill.loc not in self.current_ants):
+                    self.hive_food[player] -= 1
+                    self.add_ant(hill)
+
+    def add_food(self, loc):
+        """ Add food to a location
+
+            An error is raised if the location is not free
+        """
+        if self.map[loc[0]][loc[1]] != LAND:
+            raise Exception("Add food error",
+                            "Food already found at %s" %(loc,))
+        self.map[loc[0]][loc[1]] = FOOD
+        food = Food(loc, self.turn)
+        self.current_food[loc] = food
+        self.all_food.append(food)
+        return food
+
+    def remove_food(self, loc, owner=None):
+        """ Remove food from a location
+
+            An error is raised if no food exists there.
+        """
+        try:
+            self.map[loc[0]][loc[1]] = LAND
+            self.current_food[loc].end_turn = self.turn
+            if owner is not None:
+                self.current_food[loc].owner = owner
+                self.hive_food[owner] += 1
+            return self.current_food.pop(loc)
+        except KeyError:
+            raise Exception("Remove food error",
+                            "Food not found at %s" %(loc,))
+
+    def add_hill(self, loc, owner):
+        hill = Hill(loc, owner)
+        self.hills[loc] = hill
+        return hill
+
+    def raze_hill(self, hill, killed_by):
+        hill.end_turn = self.turn
+        hill.killed_by = killed_by
+        self.score[killed_by] += HILL_POINTS
+        self.score[hill.owner] += RAZE_POINTS
+        # reset cutoff_turns
+        self.cutoff_turns = 0
+
+    def player_hills(self, player):
+        """ Return the current hills belonging to the given player """
+        return [hill for _, hill in self.hills.items()
+                if hill.owner == player and hill.killed_by is None]
+
+    def add_ant(self, hill):
+        """ Spawn an ant on a hill
+        """