Danger function

The hitScans list and distance/danger weighting accumulation in getDanger() is very interesting. It looks like this is to avoid the sparse data problem caused by heavy segmentation which is exacerbated in the case of surfing by very few data points.

And I right in assuming this implementation is to achieve a similar effect to the kd-tree you would use in a mega bot?

In any case this gives me an idea, which like most of my ideas will probably come to nothing, but you can now feel guilty for making me waste another couple of weeks on robocode ;-)

I can't think of an easy/small way of doing KNN with this style of implementation, so I guess my distance weighting algorithm had better be a good one.

Yes, in fact I would say that a KD-Tree is an implementation/optimisation of this, and not the other way around.

Unfortunately, this doesn't work in a gun because a gun has an order of magnitude more data and it ends up being too slow. Hence me only using it in movement, and the gun being PM. But go for it. I wanted to try this in Micro as a gun, but I could never get it to fit.

Yes, that was my thought. A lot of minibots do GF/wave for gun and surfing, usually sharing a lot of the logic.
The obvious issue, as you point out, is that the gun has heaps more data than the surfing (probably 2 orders of magnitude), usually a wave every tick, so without the fast searching allowed by something like a kd-tree you end up with a slow full iteration. Additionally the fact that your data is far less sparse means you don't get empty bins with high segmentation, just not necessarily the best/closest match.

I have a silly idea that may possibly speed up the search, so I am going to do a quick and dirty test by plugging the mechanism into Cunobelin to see if I can get it to work at all. Then if that succeeds I'll try to build it into a gun, but I won't know for sure until I try the full implementation and see if it is fast enough to avoid lots of skipped turns.

Before I spend too much time on it, perhaps you could give me some idea of whether it is worth the effort. I.e. when you shifted your druss gun from traditionally segmented GF to using a kd-tree, was there a noticeable improvement. I am assuming even in guns it must help as: (a) several bots are now using kd in guns and (b) some other bots like Pugilist achieve a similar effect by having separate "fast" and "slow" segmentations.

Yes it should help in guns, but I think it would increase the hit rate by at most 1 percent vs a good VCS gun (Targeting_Challenge_RM/Results), which should translate to less than 1 APS if your movement is good (I think, not sure on that, but it's my general impression). Also I think I can prove (ie. I didn't bother to write it down and double check) that the benefit is incidental, and if you perfectly configured a VCS GF gun, it would be better. The catch is that setting up a KNN gun is a lot easier than setting up a VCS gun perfectly.

The difference between VCS and KNN is huge, if you have the time and space to tune it. Seriously, even a double-buffered VCS is nothing compared to KNN. It takes many buffers of varying depth, granularity etc to get close to what KNN can achieve, and even then it isn't as good. See targeting challenges, I believe the highest scoring VCS is Dookious.

I know Hydra and Waveserpent use a combination VCS/KNN gun, which segments on velocity and acceleration but does KNN on everything else. That way it doesn't need a tree, but still runs at reasonable speed because of the reduced data size.

Though I would note that the difference between VCS and KNN is significantly reduced when you use interpolated VCS like I did in SaphireEdge/Midboss, later adopted by WaveSerpent starting in version 2.0

True. But speed-wise, that is about as slow as KNN, because you have to smooth across all of the dimensions. Of course, the slow part is the adding data, not so much retrieval, unlike KNN.