[Home]MinimumRiskMovement

Robo Home | Changes | Preferences | AllPages

A very effective type of Melee movement that is not completely unlike AntiGravityMovement in implementation. The idea is to pick a series of points that you could go to next, and rate each one with a 'risk factor', then move to the lowest-risk location.

Some of the robots that use this basic system in melee, whether or not the authors call it that (correct me if I'm wrong, add some if you know of more):

Calculating the Risk Factor for a point/movement

For FloodHT, the system for this is somewhat like finding the magnitude of a force in an AntiGravityMovement system. For each enemy, I use a base risk of a certain point is energy/distance2. Other things I take into account for each enemy:

Other things I could add in the future: Other things I take into account aside from my enemies:

Picking points to try

It's important to pick a good range of practical places to go to for this to work well. Applying a force to the walls is unnecessary if you always just pick points within the battlefield. I believe that HawkOnFire picks several points around him in regular angular offsets at random distances. The next version of FloodHT will do this at least some of the time. Tron obviously picks 4 points, at pretty much uniform distance, up, down, left and right. He also avoids head-on aim like the plague. FloodHT 0.8 uses a divide-and-conquer sort of system. He divides the battlefield up into 16 rectangles, and rates each one based on the risk of its center point. If he's far away from that point, he goes to it, otherwise he splits that rectangle up into 16 more rectanges and rates them and goes to that point (or continues to subdivide until it just doesn't make a difference anymore). The dev version does this at the beginning of the battle to get situated and then starts picking points around him at a distance.


Comments / Questions

I have tried this but it's very hard to set the importance of each parameters. I used the following parameters :

I think setting the importance of each parameter could be a job for a genetic search. I read something about it that can be found here http://computing.dcu.ie/~humphrys/ in the abstract paper (not the whole thesis). The article is about action selection and each point can be considered as an action. I didn't implement the Genetic Algorithm as I had no simple idea on how to do it (how to build fitness... and if you must implements a robocode controller it's quite hard to do and take much time) but if you have one... --Synnalagma

I may try to put FloodHT's melee system into a Mini one of these times, and then it may help to see some code for it. I start with energy/distance2 for each enemy and then multiply it by constants if that robot has shot me recently, or if I would become the closest enemy to them... Then I add something divided by the distance to the center squared and the distance from me squared. Then I multiply by some function of distance from me to avoid picking points in an opposite corner. In the dev version of FloodHT, if I'm picking a point close to me (meaning that I'm as concerned about not getting hit as much as with getting to the best place), I also multiply the number for each enemy by the cosine of the difference of the angles or something like that, which seems to get me oscillating laterally to the closest/most dangerous enemies. -- Kawigi

Just some though : The problem with this is that in some case you don't really choose between action : imagine a bot that has two task putting out fire and collecting trash there's a fire in the north east and a trash in the south west maybe with this you'll go to north-west or south-east since it maximise your function but this it's not a choice. It's better to go to the fire and then to the trash (or inverse). So I though about that imagine each parameter is an agent rating each action then you choose to execute the agent that will suffer the most if it is not choosen. suffering is BestAction? - currentAction so there a place for opportunism and you really make a choice. main idea found on the article cited. --Synnalagma

So are you thinking of something like a maximum-benefit thing rather than minimum risk? -- Kawigi

Suffering selection

I think maximum-benefit is very close to minimum risk in this case. I gave an exemple with maximum-benefit because it was the way I implemented it. But the things goes exactly the same way. No I was thinking on another way to select the best action (or point) to take. If you sum every benefit and/or risk you take an average action or a compromise one. I don't think this is good, it could be in one case I explain later. The idea was this :

Each parameter can be regarded as a subtask of the movement. You can also call it an agent. This agent can tell us wich action would be the best in a particular case. This agent only observe a part of the current state (by state I mean description of the current situation). P. ex. if we know that there's a Bullet in the north direction and the agent only sens bullet it can tell us that we must go to south. Maybe if the agent sens bullet position and bullet heading it can tell us we must go to the west.

Now we have this agent. This agent can rate each action by telling us if it's a good or a bad action in their way. An agent percepting the distance to the other bot can't tell us about lateral angle or anything else.

What you are doing here is to sum the rating of each agent for each action and maximize (or minimize) this function. But in this case you may choose an action that no agent would have choose as the best one and take a compromize action. take a look at that, it's a bot that must collect trash and put out fire :

     a     b     c     d     e
  |-----|-----|-----|-----|-----|
1 |  F  |     |     |     |  T  |    F = fire T = trash B = Bot
  |-----|-----|-----|-----|-----|
3 |     |     |     |     |     |
  |-----|-----|-----|-----|-----|
4 |     |     |  B  |     |     |
  |-----|-----|-----|-----|-----|

We have two agent one percepting trash and the other one percepting fire. If we make the sum there's a lot of chance that we go to direction of c1 since the fire agent find this action not so bad and the same for the trash agent(since we are going closer. But it would be better to go to a1 or e1 directly and then to the other one. This situation appear because the 2 agent enter in competition here. Picking up the sum you take a compromise. So the sum can be successfull if you have agent going in the same way.

An another way to choose the action to execute is to compute the suffering of this agent if it's not choosen. the suffering is computed this way take the difference of the bettest action for this agent and the value for it's current action. Then you choose the action of the agent wich will have the biggest suffering if it's not executed. In this case you choose a real action as it's one proposed by one of the agent. Here going to fire or trash before. There's also a place for opportunism since an agent could not really suffer by not be executed.

Hope that was understandable but i've got a poor english. --Synnalagma

I'm trying to implement something like this right now. How can you tell if a bot fires on you?-Andrew

In melee? GlowBlowMelee nows it when he gets hit:). I just mean that you can't really now it before if you turn your radar all the time (because you have to compare the energy-difference between two ticks to now that the other bot is firing). But in some situations you can do it like in a OneOnOne battle if an other bot is very close (in this case you can also be pretty sure that he is shooting in your direction). -- rozu

Even if you lock your radar on a particular enemy, you won't know when he fires because the energy drop can come from another bot's bullet hitting him. Maybe a statistical algorithm could calculate the probability of a bot firing each tick, but I don't know if that info would be of much use... A melee battle is packed with bullets flying all over, a good movement is one that looks like it is dodging them as if it would know where they are. :) -- ABC

Though the energy drop from a bullet hit is often larger than 3. -- PEZ

If the bullet hitting the target is power between .1 and .75 inclusive it'll be in the range where it can be mistaken for a shot, otherwise it won't be. On the plus side, bullets this weak are kind of rare, and in OneOnOne you can know for sure if there are any bullets this weak in the air (at least ones that can hit your target) since they would've had to come from you. In melee you're probably better off not trying to dodge too much or you'll find yourself quickly ruling out all the possible directions of movement (if you assume every bot is firing at you you'll get to try to dodge all the 20-30 bullets that are in the air at any one time). -- Kuuran

Can you tell me if this finds the angle i should turn to get to point (destinationx,destinationy)? I came up with: setTurnRightRadians?(Math.PI/2-Math.atan((destinationy-getY())/(getX()-destinationx))); --Andrew

I think it's setTurnRightRadians?(robocode.util.Utils.normalRelativeAngle(Math.atan2(destinationx-getX(), destinationy-getY())-getHeadingRadians())); that you're looking for. Of course, if the turn is more than 90 degrees, it makes sense to adjust it by 180 degrees and go backward. -- Kawigi

this seems to vaguely work. but not be accurate enough. i am using it to go to a destination point i choose --andrew

You need to continiously (every tick or so) do it to actually arrive at the destination point. Look at GoToBot for some more code and discussion on the subject. -- PEZ

thanks. what exactly is atan2 though? --andrew

atan2() returns the base angle of a triangle with the sides X and Y. It could be used as a way to find out the absolute bearing between two points. You could use plain atan() for this too, but you'll have to account for the sign of the Y distance yourself then. -- PEZ

Just beware that the sintaxe is: atan2(Y,X), and not X,Y as usual... I'm saying that because i've got myself trapped in that a lot of times... -- Axe

you mean the other way around--andrew

The syntax is Math.atan2(Y, X) unless you're dealing with robocode. -- Kuuran

=) Looks like Axe trapped himself over again! Because of this peculiarity of ClockMath I recommend you to implement these two functions in all your bots.

    static double absoluteBearing(Point2D source, Point2D target) {
        return Math.atan2(target.getX() - source.getX(), target.getY() - source.getY());
    }

    static Point2D vectorToLocation(Point2D sourceLocation, double angle, double length) {
        return new Point2D.Double(sourceLocation.getX() + Math.sin(angle) * length,
            sourceLocation.getY() + Math.cos(angle) * length);
    }
