View source for 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.
- [View source↑]
- [History↑]
Contents
Thread title | Replies | Last modified |
---|---|---|
retry | 1 | 20:09, 22 December 2013 |
narya class | 3 | 14:44, 22 December 2013 |
open source dynamic clustering gun | 5 | 00:24, 22 December 2013 |
how is the narya class used by gandalf ,how does the narya class work ,how do the classes used by the narya class work ,how are the classes used by the narya class used for ,how are the classes used by the narya class used by gandalf
Narya is used as you might think by the method names. Update is called every tick with enemy X, Y, and the time. Fire is called whenever the bot fires a bullet. GF(Status) is called whenever a firing angle needed. Status contains info like lateral and advancing velocity, distance etc. Ent is a kD-Tree. Wave represents a bullet wave. I'm sure you can figure out how it works by looking at the code.
i'm sorry, but I really consider this series of questions rude. Please spend more time trying to find the answers to your own questions before posting them on the wiki. "How does your whole bot work" is not a meaningful question. Each time you ask a question, you're requesting that other people in the community take time to read your question and construct a helpful answer to your question. It's only fair that before you ask us to spend our time, you spend your own time trying to find the answer first. And hopefully by that point, you will be able to ask a more specific question so that we can give you a good answer that will help you out.
I agree. Please ask specific questions about specific parts of a robot if you want to know, but please try to avoid over generalized questions or opinion based questions.
Which means try to avoid questions like "which is better" or "how does class A, B, C/bot X work". Try to read the questions of other users to get a better idea of what is acceptable and what is not.
Basically any question that is very easy to answer, but isn't easy to figure out through a little work and is not asking for an opinion as fact, is acceptable.
Good: "Did Diamond at one time use Displacement Vectors in it's movement?"
- Shows you have done research, but don't want to review every version of Diamond ever made for the answer, plus it might have in development but never in a released version. The question is easy to answer, and the author might be willing to throw additional detail on the question. (p.s. Voidious, I am now interested, did it?)
- P.S. While this is a good question, it is not a template. Do not just go asking "Did X at one time use Y in it's Z."
Acceptable: "How does Diamond use Displacement Vectors? I can't get mine to work. I am currently doing X and Y."
- This is asking for specific details about the inner workings of Diamond. It may require a bit more work to answer, but we will be much more inclined to do so since not only is it obvious have you done research, but you are trying to implement it as well.
Bad: "Is Diamond a Wave Surfer?" or "What movement does Diamond use?"
- Shows you have done no research, aside from looking at the rankings table to find out it's name. Such answers are easy to find.
Ugly: "How does Diamond work?" or "Can you make a Understanding Diamond article?"
- This is horrible, this is asking the author or someone else who has a deep understanding of the robot to give you extensive details on it. This would include a great deal of writing and possible research by the answerer. The second is a little more acceptable, but pretty much amounts to the first thing. You would need a lot of built up 'respect' in the community for someone to go through that much work, and even then, they probably have better things to be doing.
Useless: "Which X is best?" or "Is X better than Y?"
- These most likely are asking for an opinion, opinions are great, but no useful information has been exchanged. Plus it leaves out vital information needed to answer the question. Best at what? Better at what? In what situations? Even if you had asked "Is a wave surfer better then a sandbox flattener at dodging the most bullets in the rumble?", there are still problems, since the answer is "It depends on the implementation." So one should just avoid asking these questions period.
P.S. Do not 'massively' alter questions after they have received replies. You can add to them, clean them up (spelling, grammar), or even rephrase them, but don't change them.
You do not have permission to edit this page, for the following reasons:
You can view and copy the source of this page.
Return to Thread:User talk:Straw/open source dynamic clustering gun.