Displacement Targeting
Overview
Subset of: Targeting
Displacement Targeting is a log based targeting method which is designed to predict the future location of an enemy based on its past movement. The unique aspect of this technique is the use of Displacement Vectors (of the math variety, of course). The robot stores the enemy's displacement from its initial location with respect to time, up to a designated timestep. When aiming the robot can then reiterate through its stored displacement values and find either a mean, a mode, or perhaps chose between a bimodal or statistical distribution to find the predicted target. Using the time scale, various distances can be used.
Currently my version of the algorithm segments data by velocity (so if a robot is still, we predict one displacement. If it is moving fast we predict another) Displacement vectors are relative to the velocity vector (this a robot moving right at speed 8 will create a perpendicular displacement vector to one moving down at seed 8, for the same distance to the target)
I am developing this algorithm in response to the utter failure that linear predictions have on rotating bots, like SpinBot. I think this algorithm might create an applicable gun for many competitors.
Some details: For each enemy bot I am creating a 'StatPack' (not sure that stat is the best word, but it'll do for now). In it is a double array of linked lists (this could easily enough be a triple array). The lists themselves contain actual observed displacements. The array holds [velocities 0-8][timesteps 0-99, or whatever you like...could vary for field size].
For the purpose of data collection, each observed enemy location is stored along with a timestamp. When it's been there for more timesteps than we're storing, the positon is removed.
The number of displacement vectors per list is limited to avoid too much lag, and to facilitate adaptation to a change in movement (SpinBot hitting a wall, for example, generates a different set of displacement vectors, and needs to be 'recognized'. Since there is not going to be an observation every timestep, when requesting a dispacement for a given time (either sequentially or predicted... i'm doing the former but the latter would be much more efficient), if no observed data is present for the given velocity and time, other data can be interpolated to approximate the vector.
I should also mention that it currently uses the mode average exclusivly when finding magnitude and direction. This may not be best. Other options will be tried in the future. -- Franzor
This is a form of PatternMatching. It looks like one anyway -- Xero
I suppose it could be considered PatternMatching. I think it may generalize a bit more than conventional PatternMatching, but I honestly haven't had a chance to dive too deeply into PatternMatching at this point. In any case, I'll have a sample up and a better explanation within a few days. Thanks for the feed back though -- Franzor
(Edit Conflict) Well, there is no pattern matching involved at all, actually; it sounds like stats are segmented the way they are in a VisitCountStats gun (Dookious / Ascendant / CassiusClay), but it's using a displacement vector instead of a GuessFactor to figure out the future position / angle to shoot at. My initial thoughts are that it could work better against tanks that don't tend to orbit you, which is rare in 1v1, but common in melee. In fact, if you adjust the size of the displacement vector based on bullet time - which seems like a good idea - it starts looking a whole lot like GuessFactors (or GuessVectors, as I've heard ABC say somewhere.) -- Voidious
I've added some details to the page to start clearing things up -- Franzor