Look in the source of any of my bots to see how they're used. The second function is ill named, but I have never figured out what the name should be. =)

-- PEZ

Coriantumr calls the latter function projectPoint() - projects a point starting from sourceLocation, length pixels in the direction of angle. -- Kawigi

Yes, that's better. Maybe

static Point2D project(Point2D sourceLocation, double angle, double length)
is a good signature. -- PEZ

can someone help me come up with a way to move sinusoidaly to a point. so instead of moving in a strait line in a point it osscilates to it. this math is to complicated for me --andrew

I guess the easiest way is to face the point, and then do this:

setAhead(Double.POSITIVE_INFINITY); turnLeft(30); while (!nearDestination()) {

  turnRight(60);
  turnLeft(60);
} stop();

You will need to write some code to work out when you have passed the destination point (prehaps something along the lines of the desitination being between your starting point and your current point), but it should work ok. -- Tango

Is this Even implantmentable into a Normal Robot? - Error

In theory: yes, but I don't think it would be as effective as an EAR bot --UnderDark

import robocode.*;
import robocode.util.Utils;
import java.awt.Color;
import java.util.Hashtable;
import java.util.Enumeration;
import java.awt.geom.*;

/** Smash - a robot by Starrynte
*/

public class Smash extends AdvancedRobot
{
	static Hashtable enemies = new Hashtable();
	static Enemy target;
	static Point2D.Double nextDestination;
	static Point2D.Double lastPosition;
	static Rectangle2D.Double field;
	static double myEnergy;	
	static double myX;
	static double myY;
	static double timeSinceLastScan=0;	

