sangho lights stationary with walls

a.java

package mosquito.g1;

import java.awt.geom.Line2D;
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map.Entry;
import java.util.Random;
import java.util.Set;

import org.apache.log4j.Logger;

import mosquito.sim.Collector;
import mosquito.sim.Light;
import mosquito.sim.Player;

/**
 * This is a Group 1's Player that dynamically places the lights.
 * 
 * 0. Let the Walls be high, then the more open the lower.
 * 1. randomly distribute candidate points. Note that higher area has more
 * chance to be a candidate point due to cases where there are tiny holes. The
 * possibility of trees passing through the tiny holes decreases.
 * 2. the algorithm will choose one of the lowest candidates as the root.
 * (collector will be here)
 * 3. construct the tree in greedy way. Greedy way is defined by the extent of
 * area the new light will newly cover. The growing is very similar to the
 * Dijkstra's algorithm.
 * 4. if the tree is good enough, we are done, if not, try more until
 * MAX_TRIALS.
 * 
 * 03 Feb 2013
 * 
 * @author Lee Sangho (sangho@seas)
 * @author Meredith Kevin (kevin.m.meredith@gmail)
 */
public class G1_GreedyDecrH extends Player {
    private Logger log = Logger.getLogger(this.getClass());
    /**
     * the maximum coverage radius of the light.
     */
    private static int LIGHT_RANGE = 20;
    /**
     * when we put the candidates of light-point, the light may roll down to
     * lower position within the range of 1 to this.
     */
    private static int ROLLING_RANGE = 2;
    /**
     * the maximum coverage radius of the candidate point.
     */
    private static int CANDIDATE_RANGE = 6;
    /**
     * if a node will not cover more than this, that node is useless.
     */
    private static int UESLESS_DETERMINER = 14;
    /**
     * Note: if this is too low, the algorithm will give up too easily.
     * if this is too high, there will be too many useless candidates.
     */
    private static int MAX_NOPROGRESS_BUILD_CANDIDATES = 600;
    /**
     * Note: if this is too low, the algorithm will give up too easily.
     * if this is too high, the calculation will take more time.
     */
    private static int MAX_NOPROGRESS_BUILD_TREE = 10;
    /**
     * the max number of trials to build the tree.
     * we will use the best.
     */
    private static int MAX_TRIALS = 5;
    /**
     * the dimension of the map.
     */
    private static int DIM = 100;
    /**
     * the maximum height. we use lightRange.
     */
    private static byte MAX_H = 20;
    /**
     * if a cell is higher than this, we will put an additional candidate point,
     * and cut the adjacent cells' height by H_DECR_RATE. (adjacency is
     * determined by CANDIDATE_RANGE)
     */
    private static byte TARGET_H = 10;
    /**
     * if this is too high, there will be too much lowest area.
     */
    private static byte H_DECR_RATE = 1;
    /**
     * the number of lights to use.
     */
    private int numLights;
    /**
     * the obstacles.
     */
    private Line2D[] walls;
    /**
     * the number of passable cells.
     */
    private int numPassableCells;
    /**
     * the candidate nodes of light-point.
     * treeNodes will be chosen from this.
     */
    private LinkedHashSet<Pair<Integer, Integer>> candidateNodes;
    /**
     * the chosen nodes of light-point.
     * Map: XYPair-TopoLevel
     */
    private LinkedHashMap<Pair<Integer, Integer>, Integer> treeNodes;
    /**
     * max topological order of the tree.
     */
    private int maxTopoLevel;
    /**
     * the installed lights on the chosen position with light-timing
     * information.
     */
    private LinkedHashMap<Integer, Light> dynamicLights;
    /**
     * the index of the light holding a collector.
     */
    private int collectingLight;
    private int lowestH;
    /**
     * the height of each cell. the boundaries and walls are highest and it goes
     * lower when it goes away.
     */
    private byte[][] heightCell;
    private byte[][] remainingHeightCell;
    /**
     * true if the cell is covered already.
     */
    private boolean[][] coverageCell;

