# Chase-san/PatternBot

Robo Home | Chase-san | Changes | Preferences | AllPages

```package chase.pm;

import robocode.*;
import java.awt.Color;
import java.awt.Graphics2D;
import java.awt.geom.Point2D;
import java.awt.geom.Rectangle2D;
import java.util.ArrayList;

import static java.lang.Math.*;
import static robocode.util.Utils.*;

/**
* A simple demonstration of a one on one
* pattern matching robot.
*
* @author Chase
*/
public class PatternBot extends AdvancedRobot {
//the deepest backward trace to determine the best match
private static final int MAX_MATCH_LENGTH = 500;
//Limit the size of the pattern, so that it doesn't get to slow
private static final int MAX_PATTERN_LENGTH = 100000;
//the maximum angle difference between heading delta's to be considered a match
private static final double MAX_ANGLE_DIFF = PI/128; //== 1.40625 degrees
//the maximum velocity difference between velocity delta's to be considered a match
private static final double MAX_VELOCITY_DIFF = .25;
private static int patternLength = 0;
private static Rectangle2D.Double battlefield;
private Point2D.Double nextPredicted;
private ArrayList<Point2D.Double> bestList;

public void run() {
//adjust for all the turns, by way of hierarchy

//some nice flamy red colors
setColors(Color.red, Color.red, Color.red);

//Add a break to the pattern, so that we don't
//track patterns that never happened
lastVelocity = 100;

//setup the battlefield for later
if(battlefield == null) {
battlefield = new Rectangle2D.Double(17,17,
getBattleFieldWidth()-34,
getBattleFieldHeight()-34);
}

do {
} while(true);
}

public void onScannedRobot(ScannedRobotEvent e) {
//This is the direct angle to the enemy

if(getEnergy() < 0.09) return;

//since this is one on one robot, reset the radar
//we do this first as the lag may cause the robot
//to skip a turn, this way we don't have broken scans

double arcToScan = atan(36.0 / e.getDistance());

//Initialize some more variable
double eVelocity = e.getVelocity();
double eDistance = e.getDistance();
Point2D.Double myLocation = new Point2D.Double(getX(), getY());
Point2D.Double eLocation = project(myLocation,eAbsoluteBearing,eDistance);

if(lastVelocity == 100) {
lastVelocity = eVelocity;
return;
}

//record the latest data into the pattern

//check and eliminate extra states over the limit
while(patternLength > MAX_PATTERN_LENGTH) pruneTail();

//update the last heading and velocity
lastVelocity = eVelocity;

//check to see if we need to fire this tick
if (getGunHeat()/getGunCoolingRate() < 5 && patternLength > 3) {
//determine the bullet power and speed
double bulletPower = 3;
double bulletSpeed = 20-3*bulletPower;

//now for the meat of the gun, we scan from the head
State state = head.reverse.reverse; //atleast 2 back
int deepestDepth = 2; //to save time
Point2D.Double predictedLocation = null;
while(state.reverse != null) {
State state2 = state.reverse;
int depth = 1; //could be 0 aswell
//check to see if the state is a match for the current state
while(matchState(state2,recent) && depth <= MAX_MATCH_LENGTH
&& !state2.isBreak && !recent.isBreak) {
depth++;
state2 = state2.reverse;
recent = recent.reverse;
}
//now play it forward to determine where to aim, but
//only if the depth was deeper then the deepest
if(depth > deepestDepth) {
state2 = state.forward;
Point2D.Double predict = eLocation;
int predictTime = -1;
double velocity = eVelocity;
ArrayList<Point2D.Double> list = new ArrayList<Point2D.Double>();
while(battlefield.contains(predict)
&& predictTime++ < predict.distance(myLocation)/bulletSpeed
&& state2 != null && !state2.isBreak) {
velocity = max(-8, min(8,velocity + state2.velocityDelta));
state2 = state2.forward;
}
if(battlefield.contains(predict)
&& predictTime > predict.distance(myLocation)/bulletSpeed) {
bestList = list;
deepestDepth = depth;
predictedLocation = predict;
}
}
}
state = state.reverse;
}

nextPredicted = predictedLocation;

if(getGunTurnRemaining() < .5 &&
nextPredicted != null) setFire(bulletPower);

double aimAngle = eAbsoluteBearing;
if(predictedLocation != null)
aimAngle = absoluteAngle(myLocation, predictedLocation);
}

public void onPaint(Graphics2D g) {
g.setColor(Color.white);
if(bestList != null) {
Point2D.Double last = null;
for(int i=0;i<bestList.size();i++) {
Point2D.Double c = bestList.get(i);
if(last == null) {
g.setColor(Color.red);
g.fillOval((int)c.x-4, (int)c.y-4, 8, 8);
g.setColor(Color.white);
} else {
g.drawLine((int)last.x, (int)last.y, (int)c.x, (int)c.y);
}
last = c;
}
}
if(nextPredicted != null) {
g.drawString("Next Point: ("+(float)nextPredicted.x
+","+(float)nextPredicted.y+")", 0, 5);
g.setColor(Color.GREEN);
g.fillOval((int)nextPredicted.x-4,
(int)nextPredicted.y-4, 8, 8);
} else {
g.drawString("Next Point: null", 0, 5);
}
g.setColor(Color.white);
g.drawString("Pattern Length: " + patternLength, 0, 20);
}

public boolean matchState(State s1, State s2) {
if(s1 != null && s2 != null &&
&& abs(s1.velocityDelta - s2.velocityDelta) <= MAX_VELOCITY_DIFF) {
return true;
}
return false;
}

public void pruneTail() {
State temp = tail;
tail = tail.forward;
tail.reverse = null;
temp.forward = null;
patternLength--;
}

patternLength++;
State s = new State();
s.velocityDelta = velocity - lastVelocity;

}

patternLength++;
State s = new State();
s.isBreak = true;

} else {
}
}

if(tail == null) {
tail = tmp;
}
}

public static final Point2D.Double project(Point2D.Double l, double a, double d){
return new Point2D.Double(l.x + d*Math.sin(a), l.y + d*Math.cos(a));
}
public static final double absoluteAngle(Point2D source, Point2D target) {
return Math.atan2(target.getX() - source.getX(), target.getY() - source.getY());
}
}

//only in the same file for completeness
class State {
boolean isBreak;
State reverse, forward;

public State() {
isBreak = false;
}
}
```

