0
$\begingroup$

Context
Suppose we have a grid-based game where a unit has a range parameter that serves as the upperbound of the sum of the costs of his movements in a single turn. Moving orthogonally to an adjacent tile costs 1, and moving diagonally to an adjacent tile costs $\sqrt{2}$.
So a unit with range 4 can move up to 2 tiles diagonally (costs about 2.8284) and one more tile orthogonally if he wishes. But he cannot move 3 tiles diagonally since its cost (about 4.2426) is strictly greater than 4.

Prompt
Suppose we were to use an approximation of $\sqrt{2}$ for the diagonal cost. My question is: at what point will this approximation fails in terms of the context above?

i.e. if $x = \sqrt{2}$, and $\bar{x}$ its approximation, $\bar{x} = 1.414$, say. What's the smallest $k \in \mathbb{N}$ for which $\lceil k x\rceil \neq \lceil k \bar{x}\rceil$?

By using a spreadsheet (dropbox), I get the following results:

x bar    k
------------------
1.5      7
1.4      5
1.41     17
1.414    99
1.4142   169

So if our grid is sufficiently large to allow for more than 99 diagonal movement, then we should use 1.4142 instead of 1.414, say.

But there's also an immediate extension:
Suppose we know that our grid won't exceed 300 diagonals, say. Then what's the least precise (in terms of the number of decimal places) we can be?

i.e. Given a $K \in \mathbb{N}$, find the least precise $\bar{x}$ for which $k > K$, where $k$ is as defined above.

$\endgroup$
  • 1
    $\begingroup$ You should learn about continued fractions and how they generate rational approximations ("convergents") to irrational numbers. The measure you're looking at might be slightly nonstandard, but the convergents are going to be better in general than just truncating the base-10 expansion of $\sqrt2$. $\endgroup$ – Greg Martin Aug 17 '14 at 3:14
  • $\begingroup$ Apart from the 1.5, the rest is from rounding. I didn't realise that, in this case, it also appears as a truncation. Speaking in terms of this measure I've described, do you mean that the convergents will have larger $k$? $\endgroup$ – Sylin Aug 17 '14 at 3:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.