    @Override
    public String getName() {
        return "Greedy DecrH LF-0";
    }

    /**
     * initialize parameters and data.
     * 
     * @param numLights
     * @param walls
     */
    private void init(Set<Line2D> walls, int numLights) {
        this.walls = new Line2D[walls.size()];
        this.walls = walls.toArray(this.walls);
        this.numLights = numLights;

        numPassableCells = 0;
        candidateNodes = new LinkedHashSet<Pair<Integer, Integer>>();
        treeNodes = new LinkedHashMap<Pair<Integer, Integer>, Integer>();
        maxTopoLevel = 0;
        dynamicLights = new LinkedHashMap<Integer, Light>();
        collectingLight = 0;

        lowestH = MAX_H;
        heightCell = new byte[DIM][DIM];
        remainingHeightCell = new byte[DIM][DIM];
        coverageCell = new boolean[DIM][DIM];
    }

    /**
     * decrease the height of close visible cells, and if the cell is lower than
     * the targetH then return a list of the cells.
     * 
     * @param px
     * @param py
     * @param r
     * @return
     */
    private List<Pair<Integer, Integer>> decrCloseVisibleCells(int px, int py,
            int r) {
        List<Integer> adjWalls = getAdjWalls(px, py);
        List<Pair<Integer, Integer>> ret = new LinkedList<Pair<Integer, Integer>>();
        int startX = Math.max(0, px - r);
        int startY = Math.max(0, py - r);
        int endX = Math.min(99, px + r);
        int endY = Math.min(99, py + r);
        for (int x = startX; x <= endX; x++) {
            for (int y = startY; y <= endY; y++) {
                int dx = x - px;
                int dy = y - py;
                int tmpSqDist = dx * dx + dy * dy;
                if (tmpSqDist <= r * r) {
                    if (isVisible(x, y, px, py, adjWalls)) {
                        if (remainingHeightCell[x][y] >= TARGET_H) {
                            remainingHeightCell[x][y]--;
                        }
                        else {
                            ret.add(new Pair<Integer, Integer>(x, y));
                        }
                    }
                }
            }
        }
        return ret;
    }