I made this bot for three reasons, one to jumpstart my creation of a decent pattern matching robot (probably folding), to gain more advanced knowledge of the nicities surrounding pattern matcher design, and to make a very well commented base bot for people who do not yet understand pattern-matchers (like me) and wanna try to learn. While the comments are a little flaky (as am I), I post it here for the world (or atleast the other members of the wiki) to edit and allow correct all my horrible programming mistakes and shabby commenting (even though CommentsAreBad?).

I'll post some challenge scores for it in a bit. --Chase-san

Also if someone can tell me while it sometimes misses SpinBot when it aims at a left or right edge (relatively) of SpinBots? circle, that the bullets just misses as SpinBot drives away (dispite a hour of debugging I couldn't come up with a solution). --Chase-san

It sounds like it might be a 1-off problem. But to me your movement-rebuilding code seems horribly, and unnecessarily complex. Take a look in Waylander for a REALLY simple way to rebuild the movement. -- Skilgannon

What can I say, I haven't made many PatternMatchers, the rebuild step is based off foggy ememories of what I saw in early editions of chalk. But i'll take a look at waylander. --Chase-san
You must also remember this is not a symbolic or folded pattern matcher, this is one of the original kind that (I like to think, but not so nicely) and its supoose to be simple. While the point2d project is a tad more complex then yours, they two different styles do more or less the same thing, mine isn't fast, because its not suppose to be, it is complex, only because it is suppose to be simple. Overally I see no trick in yours that would easily translatable to the code above in the rebuild step, as they are both about the same in that. Thought it is true I am disabled, so if I missed something obvious in your code that would simplify this (and thats not symbolic or folded in nature), I would be glad to have it explained. --Chase-san

I just took a thorough look through your rebuilding code, and I can see the problem. Rather than seeing whether the bullet would have traveled as far as the enemy in that amount of time, you presume that the enemy will be at the same distance as they are currently, and then subtract from that. What this doesn't factor in is if the enemy is moving away or towards you, that this will change the bullet flight time. So rather than subtracting from bulletDistance, initialize it to zero, and add to it each time. When the distance from your current location to the predicted enemy location is smaller than the bulletDistance, then break the loop. Another point: it would probably be quicker to find the longest match, and only then rebuild the movement. Otherwise you will rebuild a movement every single time you find a longer match than you had before. -- Skilgannon

• However if you do that then there is no guarantee that the longest match can be rebuilt without a end game break or going off the field. Also I fixed the code to correct that problem, it now easily destroys SpinBot as it should. (most predictable pattern in existance, even hitting walls) --Chase-san

• What I would do is create an array of Match objects, and sort them by length. Then rebuild from longest to shortest, until you have one that stays in the field and doesn't go into another round. But I am a bit of a perfectionist with regard to implementations =) -- Skilgannon

• I think this way is a tad simpler in the way that its all togeather in one place, I was trying to make it simple as a start point. But it is still true I am new to pattern matchers, but to just see one work is amazing (this one especially as it maps out the path in the graphics) --Chase-san

• The only reason I say that is because speed is usually an issue for pattern matchers. Yep, that is pretty cool, isn't it =). Have you tried it in the PMC yet? -- Skilgannon

• Yah there you go, some results for yah, old fashioned pm gun. Nothing fancy, just what you see here. I updated the gun above to the configuration I used in the PMC, except for the bulletPower. I didn't skip a round during the whole PMC so I figure its pretty decent. --Chase-san

Robo Home | Chase-san | Changes | Preferences | AllPages