Melee Strategy/Understanding Coriantumr
First of all, this tutorial is just as much about Shiz as Coriantumr, so I suggest as you go through this tutorial that unless you have spent a good amount of time understanding my flavor of GuessFactor Targeting, that you refer mostly to Shiz's code (which has alot of the same core ideas without the complicated gun implementation), unless I'm talking about things specific to Coriantumr. Any direct references I make to code will be from Shiz 1.0 and Coriantumr 1.1 unless I state differently.
- The main robot class (in Coriantumr.java or Shiz.java)
- The EnemyInfo class (or MicroEnemyInfo in Shiz)
- The MeleeBullet class (in Coriantumr only) - this is almost exactly shamelessly ripped from FloodMini and Fhqwhgads, but it's not that shameless, since I wrote them, too).
Things to notice in the EnemyInfo class:
- It has all the current information about the enemy that should go away at the end of the round or when the enemy dies:
- Last time when the enemy hit me
- Waves (in Coriantumr)
- Heading (in Shiz - helps in targeting blind)
- Location - note that there is no location variable in the class. It is inherited from its parent class, which is Point2D.Double. I don't know how I came up with this idea (to inherit from Point2D), but it was pure genius - it makes alot of other operations easier (finding your distance from an enemy or from the enemy to another point, projecting points from the enemy's location, etc) than if you had a Point2D object in the enemy class or x and y coordinates, and it saves code size in tons of places. I recommend it.
There is a HashMap called enemies which is a map from String (robot name) to the EnemyInfo (or MicroEnemyInfo) object. This is where the enemy objects live each round. Note that it's static for codesize reasons, but it is reinitialized each round in the run() method. Enemy objects are removed from this HashMap when they die (so if I iterate through it, I never look at dead enemies. Also, I don't need a dead variable in my enemy objects :-).
Coriantumr has an additional HashMap called stats which maps robot names to multi-dimensional arrays of ints (for targeting information). This is really static (it is only initialized once).
Both robots also have a couple points representing their current location and the one they just came from (this is just a movement hack), as well as an enemy object called currentTarget (whose purpose should be obvious).
Coriantumr uses GuessFactor Targeting, and fires while looking at the enemy. His radar is a little more complicated, but not too much so. It's basically based on the infinite radar lock that became popular with the first pattern-matching nanos (although it wasn't invented by them) - Basically it starts with rotating the radar infinitely, but when he's getting closer to firing, he reverses the radar when he's scanning the current target (this way, the radar should swing back over the enemy). This has maybe a 90% lock rate, which is good for its simplicity and small code size. It also locks when it scans if there is only one other robot left on the battlefield. The radar code in Coriantumr is in Coriantumr.java, lines 51, 214 and 215.
The Point-Generating Function
These robots use Minimum Risk Movement, which I always say is the combination of a point-generating function and a risk function.
- Pick a distance to move
- Project some number of points (about 60) out from your position at that distance at regular intervals
- For each point, see if it's risk is smaller than that of the point you're currently moving towards
- If it is, it is the new next point.
The distance to move becomes important here - in Shiz, it's the distance between Shiz and the enemy. Note that this doesn't mean Shiz always moves that distance before picking a new point - that's just how far he looks. In reality, Shiz will change direction as soon as there is a point that distance away from it that is better. I found a particular weakness in this system, which is that when there are only 4 or fewer bots on the field (imagine 3 or 4 bots in the corners of the battlefield), the best point Shiz has to go to is on the other side of the middle of the field, so you'll see Shiz at this point venturing right out into the middle of the field and turning around when the distance back to its corner is roughly the same as the distance to the closest enemy.
I haven't gotten around to publishing a fixed version of Shiz in this respect, but I have fixed the problem in Coriantumr. Coriantumr's distance is half the distance to the closest enemy, but no more than 250. In one-on-one, the distance is random between 0 and half the distance (not bounded).
I also remember if I changed my "next" point in the loop, and if I did, I remember where I was at the time. Note that I don't always change next points when I go into the point-generating loop, in fact, I don't even think it happens that often in most cases. Saving the last point is for later use in the risk function (if I did this update in the point-generating loop, it would screw up later calls to the risk function).
Another thing to notice - the point-generating function trivially discards any points lying outside the battlefield, or even too close to the walls.
The Risk Function
This is where the real magic happens - evaluating each point.
Typical risk (and anti-gravity) functions have two parts -
- Risk that is applied to each enemy.
- Risk that is applied to constant objects like walls or the center or your current location.
Risk function elements applied to each enemy
A basic antigravity-like value - how strong the force of gravity is on this enemy from the given point, calculated as (energy+50)/distance2. Without the +50, notice that I'll almost disregard enemies that are almost dead, which is good because I'll get close to people who are dying and who aren't firing as hard, but you shouldn't take those bots TOO lightly, either. Especially if your energy is also low.
Decide if the robot is likely targeting me - This is possibly unique to my bots (I'm not sure that anyone else does it, but they might), but I mentioned it on the Melee Strategy page because I think it has a lot of merit. Basically I make another iterator on my enemies and I see how many other enemies are at least 10% closer to this enemy than the candidate point is. If the count is no more than 1, or if they hit me recently, or if I'm currently shooting at this enemy, I assume they might be shooting at me. This has two effects on the risk function for this enemy:
- Their risk is doubled.
- "perpendicularity" is taken into account (I think David Alves might have invented that word, I think I got it from him at least). "Perpendicularity" is just the absolute value of the cosine of the angle between the movement path (from my position to the given point) and the line between my current location and the enemy's current location. This means it will be zero if I'm moving at an exactly right angle to the enemy and it will be 1 if I'm moving directly toward or away from the enemy. If you are applying this to teams, you might consider taking out the risk doubling and only multiplying the risk by perpendicularity on an enemy (particularly if the enemy is a target you want to stick with).
Check to see if the path to the point intersects an enemy - This shouldn't be an issue often, and it takes up code size, so it's currently left commented out of both bots. If the distance to the candidate point is too far or if you picked the point before you scanned the whole battlefield, it may still be a problem, though.
Constant Risk Function Elements
Repel the last point I was at - This helps you not get hit by head-on targeting as much. Of course, it might make you more vulnerable to the pseudo-linear targeting algorithms that are also common in melee. Choose your poison. I consider this something of a hack, but HawkOnFire does something like it, too, so it can't be that bad. Coriantumr doesn't do this in 1-on-1.
Repel my current position lightly - This causes me to become increasingly likely to change directions as I get closer to my "next" point.
See Shiz.java, lines 126-127 or Coriantumr.java, lines 162-163. It looks like in these versions I just use shorter distance, but in the dev version, I have better resistance to thrashing and also take energy into account. In my experiments with teams, I also would make the leader more likely to be targeted, but that's a whole different story.
Shiz aims and fires in the run method (Shiz.java, lines 52-54) at the location where the current target is. I think I also experimented with projecting currentTarget forward each tick in run() (to avoid firing behind them), but it must not have been worth the code size.
Before trying to understand this, you should probably be familiar with GuessFactor Targeting. I recommend my tutorial at GuessFactor Targeting Tutorial. Also, see how the MeleeBullet class is a simplified version of the WaveBullet class described there.
So, basically, we're looking at a segmented GuessFactor gun here, with very much in common to FloodMini and every other bot which has copied FloodMini's implementation. The segmentations are:
- Battle size - is this 1-on-1 or melee? I think that Math.min(getOthers()-1, 1) is a great way of calculating this segmentation, and it should only crash if there are zero enemies left (in that case, what are you doing in onScannedRobot?)
- acceleration or lateral direction - acceleration like in FloodMini in one-on-one, in melee it's what I call "lateral direction" - whether the enemy is moving toward you, away from you, or perpendicularly to you.
- BFT (projected Bullet Flight Time) - how long it would take a bullet to reach them at the given power if they stayed at this distance? Segmented at 15-tick intervals I guess (maybe more granularity would be good?) Notice that I calculate my bullet power at the same time as calculating this segment index, which doesn't really add to clarity, but helps my code size.
- 31 GuessFactors in each segment. No reason, it just works.
Each scan, I update each wave, and the waves return true if they hit and I should discard them (during this update, if they hit, they also update the stats in their corresponding segment. See MeleeBullet.java). Then I make a new wave from the current segment and data.
If I'm scanning at the current target, I iterate the guess factors in the current segment and pick the one that is highest. There is a caveat. On line 205 of Coriantumr.java, you'll see that I make a quick geometric guess as to whether or not the enemy can even reach that guess factor. This is because it's quite easy to waste a shot or two in melee by projecting your enemy to keep going forward even if there's a wall there. I can't remember exactly what the mathematical thinking was behind it, but I think it just figures out if it would be possible to reach that guess factor inside the battlefield if you turned and went at velocity 8 instantly toward the closest point on the battlefield that is in that guessfactor. Someone should look closer at it. At least it works.
Finally, I turn my gun to that best feasible guessfactor and I fire - except I don't fire yet if my gun isn't done turning or if my targets energy is more than 5 times my own (this makes me play a sort of waiting game against opponents who have an advantage, and sometimes it works :-))
Anything else in either of these bots should be pretty transparent I think. It looks like I have a little victory dance commented out of Coriantumr 1.1, too.