    /**
     * initialize data for the given walls.
     */
    private void initGraph() {
        /*
         * the remaining uncovered cells.
         * we will pick the candidateNode from this.
         */
        List<Pair<Integer, Integer>> remainingCells = new LinkedList<Pair<Integer, Integer>>();

        // set boundaries and walls as highest cell.
        for (int i = 0; i < DIM; i++) {
            heightCell[i][0] = (byte) (MAX_H - H_DECR_RATE);
            heightCell[i][DIM - 1] = (byte) (MAX_H - H_DECR_RATE);
            heightCell[0][i] = (byte) (MAX_H - H_DECR_RATE);
            heightCell[DIM - 1][i] = (byte) (MAX_H - H_DECR_RATE);
        }
        for (Line2D wall : walls) {
            int x1, x2, y1, y2;
            // x1 is always on the left of the x2.
            if (wall.getX1() <= wall.getX2()) {
                x1 = (int) (wall.getX1() - 0.5);
                x2 = (int) (wall.getX2() - 0.5);
                y1 = (int) (wall.getY1() - 0.5);
                y2 = (int) (wall.getY2() - 0.5);
            }
            else {
                x1 = (int) (wall.getX2() - 0.5);
                x2 = (int) (wall.getX1() - 0.5);
                y1 = (int) (wall.getY2() - 0.5);
                y2 = (int) (wall.getY1() - 0.5);
            }
            double slope;
            if (x2 == x1)
                slope = (double) DIM;
            else if (y2 == y1)
                slope = 0.0;
            else slope = (y2 - y1) / (double) (x2 - x1);
            // log.trace(x1 + "," + y1 + " -> " + x2 + "," + y2 + " -> " +
            // slope);
            int curY = y1;
            for (int x = x1; x <= x2; x++) {
                if (slope >= (double) DIM) {
                    if (y1 < y2) {
                        int ty = y2;
                        y2 = y1;
                        y1 = ty;
                    }
                    for (int y = y2; y <= y1; y++) {
                        heightCell[x][y] = MAX_H;
                    }
                }
                else if (slope >= 0.0) {
                    int maxY = (int) (y1 + Math.floor(slope * (x - x1)));
                    for (int y = curY; y <= maxY; y++) {
                        if (y < DIM - 1 && y >= 0) {
                            heightCell[x][y] = MAX_H;
                        }
                    }
                    curY = maxY;
                }
                else {
                    int minY = (int) (y1 + Math.floor(slope * (x - x1)));
                    for (int y = curY; y >= minY; y--) {
                        if (y < DIM - 1 && y >= 0) {
                            heightCell[x][y] = MAX_H;
                        }
                    }
                    curY = minY;
                }
            }
        }

        // initialize coverage information.
        LinkedHashSet<Pair<Integer, Integer>> updatingCell = new LinkedHashSet<Pair<Integer, Integer>>();
        LinkedHashSet<Pair<Integer, Integer>> nextUpdatingCell;
        for (int i = 0; i < DIM; i++) {
            for (int j = 0; j < DIM; j++) {
                if (heightCell[i][j] >= MAX_H) {
                    updatingCell.add(new Pair<Integer, Integer>(i, j));
                    coverageCell[i][j] = true;
                }
                else {
                    if (heightCell[i][j] >= MAX_H - H_DECR_RATE) {
                        // for boundaries
                        updatingCell.add(new Pair<Integer, Integer>(i, j));
                    }
                    remainingCells.add(new Pair<Integer, Integer>(i, j));
                    numPassableCells++;
                }
            }
        }

        // calculate height of cells.
        for (byte k = (byte) (MAX_H - H_DECR_RATE); k >= 1; k -= H_DECR_RATE) {
            nextUpdatingCell = new LinkedHashSet<Pair<Integer, Integer>>();
            for (Pair<Integer, Integer> cell : updatingCell) {
                int i = cell.x;
                int j = cell.y;
                if (i >= 1) {
                    if (heightCell[i - 1][j] <= k) heightCell[i - 1][j] = k;
                    nextUpdatingCell.add(new Pair<Integer, Integer>(i - 1, j));
                }
                if (i < DIM - 1) {
                    if (heightCell[i + 1][j] <= k) heightCell[i + 1][j] = k;
                    nextUpdatingCell.add(new Pair<Integer, Integer>(i + 1, j));
                }
                if (j >= 1) {
                    if (heightCell[i][j - 1] <= k) heightCell[i][j - 1] = k;
                    nextUpdatingCell.add(new Pair<Integer, Integer>(i, j - 1));
                }
                if (j < DIM - 1) {
                    if (heightCell[i][j + 1] <= k) heightCell[i][j + 1] = k;
                    nextUpdatingCell.add(new Pair<Integer, Integer>(i, j + 1));
                }
            }
            updatingCell = nextUpdatingCell;
        }

        // build remainingHeightCell
        for (int i = 0; i < DIM; i++) {
            for (int j = 0; j < DIM; j++) {
                remainingHeightCell[i][j] = heightCell[i][j];
            }
        }

        // build candidateNodes
        Random rand = new Random();
        int cntNoProgress = 0;
        while (remainingCells.size() > 0) {
            Pair<Integer, Integer> curPt = pickRandom(remainingCells);
            int rx = curPt.x;
            int ry = curPt.y;
            int numRolling = 1 + rand.nextInt(ROLLING_RANGE);

            int lowx = rx;
            int lowy = ry;
            int minh = heightCell[rx][ry];
            for (int i = 0; i < numRolling; i++) {
                if (rx >= 1) {
                    int th = heightCell[rx - 1][ry];
                    if (minh > th) {
                        lowx = rx - 1;
                        lowy = ry;
                        minh = th;
                    }
                }
                if (ry >= 1) {
                    int th = heightCell[rx][ry - 1];
                    if (minh > th) {
                        lowx = rx;
                        lowy = ry - 1;
                        minh = th;
                    }
                }
                if (rx < DIM - 1) {
                    int th = heightCell[rx + 1][ry];
                    if (minh > th) {
                        lowx = rx + 1;
                        lowy = ry;
                        minh = th;
                    }
                }
                if (ry < DIM - 1) {
                    int th = heightCell[rx][ry + 1];
                    if (minh > th) {
                        lowx = rx;
                        lowy = ry + 1;
                        minh = th;
                    }
                }

                if (lowx == rx && lowy == ry) {
                    break;
                }
                else {
                    rx = lowx;
                    ry = lowy;
                }
            }
            if (heightCell[rx][ry] < lowestH) {
                lowestH = heightCell[rx][ry];
            }
            Pair<Integer, Integer> newPt = new Pair<Integer, Integer>(rx, ry);
            candidateNodes.add(newPt);
            List<Pair<Integer, Integer>> wellCoveredCells = decrCloseVisibleCells(
                    newPt.x, newPt.y, CANDIDATE_RANGE);
            int delta = remainingCells.size();
            remainingCells.removeAll(wellCoveredCells);
            delta -= remainingCells.size();

            if (delta > 0) {
                cntNoProgress = 0;
                // log.trace("Progress, numUncovered=" + remainingCells.size());
            }
            else {
                cntNoProgress++;
                if (cntNoProgress >= MAX_NOPROGRESS_BUILD_CANDIDATES) {
                    log.trace("no more progress, numUncovered="
                            + remainingCells.size());
                    remainingCells.clear();
                }
            }
        }

        for (int i = 0; i < DIM; i++) {
            // log.trace(Arrays.toString(heightCell[i]));
        }
    }

