User talk:Straw

Here is the main targeting class: WhiteCouncil is for dynamic reweighting but currently has bugs. This is being actively worked on, this is just the current version, currently configured to use the GF as dimensions knn gun. <syntaxhighlight> package straw;

import java.awt.Graphics; import java.awt.geom.Point2D; import java.util.ArrayList; import java.util.Arrays; import java.util.Iterator; import java.util.LinkedList; import java.util.List; import java.util.ListIterator; import java.util.Queue;

import robocode.Bullet; import robocode.BulletHitEvent; import straw.KDTree.Ent; import straw.KDTree.SearchResult;

public class Narya { //TODO Glamdring // implements KNN (DC) targeting using Julian Kent's KDTree public ArrayList<Wave> waves = new ArrayList<>(); private double[] ARWeights = {1,1,1,1}; private double[] ASWeights = {1,1,1,1,.11}; private int decay = 50; private double ARE = .15; private double ASE = .5; private int bulletsHit = 0; private final int segCount = 5; public Ent<Double> subTreeAR; public Ent<Double> subTreeAS = new Ent<Double>(segCount,ASWeights); public Ent<Double> hitLog = new Ent<>(segCount,new double[]{1,1,1,1,1}); public Ent<Double> GFLogGun = new Ent<>(10,new double[]{1,.9,.8,.7,.6,.5,.4,.3,.2,.1}); private ArrayList<Double> GFLog = new ArrayList<>(1000); private WhiteCouncil council = new WhiteCouncil(subTreeAS);

