2
\$\begingroup\$

So I have a game in which basically everything is a square inside a big grid. It's easy to check if a square is inside a box whose center is another square:

*** x
*o*      --> x is not in o's square
***

**x
*o*      --> x IS in o's square
***

This can be done by simply subtracting the coordinates of o and x, then taking the largest coordinate of that and comparing it with the half side length.

Now I want to do the same thing but check if x is in o's diamond, like so:

  *
 **x
**o**    --> x IS in o's diamond
 ***
  *

What would be the best way to check if a square is in another square's surrounding diamond-shaped area, given the diamond's half width/height?

\$\endgroup\$
3
\$\begingroup\$

The diamond shape here has 2 useful properties:

  1. A diamond that has a width of x fits completely within the square of width x
  2. A diamond like this (ie. a square rotated through 90 degrees) based on a grid pattern can be defined by the Manhattan distance from the centre of the diamond.

So, an efficient check to see if a value is within this diamond would be this:

  1. Iterate through each position in the containing square of the equivalent size. You can quickly calculate these bounds by subtracting/adding the square size to the centre position.
  2. For each of those possible positions, it is in range if the Manhattan distance to the centre is less than or equal to the half-width/height of the diamond.
\$\endgroup\$
  • \$\begingroup\$ Ah, Manhattan distance! That's it! So I have: (x - o).abs().sum() <= half where abs() returns the coordinates' absolute values and sum() returns the sum of the coordinates. \$\endgroup\$ – slartibartfast Jul 3 '12 at 2:25

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.