    /**
     * return a randomly picked pair from the list of pairs.
     * 
     * @param searchSpace
     * @return
     */
    private Pair<Integer, Integer> pickRandom(
            List<Pair<Integer, Integer>> searchSpace) {
        Random rand = new Random();
        return searchSpace.get(rand.nextInt(searchSpace.size()));
    }

    /**
     * return true if two points can see each other. In other words, true if
     * there is no obstacle between two points.
     * 
     * @param x1
     * @param y1
     * @param x2
     * @param y2
     * @param obstaclesIdx
     * @return
     */
    private boolean isVisible(double x1, double y1, double x2, double y2,
            List<Integer> obstaclesIdx) {
        double tolerR = 0.20;
        for (Integer obsIdx : obstaclesIdx) {
            Line2D obs = walls[obsIdx];
            if (obs.intersectsLine(x1, y1, x2, y2)
                    || obs.intersectsLine(x1, y1, x2 + tolerR, y2 + tolerR)
                    || obs.intersectsLine(x1, y1, x2 + tolerR, y2 - tolerR)
                    || obs.intersectsLine(x1, y1, x2 - tolerR, y2 - tolerR)
                    || obs.intersectsLine(x1, y1, x2 - tolerR, y2 + tolerR)
                    || obs.intersectsLine(x1 + tolerR, y1 + tolerR, x2, y2)
                    || obs.intersectsLine(x1 + tolerR, y1 - tolerR, x2, y2)
                    || obs.intersectsLine(x1 - tolerR, y1 - tolerR, x2, y2)
                    || obs.intersectsLine(x1 - tolerR, y1 + tolerR, x2, y2)) {
                return false;
            }
        }
        return true;
    }

    /**
     * 
     * @param px
     * @param py
     * @return the list of indices of adjacent walls (determined by lightRange)
     */
    private List<Integer> getAdjWalls(double px, double py) {
        List<Integer> adjWalls = new LinkedList<Integer>();
        for (int i = 0; i < walls.length; i++) {
            double dist = walls[i].ptLineDist(px, py);
            if (dist <= (double) LIGHT_RANGE) {
                adjWalls.add(i);
            }
        }
        return adjWalls;
    }

