Danger function

Jump to navigation Jump to search
Revision as of 19 June 2013 at 10:44.
The highlighted comment was created in this revision.

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.

    Nz.jdc (talk)07:27, 19 June 2013

    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.

      Skilgannon (talk)08:16, 19 June 2013

      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.

        Nz.jdc (talk)11:44, 19 June 2013