   private int hits = 0;

private int shots = 0; private int sdecay = 0; private double latestGF = 0; public Narya() { subTreeAR = new Ent<Double>(segCount-1,ARWeights); for(int i = 0; i < 10; i++) { GFLog.add(0.0); }

} public void nonFiringTick() { council.onFreeTick(); } public void fire(long time,double speed,Point2D.Double position,double maximumEscapeAngle,double guessFactorZero,Status data) { Wave w = new Wave(time, speed, position, maximumEscapeAngle, guessFactorZero,data); w.setGFs(lastGFs(10)); waves.add(w); } private double[] lastGFs(int depth) { double[] GFs = new double[depth]; for(int i = 1; i <= depth; i++) { GFs[i-1] = (GFLog.get(GFLog.size()-i)+1)/2; } return GFs; } public void fire(Bullet b,double x,double y) { shots++; } public void bulletCollision() { sdecay += decay; bulletsHit ++; } public double GF(Status situation) {

if(bulletsHit/(double)shots > .5) return Math.random()/10-.05; if(shots > 10) { ///* double[] GFs = lastGFs(10); return highestDensity(GFLogGun.nearestNeighbours(GFs, (int)Math.min(Math.sqrt(GFLogGun.size()),5)), situation.distance); //*/ //return GF(ASLocation(situation),subTreeAS); } return (Math.random()/2-.25); } private double GF(double[] location, Ent<Double> tree) { int NN = (int) Math.min(Math.sqrt(subTreeAS.size()+1), 100); ArrayList<SearchResult<Double>> results = tree.nearestNeighbours(location, NN); return results.get(0).payload;//highestDensity(results,location[2] * 1000); } private double highestDensity(ArrayList<SearchResult<Double>> points,double distance) { double range = Math.atan(18/distance); double bestGF = 0; double bestScore = 0; for(double i = -1; i <= 1; i += .04) { double score = score(i, points,range); bestScore = Math.max(score, bestScore); if( score == bestScore) bestGF = i; } return bestGF; } private double score(double GF,ArrayList<SearchResult<Double>> points, double range) { double score = 0; for(int i = 0; i < points.size();i++) { SearchResult<Double> a = points.get(i); if(Math.abs(GF - a.payload) <= range) { score += 1/(1 + a.distance*a.distance); } } return score; } public void update(double eX,double eY,long time) { ListIterator<Wave> it = waves.listIterator(); while (it.hasNext()) { Wave currentWave = it.next(); if(currentWave.hit(time, eX, eY)) { Status conditions = currentWave.getStatus(); double GF = currentWave.guessFactor(eX, eY); if(shots > 10) { //council.inform(ASLocation(conditions), GF); //council.onFreeTick(); } subTreeAR.addPoint(ARLocation(conditions), new Double(GF)); subTreeAS.addPoint(ASLocation(conditions), new Double(GF)); GFLog.add(GF); double[] GFs = currentWave.lastGFs; GFLogGun.addPoint(GFs, GF); latestGF = GF; it.remove(); } } }

public double hitRate() { return ((double)hits)/shots; }

public double latestGF() { return latestGF; } private double[] ASLocation(Status situation) { double[] s = situation.segments(); double[] a = Arrays.copyOf(s, segCount); a[4] = Math.pow((sdecay+shots), ASE); return a; } private double[] ARLocation(Status situation) { double[] s = situation.segments(); double[] a = Arrays.copyOf(s, segCount-1); return a; }

private double[] location(Status situation) { double[] s = situation.segments(); double[] a = Arrays.copyOf(s, segCount); a[4] = shots; return a; } public void onBulletHit(BulletHitEvent e, long time) { hits++; sdecay += decay; int farthestWave = 0; if(waves.size() > 0) { double distance = 0; for(int i = 0; i < waves.size();i++) { distance = Math.max(waves.get(i).getDistance((int)time),distance); if(distance == waves.get(i).getDistance((int)time)) farthestWave = i; } } Bullet b = e.getBullet(); double x = b.getX(),y = b.getY(); Wave w = waves.get(farthestWave); Status s = w.getStatus(); double GF = w.guessFactor(x, y); hitLog.addPoint(location(s), GF); } private double distance(double x1,double y1, double x2, double y2) {

return Math.sqrt(Math.pow(x1-x2,2)+Math.pow(y1-y2, 2)); } public void onPaint(Graphics g, long time) { for(int i = 0; i < waves.size();i++) { waves.get(i).draw(g, time); }

} public void onRoundEnd() { //waves.clear();

} public void run() { System.out.println("Weights: " + Arrays.toString(subTreeAS.weights)); waves.clear(); } private class WhiteCouncil { private Queue<Info> queue = new LinkedList<>(); private double[] multipliers = new double[10];

private Ent<Double> tree; public WhiteCouncil(Ent<Double> tree) { this.tree = tree; Arrays.fill(multipliers, 1.0); } public void inform(double[] location,double correctGF) { queue.add(new Info(location,correctGF)); } public void onFreeTick() { Info i = queue.poll(); if(i != null) { double[] weights = Arrays.copyOf(tree.weights,tree.weights.length); double[] location = i.location; double GF = i.correctGF; double bscore = score(location,GF); double multiplier = 1; for(double d = .9; d <= 1.1; d += .02) { tree.adjustWeight(4, d); double score = score(location,GF); bscore = Math.min(bscore,score);

if ( bscore == score) { multiplier = d; }

tree.setWeight(4, weights[4]); } addMultiplier(multiplier); applyMultipliers(); } } private void addMultiplier(double multiplier) { for(int i = multipliers.length-1; i > 0;i--) { multipliers[i] = multipliers[i - 1]; } multipliers[0] = multiplier; } private void applyMultipliers() { double sum = 0; for(int i = 0; i < multipliers.length;i++) { sum += multipliers[i]; } sum /= multipliers.length; tree.adjustWeight(4, sum); } private double score(double[] location, double correctGF) { double GF = GF(location,tree); return Math.abs(correctGF-GF);

} private class Info { public double[] location; public double correctGF; Info(double[] l, double GF) { location = l; correctGF = GF; } } }

} <syntaxhighlight> Here is the modified kD-Tree:

<syntaxhighlight> /*

• • KDTree.java by Julian Kent
  • Licenced under the Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License
  • See full licencing details here: http://creativecommons.org/licenses/by-nc-sa/3.0/
  • For additional licencing rights please contact jkflying@gmail.com
• /

package straw; import java.util.ArrayList; import java.util.Arrays;

public abstract class KDTree<T>{

//use a big bucketSize so that we have less node bounds (for more cache hits) and better splits

  private static final int  _bucketSize = 50;

  private final int _dimensions;
  private int _nodes;   
  private final Node root;
  private final ArrayList<Node> nodeList = new ArrayList<Node>();

  //prevent GC from having to collect _bucketSize*dimensions*8 bytes each time a leaf splits
  private double[] mem_recycle;

  //the starting values for bounding boxes, for easy access
  private final double[] bounds_template;

  //one big self-expanding array to keep all the node bounding boxes so that they stay in cache
  // node bounds available at:
  //low:  2 * _dimensions * node.index + 2 * dim
  //high: 2 * _dimensions * node.index + 2 * dim + 1
  private final ContiguousDoubleArrayList nodeMinMaxBounds;

  private KDTree(int dimensions){
     _dimensions = dimensions;

  //initialise this big so that it ends up in 'old' memory
     nodeMinMaxBounds = new ContiguousDoubleArrayList(512 * 1024 / 8 + 2*_dimensions);
     mem_recycle = new double[_bucketSize*dimensions];

     bounds_template = new double[2*_dimensions];
     Arrays.fill(bounds_template,Double.NEGATIVE_INFINITY);
     for(int i = 0, max = 2*_dimensions; i < max; i+=2)
        bounds_template[i] = Double.POSITIVE_INFINITY;

  //and.... start!
     root = new Node();
  }
  public int nodes(){
     return _nodes;
  }
  public int size(){
     return root.entries;
  }
  public int addPoint(double[] location, T payload){

     Node addNode = root;
  //Do a Depth First Search to find the Node where 'location' should be stored
     while(addNode.pointLocations == null){
        addNode.expandBounds(location);
        if(location[addNode.splitDim] < addNode.splitVal)
           addNode = nodeList.get(addNode.lessIndex);
        else
           addNode = nodeList.get(addNode.moreIndex);
     }
     addNode.expandBounds(location);

     int nodeSize = addNode.add(location,payload);

     if(nodeSize % _bucketSize == 0)
     //try splitting again once every time the node passes a _bucketSize multiple
     //in case it is full of points of the same location and won't split
        addNode.split();

     return root.entries;
  }


  public ArrayList<SearchResult<T>> nearestNeighbours(double[] searchLocation, int K){
     IntStack stack = new IntStack();
     PrioQueue<T> results = new PrioQueue<T>(K,true);

     stack.push(root.index);

     int added = 0;

     while(stack.size() > 0 ){
        int nodeIndex = stack.pop();
        if(added < K || results.peekPrio() > pointRectDist(nodeIndex,searchLocation)){
           Node node = nodeList.get(nodeIndex);
           if(node.pointLocations == null)
              node.search(searchLocation,stack);
           else
              added += node.search(searchLocation,results);
        }
     }

     ArrayList<SearchResult<T>> returnResults = new ArrayList<SearchResult<T>>(K);
     double[] priorities = results.priorities;
     Object[] elements = results.elements;
     for(int i = 0; i < K; i++){//forward (closest first)
        SearchResult s = new SearchResult(priorities[i],(T)elements[i]);
        returnResults.add(s);
     }
     return returnResults;
  }

  public ArrayList<T> ballSearch(double[] searchLocation, double radius){
     IntStack stack = new IntStack();
     ArrayList<T> results = new ArrayList<T>();

     stack.push(root.index);

     while(stack.size() > 0 ){
        int nodeIndex = stack.pop();
        if(radius > pointRectDist(nodeIndex, searchLocation)){
           Node node = nodeList.get(nodeIndex);
           if(node.pointLocations == null)
              stack.push(node.moreIndex).push(node.lessIndex);
           else
              node.searchBall(searchLocation, radius, results);
        }
     }
     return results;
  }
  public ArrayList<T> rectSearch(double[] mins, double[] maxs){
     IntStack stack = new IntStack();
     ArrayList<T> results = new ArrayList<T>();

     stack.push(root.index);

     while(stack.size() > 0 ){
        int nodeIndex = stack.pop();
        if(overlaps(mins,maxs,nodeIndex)){
           Node node = nodeList.get(nodeIndex);
           if(node.pointLocations == null)
              stack.push(node.moreIndex).push(node.lessIndex);
           else
              node.searchRect(mins, maxs, results);
        }
     }
     return results;

  }


  abstract double pointRectDist(int offset, final double[] location);
  abstract double pointDist(double[] arr, double[] location, int index);

  boolean contains(double[] arr, double[] mins, double[] maxs, int index){

     int offset = (index+1)*mins.length;

     for(int i = mins.length; i-- > 0 ;){
        double d = arr[--offset];
        if(mins[i] > d | d > maxs[i])
           return false;
     }
     return true;
  }

  boolean overlaps(double[] mins, double[] maxs, int offset){
     offset *= (2*maxs.length);
     final double[] array = nodeMinMaxBounds.array;
     for(int i = 0; i < maxs.length; i++,offset += 2){
        double bmin = array[offset], bmax = array[offset+1];
        if(mins[i] > bmax | maxs[i] < bmin)
           return false;
     }

     return true;
  }


  public static class Euclidean<T> extends KDTree<T>{
     public Euclidean(int dims){
        super(dims);
     }
     double pointRectDist(int offset, final double[] location){
        offset *= (2*super._dimensions);
        double distance=0;
        final double[] array = super.nodeMinMaxBounds.array;
        for(int i = 0; i < location.length; i++,offset += 2){

           double diff = 0;
           double bv = array[offset];
           double lv = location[i];
           if(bv > lv)
              diff = bv-lv;
           else{
              bv=array[offset+1];
              if(lv>bv)
                 diff = lv-bv;
           }
           distance += sqr(diff);
        }
        return distance;
     }
     double pointDist(double[] arr, double[] location, int index){
        double distance = 0;
        int offset = (index+1)*super._dimensions;

        for(int i = super._dimensions; i-- > 0 ;){
           distance += sqr(arr[--offset] - location[i]);
        }
        return distance;
     }

  }
  public static class Manhattan<T> extends KDTree<T>{
     public Manhattan(int dims){
        super(dims);
     }
     double pointRectDist(int offset, final double[] location){
        offset *= (2*super._dimensions);
        double distance=0;
        final double[] array = super.nodeMinMaxBounds.array;
        for(int i = 0; i < location.length; i++,offset += 2){

           double diff = 0;
           double bv = array[offset];
           double lv = location[i];
           if(bv > lv)
              diff = bv-lv;
           else{
              bv=array[offset+1];
              if(lv>bv)
                 diff = lv-bv;
           }
           distance += (diff);
        }
        return distance;
     }
     double pointDist(double[] arr, double[] location, int index){
        double distance = 0;
        int offset = (index+1)*super._dimensions;

        for(int i = super._dimensions; i-- > 0 ;){
           distance += Math.abs(arr[--offset] - location[i]);
        }
        return distance;
     }
  }
  public static class Ent<T> extends KDTree<T>
  {

public double[] weights; public Ent(int dims, double[] weights){ super(dims); this.weights = Arrays.copyOf(weights, dims); } public void setWeights(double[] newWeights) { weights = newWeights; } public void adjustWeight(int dimension, double multiplier) { weights[dimension] *= multiplier; } public void setWeight(int dimension, double value) { weights[dimension] = value; } double pointRectDist(int offset, final double[] location){ offset *= (2*super._dimensions); double distance=0; final double[] array = super.nodeMinMaxBounds.array; for(int i = 0; i < location.length; i++,offset += 2){

double diff = 0; double bv = array[offset]; double lv = location[i]; if(bv > lv) diff = bv-lv; else{ bv=array[offset+1]; if(lv>bv) diff = lv-bv; } distance += (diff)*weights[i]; } return distance; } double pointDist(double[] arr, double[] location, int index){ double distance = 0; int offset = (index+1)*super._dimensions;

for(int i = super._dimensions; i-- > 0 ;){ distance += Math.abs(arr[--offset] - location[i])*weights[i]; } return distance; } }

    //NB! This Priority Queue keeps things with the LOWEST priority. 

//If you want highest priority items kept, negate your values

  private static class PrioQueue{

     Object[] elements;
     double[] priorities;
     private double minPrio;
     private int size;

     PrioQueue(int size, boolean prefill){
        elements = new Object[size];
        priorities = new double[size];
        Arrays.fill(priorities,Double.POSITIVE_INFINITY);
        if(prefill){
           minPrio = Double.POSITIVE_INFINITY;
           this.size = size;
        }
     }
      //uses O(log(n)) comparisons and one big shift of size O(N)
      //and is MUCH simpler than a heap --> faster on small sets, faster JIT

     void addNoGrow(S value, double priority){
        int index = searchFor(priority);
        int nextIndex = index + 1;
        int length = size - index - 1;
        System.arraycopy(elements,index,elements,nextIndex,length);
        System.arraycopy(priorities,index,priorities,nextIndex,length);
        elements[index]=value;
        priorities[index]=priority;

        minPrio = priorities[size-1];
     }

     int searchFor(double priority){
        int i = size-1;
        int j = 0;   
        while(i>=j){
           int index = (i+j)>>>1;
           if( priorities[index] < priority)
              j = index+1;
           else 
              i = index-1;
        }
        return j;
     }
     double peekPrio(){
        return minPrio;
     }
  }

  public static class SearchResult{
     public double distance;
     public S payload;
     SearchResult(double dist, S load){
        distance = dist;
        payload = load;
     }
  }

  private class Node {

  //for accessing bounding box data 
  // - if trees weren't so unbalanced might be better to use an implicit heap?
     int index;

  //keep track of size of subtree
     int entries;

  //leaf
     ContiguousDoubleArrayList pointLocations ;
     ArrayList<T> pointPayloads = new ArrayList<T>(_bucketSize);

  //stem
     //Node less, more;
     int lessIndex, moreIndex;
     int splitDim;
     double splitVal;

     Node(){
        this(new double[_bucketSize*_dimensions]);
     }
     Node(double[] pointMemory){
        pointLocations = new ContiguousDoubleArrayList(pointMemory);
        index = _nodes++;
        nodeList.add(this);
        nodeMinMaxBounds.add(bounds_template);
     }


     //returns number of points added to results
     void search(double[] searchLocation, IntStack stack){
        if(searchLocation[splitDim] < splitVal)
           stack.push(moreIndex).push(lessIndex);//less will be popped first
        else
           stack.push(lessIndex).push(moreIndex);//more will be popped first
     }
     int search(double[] searchLocation, PrioQueue<T> results){
        int updated = 0;
        for(int j = entries; j-- > 0;){
           double distance = pointDist(pointLocations.array,searchLocation,j);
           if(results.peekPrio() > distance){
              updated++;
              results.addNoGrow(pointPayloads.get(j),distance);
           }
        }
        return updated;
     }

     void searchBall(double[] searchLocation, double radius, ArrayList<T> results){

        for(int j = entries; j-- > 0;){
           double distance = pointDist(pointLocations.array,searchLocation,j);
           if(radius >= distance){
              results.add(pointPayloads.get(j));
           }
        }
     }

     void searchRect(double[] mins, double[] maxs, ArrayList<T> results){

        for(int j = entries; j-- > 0;)
           if(contains(pointLocations.array,mins,maxs,j))
              results.add(pointPayloads.get(j));

     }   

     void expandBounds(double[] location){
        entries++;
        int mio = index*2*_dimensions;
        for(int i = 0; i < _dimensions;i++){
           nodeMinMaxBounds.array[mio] = Math.min(nodeMinMaxBounds.array[mio++],location[i]);
           nodeMinMaxBounds.array[mio] = Math.max(nodeMinMaxBounds.array[mio++],location[i]);
        }
     }

     int add(double[] location, T load){
        pointLocations.add(location);
        pointPayloads.add(load);
        return entries;
     }
     void split(){
        int offset = index*2*_dimensions;

        double diff = 0;
        for(int i = 0; i < _dimensions; i++){
           double min = nodeMinMaxBounds.array[offset];
           double max = nodeMinMaxBounds.array[offset+1];
           if(max-min>diff){
              double mean = 0;
              for(int j = 0; j < entries; j++)
                 mean += pointLocations.array[i+_dimensions*j];

              mean = mean/entries;
              double varianceSum = 0;

              for(int j = 0; j < entries; j++)
                 varianceSum += sqr(mean-pointLocations.array[i+_dimensions*j]);

              if(varianceSum>diff*entries){
                 diff = varianceSum/entries;
                 splitVal = mean;

                 splitDim = i;
              }
           }
           offset += 2;
        }

        //kill all the nasties
        if(splitVal == Double.POSITIVE_INFINITY)
           splitVal = Double.MAX_VALUE;
        else if(splitVal == Double.NEGATIVE_INFINITY)
           splitVal = Double.MIN_VALUE;
        else if(splitVal == nodeMinMaxBounds.array[index*2*_dimensions + 2*splitDim + 1])
           splitVal = nodeMinMaxBounds.array[index*2*_dimensions + 2*splitDim];   

        Node less = new Node(mem_recycle);//recycle that memory!
        Node more = new Node();
        lessIndex = less.index;
        moreIndex = more.index;

        //reduce garbage by factor of _bucketSize by recycling this array
        double[] pointLocation = new double[_dimensions];
        for(int i = 0; i < entries; i++){
           System.arraycopy(pointLocations.array,i*_dimensions,pointLocation,0,_dimensions);
           T load = pointPayloads.get(i);

           if(pointLocation[splitDim] < splitVal){
              less.expandBounds(pointLocation);
              less.add(pointLocation,load);
           }
           else{
              more.expandBounds(pointLocation);   
              more.add(pointLocation,load);
           }
        }
        if(less.entries*more.entries == 0){
        //one of them was 0, so the split was worthless. throw it away.
           _nodes -= 2;//recall that bounds memory
           nodeList.remove(moreIndex);
           nodeList.remove(lessIndex);
        }
        else{

        //we won't be needing that now, so keep it for the next split to reduce garbage
           mem_recycle = pointLocations.array;

           pointLocations = null;

           pointPayloads.clear();
           pointPayloads = null;
        }
     }

  }


  private static class ContiguousDoubleArrayList{
     double[] array;
     int size;
     ContiguousDoubleArrayList(){this(300);}
     ContiguousDoubleArrayList(int size){this(new double[size]);}
     ContiguousDoubleArrayList(double[] data){array = data;}

     ContiguousDoubleArrayList add(double[] da){
        if(size + da.length > array.length)
           array = Arrays.copyOf(array,(array.length+da.length)*2);

        System.arraycopy(da,0,array,size,da.length);
        size += da.length;
        return this;
     }
  }
  private static class IntStack{
     int[] array;
     int size;
     IntStack(){this(64);}
     IntStack(int size){this(new int[size]);}
     IntStack(int[] data){array = data;}

     IntStack push(int i){
        if(size>= array.length)
           array = Arrays.copyOf(array,(array.length+1)*2);

        array[size++] = i;
        return this;
     }
     int pop(){
        return array[--size];
     }
     int size(){
        return size;
     }
  }

  static final double sqr(double d){
     return d*d;}

}

<syntaxhighlight> If you have questions about the classes used by the Narya class or how it is used by the robot, ill post that code too.