    /**
     * return the closest visible node's position for the given point.
     * Note that the return pair can be further than lightRange.
     * 
     * @param px
     * @param py
     * @return
     */
    private Pair<Integer, Integer> getClosestVisibleTreeNode(int px, int py) {
        if (treeNodes.size() == 0) {
            return null;
        }
        else {
            List<Integer> adjWalls = getAdjWalls(px, py);
            Pair<Integer, Integer> closestPt = null;
            int minSqDist = DIM * DIM;
            for (Pair<Integer, Integer> tmpPt : treeNodes.keySet()) {
                if (isVisible(tmpPt.x, tmpPt.y, px, py, adjWalls)) {
                    int dx = px - tmpPt.x;
                    int dy = py - tmpPt.y;
                    int tmpSqDist = dx * dx + dy * dy;
                    if (tmpSqDist <= minSqDist) {
                        minSqDist = tmpSqDist;
                        closestPt = tmpPt;
                    }
                }
            }
            return closestPt;
        }
    }

    /**
     * return the number of cells which will be NEWLY covered when we put a
     * light at pt position.
     * 
     * @param pt
     * @return
     */
    private int checkCoverage(Pair<Integer, Integer> pt) {
        int numWillBeCovered = 0;
        int px = pt.x;
        int py = pt.y;
        List<Integer> adjWalls = getAdjWalls(px, py);
        int startX = Math.max(0, px - LIGHT_RANGE);
        int startY = Math.max(0, py - LIGHT_RANGE);
        int endX = Math.min(99, px + LIGHT_RANGE);
        int endY = Math.min(99, py + LIGHT_RANGE);
        for (int x = startX; x <= endX; x++) {
            for (int y = startY; y <= endY; y++) {
                int dx = x - px;
                int dy = y - py;
                int sqDist = dx * dx + dy * dy;
                if (sqDist < LIGHT_RANGE * LIGHT_RANGE) {
                    if (heightCell[x][y] < MAX_H
                            && isVisible(x, y, px, py, adjWalls)) {
                        if (coverageCell[x][y] == false) {
                            numWillBeCovered++;
                        }
                    }
                }
            }
        }
        return numWillBeCovered;
    }

    /**
     * put a light-position at pt, and then return the candidates of next
     * light-positions.
     * 
     * @param pt
     * @return
     */
    private List<Pair<Integer, Integer>> getNewFrontNodes(
            Pair<Integer, Integer> pt) {
        List<Pair<Integer, Integer>> ret = new LinkedList<Pair<Integer, Integer>>();
        int px = pt.x;
        int py = pt.y;
        List<Integer> adjWalls = getAdjWalls(px, py);
        int startX = Math.max(0, px - LIGHT_RANGE);
        int startY = Math.max(0, py - LIGHT_RANGE);
        int endX = Math.min(99, px + LIGHT_RANGE);
        int endY = Math.min(99, py + LIGHT_RANGE);
        for (int x = startX; x <= endX; x++) {
            for (int y = startY; y <= endY; y++) {
                int dx = x - px;
                int dy = y - py;
                int sqDist = dx * dx + dy * dy;
                if (sqDist < LIGHT_RANGE * LIGHT_RANGE) {
                    Pair<Integer, Integer> tmpPt = new Pair<Integer, Integer>(
                            x, y);
                    if (isVisible(x, y, px, py, adjWalls)) {
                        if (candidateNodes.contains(tmpPt)) {
                            if (coverageCell[x][y] == false) {
                                ret.add(tmpPt);
                            }
                            candidateNodes.remove(tmpPt);
                        }
                        coverageCell[x][y] = true;
                    }
                }
            }
        }
        return ret;
    }

