Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

My game is in 3D environment partitioned with 2D grids in 2 dimensioned array

So I can get any cell/node by passing row and col like return _nodes[r][c].

When the an attacker attacks an enemy with ranged weapon, I want to check if there is any obstacle in between the two points.

Without using mesh collision methods, I want to achieve it by checking all the cells which falls between the source and target points and check if there are any obstacles.

I want to write this in a routine which will return false as soon as it finds an obstacle and returns true if it finds no obstacle in any of the cells between the source and target

enter image description here

From the above picture, I want to get yellow that falls between the two end points

Can some one suggest me the approach?

share|improve this question
Bresenham's Line Algorithm – Doorknob Jan 16 '13 at 12:55
@Doorknob Good answer, Why did you put it on a comment? – Zhen Jan 16 '13 at 15:41
up vote 5 down vote accepted

One of the popular ways to do this, as Doorknob says in their comment, is Bresenham's line algorithm. The example image of which looks nearly identical to you requirement example:

enter image description here

It's commonly used to draw lines on the computer screen deciding which pixels to use to represent that line. In your case, you'll use it to decide which grid spaces to check.

Essentially, you start at the fire location and step through the line generated by connecting the fire location and hit location. For each square the line enters, you check for obstacles.

The wikipedia page linked above has some pseudo code examples, and it should be simple to find examples in your language of choice.

You should also check this similar question.

share|improve this answer

Your Answer


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.