Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 3 down vote accepted

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.
share|improve this answer
    
Are you sure this is THE way to do it? You're not really covering the alternatives ;) Kidding. –  Byte56 Jul 2 '12 at 23:16
    
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. –  slartibartfast Jul 3 '12 at 2:25
    
Excellent answer +1 –  Valmond Jul 3 '12 at 14:01

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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