    /**
     * build graph by greedy method with look-forwarding.
     * TODO look-forward feature is not yet implemented.
     * 
     * @param numTargetingCoverage
     * @param uselessNodeBound
     * @param numLookForward
     */
    private int buildTreeGreedyLookForward(int numTargetingCoverage,
            int uselessNodeBound, int numLookForward) {
        Set<Pair<Integer, Integer>> frontNodes = new LinkedHashSet<Pair<Integer, Integer>>();
        Pair<Integer, Integer> curPt;
        int curCoverage = 0;

        // pick the first tree node among the lowest nodes.
        List<Pair<Integer, Integer>> consideringNodes = new LinkedList<Pair<Integer, Integer>>();
        for (Pair<Integer, Integer> tmpPt : candidateNodes) {
            int tx = tmpPt.x;
            int ty = tmpPt.y;
            if (heightCell[tx][ty] == lowestH) {
                consideringNodes.add(new Pair<Integer, Integer>(tx, ty));
            }
        }
        curPt = pickRandom(consideringNodes);
        curCoverage += checkCoverage(curPt);
        frontNodes.addAll(getNewFrontNodes(curPt));
        treeNodes.put(new Pair<Integer, Integer>(curPt.x, curPt.y), 0);
        maxTopoLevel = 0;
        collectingLight = 0;

        // pick the rest tree nodes.
        consideringNodes.clear();
        int cntNoProgress = 0;
        while (numTargetingCoverage > curCoverage && frontNodes.size() > 0
                && treeNodes.size() <= numLights) {
            int maxValue = 0;
            Pair<Integer, Integer> maxPt = null;
            List<Pair<Integer, Integer>> uselessNodes = new LinkedList<Pair<Integer, Integer>>();
            for (Pair<Integer, Integer> tmpPt : frontNodes) {
                int tmpValue = checkCoverage(tmpPt);
                if (tmpValue < uselessNodeBound) {
                    uselessNodes.add(tmpPt);
                }
                else {
                    if (tmpValue >= maxValue) {
                        maxValue = tmpValue;
                        maxPt = tmpPt;
                    }
                }
            }
            // remove already well-covered points.
            frontNodes.removeAll(uselessNodes);
            // when maxPt == null...
            if (maxPt == null) {
                log.trace("All visible nodes are useless...");
                break;
            }
            // log.trace("curPt=" + maxPt.x + "," + maxPt.y + ", coverage="
            // + maxValue);

            curPt = maxPt;
            curCoverage += maxValue;
            frontNodes.addAll(getNewFrontNodes(curPt));
            int topoLevel = treeNodes.get(getClosestVisibleTreeNode(curPt.x,
                    curPt.y)) + 1;
            treeNodes.put(new Pair<Integer, Integer>(curPt.x, curPt.y),
                    topoLevel);
            if (maxTopoLevel < topoLevel) {
                maxTopoLevel = topoLevel;
            }

            log.trace("curCoverage=" + curCoverage + ", treeNodes="
                    + treeNodes.size() + ", frontNodes=" + frontNodes.size()
                    + ", candidateNodes=" + candidateNodes.size());

            if (maxValue > 0) {
                cntNoProgress = 0;
            }
            else {
                cntNoProgress++;
                if (cntNoProgress >= MAX_NOPROGRESS_BUILD_TREE) {
                    log.trace("no more progress");
                    frontNodes.clear();
                }
            }
        }
        return curCoverage;
    }

    /**
     * build dynamicLights from the nodes. light timing is single sweep which
     * means that at a phase, a set of lights of the same level will light.
     */
    private void installSingleSweepLights(
            LinkedHashMap<Pair<Integer, Integer>, Integer> tree) {
        int timeT = 25;
        int timeD = (maxTopoLevel + 1) * timeT;
        int lightCnt = 0;
        for (int topo = 0; topo <= maxTopoLevel; topo++) {
            for (Entry<Pair<Integer, Integer>, Integer> tmpEntry : tree
                    .entrySet()) {
                Pair<Integer, Integer> tmpPt = tmpEntry.getKey();
                int tmpTopoLevel = tmpEntry.getValue();
                if (tmpTopoLevel == topo) {
                    int timeS = timeD - (topo + 1) * timeT;
                    if (topo == 0) {
                        // install the collecting light without the trap.
                        dynamicLights.put(lightCnt, new Light(tmpPt.x, tmpPt.y,
                                timeT + 13, timeT, timeS));
                    }
                    else {
                        dynamicLights.put(lightCnt, new Light(tmpPt.x, tmpPt.y,
                                timeD, timeT, timeS));
                    }
                    lightCnt++;
                }
            }
        }
        collectingLight = 0;
    }

