Talk:Displacement Vector

Kudos

Thanks for posting this. I thought I understood it before, but now I really get it. Now to figure out a good neural network representation... =) --Darkcanuck 04:49, 24 September 2009 (UTC)

Hi mates. I would appreciate a little help with displacement vectors, my brain starts to rotate in circles and i guess i do it horribly wrong.

What i do so far is:

1) collect all target positions (scan)
2) build a map with every displacement vector from 1-60 (if possible) for every scan (60 is enough for me with 3.0 bullets 11*60=660 and 0.1 bullets 19.7*60=1182) which is within my combat distance

so far so good (bad?) ...
3) i want to shoot :) ... because i guess it is a good idea
4) i calculate a appropriate bullet power for the current distance to the target

from now on i guess i do something wrong...
5) what i have now is a huge bunch of displacement vectors and don't know which one to choose... (more important - which one is the right for my bullet power)
6) so i calculate the bullet ticks it would take to reach the target at his current position... (thats nice but i wouldn't hit the target with this)
7) now i limit the displacement vectors to min/max tick (minTick= travel time of my bullet if the target is approaching me at full speed, maxTick the opposite) (this should be more precise but for the first try it should be enough)
8) next is to take all displacement vectors from the map which are from minTick to maxTick
9) now i eliminate all vectors which point out of the field
10) for all remaining vectors i make a max visit check - max visit is calculated by indices so vectors with almost the same angel and distance will be counted as the same (i guess this is not good)
11) take the most visited and calculate an angle for this one. 12) shoot next turn with this angle

Well, this works so far and i got an acceptable hit rate out of it. But it looks so horrible wrong that i could cry out in pain.

The main questions now are: Do i have to rely on waves and make the vectors scalable or did i oversee something that could make my approach also scalable. What is a good way to select the right displacement vector for the current enemy state? Is it comparable to GuessFactors and i should map additional informations to the displacement vectors?

I guess i don't full get it how the collected vectors will be used. If i look at the picture from the displacement vector side i see a bunch of vectors as well and lets say they are all for the same bullet speed - how do you decide which one is the right?. Because i collect every single displacement vector, the target looks like an hedgehog if i paint all vectors.

I guess i just need to talk a little about it to get it right, and i would appreciate any heads up in the right direction.

Take care

Well, what I do, is the displacement vector is always scaled by time, so every displacement vector is just a per tick average of the enemy's movement. Bullet power is forgotten, like with GFs. So if the bot moved forward 30 and left 50, relative to their initial heading, and this was over 10 ticks, the displacement vector recorded would be (3, -5). To select which displacement vectors to use, I do it the same as for GuessFactors or anything else, by recording other attribute data for inputs and doing a KNN search. In fact, all of my gun code is exactly the same except for the method that translates their movement over the time of the wave to a GuessFactor or Displacement Vector, and back into a firing angle relative to the absolute bearing to the enemy.

To project the displacement vectors into firing angles, I go tick by tick, adding the dx and dy of the displacement vector to their current position (you can do the trig once and cache it, since the angle isn't changing) and advancing my wave by bullet velocity until the bullet would pass their position. It's true you might want bullet power to also be one of the attribute inputs. I do this in Diamond's main gun (though it's GF). But it's not hugely important.

So, I'd say yes, use waves. You could use any timer, but waves mean the timer is bullet flight time, which is a reasonable choice. If you want to go to a lot of trouble not to suffer the loss of fidelity in dividing and re-inflating all the vectors by bullet time, it would probably be simpler to just do real Play It Forward from the raw movement logs.

Does any of that make sense / help? You could also check out Diamond's wave class or BrokenSword for a really basic version of how I use them. (Though I store them as polar coordinates in BrokenSword, for code size. ;))

Oh, I missed that part of your confusion is how the vectors get used. You don't select "which one" to fire at - each of them produces a firing angle, and then you do a kernel density calculation on all the firing angles to decide where to shoot. At least that's what I do, for both GFs and displacement vectors. This can be a really simple calculation, like:

• Look at 59 evenly spaced angles from GF -1 to 1 (Math.asin(8 / bullet speed) yada yada).
• For each one, count how many of your firing angles are within half a bot width (roughly (18 / distance)).
• Fire at the angle with the highest count.

I do something a little fancier, with some smoothing and weighting the count by the scan distance calculation, but you get the idea.

My thought was, if i'm using waves i have to rely on the radar at the right position if the wave hits the target. But i would like to just collect the scan and build all known displacement vectors for this scan. That would give me a little more robustness against missed targets/scans. While reading your posts i got a glimpse of an idea what i could do better, but i have to think a little more about it. I guess i will play a little with the timer and look where it goes.

