I previously spoke about ded reckoning in an earlier blog while I was working on the killbot for our tournament. Well, I won the tournament for the pathfinding section and came fourth for the target prediction section, but i would like to talk about the research and implementation of the ded reckoning system itself.
What is ded reckoning?
ded reckoning (or deduced reckoning) is used in navigation systems and is the process of calculating one’s current position by using a previously determined position, or fix, and advancing that position based upon known or estimated speeds over elapsed time and course.
Dead reckoning can give the best available information on position, but is subject to significant errors due to many factors as both speed and direction must be accurately known at all instants for position to be determined accurately.
This sort of system isnt often used for target prediction, because of the cumulative effect that errors will cause over time, however, if you only need to know where a target will be in a second or less, it can be very cost effective.
This is why it is used for dogfighting games, to display to players where they need to aim to accurately hit a target. Here is what they are displayed as in war thunder.
The reason it is needed for this situation, is the bullets have travel time, they will not immediately complete their flight path the second the trigger is pulled, so we must lead the target. However, this can be pretty hard to do, as judging distances from a screen isnt quite what our eyes are designed for. Displaying a simple, predicted flight path target for players to fire at makes the game much more accessable for every player.
What its doing, instead of using hard information to determine current position, it uses assumed information as well. It takes the current speed and direction and acceleration, the distance from the gun, and the bullet speed, and uses that info to decide, based on how long it would take a bullet to get there, how far ahead the player should lead the target to accurately hit them, and displays that position.
How did I use it for my killbot?
As we saw in the last post about my killbots targetting plans, this is what is happening behind the scenes. The killbot gets 2 scans of an enemy in the previous two turns. from this it can assume a speed and direction. (using three scans would have ensured complete accuracy though, which proved to be more useful as that is what won the tournament focussing on prediction). The simplest solution is to then determine how far the target is from my killbot, and how many turns it would take the projectile to travel that distance, and then shoot that many turns of the bots current predicted path ahead of it, however, the bullet’s travel time itself was not being taken into account for the new target. I has assumed that this would be ‘close enough’, but it was throwing my accuracy completely off. I could also not hit anyone who was always moving along a curve, but did not acocunt for this.
The problem with the bullets own travel time was that it kept adding more distance to travel for each turn it needed to travel. This looks a lot like Zeno’s paradox, Achelies and the tortoise:
So to account for this, what we need to do is, using the target prediction that we have, test to see how close the bullet will be to the enemies predicted path, for up to 60 turns, and once we find the closest that the bullet can get, use that angle. This means that the bullets travel time is now taken into acocunt. it still isnt perfect, but by including burst fire into the build, it made my bot a strong contender, coming 4th for the target prediction section.
Below is the block of code i used to converge the bullets path and target path as close as possible.
for (int i = 1; i < 60; i++)
{
tempMagnitude = ((currentPos - input.position) / i) + tempVelocity;
if (GetDistVec2(tempMagnitude, checkVelocity) < GetDistVec2(bestMagnitude,
checkVelocity))
{
bestMagnitude = currentPos + (tempMagnitude*(i - 1)*0.1);
}
}
tempMagnitude = bestMagnitude;
Ben Welsh 
LikeLike