{"id":383,"date":"2024-05-30T19:29:05","date_gmt":"2024-05-30T18:29:05","guid":{"rendered":"https:\/\/blog.powered-up-games.com\/wordpress\/?p=383"},"modified":"2024-07-09T11:44:40","modified_gmt":"2024-07-09T10:44:40","slug":"lazy-problem-solving","status":"publish","type":"post","link":"https:\/\/powered-up-games.com\/blog\/wordpress\/archives\/383","title":{"rendered":"Lazy problem solving"},"content":{"rendered":"\n

One problem I’ve set as an exercise for students for some time is hitting a moving target. The problem is, if the projectile takes some time to reach the target, then you need to aim ahead of the target by an amount. And that amount depends on the distance to the aim ahead point, which depends on the time, and so on.<\/p>\n\n\n\n

The typical approach to solving this problem is to create a quadratic equation to find the time when the projectile trajectory intersects the target trajectory. Then you can work your way back by plugging the time into the target velocity and calculating the aim ahead point. Finally you calculate the angle you need to hit that point and fire at that angle.<\/p>\n\n\n\n

    \n
  1. equate target and projectile positions in terms of time<\/li>\n\n\n\n
  2. solve for time<\/li>\n\n\n\n
  3. project target position at time<\/li>\n\n\n\n
  4. find angle to projected position<\/li>\n\n\n\n
  5. fire along that angle<\/li>\n<\/ol>\n\n\n\n

    If you’ve ever been through this process, you’ll know the number of terms in the equation you need to solve gets quite large during the working out. And that means that the potential for making a mistake is quite high. So you have to proceed carefully to avoid factoring errors.<\/p>\n\n\n\n

    While it is<\/em> good practice, it is also tedious. Having done it a number of times before, I found that I couldn’t be bothered going through the explanation again. I wondered if there was a simpler approach. As it turned out, there was.<\/p>\n\n\n\n

    The trick to lazy programming is not calculating things until you absolutely need them. And the way to do that is to write your program backwards. Sometimes this is called programming by wishful thinking, or programming by intent, or top down programming. But whatever you want to call it, the purpose is to stake out our final destination before writing the code.<\/p>\n\n\n\n

    if only there were a function like this<\/span><\/path><\/path><\/svg><\/span>
    transform<\/span>.<\/span>rotation<\/span> <\/span>=<\/span> <\/span>AimAheadOfMovingTarget<\/span>(<\/span>target<\/span>)<\/span>;<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n
    Another problem solving trick is to solve a simpler problem first. So let’s ignore cases where the target velocity could be in any direction and focus just on the case that forms a right angled triangle.<\/p>\n\n\n\n
    \"\"<\/a>
    a simpler problem<\/figcaption><\/figure>\n\n\n\n
    To find the angle here we only need lengths o<\/em> and h<\/em> and we can use simple trigonometry to find the angle a<\/em>:<\/p>\n\n\n\n
    \\sin{a} = \\frac{o}{h}<\/pre><\/div>\n\n\n\n
    Or:<\/p>\n\n\n\n
    a = \\arcsin{\\frac{o}{h}}<\/pre><\/div>\n\n\n\n
    So all we really need, to calculate angle a<\/em>, is the ratio of lengths o<\/em> and h<\/em>. Given:<\/p>\n\n\n\n
    v = target\\ velocity\\\\\np = projectile\\ velocity\\\\\nt = time<\/pre><\/div>\n\n\n\n
    The values for o<\/em> and h<\/em> are:<\/p>\n\n\n\n
    o = ||v||\\ t\\\\\nh = ||p||\\ t<\/pre><\/div>\n\n\n\n
    So plugging that back into the expression for the angle we get:<\/p>\n\n\n\n
    a = \\arcsin{\\frac{||v||\\ t}{||p||\\ t}}<\/pre><\/div>\n\n\n\n
    And as you can see, the time variables t<\/em> will cancel out leaving:<\/p>\n\n\n\n
    a = \\arcsin{\\frac{||v||}{||p||}}<\/pre><\/div>\n\n\n\n
    So we don’t need to know the intercept time t<\/em>. And we also don’t need to know the distance to the target. And what this means is that the angle will be the same whatever distance the target is from us.<\/p>\n\n\n\n
    One thing we do need to know though, is the relative direction. If the target trajectory was to the left of us, instead of to the right, the values for o<\/em> and h<\/em> would be the same. We wouldn’t know whether to rotate to the left or the right.<\/p>\n\n\n\n
    To make this work we really want a negative value for o<\/em> if the trajectory of the target is to the left. That way, our result will be positive for a clockwise turn and negative for anti-clockwise. So what we want is a function that, given a vector and a direction, will return us a distance in that direction. Fortunately, that function already exists. It is the dot product:<\/p>\n\n\n\n
    {a} \\cdot {b} = ||a||\\ ||b|| \\cos{\\theta}<\/pre><\/div>\n\n\n\n
    Where a<\/em> and b<\/em> are vectors, and θ<\/em> is the angle between them. So given a vector that points to the right of our target:<\/p>\n\n\n\n
    r = unit\\ vector\\ to\\ the\\ right\\ of\\ target<\/pre><\/div>\n\n\n\n
    We can find a directional value for the trajectory v<\/em> like this:<\/p>\n\n\n\n
    v \\cdot r = ||v||\\ ||r|| \\cos{\\theta}<\/pre><\/div>\n\n\n\n
    And since we defined r<\/em> to be of length 1, this becomes:<\/p>\n\n\n\n
    v \\cdot r = ||v||\\cos{\\theta}<\/pre><\/div>\n\n\n\n
    If angle θ<\/em> is 0, the cosine will be 1, so the result will be the length of v<\/em>. But if the angle θ<\/em> is 180\u00b0, the cosine will be -1, so the result will be the negative length of v<\/em>.<\/p>\n\n\n\n
    the simple case<\/span><\/path><\/path><\/svg><\/span>
    Quaternion <\/span>AimAheadOfMovingTarget<\/span>(<\/span>Target target<\/span>)<\/span><\/span>\n{<\/span><\/span>\n\t<\/span>float<\/span> v <\/span>=<\/span> <\/span>Vector3<\/span>.<\/span>Dot<\/span>(<\/span>target<\/span>.<\/span>velocity<\/span>,<\/span> <\/span>Vector3<\/span>.<\/span>right<\/span>)<\/span>;<\/span><\/span>\n\t<\/span>float<\/span> p <\/span>=<\/span> <\/span>projectile<\/span>.<\/span>speed<\/span>;<\/span><\/span>\n\t<\/span>float<\/span> a <\/span>=<\/span> <\/span>Mathf<\/span>.<\/span>Asin<\/span>(<\/span>v<\/span> <\/span>\/<\/span> <\/span>p<\/span>)<\/span> <\/span>*<\/span> <\/span>Mathf<\/span>.<\/span>Rad2Deg<\/span>;<\/span><\/span>\n\t<\/span>return<\/span> <\/span>Quaternion<\/span>.<\/span>AngleAxis<\/span>(<\/span>a<\/span>,<\/span> <\/span>Vector3<\/span>.<\/span>up<\/span>)<\/span>;<\/span><\/span>\n}<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n
    As a bonus, if the angle is anything in between, the result will be that component of the velocity that is moving orthogonally to the right of us. So wherever the target is moving, we will get the right value to plug into our triangle to get the aim ahead angle. It does seem odd here that the other component is not relevant. It’s fairly obvious in the case that the target is coming directly towards or away from us that the angle would be 0 in both cases. Although it might be that we will never hit due to the target outrunning the projectile.<\/p>\n\n\n\n
    But if the direction was diagonally away or towards it doesn’t seem immediately intuitive that the angle needed to hit it would be the same. If we work backwards, starting with the assumption that we hit, we can trace back to where the target must have come from.<\/p>\n\n\n\n
    \"\"<\/a>
    working backwards<\/figcaption><\/figure>\n\n\n\n
    Now if we scale down the far target triangle such that its location matches the near target, we can see that these are similar triangles and the ratio between o<\/em>  and h<\/em>, and therefore the angle a<\/em>, remain the same.<\/p>\n\n\n\n
    \"\"<\/a>
    any parallel path scales down<\/figcaption><\/figure>\n\n\n\n
    So that solves pretty much every case. However, we do still need to find this right pointing vector r<\/em>. In our simple case it is a global constant, but in the more general case we will need to take the vector to the target start position into account. The vector r is 90\u00b0 to the up <\/em>and to target<\/em> vectors. And the up<\/em> is at 90\u00b0 to the to target<\/em> and target velocity<\/em> vectors.<\/p>\n\n\n\n
    We can find a vector at 90\u00b0<\/strong> to two vectors using the cross product function:<\/p>\n\n\n\n
    a \\times b = ||a||\\ ||b||\\sin{\\theta}\\ n<\/pre><\/div>\n\n\n\n
    Where a<\/em> and b<\/em> are the two vectors and n<\/em> is a vector at 90\u00b0. As you can see, the vector n is scaled by the lengths of the vectors and the sine of the angle between them, but we can ignore all of that and just use the vector.<\/p>\n\n\n\n
    finding the vectors<\/span><\/path><\/path><\/svg><\/span>
    Vector3 toTarget <\/span>=<\/span> <\/span>target<\/span>.<\/span>position<\/span> <\/span>-<\/span> <\/span>position<\/span>;<\/span><\/span>\nVector3 up <\/span>=<\/span> <\/span>Vector3<\/span>.<\/span>Cross<\/span>(<\/span>toTarget<\/span>,<\/span> <\/span>target<\/span>.<\/span>velocity<\/span>)<\/span>;<\/span><\/span>\nVector3 right <\/span>=<\/span> <\/span>Vector3<\/span>.<\/span>Cross<\/span>(<\/span>up<\/span>,<\/span> <\/span>toTarget<\/span>).<\/span>normalized<\/span>;<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n
    final code<\/span><\/path><\/path><\/svg><\/span>
    Quaternion <\/span>AimAheadOfMovingTarget<\/span>(<\/span>Target target<\/span>)<\/span><\/span>\n{<\/span><\/span>\n\tVector3 toTarget <\/span>=<\/span> <\/span>target<\/span>.<\/span>position<\/span> <\/span>-<\/span> <\/span>position<\/span>;<\/span><\/span>\n\tVector3 up <\/span>=<\/span> <\/span>Vector3<\/span>.<\/span>Cross<\/span>(<\/span>toTarget<\/span>,<\/span> <\/span>target<\/span>.<\/span>velocity<\/span>)<\/span>;<\/span><\/span>\n\tVector3 right <\/span>=<\/span> <\/span>Vector3<\/span>.<\/span>Cross<\/span>(<\/span>up<\/span>,<\/span> <\/span>toTarget<\/span>).<\/span>normalized<\/span>;<\/span><\/span>\n\t<\/span>float<\/span> v <\/span>=<\/span> <\/span>Vector3<\/span>.<\/span>Dot<\/span>(<\/span>target<\/span>.<\/span>velocity<\/span>,<\/span> <\/span>right<\/span>)<\/span>;<\/span><\/span>\n\t<\/span>float<\/span> p <\/span>=<\/span> <\/span>projectile<\/span>.<\/span>speed<\/span>;<\/span><\/span>\n\t<\/span>float<\/span> a <\/span>=<\/span> <\/span>Mathf<\/span>.<\/span>Asin<\/span>(<\/span>v<\/span> <\/span>\/<\/span> <\/span>p<\/span>)<\/span> <\/span>*<\/span> <\/span>Mathf<\/span>.<\/span>Rad2Deg<\/span>;<\/span><\/span>\n\t<\/span>return<\/span> <\/span>Quaternion<\/span>.<\/span>AngleAxis<\/span>(<\/span>a<\/span>,<\/span> <\/span>up<\/span>)<\/span> <\/span>*<\/span> <\/span>Quaternion<\/span>.<\/span>LookRotation<\/span>(<\/span>toTarget<\/span>,<\/span> <\/span>up<\/span>)<\/span>;<\/span><\/span>\n}<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n
    Sometimes, if you are lazy enough, you can get a solution without having to do all the working out<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[7,6,5],"tags":[24,39,32],"class_list":["post-383","post","type-post","status-publish","format-standard","hentry","category-process","category-programming","category-video-games","tag-education","tag-programming","tag-unity"],"_links":{"self":[{"href":"https:\/\/powered-up-games.com\/blog\/wordpress\/wp-json\/wp\/v2\/posts\/383","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/powered-up-games.com\/blog\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/powered-up-games.com\/blog\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/powered-up-games.com\/blog\/wordpress\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/powered-up-games.com\/blog\/wordpress\/wp-json\/wp\/v2\/comments?post=383"}],"version-history":[{"count":13,"href":"https:\/\/powered-up-games.com\/blog\/wordpress\/wp-json\/wp\/v2\/posts\/383\/revisions"}],"predecessor-version":[{"id":402,"href":"https:\/\/powered-up-games.com\/blog\/wordpress\/wp-json\/wp\/v2\/posts\/383\/revisions\/402"}],"wp:attachment":[{"href":"https:\/\/powered-up-games.com\/blog\/wordpress\/wp-json\/wp\/v2\/media?parent=383"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/powered-up-games.com\/blog\/wordpress\/wp-json\/wp\/v2\/categories?post=383"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/powered-up-games.com\/blog\/wordpress\/wp-json\/wp\/v2\/tags?post=383"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
    I have uploaded a Unity project<\/a> to GitHub to demonstrate this approach.<\/p>\n","protected":false},"excerpt":{"rendered":"
    The final step is to combine the rotation around the up <\/em>axis with a rotation to point at the target. The Quaternion <\/a>class provides functions to do both of these. We just need to remember to combine them in reverse order.<\/p>\n\n\n\n