# Finding cells between two points (along line) to finding obstacles

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

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

Can some one suggest me the approach?

• 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

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:

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.

I implemented the pseudocode from wikipedia for Bresenham's algorithm and got a result like this:

   0  1  2  3  4  5  6  7  8  9  10
0   0  0  .  .  .  .  .  .  .  .  .
1   .  .  0  .  .  .  .  .  .  .  .
2   .  .  .  0  .  .  .  .  .  .  .
3   .  .  .  .  0  .  .  .  .  .  .
4   .  .  .  .  .  0  .  .  .  .  .
5   .  .  .  .  .  .  .  .  .  .  0
6   .  .  .  .  .  .  .  .  .  .  .
7   .  .  .  .  .  .  .  .  .  .  .
8   .  .  .  .  .  .  .  .  .  .  .
9   .  .  .  .  .  .  .  .  .  .  .
10  .  .  .  .  .  .  .  .  .  .  .


As you can see the algorithm falls apart when dy > dx. It also is not tracing the line very well from (0,0) to (5,10). I implemented my own algorithm that plugs values into y=mx+b,rounds the result and uses that to modify the grid.

Python 2.7 code:

def get_grid_cells_btw2(p1,p2):
x1,y1 = p1
x2,y2 = p2
dx = x2-x1
dy = y2-y1

if dx == 0: # will divide by dx later, this will cause err. Catch this case up here
step = int(copysign(1,dy))
pts =[]
for y in range(0,dy,step):
pts.append((x1,y))
return pts

m = dy/(dx+0.0)
b = y1 - m * x1

points = {}
step = 1.0/(max(abs(dx),abs(dy)))
steps = [x * step for x in range(int(x1 / step), int(x2/step + copysign(1,x2)), int(copysign(1,dx)))]
for x in steps:
y = m * x + b
pt = (int(round(x)),int(round(y)))
points["%d,%x"%pt] = pt #catch duplicates

return points.values()


And a much simpler+faster version using Numpy

#function COPIED from stack overflow - https://stackoverflow.com/questions/31097247/remove-duplicate-rows-of-a-numpy-array
def remove_np_duplicates(data):
# Perform lex sort and get sorted data
sorted_idx = np.lexsort(data.T)
sorted_data =  data[sorted_idx,:]

# Get unique rows
return out

def get_grid_cells_btw(p1,p2):
x1,y1 = p1
x2,y2 = p2
dx = x2-x1
dy = y2-y1

if dx == 0: # will divide by dx later, this will cause err. Catch this case up here
step = np.sign(dy)
ys = np.arange(0,dy+step,step)
xs = np.repeat(x1, ys.shape[0])
else:
m = dy/(dx+0.0)
b = y1 - m * x1

step = 1.0/(max(abs(dx),abs(dy)))
xs = np.arange(x1, x2, step * np.sign(x2-x1))
ys = xs * m + b

xs = np.rint(xs)
ys = np.rint(ys)
pts = np.column_stack((xs,ys))
pts = remove_np_duplicates(pts)

return pts.astype(int)


And run it with

    from pandas import *
cells = get_grid_cells_btw2((0,0),(5,10))
grid = [['.' for row in range(11)] for col in range(11)]
for pt in cells:
x,y=pt
grid[x][y] = '0'
print(DataFrame(grid))


We get

   0  1  2  3  4  5  6  7  8  9  10
0   0  0  .  .  .  .  .  .  .  .  .
1   .  0  0  0  .  .  .  .  .  .  .
2   .  .  .  0  0  0  .  .  .  .  .
3   .  .  .  .  .  0  0  0  .  .  .
4   .  .  .  .  .  .  .  0  0  0  .
5   .  .  .  .  .  .  .  .  .  0  0
6   .  .  .  .  .  .  .  .  .  .  .
7   .  .  .  .  .  .  .  .  .  .  .
8   .  .  .  .  .  .  .  .  .  .  .
9   .  .  .  .  .  .  .  .  .  .  .
10  .  .  .  .  .  .  .  .  .  .  .


to (2,10)

   0  1  2  3  4  5  6  7  8  9  10
0   0  0  0  .  .  .  .  .  .  .  .
1   .  .  .  0  0  0  0  0  .  .  .
2   .  .  .  .  .  .  .  .  0  0  0
3   .  .  .  .  .  .  .  .  .  .  .
4   .  .  .  .  .  .  .  .  .  .  .
5   .  .  .  .  .  .  .  .  .  .  .
6   .  .  .  .  .  .  .  .  .  .  .
7   .  .  .  .  .  .  .  .  .  .  .
8   .  .  .  .  .  .  .  .  .  .  .
9   .  .  .  .  .  .  .  .  .  .  .
10  .  .  .  .  .  .  .  .  .  .  .


to (10,6)

   0  1  2  3  4  5  6  7  8  9  10
0   0  .  .  .  .  .  .  .  .  .  .
1   0  0  .  .  .  .  .  .  .  .  .
2   .  0  .  .  .  .  .  .  .  .  .
3   .  .  0  .  .  .  .  .  .  .  .
4   .  .  0  0  .  .  .  .  .  .  .
5   .  .  .  0  .  .  .  .  .  .  .
6   .  .  .  0  0  .  .  .  .  .  .
7   .  .  .  .  0  .  .  .  .  .  .
8   .  .  .  .  .  0  .  .  .  .  .
9   .  .  .  .  .  0  0  .  .  .  .
10  .  .  .  .  .  .  0  .  .  .  .


to (10,10)

   0  1  2  3  4  5  6  7  8  9  10
0   0  .  .  .  .  .  .  .  .  .  .
1   .  0  .  .  .  .  .  .  .  .  .
2   .  .  0  .  .  .  .  .  .  .  .
3   .  .  .  0  .  .  .  .  .  .  .
4   .  .  .  .  0  .  .  .  .  .  .
5   .  .  .  .  .  0  .  .  .  .  .
6   .  .  .  .  .  .  0  .  .  .  .
7   .  .  .  .  .  .  .  0  .  .  .
8   .  .  .  .  .  .  .  .  0  .  .
9   .  .  .  .  .  .  .  .  .  0  .
10  .  .  .  .  .  .  .  .  .  .  0