	public void run()
	{
		field=new Rectangle2D.Double(36,36,getBattleFieldWidth()-72,getBattleFieldHeight()-72);
		nextDestination=lastPosition=new Point2D.Double(getX(),getY());
		target=new Enemy();
		setAdjustGunForRobotTurn(true);
		setAdjustRadarForGunTurn(true);
		while(true){
			doMovement();
			doGunning();
			doRadar();
			myEnergy=getEnergy();
			myX=getX();
			myY=getY();
			timeSinceLastScan++;
			execute();
		}	
	}
	public void onScannedRobot(ScannedRobotEvent e){
		Enemy en=(Enemy)enemies.get(e.getName());
		if(en==null){
			en=new Enemy();
			enemies.put(e.getName(),en);
		}
		en.energy=e.getEnergy();
		en.live=true;
		double x=myX + Math.sin(e.getBearingRadians()+getHeadingRadians())*e.getDistance();
		double y=myY + Math.cos(e.getBearingRadians()+getHeadingRadians())*e.getDistance();
		en.location=new Point2D.Double(x,y);
		en.distance=e.getDistance();
		en.velocity=e.getVelocity();
		en.heading=e.getHeadingRadians();
		en.bearing=e.getBearingRadians();
		en.name=e.getName();
		if(!target.live || (en.distance<target.distance*0.8 && en.energy<=target.energy*1.1) || (en.energy<target.energy*0.8 && en.distance<=target.distance*1.15)){
			target=en;
		}
		if(target.name.equals(e.getName())){
			timeSinceLastScan=0;
		}
	}
	public void onRobotDeath(RobotDeathEvent e) {
		Enemy en=(Enemy)enemies.get(e.getName());
		if(en!=null){
			en.live=false;
		}
	}
	public void onHitRobot(HitRobotEvent e){
		Enemy en=(Enemy)enemies.get(e.getName());
		if(en==null){
			en=new Enemy();
			enemies.put(e.getName(),en);
		}
		en.energy=e.getEnergy();
		en.live=true;
		en.bearing=e.getBearingRadians();
		en.name=e.getName();
		target=en;
		setTurnGunRightRadians(en.bearing+getHeadingRadians()-getGunHeadingRadians());
		setFire(3);
	}
	void doMovement(){
		for(int i=0;i<250;i++){
			if(target!=null){
				double ang=2*Math.PI*Math.random();
				double dist=150+250*Math.random();
				double testX=myX+Math.sin(ang)*dist;
				double testY=myY+Math.cos(ang)*dist;
				if(field.contains(testX,testY)){
					if(evaluate(new Point2D.Double(testX,testY))<evaluate(nextDestination)){
						nextDestination.setLocation(testX,testY);
					}
				}
			}
		}
		double ang=calcAngle(new Point2D.Double(myX,myY),nextDestination)-getHeadingRadians();
		double dist=nextDestination.distance(myX,myY);
		setTurnRightRadians(Utils.normalRelativeAngle(ang));
		setAhead(dist);
		setMaxVelocity((Math.abs(Utils.normalRelativeAngle(ang))>1) ? 2.25 : 8);
	}
	void doGunning(){
		if(getGunTurnRemainingRadians()<0.01){
			setTurnGunRightRadians(Utils.normalRelativeAngle(target.bearing+getHeadingRadians()-getGunHeadingRadians()));
			
		}
		if(getGunHeat()==0 && getEnergy()>5){
			double firePower=Math.min(Math.min(myEnergy/10,1300/target.distance),target.energy/4);			
			setFire(firePower);
		}
	}
	void doRadar(){
		if(timeSinceLastScan<10 && getOthers()==1){
			setTurnRadarRightRadians(Utils.normalRelativeAngle(target.bearing+getHeadingRadians()-getRadarHeadingRadians())*2);
		}else{
			setTurnRadarRightRadians(Double.POSITIVE_INFINITY);
		}
	}
	double evaluate(Point2D.Double destination){
		double risk=0;
		Enumeration e=enemies.elements();
		while(e.hasMoreElements()){
			Enemy en=(Enemy)e.nextElement();
			if(en.live){
				double eratio=Math.min((en.energy*2)/myEnergy,2.5);
				double perp=Math.abs(Math.cos(calcAngle(destination,new Point2D.Double(myX,myY))-calcAngle(destination,en.location)));
				risk+=(eratio*(1+perp))/destination.distance(en.location);
			}
		}
		return risk;
	}
	double calcAngle(Point2D.Double s,Point2D.Double t){
		return Math.atan2(t.getX()-s.getX(),t.getY()-s.getY());
	}
	class Enemy{
		boolean live;
		Point2D.Double location;
		double energy;
		double distance;
		double velocity;
		double heading;
		double bearing;
		String name;
	}
}
The robot doesn't seem to "recognize" that setAdjustGunForRobotTurn(true); is there and setAdjustRadarForGunTurn(true); is there either. The firepower is also strange. (Try it in a battle with sittingduck). But if i comment out the "doGunning()" it does seem to adjust the gun. Does anyone know why? --Starrynte