If you use the bullet flight time as timer would that mean if the target gets closer to you, you have no displacement vectors and have to collect it new for the now changed bullet time? Or do you scale the vectors on the new bullet time as well? I'm always concerned my gun could not learn fast enough if i take to much different states into account.

I have to admit that i don't get the point, of having displacement vectors and still do the tick by tick stuff. I thought you have it once calculated and then you can use it at the right time - at least this is what i do right now (not to speak in a crummy way :)), i guess i have to change my thinking there.

For the density stuff - i guess i do it somehow right now (point 10) there i take all remaining vectors and make a highest count check. I might have a look at the more 'fancier' :) densities. Thanks for pointing me at this.

I try to avoid to look at Diamond, because it is way to sophisticated for me :) and it gave me quite a headache the couple of times i had a look at it. I guess i take my chances with BrokenSword :).

Anyway thanks for taking the time to bring a little light at this stuff.

I see what you mean about collecting vectors between the current scan and all previous scans within a certain range. That makes sense and should get you more data. I do something different that gives me more gun data in Melee - I also fire waves from the position of all other bots alive on the field. The effect might be similar. This seems separate from whether you scale them by time when you collect and project them.

I was wrong about how I do the tick by tick projection stuff, but regardless, you want to account for the fact that the projected movement might change the bullet time you're using to project. I.e., you don't want to project the displacement vector 35 ticks if they'll end up 30 bullet ticks away from you at the projected location. I do it the same way many do for Linear or Circular Targeting: take their current distance / bullet speed and project the vector that much; get the bullet time for the new location and re-project; do this until the bullet time doesn't change, or I'm alternating between two bullet times.

Dunno when you last looked at Diamond, but the code has gotten a huge overhaul since the 1.6.x versions. I think it's a lot better now. But it might still be "sophisticated". =)

After looking at BrokenSword i'm now even more confused :). I saw you classify the vector by distance and velocity and collect 200 vectors for each index. This is quite similar to what i do right now, but i take lastHeading change and velocity. Then you fire a wave and register the displacement vector if the wave reaches the target and you have scanned it one tick before. so far i can follow :). Now it comes to calculate the fireAngle. You take for all targets the lastVectors (are you not concerned that you haven't seen the target for quite a while?) and then just scale the vectors to the current distance and bulletPower. If you just scale the vector to whatever tick you want, would that not be against the displacement vector idea? Because the target could be anywhere between the vectors start and end point, i guess. I would say the worst thing that could happen is, you calculate the vector for lets say 20 ticks and scale it down to 1 tick. Now the battle progresses and you use these vector, but the target travels 30 ticks. If you scale the 20 tick vector the target could be anywhere. Don't get me wrong maybe i missed something important :). I was a little unsure about my thoughts and started a little test match against my current arch enemies Tron and DoctorBob :) (meleefield). Tron moves very straight but jiggles in a very nice manner so he should be save against almost all simple guns but vulnerable against displacement vectors. Maybe you have a look by yourself :) but be prepared it is very devastating what he does with BrokenSword. DoctorBob is a nano bot and he just oscillates to close combat distance. Which is quite nasty with simple guns but every learning gun should kill him quite well.

The question is, how is the average displacement vector working? To me it looks like the classifyer attributes are very important to group the right vectors but the scaling generates a lot of noise and misinterpretations. My gun is a little better in hit rate against these both bots but still not competitive. I will give the timer tomorrow a try and play a little with the attributes i let you know how it worked out.

Take care

Hmm. I can't tell if there's anything you're misunderstanding or if you just disagree that average displacement per tick is a reasonable way to deconstruct a bot's movement. If it's the latter, I would argue that GuessFactors are the undisputed king of representing enemy movement in 1v1 and they scale across the exact same dimension, so I think it's at least a reasonable approach. I'll just outline an example so we can make sure we're on the same page, and to show how they are similar to GFs in 1v1.

Let's say the enemy is at a distance of 420, exactly perpendicular to you, traveling at full speed, and you're using bullet power 2. By the time your bullet or wave gets there, something like 35 ticks have passed, and let's say the enemy traveled straight at full speed the whole time. Here we can record a GuessFactor of 1 or a displacement vector of (0, 8). Later, the enemy is at a distance of 470 - close, but different - and you use this previous data point to fire. Both the GF=1 and the vector=(0, 8) would translate to the same firing angle, and if the enemy traveled at full speed directly ahead again, they would both hit. If the enemy had traveled at half speed, or traveled ahead for 2/3 of the time and reversed direction the last 1/3, you'd end up with something like GF=0.5 and vector=(0, 4). If the enemy is not perpendicular when you apply the GF and the DV, that's when they start to act differently. And in Melee, I think the DV acts differently in a good way - in 1v1, perpendicular is the default position for you to work relative to, but in Melee it certainly isn't, so the DV has an advantage in that it works relative to the enemy's initial heading.

