PIF/Interpolating PIF

Algorithm

Gradient PIF algorithm allows reduce amount of PIF iterations by several times. To implement it you need log of turn snapshots, which contains at least enemy x, enemy y and enemy absolute heading (regardless speed's sign - for example if enemy heading is 0 degress and velocity is -8, then absolute heading is 180 degrees).

The algorithm:

1. set current snapshot to start->next
2. set future position to enemy's current position
3. set bullet travelled distance to bullet speed
4. set speed sum to bullet speed + 8 (Rules.MAX_VELOCITY)
5. check, is bullet hit enemy at future position. if hit - exit
6. calculate enemy's displacement vector from start snapshot to current snapshot
7. calculate future pos, by applying displacement vector to enemy's initial position
8. check, is battle field contains future pos. if not - stop
9. calculate time delta for prev future pos: current snapshot time - start snapshot time
10. calculate prev bullet travelled distance: time delta * bullet speed - it's distance to prev future positon
11. calculate minimum bullet flight time between future positions ((<distance between robot pos and new future pos> - prev bullet travelled distance) / speed sum)
12. set current snapshot to current snapshot-><minimum bullet flight time>
13. go to step 5

Implementations

Tomcat's implementation of gradient PIF

Feel free to use this code without any restrictions

private APoint getFuturePos(Target t, TurnSnapshot start, double bulletSpeed) {
        final LXXPoint targetPos = t.getPosition();
        APoint futurePos = new LXXPoint(targetPos);

        TurnSnapshot currentSnapshot = start.next;
        currentSnapshot = skip(currentSnapshot, AIMING_TIME);
        final BattleField battleField = robot.getState().getBattleField();
        final double absoluteHeadingRadians = t.getAbsoluteHeadingRadians();
        final double speedSum = bulletSpeed + Rules.MAX_VELOCITY;
        long timeDelta;
        double bulletTravelledDistance = bulletSpeed;
        BulletState bs;
        while ((bs = isBulletHitEnemy(futurePos, bulletTravelledDistance)) == BulletState.COMING) {
            if (currentSnapshot == null) {
                return null;
            }
            // DeltaVector is same as displacement vector
            final DeltaVector dv = LXXUtils.getEnemyDeltaVector(start, currentSnapshot);
            final double alpha = absoluteHeadingRadians + dv.getAlphaRadians();
            futurePos = targetPos.project(alpha, dv.getLength());
            if (!battleField.contains(futurePos)) {
                return null;
            }
            timeDelta = currentSnapshot.getTime() - start.getTime() - AIMING_TIME;
            bulletTravelledDistance = timeDelta * bulletSpeed;
            int minBulletFlightTime = max((int) ((robotPosAtFireTime.aDistance(futurePos) - bulletTravelledDistance) / speedSum) - 1, 1);
            currentSnapshot = skip(currentSnapshot, minBulletFlightTime);
        }

        if (bs == BulletState.PASSED) {
            throw new RuntimeException("Future pos calculation error");
        }

        return futurePos;
    }