Why don't you think it recognizes those commands? When I run this tank, it looks pretty clear to me that the radar stays focused on the enemy independent of the tank's movement, and the gun doesn't turn with the tank or the radar. Are you seeing something different, or what did you think those commands should do? Also, what is it about the fire power that seems strange? I ran it against SittingDuck, and the fire power seemed right, generally the 1300 / distance being the minimum in that expression. Note that fire power maxes out at 3.0, so it will be 3.0 if you set it to more than that. -- Voidious

The problem isn't with the setAdjust() commands. You're not taking into accout that the bearing to the enemy changes as your robot's position changes. This means target.bearing won't be accurate because your bot will be using the bearing from when it last scanned the target instead the real one. A simple fix would be changing the doGunning() method to:

if(target.location != null){
	double absoluteBearing = Math.atan2(target.location.getX() - getX(), target.location.getY() - getY());
	setTurnGunRightRadians(Utils.normalRelativeAngle(absoluteBearing - getGunHeadingRadians()));
	if(getGunHeat() == 0 && getEnergy() > 5){
		double firePower=Math.min(Math.min(myEnergy/10, 1300/target.distance), target.energy/4);			
		setFire(firePower);
	}
}

I hope this helps -- Kev

That is the problem. Thnx! --Starrynte

void doMeleeMovement(){
		if(nextDestination.distanceSq(myX,myY)<1000 || (target.distance<70 && (target.energy>0.5 || myEnergy<=0.6))){
			for(int i=0;i<250;i++){
				double ang=(2*Math.PI)*Math.random();
				double dist=Math.min((closestEn==null ? 10000:closestEn.distance*0.7),100+200*Math.random());
				double testX=myX+Math.sin(ang)*dist;
				double testY=myY+Math.cos(ang)*dist;
				if(field.contains(testX,testY)){
					if(evaluate(new Point2D.Double(testX,testY))<evaluate(nextDestination)){
						nextDestination.setLocation(testX,testY);
					}
				}
			}			
			if(timeSinceLastScan>100){
				nextDestination.setLocation(18+((getBattleFieldWidth()-54)*Math.random())+18,18+((getBattleFieldHeight()-54)*Math.random())+18);
			}
			lastPosition.setLocation(myX,myY);							
		}else{
			double dir=1;
			double ang=calcAngle(new Point2D.Double(myX,myY),nextDestination)-getHeadingRadians();
			double dist=nextDestination.distance(myX,myY);
			if(Math.cos(ang)<0){
				dir=-1;
				ang+=Math.PI;
			}
			ang=Utils.normalRelativeAngle(ang);
			setTurnRightRadians(ang);
			setAhead(dist*dir);		
			setMaxVelocity((Math.abs(ang)>1) ? Math.max(Math.random(),0.1)*1 : 8);						
		}
	}