Are we on the same page with that? And do either or both of those seem like reasonable ways to record and reconstruct the enemy firing angle?

To answer your questions about BrokenSword:

• Yes, I do care that I haven't seen the enemy for a few ticks, and in Diamond I add those ticks to the amount that I project the displacement vectors. I tried doing this in BrokenSword and saw no improvement, so I left it out. His displacement vector stuff is rough enough that I wasn't surprised, and I can use all the code size I can save here.
• Why is scaling the vector to whatever bullet time I want such a bad thing? Taking the 20-tick vector and applying it to a 30-tick situation, I just assume the enemy will move 50% farther, and in the same direction relative to his current heading as he did in the 20-tick case. Is this not a reasonable guess based on the enemy's behavior in the 20-tick situation?
• Actually, I think Tron sounds like a perfect movement to confuse displacement vectors, because they are applied relative to his initial heading, which is wiggling all over the place. Also, BrokenSword's gun is currently pretty crap :-), despite having a pretty cool base with the DV and Shadow Melee Gun stuff. I'm hoping I could improve it when I stop to give it some love.

I still wonder if your view is more that Play It Forward is the only way to go? I actually think that's a pretty reasonable viewpoint. But I think with Displacement Vectors, and particularly with GuessFactors, you save so much CPU speed vs PIF that you can apply a lot more data for each time you aim, and this makes up for the noise added when you distill the movement into a scalar value.

I found I could speed up my PIF enormously through a combination of 2 things:

1) Using a Shadow-style 'projected' PIF that doesn't need trig except at the beginning/end to transform between fields

2) Doing the PIF over the sparse scans that I get from melee radar, and only interpolating at the end after I have determined between which two sparse scans the wave would hit.

The first technique knocks out all of the trig, and the second reduces the time of each PIF by ~4-8x. My gun now hardly even contributes to my runtime, which basically means that I could increase my kNN's 'K' by quite a bit if it improved the scores.

Speaking of, I've found it really odd that I don't gain anything by increasing the k in my Melee gun. I'm at like 100 total for all bots and increasing it doesn't seem to change anything. That's only 20 scans per bot in the average case. In 1v1 my gun scales up to hundreds of scans for a single bot!

It is just misunderstanding :). I still think displacement vectors are a very nice concept, especially for melee. My post was more meant as "Why do you do this and that..?" because i don't fully get it. I also can say BrokenSword is a nice bot (he wouldn't be rank 9 if not) and i just wanted to understand why you do this and that. I think you are way more experienced than i am and so i thought there must be something behind it if he does it. I have no idea about guess factors (beside how they work) and therefor i have some difficulties to interpret displacement vectors, i guess.

Looking at BrokenSword again (sorry :)) it looks to me that you scale the vector on the current distance but did not adjust the resulting angle to the new distance. If something moves perpendicular to you, you would miss him, because you scaled on the wrong bullet ticks - or am i wrong with this? I ask because this exactly the point where i'm stuck right now.

I don't think PIF is the only way to go, i just dig through all the available knowledge about guns and try to find something that can support my ideas. I have spotted some weak points within my single tick gun and hoped the displacement vectors can provide some additional robustness. After playing the whole day with it, i gave up and ask the above questions :). Beside of that i think every concept has it pros and cons and there is no one way to do things :).

I hope i haven't offended you somehow, if so, please take my apologies for this.

In 1v1 the GF is not time/distance dependant, because if they had time to move another tick perpendicularly, then the bullet had time to move another tick towards them, keeping the angle constant. It's not exactly the same with DV, because you are not storing the angle but rather a velocity which needs to be scaled by the bullet flight time, but in essence I think the concept comes out pretty much the same.

Of course you haven't offended me! :-)

I think I'm scaling correctly... Note that BrokenSword keeps his vectors in polar coordinates, so it's (angle, distance) instead of (x, y). When I collect it I have this:

   displacementVector.setLocation(
       absoluteBearing(targetLocation, enemyData) - targetHeading,
       targetLocation.distance(enemyData) / (timer - 1));

And when I project it I have this:

   if (battleField.contains(projectedLocation = project(enemyData,
           enemyData.heading + vector.x, vector.y
           * (int)
               (enemyDistance / Rules.getBulletSpeed(bulletPower))))) {

The bullet ticks could be off because I don't iterate to make sure the bullet ticks aren't changed by the projection. That's another corner I'm cutting because he's a MiniBot.

Really hope I didn't come off as too serious or argumentative! :-) Hopefully I've cleared up some of your confusion and we'll see your super strong gun in the Melee top 5 soon. ;)