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

Question

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?

Answer 1

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.

Answer 2

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 row mask
  row_mask = np.append([True],np.any(np.diff(sorted_data,axis=0),1))

  # Get unique rows
  out = sorted_data[row_mask]
  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

Answer 3

I tried the code and it seems working but I found some issues. For Example:
[[97, 281], [96, 276]] I received only
[[96, 280]].
Decided to debug, but found Bresenham’s line drawing algorithm, which has python package. The code looks like this:

from bresenham import bresenham

cells = list(bresenham(96, 280, 95, 275))
print(cells)

I received [(96, 280), (96, 279), (96, 278), (95, 277), (95, 276), (95, 275)]