double evaluate(Point2D.Double destination){
		double risk=1/destination.distanceSq(myX,myY) + 1/destination.distanceSq(getBattleFieldWidth()/2,getBattleFieldHeight()/2) + 1/destination.distanceSq(lastPosition);
		Enumeration e=enemies.elements();
		while(e.hasMoreElements()){
			Enemy en=(Enemy)e.nextElement();
			if(en.live && en.location!=null){
				double eratio=(en.energy*2*Math.max(en.fearFactor,1))/myEnergy;
				double perp=Math.abs(Math.cos(calcAngle(destination,new Point2D.Double(myX,myY))-calcAngle(destination,en.location)));
				//double perp=Math.abs(en.distance-destination.distance(en.location));
				double closeEnCount=0;
				double eval=(eratio*(1+perp))/destination.distanceSq(en.location);
				Enumeration enEnemies=enemies.elements();
				while(enEnemies.hasMoreElements()){
					Enemy enEn=(Enemy)enEnemies.nextElement();
					if(!enEn.name.equals(en.name)){
						if(enEn.location.distanceSq(en.location)<destination.distanceSq(en.location)*0.9){
							closeEnCount++;
						}
					}
				}
				if(closeEnCount<2){
					eval*=2;					
				}
				risk+=eval;
			}
		}
		return risk;
	}