    /**
     * test-only.
     */
    private void installCandidateLights() {
        int lightCnt = 0;
        for (Pair<Integer, Integer> tmpPt : candidateNodes) {
            dynamicLights.put(lightCnt, new Light(tmpPt.x, tmpPt.y, 1, 0, 1));
            lightCnt++;
        }
    }

    /*
     * This is called when a new game starts. It is passed the set
     * of lines that comprise the different walls, as well as the
     * maximum number of lights you are allowed to use.
     */
    @Override
    public void startNewGame(Set<Line2D> walls, int numLights) {
        LinkedHashMap<Pair<Integer, Integer>, Integer> bestTreeNodes = null;
        int bestCoverage = 0;
        int cntTrial = 0;
        long startTime = System.currentTimeMillis();
        while (cntTrial < MAX_TRIALS) {
            init(walls, numLights);
            log.trace("Starting new game: numLights=" + numLights
                    + " numWalls=" + walls.size());

            initGraph();
            log.trace("Init Graph base done. numCandidateNodes="
                    + candidateNodes.size() + " numPassable="
                    + numPassableCells);

            int tmpCoverage = buildTreeGreedyLookForward(numPassableCells,
                    UESLESS_DETERMINER, 1);
            log.trace("Build Tree done. maxTopoLevel=" + maxTopoLevel);

            if (tmpCoverage > (double) (numPassableCells) * 0.8
                    || numLights <= treeNodes.size()) {
                if (tmpCoverage > bestCoverage) {
                    bestCoverage = tmpCoverage;
                    bestTreeNodes = treeNodes;
                }
                cntTrial = MAX_TRIALS;
                break;
            }
            else {
                if (tmpCoverage > bestCoverage) {
                    bestCoverage = tmpCoverage;
                    bestTreeNodes = treeNodes;
                }
                cntTrial++;
            }
        }

        installSingleSweepLights(bestTreeNodes);
        // installCandidateLights();
        long elapsedTime = System.currentTimeMillis() - startTime;
        log.trace("maxNodes=" + bestTreeNodes.size() + " maxDynamicLights="
                + dynamicLights.size() + " elapsedTime=" + elapsedTime);
    }

    /**
     * use the dynamicLights first, and if we allowed more lights but we do not
     * need, then put them at (0,0) without the function.
     * 
     * @return
     */
    private Set<Light> getDynamicLights() {
        HashSet<Light> ret = new HashSet<Light>();
        int maxDynamicLights = dynamicLights.size();
        for (int k = 0; k < numLights; k++) {
            Light tmpLight;
            if (k < maxDynamicLights) {
                tmpLight = dynamicLights.get(k);
            }
            else {
                tmpLight = new Light(0, 0, 1, 0, 1);
            }
            // log.trace("Positioned a light at (" + l.getX() + "," + l.getY()
            // + ")");
            ret.add(tmpLight);
        }
        return ret;
    }

    /*
     * This is called after startNewGame. If your Set contains more
     * than the maximum allowed number of Lights, an error will occur.
     */
    @Override
    public Set<Light> getLights() {
        return getDynamicLights();
    }

    /*
     * This is called after getLights.
     */
    @Override
    public Collector getCollector() {
        Light l = dynamicLights.get(collectingLight);
        double tx = l.getX() + 0.6;
        double ty = l.getY();
        Collector c = new Collector(tx, ty);
        log.debug("Positioned Collector at (" + tx + "," + ty + ")");
        return c;
    }
}