Above is my movement code and risk function. When I run my bot, it doesn't move at all. If i remove the lastPosition line in the doMovement() and evaluate(), then it does move. Does anyone know how to fix??? --Starrynte

If just the lastPosition.setLocation(myX,myY) line in doMovement() isn't commented out, it doesn't move. --Starrynte

Everything is weird! The gun can't hit sample.Fire! The gun uses linear targeting when the target's 'headDelta' is less than 0.0001, otherwise it uses HOT. The above problem also still exists. The code can be found at Starrynte/Smash. --Starrynte

OK, I think what you need to do is normalize headDelta to between pi and -pi (using normalRelativeAngle) then check if Math.abs(headDelta) < .0001. --wcsv

It doesn't help the gun or the movement. It still can't hit sample.Fire, and the movement is still weird. --Starrynte

Basically what happens when it's 1v1 against Fire is that the 'bot will "vibrate" (turning a little past perpendicular one way, then the other way, etc, etc) and the gun "vibrates" with the 'bot. It's almost as is

setAdjustGunForRobotTurn(true);
did not exist, and the bearing to the enemy changes every tick. Notice i've commented out the lastPosition line in doMovement() and evaluate(), because there is still a problem (see above)--Starrynte

Does it go wrong on everyone's computer or is it just my comp? --Starrynte

This probably isn't the problem, but you should make sure to update your info (your position, energy etc) before you use it each tick. Right now you are using your old position to calculate the enemy position (remember that events are processed before your run loop executes each tick). I've got no time to test this code right now, but maybe later in the week.--wcsv

I just figured it out last week, but I think FloodHT has this bug in its wave surfer. -- Kawigi

Where should I update the info? If i update it after execute() it doesn't do anything. --Starrynte

At the beginning of whatever event handler the information is needed in (probably onScannedRobot). When execute() returns, all the event handlers for that turn will already have been called. -- Kawigi

Thnx wcsv and Kawigi, the gun problem is fixed. Now, the movement problem from above is left --Starrynte

Whenever my bot hits another bot that rams, like Spinbot or RamFire, it gets disabled because it makes too many calls to getXXX() methods. The only getXXX() method I call is e.getVelocity(). It gets really annoying because RamFire just rams it for a few ticks then it gets disabled. If anyone knows how to fix...thnx (code will be posted at Starrynte/Smash) --Starrynte

Ramming problem from above fixed. Now for the movement problem. --Starrynte

I used lastPosition in another bot, and it worked, but when i use it in this bot, it sits still. --Starrynte

According to http://java.sun.com/j2se/1.3/docs/api/java/awt/geom/Rectangle2D.Double.html, when you make a Rectangle2D.Double, the x,y coordinate is the upper-left corner of the rectangle. Is that different in robocode? If not, is this the right way to construct it:

field=new Rectangle2D.Double(36,getBattleFieldHeight()-36,getBattleFieldWidth()-72,getBattleFieldHeight()-72);
--Starrynte

I made a new bot called Lightning, it's based on Smash, but it doesn't move at all when i run it! Also, in the first round, it says

You cannot call fire(NaN)
--Starrynte/Lightning

Does it say that near the beginning of the round, or toward the end? -- Kawigi

fire(NaN) happens because you have called fire with a NaN parameter. Looking at your firepower evaluation algoritum, it looks like the base, getTime()-target.ctime, is causing you problems, as there may be a time when you fire on the same tick as you scan, causing the base to be 0, and therefore a NaN. One solution is to do getTime()-target.ctime+1 instead, or use another base. --Nfwu

Ok, I will change it to Math.max(getTime()-target.ctime,1); --Starrynte


Robo Home | Changes | Preferences | AllPages
Edit text of this page | View other revisions
Last edited December 17, 2007 0:01 EST by AaronR (diff)
Search: